最多255个字符的字符串的非冲突哈希算法

Question

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

我意识到26 ^ 255＆gt;＆gt; 2 ^ 32，但也知道英语中的单词数远远小于2 ^ 32。

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

---

答案：

其中一个 FNV变体应符合您的要求。它们很快，并且产生相当均匀的分布式输出。 （由 Arachnid回答）

---

Answer 1

参见这里对于此问题的前一次迭代（以及答案）。

Answer 2

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

请注意，哈希冲突的风险增长速度超出预期。有关这方面的信息，请阅读生日悖论。

Answer 3

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

Answer 4

H（key）= [GetHash（key）+ 1 +（（（GetHash（key）＆gt;＆gt; 5）+ 1）％（hashsize＆＃8211; 1））]％hashsize

关于HashCodes的MSDN文章

Answer 5

可以在这里轻松查看Java的String.hash（） ，其算法

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]