试试 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 字；缩小尺寸是查找不能比O(log n)这种情况更快）。在大多数情况下，任何一种方式都无法实现无冲突哈希表。几乎所有的哈希表实现都期望发生冲突，并且通常有某种方式来处理它们（通常冲突会使查找速度变慢，但哈希表仍然可以工作并且在许多情况下仍然优于其他数据结构）。
另请注意，如果您使用的是非常好的哈希函数，那么如果哈希表的容量为 2 的幂，%并且最后使用模 ( ) 裁剪哈希值，则没有要求，甚至没有优势。许多哈希表实现总是使用 2 的幂的原因是因为它们不使用模数，而是使用 AND ( &) 进行裁剪，因为 AND 操作是大多数 CPU 上最快的操作之一（模永远不会比 AND ，在最好的情况下它会同样快，在大多数情况下它会慢很多）。如果您的哈希表使用 2 个大小的幂，您可以使用 AND 操作替换任何模块：
x % 4 == x & 3
x % 8 == x & 7
x % 16 == x & 15
x % 32 == x & 31
...
不过，这仅适用于 2 大小的幂。如果您使用模数，则 2 大小的幂只能买一些东西，如果哈希是非常糟糕的哈希，并且“位分布”非常糟糕。错误的位分布通常是由不使用任何类型的位移（>>或<<）或任何其他与位移具有类似效果的操作的散列引起的。
我为您创建了一个精简的 lookup3 实现：
#include <stdint.h>
#include <stdlib.h>
#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为0是否喜欢或在创建哈希表时选择一个随机值（并且始终将此随机值用于此哈希表实例，但每个哈希表都有自己的随机值）。
碰撞注意事项：
在实践中，碰撞通常不是一个大问题，为了避免它们而浪费大量内存通常是没有回报的。问题是您将如何以有效的方式处理它们。
您说您目前正在处理 9000 个单词。如果您使用的是未排序的数组，则在数组中查找一个单词平均需要 4500 次比较。在我的系统上，4500 个字符串比较（假设单词长度在 3 到 20 个字符之间）需要 38 微秒（0.000038 秒）。因此，即使是这样一个简单、无效的算法，对于大多数用途来说也足够快。假设您正在对单词列表进行排序并使用二进制搜索，则在数组中查找单词平均只需要 13 次比较。13 次比较在时间上几乎为零，甚至无法可靠地进行基准测试。因此，如果在哈希表中查找一个单词需要 2 到 4 次比较，我什至不会浪费一秒钟的时间来回答这是否可能是一个巨大的性能问题。
在您的情况下，具有二进制搜索的排序列表甚至可能远远超过哈希表。当然，13 次比较比 2-4 次比较需要更多时间，但是，对于哈希表，您必须首先对输入数据进行哈希处理才能执行查找。单独散列可能已经花费了超过 13 次比较！哈希值越好，对相同数量的数据进行哈希处理所需的时间就越长。因此，只有在您拥有大量数据或必须频繁更新数据（例如，不断向表中添加/删除单词，因为这些操作对于哈希表而言，这些操作的成本比它们低用于排序列表）。哈希表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），最简单的方法是将它们存储为链表。如果到目前为止此表索引没有冲突，则只有一个键/值对。如果发生冲突，则有一个键/值对的链表。在这种情况下，您的代码必须遍历链表并验证每个键，如果匹配则返回值。根据你的数字，这个链接列表不会有超过 4 个条目，并且进行 4 次比较在性能方面是微不足道的。所以找到索引是O(1)，查找值（或检测到该键不在表中）是O(n)，但这里n只是链表条目的数量（因此最多为4）。
如果冲突次数增加，链表可能会变慢，您还可以存储一个动态大小、排序的键/值对数组，它允许O(log n)再次查找，n只是该数组中键的数量，而不是 hastable 中所有键的数量。即使一个索引有 100 次冲突，找到正确的键/值对也最多需要 7 次比较。这仍然几乎没有。尽管事实上，如果您在一个索引上确实有 100 次冲突，那么您的哈希算法不适合您的关键数据，或者哈希表的容量太小。动态大小的排序数组的缺点是添加/删除键比链表的情况要多一些工作（代码方面，不一定是性能方面）。因此，如果您将冲突的数量保持在足够低的水平，那么使用链表通常就足够了，并且在 C 中自己实现这样的链表并将其添加到现有的哈希表实现中几乎是微不足道的。
我似乎使用过的大多数哈希表实现都使用这种“回退到备用数据结构”来处理冲突。缺点是这些需要一点额外的内存来存储替代数据结构和更多的代码来搜索该结构中的键。还有一些解决方案可以将冲突存储在哈希表本身内，并且不需要任何额外的内存。然而，这些解决方案有几个缺点。第一个缺点是随着更多数据的添加，每次碰撞都会增加更多碰撞的机会。第二个缺点是，虽然到目前为止，键的查找时间随着碰撞次数线性减少（正如我之前所说，随着数据的添加，每次碰撞都会导致更多的碰撞），不在哈希表中的键的查找时间会减少得更糟，最后，如果您对不在哈希表中的键执行查找（但不执行查找就无法知道），查找时间可能与线性时间一样长搜索整个哈希表（YUCK !!!）。因此，如果您可以节省额外的内存，请使用替代结构来处理冲突。