这是python的内置哈希函数的恰当使用吗？

Question

我需要比较大块数据的相等性,我需要每秒快速比较多个数据.每个对象都保证大小相同,并且可能/可能只是略有不同(在未知位置).

我已经看到,从下面的交互式会话中,==如果差异朝向字符串的末尾,则使用字符串字符串的运算符会更慢,并且如果在开始附近存在差异,则可以非常快.

我认为可能有某种方法可以使用某种哈希来加快速度,当然计算md5哈希值并且比较速度较慢,但​​是python的内置哈希确实可以显着提高速度.

但是,我不知道这个哈希的实现细节,它是否真的像哈希一样,我觉得很可能hash(a) == hash(b)当时a == b很可能？如果哈希冲突相当罕见,我很高兴有一些不正确的结果(在几个小时内需要一个200 PS3阵列才能发生冲突的情况很少见)

In [1]: import hashlib

In [2]: with open('/dev/urandom') as f:
   ...:     spam = f.read(2**20 - 1)
   ...:     

In [3]: spamA = spam + 'A'

In [4]: Aspam = 'A' + spam

In [5]: spamB = spam + 'B'

In [6]: timeit spamA == spamB
1000 loops, best of 3: 1.59 ms per loop

In [7]: timeit spamA == Aspam
10000000 loops, best of 3: 66.4 ns per loop

In [8]: timeit hashlib.md5(spamA) == hashlib.md5(spamB)
100 loops, best of 3: 4.42 ms per loop

In [9]: timeit hashlib.md5(spamA) == hashlib.md5(Aspam)
100 loops, best of 3: 4.39 ms per loop

In [10]: timeit hash(spamA) == hash(spamB)
10000000 loops, best of 3: 157 ns per loop

In [11]: timeit hash(spamA) == hash(Aspam)
10000000 loops, best of 3: 160 ns per loop

Answer 1

Python的哈希函数是为速度而设计的,并映射到64位空间.由于生日悖论,这意味着您可能会在大约50亿个条目中发生冲突(可能更早,因为哈希函数不是加密的).此外,精确定义hash取决于Python实现,可能是体系结构甚至是机器特定的.不要在多台机器上使用相同的结果.

md5被设计为加密哈希函数; 即使输入中的轻微扰动也会完全改变输出.它也映射到一个128位的空间,这使你不可能遇到任何碰撞,除非你专门寻找一个.

如果你可以处理冲突(即测试存储桶中所有成员之间的相等性,可能使用像MD5或SHA2这样的加密算法),Python的哈希函数就完全可以了.

还有一件事:为了节省空间,如果将数据写入磁盘,则应以二进制形式存储数据.(即struct.pack('!q', hash('abc'))/ hashlib.md5('abc').digest()).

作为旁注:is与==Python不同.你的意思==.