快速、大宽度、非加密的字符串哈希在Python中

48 投票

6 回答

22631 浏览

数据工程师

提问于 2025-04-16 14:14

我需要在Python中实现一个高性能的字符串哈希函数，这个函数的输出至少要有34位（64位更好，但32位太少了）。在Stack Overflow上有很多类似的问题，但我发现那些被接受或点赞的回答都不适合我的需求。

使用内置的 hash() 函数。 在我开发的机器上（使用Python 2.7和64位CPU），这个函数产生的整数只有32位，根本不够用。
使用hashlib。 hashlib提供的加密哈希算法速度非常慢，不适合非加密的用途。我觉得这很明显，但如果你需要一些基准测试和引用来证明这一点，我可以提供。
使用 string.__hash__() 函数作为原型来编写自己的函数。 我觉得这可能是正确的方向，但这个函数的效率依赖于c_mul函数，而这个函数的输出又限制在32位，还是不够用！真让人沮丧，差一点就完美了！

理想的解决方案应该具备以下特性，按重要性大致排序。

输出范围至少要有34位，最好是64位，同时在所有位上保持一致的雪崩效应。（简单拼接32位哈希值往往会破坏雪崩效应，至少在我简单的例子中是这样。）
可移植性。给定相同的输入字符串，在两台不同的机器上应该得到相同的结果。这些值会被存储在文件中以便后续使用。
高性能。越快越好，因为这个函数在我运行的程序中大约会被调用200亿次（目前是性能关键的代码）。不一定要用C语言编写，只要比md5快就行（大概和内置的hash()函数在字符串上的表现相当）。
接受一个'扰动'（这里用什么词更好呢？）整数作为输入来修改输出。我在下面放了一个例子（格式限制让我不能放得更近）。我想这不是绝对必要的，因为可以通过手动扰动函数的输出来模拟，但作为输入的话让我感觉更好。
完全用Python编写。如果绝对需要用C语言写，那也可以，但我宁愿要一个慢20%的Python函数，也不想因为使用两种不同语言而带来的项目协调麻烦。是的，这有点偷懒，但这是我的愿望清单。

‘扰动’哈希示例，其中哈希值因一个小整数n而发生显著变化

def perturb_hash(key,n):
    return hash((key,n))

最后，如果你想知道我为什么需要这么具体的哈希函数，我正在对pybloom模块进行全面重写，以显著提高其性能。我已经成功了（现在运行速度快了大约4倍，空间使用减少了约50%），但我发现如果过滤器变得足够大，假阳性率会突然飙升。我意识到这是因为哈希函数没有处理足够的位数。32位只能表示40亿个位（要知道，过滤器是处理位而不是字节），而我用于基因组数据的一些过滤器则是这个的两倍或更多（所以至少需要34位）。

谢谢！

效率优化可移植性高性能计算假阳性率字符串哈希雪崩效应散列函数 pybloom模块

6 个回答

你可以看看 xxHash，还有一个 pip包。

xxHash 是一种非常快速的哈希算法，运行速度接近内存的极限。它通过了 SMHasher 测试，这个测试用来评估哈希函数的碰撞、分散和随机性等特性。它的代码非常便于移植，而且在不同的平台上生成的哈希值是完全相同的（无论是小端还是大端格式）。

我使用 xxHash 已经很长时间了（我主要是用它来哈希字符串，不是为了安全目的），我对它的性能非常满意。

回答于 2025-04-16 由 Python大师

分享举报

使用内置哈希函数要小心！

从Python3开始，每次启动解释器时，它都会用不同的种子（具体细节我不太清楚）来生成哈希值。因此，每次生成的值都不一样——但对于原生的数字类型来说，情况就不一样了。

$ python3 -c 'print(hash("Hello!"), hash(3.14))'
-1756730906053498061 322818021289917443
$ python3 -c 'print(hash("Hello!"), hash(3.14))'
-4556027264747844925 322818021289917443
$ python3 -c 'print(hash("Hello!"), hash(3.14))'
-4403217265550417031 322818021289917443

回答于 2025-04-16 由 Python大师

分享举报

看看这个128位的MurmurHash3变种。这个算法页面上有一些性能数据。应该可以把它移植到Python中，可以是纯Python或者作为C扩展来使用。（更新：作者建议使用128位的变种，并丢掉你不需要的位数）。

如果MurmurHash2的64位版本对你有效的话，可以在pyfasthash包中找到一个Python实现（C扩展），这个包还包括其他一些非加密的哈希变种，不过其中一些只提供32位的输出。

更新：我为Murmur3哈希函数做了一个简单的Python封装。Github项目在这里，你也可以在Python包索引找到它；只需要一个C++编译器来构建，不需要Boost库。

使用示例和时间比较：

import murmur3
import timeit

# without seed
print murmur3.murmur3_x86_64('samplebias')
# with seed value
print murmur3.murmur3_x86_64('samplebias', 123)

# timing comparison with str __hash__
t = timeit.Timer("murmur3.murmur3_x86_64('hello')", "import murmur3")
print 'murmur3:', t.timeit()

t = timeit.Timer("str.__hash__('hello')")
print 'str.__hash__:', t.timeit()

输出：

15662901497824584782
7997834649920664675
murmur3: 0.264422178268
str.__hash__: 0.219163894653

回答于 2025-04-16 由 Python大师

分享举报

快速、大宽度、非加密的字符串哈希在Python中

6 个回答

撰写回答