在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位，并保持所有位上的一致avalanche特性。（串接32位哈希往往会违反avalanche属性，至少在我的愚蠢示例中是这样。）
2. 可移植。在两台不同的机器上给定相同的输入字符串，应该得到相同的结果。这些值将存储在文件中以供以后重用。
3. 高性能。越快越好，因为在程序执行期间调用此函数大约20亿次（目前是性能关键代码）。它不需要用C编写，它真的只需要胜过md5（在字符串的内置哈希中的某个地方）。
4. 接受'扰动'（在这里使用什么更好的词？）整数作为输入以修改输出。我在下面放了一个示例（列表格式规则不允许我将其放得更近）。我想这并不是100%必要的，因为可以通过手动扰动函数的输出来模拟它，但是将其作为输入使我感觉很好。
5. 完全使用Python编写。如果绝对，肯定需要使用C编写，那么我想这可以完成，但是对于使用两种不同语言的项目协调头痛来说，我会接受用Python编写的速度慢20%的函数。是的，这很拍脑袋，但这是一个心愿单。

'扰动'哈希示例，其中哈希值受小整数值n的剧烈更改

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

最后，如果你好奇我在做什么需要如此特定的哈希函数，我正在完全重写pybloom模块以大大提高其性能。我成功地完成了这个任务（现在它运行速度约快4倍，使用的空间约为原来的50%），但我注意到有时候如果过滤器足够大，误报率会突然上升。我意识到这是因为哈希函数没有足够的位数。32位只能寻址40亿个位（注意，过滤器寻址的是位而不是字节），而我用于基因组数据的一些过滤器会加倍以上（因此需要至少34位）。

谢谢！

- eblume

---

hash(s) * 2**32 + hash(s+s)是否有问题？如果hash足够好的话，那么这就足够好了，对吗？假设hash(s+s)与hash(s)没有明显的关联，那么您将在所有输出位上获得雪崩效应。如果由于内存分配而不够快，您可以使用C编写代码来将哈希算法应用于s+s，但实际上不执行字符串连接。 - Steve Jessop

换句话说，hash(s)<<32 + hash(s+s)。我会尝试一下 - 谢谢你的想法！ - eblume

Answer 1

看一下128位MurmurHash3变体。算法页面包括一些性能数字。应该可以将其移植到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

- samplebias

---

你知道我之前看过这个模块，但由于缺少C++ python_boost库（或者是boost_python？）无法编译。我会再仔细看一下的，看看能否解决问题。谢谢！ - eblume

是的，它需要Boost Python。在Ubuntu上，可以使用sudo apt-get install libboost-python-dev进行安装。我在我的PPA中构建了一个软件包作为示例。 - samplebias

SetAffinity函数在murmur3代码中没有被调用，platform.cpp文件只是为了完整性而存在。 - samplebias

我明天才能测试，但我相信这是正确的方法。再次感谢！ - eblume

在我的个人使用情况中，我总是指定一个“种子”值（别名为我在原始问题中提到的“扰动”值），C++实现的murmur3比Python的hash((key,n))性能提高了10%以上。这绝对是正确的选择。非常感谢！ - eblume

Answer 2

小心使用内置哈希函数！

自从Python 3版本以后，每次解释器启动它都会使用不同的种子（我不知道更多细节），因此每次生成的值都是不同的 - 但不适用于本地数字类型。

$ 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

- Simone Aonzo

---

正确。在哈希函数初始化之前，您必须正确设置环境中的PYTHONHASHSEED。 - ldmtwo

Answer 3

请看xxHash，还有pip软件包。

xxHash 是一种极快的哈希算法，运行速度接近 RAM 速度极限。它成功完成了 SMHasher 测试套件，该测试套件评估哈希函数的冲突、离散和随机性质。代码高度可移植，哈希在所有平台（小/大端）上都是相同的。

我已经使用了很长时间的 xxHash（我的典型用例是哈希字符串--非安全目的），并且我对其性能非常满意。

- Simone Aonzo

---

这对我的使用情况非常有效。 - Peter Gaultney

Answer 4

使用内置的hash()函数。这个函数在我正在开发的机器上（使用python 2.7和64位cpu）至少生成一个适合32位的整数 - 对我的目的来说不够大。

这是不正确的。在64位系统上，内置的哈希函数将生成一个64位的哈希值。

这是Python版本2.7中的字符串哈希函数Objects / stringobject.c：

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;
}

- Saish

---

内置的hash()函数在Python 3.3中存在另一个问题，即哈希随机化。如果布隆过滤器需要能够写入磁盘，则不能使用内置的hash()函数。 - amcnabb

此外，Python 在云平台上的实现（如 Heroku 和 GAE）将在不同的实例上返回不同的 hash() 值，使其对于任何必须在两个或多个“机器”（在 Heroku 的情况下为 dynos）之间共享的内容都是无用的。 - B Robster

Answer 5

"字符串": 我假设您想要对Python 2.x的str对象和/或Python 3.x的bytes和/或bytearray对象进行哈希。

这可能违反了您的第一个限制，但是：考虑使用类似于

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

获得一个（32+N）位哈希值。

- John Machin

---

你的猜测是正确的，我正在对“str”对象进行哈希处理-我会查看这段代码片段，谢谢。但你说得对，我个人怀疑这里每个输出比特都有一致的熵。还是谢谢！ - eblume

Answer 6

如果您使用 Python 3.2，那么在 64 位 Windows 上的哈希结果现在是一个 64 位的值。

- casevh

---

我一直在使用Python 2.7，但如果3.x引擎中的哈希宽度确实、一致地更宽，那可能足以让我转换。谢谢！ - eblume

@eblume：64位Windows上的64位哈希是3.2版本中的增强功能。64位Linux平台一直具有64位哈希值。Python的32位版本（Linux和Windows）仅具有32位哈希值。 - casevh