简单的哈希函数
我正在尝试编写一个使用哈希表来存储不同单词的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和种子价值？
试试sdbm：
hashAddress = 0; for (counter = 0; word[counter]!='\0'; counter++){ hashAddress = word[counter] + (hashAddress << 6) + (hashAddress << 16) - hashAddress; }
或者djb2：
hashAddress = 5381; for (counter = 0; word[counter]!='\0'; counter++){ hashAddress = ((hashAddress << 5) + hashAddress) + word[counter]; }
或者Adler32：
uint32_t adler32(const void *buf, size_t buflength) { const uint8_t *buffer = (const uint8_t*)buf; uint32_t s1 = 1; uint32_t s2 = 0; for (size_t n = 0; n < buflength; n++) { s1 = (s1 + buffer[n]) % 65521; s2 = (s2 + s1) % 65521; } return (s2 << 16) | s1; } // ... hashAddress = adler32(word, strlen(word));
但是，这些都不是很好。 如果你真的想要好的哈希，你需要像lookup3这样更复杂的东西。
请注意，一旦哈希表填充超过70-80％ ，就会产生大量冲突。 这是完全正常的，如果使用非常好的哈希算法，甚至会发生这种情况。 这就是为什么大多数哈希表实现增加哈希表的容量（例如capacity * 1.5或甚至capacity * 2 ），只要您向哈希表添加内容并且比率size / capacity已经高于0.7到0.8。 增加容量意味着创建一个具有更高容量的新哈希表，将当前值中的所有值添加到新哈希表中（因此它们必须全部重新加入，因为它们的新索引在大多数情况下会有所不同），新的hastable数组替换旧的，旧的释放/释放。 如果你计划散列1000个单词，哈希表容量最低建议为1250，更好1400或甚至1500。
哈希表不应该被“填满”，至少不应该是快速和有效的（因此他们总是应该有剩余的能力）。 这是哈希表的缩小，它们很快（ O(1) ），但它们通常会浪费更多的空间，而不是将相同的数据存储在另一个结构中（当你将它们存储为排序数组时，你只需要一个1000个字的容量为1000;缩小尺寸是在这种情况下查找不能比O(log n)快。 在大多数情况下，无论哪种方式都无法实现无冲突哈希表。 几乎所有散列表实现都希望碰撞发生，并且通常有某种方式来处理它们（通常碰撞会使查找速度变慢，但哈希表仍然可以工作，并且在许多情况下仍会击败其他数据结构）。
另请注意，如果您使用非常好的哈希函数，如果您最后使用模数（ % ）裁剪哈希值，则哈希表具有2的容量，则没有要求，但甚至没有优势。 许多散列表实现总是使用2个容量的原因是因为它们不使用模数 ，而是使用AND（ & ）进行裁剪，因为AND操作是大多数CPU上最快的操作之一（模数从不比并且，在最好的情况下它会同样快，在大多数情况下它会慢很多）。 如果哈希表使用2个大小的幂，则可以使用AND操作替换任何模块：
x % 4 == x & 3 x % 8 == x & 7 x % 16 == x & 15 x % 32 == x & 31 ...
但这仅适用于2种尺寸的功率。 如果你使用modulo，2个大小的function只能买东西，如果哈希是一个非常糟糕的哈希与非常糟糕的“位分布”。 坏位分布通常是由不使用任何类型的位移（ >>或<< ）的散列或任何其他与位移具有类似效果的操作引起的。
我为你创建了一个精简的lookup3实现：
#include #include #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) #define mix(a,b,c) \ { \ a -= c; a ^= rot(c, 4); c += b; \ b -= a; b ^= rot(a, 6); a += c; \ c -= b; c ^= rot(b, 8); b += a; \ a -= c; a ^= rot(c,16); c += b; \ b -= a; b ^= rot(a,19); a += c; \ c -= b; c ^= rot(b, 4); b += a; \ } #define final(a,b,c) \ { \ c ^= b; c -= rot(b,14); \ a ^= c; a -= rot(c,11); \ b ^= a; b -= rot(a,25); \ c ^= b; c -= rot(b,16); \ a ^= c; a -= rot(c,4); \ b ^= a; b -= rot(a,14); \ c ^= b; c -= rot(b,24); \ } uint32_t lookup3 ( const void *key, size_t length, uint32_t initval ) { uint32_t a,b,c; const uint8_t *k; const uint32_t *data32Bit; data32Bit = key; a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval; while (length > 12) { a += *(data32Bit++); b += *(data32Bit++); c += *(data32Bit++); mix(a,b,c); length -= 12; } k = (const uint8_t *)data32Bit; switch (length) { case 12: c += ((uint32_t)k[11])<<24; case 11: c += ((uint32_t)k[10])<<16; case 10: c += ((uint32_t)k[9])<<8; case 9 : c += k[8]; case 8 : b += ((uint32_t)k[7])<<24; case 7 : b += ((uint32_t)k[6])<<16; case 6 : b += ((uint32_t)k[5])<<8; case 5 : b += k[4]; case 4 : a += ((uint32_t)k[3])<<24; case 3 : a += ((uint32_t)k[2])<<16; case 2 : a += ((uint32_t)k[1])<<8; case 1 : a += k[0]; break; case 0 : return c; } final(a,b,c); return c; }
此代码的性能不如原始代码高度优化，因此它更简单。 它也不像原始代码那样便携，但它可以移植到当今使用的所有主要消费者平台。 它也完全忽略了CPU端，但这不是一个真正的问题，它将适用于大端和小端的CPU。 请记住，它不会为大端和小端CPU上的相同数据计算相同的哈希值，但这不是必需的; 它将计算两种CPU上的良好散列，唯一重要的是它总是为单个机器上的相同输入数据计算相同的散列。
你可以使用这个函数如下：
unsigned int stringToHash(char *word, unsigned int hashTableSize){ unsigned int initval; unsigned int hashAddress; initval = 12345; hashAddress = lookup3(word, strlen(word), initval); return (hashAddress%hashTableSize); // If hashtable is guaranteed to always have a size that is a power of 2, // replace the line above with the following more effective line: // return (hashAddress & (hashTableSize - 1)); }
你想知道initval是什么。 嗯，这是你想要的任何东西。 你可以把它称为盐。 它会影响哈希值，但由于这个原因，哈希值的质量不会变得更好或更差（至少在一般情况下，它可能导致非常特定数据的或多或少的冲突）。 例如，如果要对相同的数据进行两次哈希，则可以使用不同的initval值，但每次都应该生成不同的哈希值（不能保证它会，但如果initval不同则很可能;如果它创建相同的值，这将是一个非常不吉利的巧合，你必须将其视为一种碰撞）。 在对相同散列表进行散列数据时，不建议使用不同的initval值（这将导致平均更多的冲突）。 initval的另一个用途是，如果要将哈希与其他一些数据组合在一起，在这种情况下，当对其他数据进行哈希initval时，已存在的哈希变为initval （因此，其他数据以及之前的哈希影响哈希的结果）function）。 如果您愿意，甚至可以将initval设置为0 ，或者在创建哈希表时选择随机值（并且始终对此哈希表实例使用此随机值，但每个哈希表都有自己的随机值）。
关于碰撞的说明：
碰撞在实践中通常不是一个巨大的问题，它通常不会浪费大量的内存来避免它们。 问题是你如何以有效的方式处理它们。
你说你正在处理9000字。 如果您使用的是未排序的数组，则在数组中查找单词平均需要进行4500次比较。 在我的系统上，4500字符串比较（假设单词长度在3到20个字符之间）需要38微秒（0.000038秒）。 因此，即使是这样一个简单，无效的算法，对于大多数目的而言也足够快 假设您正在对单词列表进行排序并使用二进制搜索，那么在数组中查找单词平均只需要进行13次比较。 13个比较在时间上几乎没有任何关系，甚至可靠地进行基准测试也是如此。 因此，如果在散列表中找到一个单词需要2到4个比较，我甚至不会浪费一秒钟来判断这是否是一个巨大的性能问题。
在您的情况下，具有二进制搜索的排序列表甚至可以击败哈希表。 当然，13次比较需要比2-4次比较更多的时间，但是，在哈希表的情况下，您必须首先对输入数据进行散列以执行查找。 单独哈希可能已经花费了超过13次比较！ 散列越好 ，对相同数量的数据进行散列所需的时间就越长 。 因此，如果您拥有非常大量的数据，或者您必须经常更新数据（例如，不断向表中添加/删除单词，那么哈希表只能在性能方面得到回报，因为这些操作对哈希表的成本要低于它们是排序列表）。 hashatble是O(1)的事实只意味着无论它有多大，查找都会大约。 总是需要相同的时间。 O(log n)仅表示查找与单词数呈对数增长，这意味着更多的单词，更慢的查找。 然而，Big-O表示法没有提到绝对速度！ 这是一个很大的误解。 并不是说O(1)算法总是比O(log n)算法执行得更快。 Big-O表示法仅告诉您如果O(log n)算法对于一定数量的值更快并且您继续增加值的数量，则O(1)算法肯定会超过O(log n)算法在某个时间点，但您当前的字数可能远低于该点。 如果不对两种方法进行基准测试，只需查看Big-O表示法就不能说哪一种方法更快。
回到碰撞。 如果遇到碰撞，你该怎么办？ 如果冲突的数量很少，这里我并不是指冲突的总数（哈希表中冲突的单词数），而是每个索引一（存储在相同哈希表索引中的单词数，所以在你的情况下可能2-4），最简单的方法是将它们存储为链表。 如果此表索引到目前为止没有冲突，则只有一个键/值对。 如果发生冲突，则存在键/值对的链接列表。 在这种情况下，您的代码必须遍历链表并validation每个键，如果匹配则返回值。 根据您的数字，此链接列表不会超过4个条目，并且进行4次比较在性能方面无关紧要。 所以找到索引是O(1) ，找到值（或检测到该键不在表中）是O(n) ，但这里n只是链表项的数量（所以它最多为4） 。
如果冲突的数量增加，链表可能会变慢，你也可以存储一个动态大小的，有序的键/值对数组，允许查找O(log n) ，再次， n只是键的数量在该数组中，而不是hastable中的所有键。 即使一个索引处有100个冲突，找到正确的键/值对最多需要7个比较。 那仍然几乎没有。 尽管事实上如果你在一个索引上确实有100个冲突，你的哈希算法不适合你的密钥数据，或者哈希表的容量太小。 动态大小的排序数组的缺点是添加/删除键比链接列表的情况要多一些（代码方面，不一定是性能方面）。 因此，如果保持冲突的数量足够低，使用链表通常就足够了，并且在C中自己实现这样的链表并将其添加到现有哈希表实现中几乎是微不足道的。
我似乎使用的大多数哈希表实现都使用了“回退到备用数据结构”来处理冲突。 缺点是这些需要一点额外的内存来存储备用数据结构，并需要更多的代码来搜索该结构中的密钥。 还有一些解决方案可以在哈希表本身内部存储冲突，并且不需要任何额外的内存。 然而，这些解决方案具有一些缺点。 第一个缺点是，随着更多数据的添加，每次碰撞都会增加更多碰撞的机会。 第二个缺点是，虽然密钥的查找时间与到目前为止的冲突数量呈线性关系（正如我之前所说，每次碰撞都会在添加数据时导致更多冲突），但不在哈希表中的密钥的查找时间会减少甚至更糟最后，如果你对一个不在哈希表中的键执行查找（但是你不知道没有执行查找），那么查找可能需要在整个哈希表上进行线性搜索（YUCK !!!） 。 因此，如果您可以节省额外的内存，请寻找替代结构来处理冲突。
首先，我创建一个哈希表，其大小为素数，它是我必须存储的单词数量的关闭，然后我使用哈希函数来查找每个单词的地址。
…
return（hashAddress％hashTableSize）;
由于不同哈希的数量与单词数量相当，因此您不能期望具有更低的冲突。
我用随机哈希（这是你能达到的最好）做了一个简单的统计测试，如果你有#words == #different哈希，我发现26％是限制冲突率。