有没有一种方法可以生成一个能记住我们遇到的所有字符串的键

您需要的是某种基于树或哈希的集合实现。它基本上是一种数据结构,支持非常快速的添加、删除和查询操作,并且只保留每个元素的一个实例(即不重复)。对于这样的数据结构,几十万个字符串(假设它们本身不是几十万个字符长)不应该是问题。

您选择的编程语言可能已经有了一个,所以您不需要自己编写一个。C++有 std::set . Java有 Set 实施 TreeSet 和 HashSet . 巨蟒有一个 集合 . 它们都允许您快速添加元素并检查元素的存在(对于基于哈希表的集为O(1),对于基于树的集为O(日志(N))。除此之外,还有许多集的自由实现,以及您可以使用的通用二进制搜索树和哈希表。

您可以使用某种散列函数(md5、sha1)。

伪代码:

for each F in filelist
    hash = md5(F name)

    if not hash in storage
        process file F
        store hash in storage to remember

看见 http://tools.ietf.org/html/rfc1321 用于实现MD5

有一些概率方法可以给出近似的结果,但是如果你想确定一个字符串是否是你以前见过的字符串,你可以 必须 存储迄今为止看到的所有字符串或等效信息。这是一个鸽子洞原理论证。当然,您不必使用哈希表、二叉树等各种不同的方法对迄今为止看到的字符串进行线性搜索,就可以勉强通过。

如果我正确理解了您的问题,您希望创建一个应该具有特定值的单一键,并且从该值可以推断出哪些文件已经被处理过?我不知道你是否能做到这一点,简单地说,你的空间很大,在如此巨大的空间中生成独特的关键演示文稿需要大量的内存。

如前所述,您只需将每个路径URL存储在哈希集中即可。将十万个条目放入集合中并没有那么糟糕,并且查找时间是摊销的固定时间o(1),所以它将非常快。

布卢姆过滤器可以解决你的问题。 布卢姆过滤器的想法很简单。它以一个长度为一定的空数组开始,其所有成员的值都为零。我们将有k个散列函数。 当我们需要向bloom过滤器插入一个项目时,我们就拥有了具有所有k哈希函数的项目。这些散列函数将在bloom过滤器上获得k个索引。对于这些索引,我们需要将成员值更改为1。 要检查bloom过滤器中是否存在项,只需使用所有k散列对其进行散列,并检查相应的数组索引。如果所有这些都是1,则项目将显示在Bloom过滤器中。

请注意,Bloom过滤器可以提供假阳性结果。但这永远不会产生错误的负面结果。您需要调整Bloom过滤器算法来处理这些假阳性情况。