c++ - 对于英语单词来说，什么是好的哈希函数？

Question

我有一长串英语单词，我想对它们进行哈希处理。什么是好的哈希函数？到目前为止，我的散列函数对字母的 ASCII 值求和，然后对表大小取模。我正在寻找高效且简单的东西。

Answer 1

简单地对字母求和并不是一个好的策略，因为排列会给出相同的结果。

这个 ( djb2 ) 非常受欢迎，并且可以很好地处理 ASCII 字符串。

unsigned long hashstring(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

更多信息here .

如果您需要更多替代方案和一些性能指标，请阅读here .

补充:这些是通用散列函数，其中输入域事先未知(也许除了一些非常一般的假设:例如，上面的方法在 ascii 中效果稍好)输入)，这是最常见的情况。如果您有一个已知的受限域(固定的输入集)，您可以做得更好，请参阅 Fionn 的答案。