Tag: 散列表

简单的哈希函数

我正在尝试编写一个使用哈希表来存储不同单词的C程序，我可以使用一些帮助。 首先，我创建一个哈希表，其中素数的大小最接近我必须存储的单词的数量，然后我使用哈希函数来查找每个单词的地址。 我从最简单的function开始，将字母加在一起，结果是88％的碰撞。 然后我开始尝试该function，发现无论我改变它，碰撞都不会低于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); } 这只是我提出的随机function，但它给了我最好的结果 – 大约35％的碰撞。 过去几个小时我一直在阅读关于散列函数的文章，我尝试使用一些简单的函数，比如djb2，但是所有这些都给了我更糟糕的结果。（djb2导致了37％的碰撞，这是’更糟糕的是，但我期待更好而不是更糟糕的事情）我也不知道如何使用其他更复杂的一些，比如murmur2，因为我不知道参数是什么（关键，len ，种子）他们接受的是。 即使使用djb2，或者我做错了什么，获得超过35％的碰撞是正常的吗？ 什么是关键，len和种子价值？