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

Question

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

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

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

---

答案：

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

---

Answer 1

请参阅here以获取此问题的上一次迭代（以及答案）。

Answer 2

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

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

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）>> 5）+ 1）％（hashsize - 1））]％hashsize

MSDN article on HashCodes

Answer 5

Java String.hash（）可以很容易地查看qazxsw poi，它的算法是

here