我正在用C语言编写哈希表,我正在测试字符串的哈希函数。
我尝试的第一个函数是添加ascii代码并使用模数(%100),但我在第一次数据测试中得到了很差的结果: 130个单词发生40次冲突。
最终的输入数据将包含8000个单词(它是一个存储在文件中的字典)。哈希表被声明为int table10000,并且包含单词在txt文件中的位置。
第一个问题是,哪种算法是对字符串进行散列的最佳算法?如何确定哈希表的大小?
提前感谢!
:-)
发布于 2011-10-06 03:26:03
我用Dan Bernstein的djb2
得到了很好的结果。
unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
发布于 2011-10-06 03:42:46
Wikipedia shows一个很好的字符串散列函数,叫做Jenkins,每次一个散列。它还引用了这个散列的改进版本。
uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
uint32_t hash, i;
for(hash = i = 0; i < len; ++i)
{
hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
发布于 2011-10-06 10:16:17
有许多现有的用于C的哈希表实现,从C标准库hcreate/hdestroy/hsearch到APR和glib中的实现,它们也提供了预先构建的哈希函数。我强烈建议使用这些,而不是发明自己的哈希表或哈希函数;它们已经针对常见用例进行了大量优化。
但是,如果数据集是静态的,则最好的解决方案可能是使用perfect hash。对于给定的数据集,gperf将为您生成完美的哈希。
https://stackoverflow.com/questions/7666509
复制相似问题