python中的快速，大宽度，非加密字符串哈希

Question

我需要python中的高性能字符串哈希函数，该函数可以生成至少具有 34 位输出的整数（64位是有意义的，但32位太少了）。在Stack
Overflow上还有其他类似的问题，但是在我能找到的每一个被接受/赞成的答案中，我都属于以下几类之一，这些问题都不适用（由于给定的原因）。

• 使用内置hash()功能。至少在我正在开发的机器上（使用python 2.7和64位cpu），此函数会产生一个整数，该整数适合32位-不足以满足我的目的。
• 使用hashlib。 hashlib提供了加密哈希例程，该例程比非加密目的 要 慢得多。我发现这是不言而喻的，但是如果您需要基准和引用来使您相信这一事实，那么我可以提供。
• 使用string.__hash__()函数作为原型来编写您自己的函数。我怀疑这将是正确的方法，只是该特定html" target="_blank">函数的效率取决于对c_mul函数的使用，该函数包装了32位-同样，对于我来说太小了！非常令人沮丧，它是如此接近完美！

理想的解决方案应具有以下相对重要性的松散特性。

1. 输出范围至少扩展34位，可能扩展到64位，同时在 所有 位上保持 一致的 雪崩特性。（至少在我愚蠢的例子中，将32位哈希连接在一起往往会破坏雪崩特性。） __
2. 随身携带。给定两个不同机器上的相同输入字符串，我应该两次都得到相同的结果。这些值将存储在文件中，以备将来使用。
3. 高性能。越快越好，因为此函数在我正在运行的程序的执行过程中将被调用约200亿次（此刻是性能至关重要的代码。）它不需要用C编写，实际上只需胜过md5（在字符串的内置hash（）领域中的某个地方）。
4. 接受一个“摄动”（在这里使用哪个更好的词？）整数作为输入来修改输出。我在下面放一个示例（列表格式规则不会让我更靠近它。）我想这不是100％必需的，因为可以通过手动干扰函数的输出来模拟它，但是将其作为输入可以给我一种温暖的感觉。
5. 完全用Python编写。如果绝对是肯定的，肯定 需要 用C编写，那么我想可以做到，但是由于使用两种不同语言的项目协调问题，我会以比python快20％的速度编写比python慢​​20％的函数。是的，这是一个解决方案，但这是这里的愿望清单。

“扰动”散列示例，其中，散列值由一个小的整数值n急剧改变

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

最后，如果您对我正在做的到底是什么感到好奇，我需要这样一个特定的哈希函数，那么我正在对pybloom模块进行完全重写，以显着提高其性能。我做到了这一点（它现在运行速度提高了约4倍，并使用了大约50％的空间），但是我注意到有时，如果过滤器足够大，它突然会以假阳性率出现尖峰。我意识到这是因为散列函数没有寻址足够的位。32位只能寻址40亿位（请注意，过滤器只寻址位而不是字节），而我用于基因组数据的某些过滤器要加倍甚至更多（因此最少34位）。

谢谢！

Answer 1

看一下MurmurHash3的128位变体。该算法的页面包含一些性能数字。应该可以将其纯粹地或作为C扩展移植到Python。（作者建议
更新后 使用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