字符串的哈希函数

Question

字符串的哈希函数

我正在使用C语言编写哈希表，我正在测试字符串的哈希函数。

我尝试过的第一个函数是添加ascii代码并使用modulo（％100）但是我在第一次数据测试时得到的结果很差：140个单词的40个冲突。

最终的输入数据将包含8 000个单词（它是一个文件中的dictionnary存储）。哈希表声明为int table [10000]并包含txt文件中单词的位置。

第一个问题是哪个是散列字符串的最佳算法？以及如何确定哈希表的大小？

提前致谢 ！

Answer 1

首先，您通常不希望对哈希表使用加密哈希。根据哈希表标准，加密标准非常快的算法仍然非常慢。其次，您希望确保输入的每一位都能/将影响结果。一种简单的方法是将当前结果旋转一些位，然后用当前字节对当前哈希码进行异或。重复，直到到达字符串的末尾。请注意，您通常不希望旋转为字节大小的偶数倍。例如，假设8位字节的常见情况，您可以旋转5位：int hash(char const *input) {      int result = 0x55555555;     while (*input) {          result ^= *input++;         result = rol(result, 5);     }}编辑：另请注意，10000个插槽很少是哈希表大小的好选择。您通常需要以下两种方法之一：您要么使用素数作为大小（需要确保某些类型的散列分辨率的正确性），要么需要2的幂（因此可以通过简单的方法将值减小到正确的范围位掩码）。

Answer 2

对于C，存在许多现有的哈希表实现，从C标准库hcreate / hdestroy / hsearch到APR和glib中的那些，它们还提供预构建的哈希函数。我强烈建议使用它们，而不是发明自己的哈希表或哈希函数; 它们已针对常见用例进行了大量优化。但是，如果您的数据集是静态的，那么您最好的解决方案可能是使用完美的哈希。对于给定的数据集，gperf将为您生成完美的哈希值。