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 的回答。