什么是英语单词的好哈希函数？

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

如果您需要更多替代方案和一些性能测量,请在此处阅读.

补充:这些是一般的散列函数,其中输入域事先不知道(除了一些非常一般的假设:例如上面的函数稍微好于ascii输入),这是最常见的情况.如果你有一个已知的受限域(固定的输入集)你可以做得更好,请参阅Fionn的答案.

Answer 2

也许这样的事情会对你有所帮助:http://www.gnu.org/s/gperf/

它为输入域生成优化的散列函数.

Answer 3

如果你不需要加密安全,我会建议Murmur哈希.它速度极快,扩散率高.使用方便.

http://en.wikipedia.org/wiki/MurmurHash

http://code.google.com/p/smhasher/wiki/MurmurHash3

如果你确实需要加密安全散列,那么我建议通过OpenSSL使用SHA1.

http://www.openssl.org/docs/crypto/sha.html