这是合理使用Python内置哈希函数吗？

Question

我需要比较大量的数据，看它们是否相等，而且每秒需要比较很多对数据，速度要快。每个对象的长度都是一样的，但可能在未知的位置有一些微小的差异。

下面的时间测试显示，如果数据的开头有差异，使用 == 操作符比较会非常快；但如果差异在数据的末尾，速度就会明显变慢。

>>> import os
>>> s = os.urandom(1600*1200 - 1)
>>> Aimg = b"A" + s
>>> Bimg = b"B" + s
>>> img1 = s + b"1"
>>> img2 = s + b"2"
>>> %timeit Aimg == Bimg
61.8 ns ± 0.484 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
>>> %timeit img1 == img2
159 µs ± 2.83 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

在我的使用场景中，差异可能出现在字节的中间或末尾（背景：这是未压缩的图像数据）。我想找一种方法来加快速度，考虑使用哈希值或校验和。使用 md5 的速度较慢，但 Python 内置的 hash 确实加快了速度。

>>> %timeit img1 == img2
160 µs ± 5.96 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit hash(img1) == hash(img2) and img1 == img2
236 ns ± 5.91 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

我对这个哈希的技术细节很感兴趣，它是否足够像哈希值，以至于当 hash(a) == hash(b) 时，a == b 是 非常可能 的？如果哈希碰撞的情况比较少，允许出现假阳性，目的是为了在大多数情况下加快比较的速度。

Answer 1

Python的哈希函数是为了速度而设计的，它把数据映射到一个64位的空间里。由于有个叫做生日悖论的现象，这意味着当你有大约50亿个条目时，很可能会出现哈希冲突（其实可能更早就会出现，因为这个哈希函数并不是用来加密的）。另外，hash的具体定义取决于Python的实现，可能会因不同的计算机架构或机器而有所不同。如果你想在多台机器上得到相同的结果，就不要使用它。

md5是作为一种加密哈希函数设计的；即使输入稍微有点变化，输出也会完全不同。它把数据映射到一个128位的空间，这样除非你特意去找，不然几乎不可能遇到哈希冲突。

如果你能处理哈希冲突（也就是说，检查同一个桶里的所有成员是否相等，可能需要用像MD5或SHA2这样的加密算法），那么Python的哈希函数是完全可以用的。

还有一点：为了节省空间，如果你要把数据写入磁盘，最好以二进制形式存储它。（比如说用struct.pack('!q', hash('abc')) 或 hashlib.md5('abc').digest()）。

顺便提一下：在Python中，is和==是不一样的。你应该用==。