在C语言中编写程序时我想念的一件事是字典数据结构.在C中实现一个最方便的方法是什么？我不是在寻找性能,而是从头开始编写代码.我也不希望它是通用的 - 像string-> int这样的东西.但我确实希望它能够存储任意数量的项目.
这更像是一项练习.我知道有第三方库可供使用.但考虑一下,他们不存在.在这种情况下,您可以以最快的方式实现满足上述要求的字典.
我正在尝试编写一个使用哈希表来存储不同单词的C程序,我可以使用一些帮助.
首先,我创建一个哈希表,其中素数的大小最接近我必须存储的单词的数量,然后我使用哈希函数来查找每个单词的地址.我从最简单的功能开始,将字母加在一起,结果是88%的碰撞.然后我开始尝试该功能,发现无论我改变它,碰撞都不会低于35%.现在我正在使用
unsigned int stringToHash(char *word, unsigned int hashTableSize){
unsigned int counter, hashAddress =0;
for (counter =0; word[counter]!='\0'; counter++){
hashAddress = hashAddress*word[counter] + word[counter] + counter;
}
return (hashAddress%hashTableSize);
}
这只是我提出的随机功能,但它给了我最好的结果 - 大约35%的碰撞.
过去几个小时我一直在阅读有关散列函数的文章,我尝试使用一些简单的函数,比如djb2,但是所有这些都给了我更糟糕的结果.(djb2导致了37%的碰撞,这是'更糟糕的是,但我期待更好而不是更糟糕的事情)我也不知道如何使用其他更复杂的一些,例如murmur2,因为我不知道参数是什么(关键,len ,种子)他们接受了.
即使使用djb2,或者我做错了什么,获得超过35%的碰撞是正常的吗？什么是关键,len和种子价值？