1

我正在寻找一种哈希算法，以创建尽可能接近字符串的唯一哈希（max len = 255），从而产生一个长整数（DWORD）。

我意识到26^255 >> 2^32，但也知道英语单词的数量远少于2^32。

我需要“散列”的字符串主要是单个单词或使用两个或三个单词的简单构造。

答案：

FNV 变体之一应满足您的要求。它们速度很快，并且产生相当均匀分布的输出。（由Arachnid回答）

4

5 回答 5

2

有关此问题的先前迭代（和答案），请参见此处。

于 2008-09-24T10:26:38.783 回答
1

一种技术是使用众所周知的散列算法（例如，MD5 或 SHA-1）并仅使用结果的前 32 位。

请注意，哈希冲突的风险增加得比您预期的要快。有关这方面的信息，请阅读生日悖论。

于 2008-09-24T10:27:39.967 回答
1

Ronny Pfannschmidt 昨天用常见的英语单词做了一个测试，他在 Python 字符串哈希函数中测试的 10000 个单词没有遇到任何冲突。我自己没有测试过，但是那个算法非常简单快速，而且似乎针对常用词进行了优化。

这里的实现：

static long
string_hash(PyStringObject *a)
{
    register Py_ssize_t len;
    register unsigned char *p;
    register long x;

    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;
}
于 2008-09-24T10:28:26.267 回答
0

H(key) = [GetHash(key) + 1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))] % hashsize

MSDN 关于 HashCodes 的文章

于 2008-09-24T10:32:34.790 回答
0

Java 的 String.hash() 可以在这里轻松查看，它的算法是

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
于 2008-09-24T10:33:20.420 回答