用于跟踪重复项的 python 数据类型

Question

我经常用这样的东西来跟踪重复项:

processed = set() 
for big_string in strings_generator:
    if big_string not in processed:
        processed.add(big_string)
        process(big_string)

我正在处理大量数据，因此不想在内存中维护处理过的数据集。我有一个使用 sqlite 将数据存储在磁盘上的版本，但是这个过程运行得慢得多。

要减少内存使用你认为如何使用像这样的散列:

processed = set() 
for big_string in string_generator:
    key = hash(big_string)
    if key not in ignored:
        processed.add(key)
        process(big_string)    

缺点是我可能会因偶尔的哈希冲突而丢失数据。10 亿哈希中的 1 次碰撞对我的使用来说不是问题。

我尝试了 md5 散列，但发现生成散列成为瓶颈。

你会建议什么？

Answer 1

我假设您正在散列网页。您最多必须散列 55 billion web pages (而且该措施几乎肯定会忽略一些重叠)。

您愿意接受小于十亿分之一的碰撞几率，这意味着如果我们查看一个哈希函数，其碰撞次数接近于如果哈希是真正随机的情况下我们将得到的 [^1]，我们想要一个大小为 (55*10^9)*10^9 的散列范围。即 log2((55*10^9)*10^9) = 66 位。

[^1]:由于哈希可以被认为是为此目的随机选择的， p(碰撞)=(占用范围)/(总范围)

由于存在速度问题，但没有真正的加密问题，我们可以使用 > 66 位非加密哈希 with the nice collision distribution property outlined above .

看起来我们正在寻找 Murmur3 的 128 位版本哈希。人们一直在举报speed increases upwards of 12x在 64 位机器上比较 Murmur3_128 和 MD5。您可以使用 this library做你的速度测试。另见此相关 answer ，其中:

• 显示 python 的 str_hash 范围内的速度测试结果，您认为该速度可以接受 elsewhere – 尽管 python 的 hash 是一个 32 位散列，只留下 2^32/(10^9)(即只有 4 个)存储的值的概率小于十亿分之一碰撞。
• 生成了一个 library of python bindings你应该可以直接使用。

最后，我希望概述了推理，如果您觉得有必要，可以让您与其他大小不同的函数进行比较(例如，如果您提高碰撞容忍度，如果索引集的大小小于整个互联网，等等……)。