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

Question

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

• 使用内置的hash()函数。

至少在我正在开发的机器上（使用python 2.7和64位cpu），此函数会产生一个适合32位的整数-不够我的目的。

Use hashlib。

hashlib提供了加密哈希例程，这些例程比非加密目的要慢。我发现这是不言而喻的，但是如果您需要基准和引用来使您相信这一事实，那么我可以提供。[将string.__hash__()函数用作原型来编写您自己的函数。我怀疑这将是正确的方法，只是该特定函数的效率取决于对c_mul函数的使用，该函数可以环绕32位-太小了，我无法使用！非常令人沮丧，它是如此接近完美！

一个理想的解决方案将具有以下特性，以相对的，不重要的顺序。

具有至少延伸34位长（可能为64位）的输出范围，同时在

all位上保留
1. consistent雪崩特性。 （至少在我的愚蠢示例中，连接32位哈希往往会违反雪崩特性。）便携式。给定两台不同机器上相同的输入字符串，我应该两次都得到相同的结果。这些值将存储在文件中，以供以后重用。高性能。越快越好，因为此函数在我正在运行的程序的执行期间将被调用约200亿次（此刻是性能至关重要的代码。）它不需要用C编写，实际上只需要胜过md5（在字符串的内置hash（）领域中的某个地方）。
2. 接受“扰动”（在这里使用哪个更好的词？）整数作为输入来修改输出。我在下面放一个示例（列表格式规则不会让我更靠近它。）我想这不是100％必要的，因为可以通过手动干扰函数的输出来模拟它，但是将其作为输入可以给我一种温暖的感觉。
3. 完全用Python编写。如果绝对肯定地用[[需要
用C编写，那么我想可以做到，但是由于项目协调的麻烦，我将用python编写的函数要比用C编写的更快的函数慢20％。使用两种不同的语言。是的，这是一个解决方案，但这是这里的愿望清单。
4. ''Perturbed'哈希示例，其中，哈希值被一个小的整数值n急剧改变了>]

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

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

谢谢！

我需要python中的高性能字符串哈希函数，该函数可生成至少具有34位输出的整数（64位是有意义的，但32位太少了）。还有其他几个... 
看看128-bit variant of MurmurHash3。 algorithm's page包含一些性能编号。应该可以将其纯粹地或作为C扩展移植到Python。 （
更新
作者建议使用128位变体，并丢弃不需要的位。）>
如果MurmurHash2 64位适合您，pyfasthash package中有一个Python实现（C扩展），它包括一些其他非加密哈希变体，尽管其中一些仅提供32位输出。
Update
我为Murmur3哈希函数做了一个快速的Python包装器。 Github project is here，您可以在Python Package Index as well上找到它；它只需要一个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
 
使用内置的hash（）函数。至少在我正在开发的机器上（具有python 2.7和64位cpu）产生的整数可容纳32位-不足以容纳我的目的。
不正确。内置的哈希函数将在64位系统上生成64位哈希。
这是来自Objects/stringobject.c（Python版本2.7）的python str哈希函数：
static long
string_hash(PyStringObject *a)
{
    register Py_ssize_t len;
    register unsigned char *p;
    register long x;      /* Notice the 64-bit hash, at least on a 64-bit system */

    if (a->ob_shash != -1)
    return a->ob_shash;
    len = Py_SIZE(a);
    p = (unsigned char *) a->ob_sval;
    x = *p << 7;
    while (--len >= 0)
        x = (1000003*x) ^ *p++;
    x ^= Py_SIZE(a);
    if (x == -1)
        x = -2;
    a->ob_shash = x;
    return x;
}
 
“字符串”：我想您希望散列Python 2.x str对象和/或Python3.x bytes和/或bytearray对象。
这可能违反了您的第一个约束，但是：请考虑使用类似的东西>>
(zlib.adler32(strg, perturber) << N) ^ hash(strg)
获得（32 + N）位的哈希。
 
如果可以使用Python 3.2，则在64位Windows上的哈希结果现在为64位值。 
 
请谨慎使用内置的哈希函数！
自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

Answer 1

Answer 2

不正确。内置的哈希函数将在64位系统上生成64位哈希。

Answer 3

(zlib.adler32(strg, perturber) << N) ^ hash(strg)

获得（32 + N）位的哈希。

Answer 4

请谨慎使用内置的哈希函数！

Answer 5