python中快速,大宽度,非加密的字符串散列

Question

我需要python中的高性能字符串散列函数,它产生至少34位输出的整数(64位有意义,但32位太少).在Stack Overflow上还有其他一些问题,比如这个问题,但是我发现的每一个被接受/赞成的答案都属于几个类别中的一个,这些类别不适用(由于给定的原因).

• 使用内置hash()功能.这个函数,至少在我正在开发的机器上(使用python 2.7和64位cpu)产生一个适合32位的整数 - 对我来说不够大.
• 使用hashlib.hashlib提供加密哈希例程,这些例程比非加密目的要慢得多.我发现这是不言而喻的,但如果你需要基准和引用来说服你这个事实,那么我可以提供.
• 使用该string.__hash__()函数作为原型来编写自己的函数.我怀疑这将是正确的方法,除了这个特定函数的效率在于它使用了c_mul函数,它包裹了大约32位 - 再次,太小了我的使用!非常令人沮丧,它非常接近完美!

理想的解决方案具有以下属性,具有相对宽松的重要性.

1. 输出范围至少延长34位,可能是64位,同时在所有位上保持一致的雪崩属性.(连接32位哈希值往往会违反雪崩属性,至少我的愚蠢的例子.)
2. 便携.在两台不同的机器上给出相同的输入字符串,我应该两次得到相同的结果.这些值将存储在文件中以供以后重复使用.
3. 高性能.越快越好,因为在我正在运行的程序执行期间,这个函数大约会被调用大约200亿次(这是目前性能关键的代码.)它不需要用C语言编写,它真的只需要优于md5(在字符串的内置hash()的某个地方).
4. 接受'扰动'(这里使用的更好的词是什么？)整数作为输入来修改输出.我在下面举了一个例子(列表格式化规则不会让我把它放得更近.)我想这不是100%必要的,因为它可以通过手动扰动函数的输出来模拟,但是把它作为输入给了我一种温暖的感觉.
5. 完全用Python编写.如果它是绝对的,肯定需要用C语言编写,那么我想可以做到,但是我用python编写的函数比用C语言编写的更快的函数慢了20%,这只是因为使用两种不同语言的项目协调头痛.是的,这是一个警察,但这是一个愿望清单.

'Perturbed'哈希示例,其中哈希值以小整数值n急剧变化

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

最后,如果你很好奇我正在做什么,我需要这样一个特定的哈希函数,我正在完全重写pybloom模块以大大提高它的性能.我成功了(它现在运行速度提高了大约4倍,占用了大约50%的空间)但是我注意到有时如果滤波器变得足够大,它会突然出现假阳性率.我意识到这是因为哈希函数没有解决足够的位数.32位只能解决40亿位(请注意,滤波器地址位而不是字节)和一些我用于基因组数据的滤波器加倍或更多(因此最少34位).

谢谢!

Answer 1

看一下MurmurHash3的128位变体.该算法的页面包含一些性能数字.应该可以将其移植到Python,纯或作为C扩展.(更新了作者建议使用128位变体并丢弃不需要的位).

如果MurmurHash2 64位适合您,那么pyfasthash包中有一个Python实现(C扩展),其中包含一些其他非加密哈希变体,尽管其中一些仅提供32位输出.

更新我为Murmur3哈希函数做了一个快速的Python包装器.Github项目就在这里,您也可以在Python Package Index上找到它; 它只需要一个C++编译器来构建; 不需要提升.

用法示例和时序比较:

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

Answer 2

小心内置的哈希函数！

从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