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

Question

我需要一个python中的高性能字符串哈希函数，该函数生成的整数的输出位至少为34位（64位是有意义的，但32位太少）。在堆栈溢出上还有其他一些类似的问题，但在我能找到的每一个被接受/投票的答案中，都属于少数几个类别中的一个，它们不适用（出于给定的原因）

• 使用内置的hash()函数。这个函数，至少在我正在开发的机器上（使用Python2.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%，这只是因为使用两种不同语言的项目协调问题。是的，这是一个逃避，但这是一个愿望清单在这里。

“扰动”哈希示例，其中哈希值被一个小整数值n剧烈更改

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

最后，如果您想知道我到底在做什么，我需要这样一个特定的哈希函数，我正在对pybloom模块进行完全的重新编写，以大大提高其性能。我成功地做到了这一点（现在它的运行速度提高了4倍左右，占用了大约50%的空间），但我注意到，有时如果滤波器变得足够大，它的假阳性率就会突然飙升。我意识到这是因为哈希函数没有处理足够的位。32位只能处理40亿位（请注意，过滤器只处理位而不是字节）和一些我用于基因组数据的过滤器是这个数字的两倍或更多（因此最少34位）

谢谢！

Answer 1

“strings”：我假设您希望散列Python 2.xstr对象和/或Python3.xbytes和/或bytearray对象。

这可能违反了您的第一个约束，但是：请考虑使用

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

获取（32+N）位哈希。

Answer 2

Use the built-in hash() function. This function, at least on the machine I'm developing for (with python 2.7, and a 64-bit cpu) produces an integer that fits within 32 bits - not large enough for my purposes.

那不是真的。内置哈希函数将在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;
}

Answer 3

看看128-bit variant of MurmurHash3。algorithm's page包含一些性能数字。应该可以将它移植到Python，pure或作为C扩展。（已更新作者建议使用128位变量，并丢弃不需要的位）。

如果murrushash2 64位对您有效，那么pyfasthash package中有一个Python实现（C扩展），其中包括一些其他的非加密散列变量，尽管其中一些仅提供32位输出。

更新我为murdur3散列函数做了一个快速的Python包装器。{a4}，你可以在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