38

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

  • 使用内置hash()函数。这个函数，至少在我正在开发的机器上（使用 python 2.7 和 64 位 cpu）产生一个适合 32 位的整数 - 对于我的目的来说不够大。
  • 使用哈希库。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 位。）

谢谢！

4

6 回答 6

24

看看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
于 2011-03-23T03:00:17.733 回答
3

使用内置的 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;
}
于 2012-08-31T18:25:59.427 回答
3

小心内置的哈希函数！

从 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
于 2019-11-16T12:04:22.377 回答
2

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

这可能违反您的第一个约束，但是：考虑使用类似的东西

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

得到一个 (32+N) 位的散列。

于 2011-03-23T03:05:43.873 回答
0

如果您可以使用 Python 3.2，则 64 位 Windows 上的哈希结果现在是 64 位值。

于 2011-03-23T04:29:06.947 回答
0

看看xxHash，还有pip 包。

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

我已经使用 xxHash 很长时间了（我的典型用例是对字符串进行哈希处理——不是出于安全目的），我对性能非常满意。

于 2021-09-04T08:17:37.703 回答