20

我需要比较大块数据的相等性，并且我需要每秒比较多对，快速。保证每个对象的长度相同，有可能并且很可能在未知位置处可能只有微小的差异。

下面的时序表明，==如果在数据开头附近存在差异，则使用运算符非常快，如果差异位于接近末尾，则使用操作符会显着变慢。

>>> 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很有可能？如果哈希冲突相当罕见，则可以接受误报，其目的是在平均情况下加快比较速度。

4

1 回答 1

35

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

md5 被设计为加密哈希函数；即使是输入中的轻微扰动也会完全改变输出。它还映射到一个 128 位空间，这使得您根本不可能遇到碰撞，除非您专门寻找一个。

如果您可以处理冲突（即测试桶中所有成员之间的相等性，可能通过使用像 MD5 或 SHA2 之类的加密算法），Python 的哈希函数非常好。

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

附带说明：is不等同==于 Python。你的意思是==。

于 2011-10-04T10:45:07.313 回答