尝试使用sdbm：
hashAddress = 0;
for (counter = 0; word[counter]!='\0'; counter++){
hashAddress = word[counter] + (hashAddress << 6) + (hashAddress << 16) - hashAddress;
}
或者 djb2：
hashAddress = 5381
for (counter = 0
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, murmur3或者CityHash一样使用更复杂的算法。
请注意，当一个哈希表被填充超过70-80%的容量时，预计会有大量冲突。这是完全正常的，即使你使用了非常好的哈希算法也会发生。这就是为什么大多数哈希表实现在添加元素到哈希表时，在比率size / capacity已经超过0.7到0.8时，会增加哈希表的容量（例如capacity *1.5 或甚至是capacity*2）。增加容量意味着创建一个具有较高容量的新哈希表，将当前哈希表中的所有值添加到新哈希表中（因此它们必须全部重新哈希，因为它们的新索引在大多数情况下将是不同的），替换旧哈希表数组，并释放旧哈希表。如果你打算哈希1000个单词，建议哈希表容量至少为1250，最好1400或1500。
哈希表不应该“填满”，至少不应该这样做如果它们的速度和效率要快（因此它们总是应该有备用容量）。这就是哈希表的缺点，它们很快(O(1))，但它们通常会浪费比在另一个结构中存储相同数据所需的空间多得多（当你将它们作为排序数组存储时，你只需要1000个单词的容量; 缺点是在这种情况下查找不能更快地进行O(log n)）。在大多数情况下，冲突的自由哈希表也不可能。几乎所有哈希表实现都预计会发生冲突，并且通常有某种处理它们的方法(通常冲突会使查找变得有点慢，但哈希表仍然可以继续工作，并且在许多情况下仍然能够击败其他数据结构)。
还要注意，如果你使用一个相当不错的哈希函数，如果哈希表最后使用模运算(%)截断哈希值，那么没有要求或优势，使哈希表具有2的幂容量。许多哈希表实现始终使用2的幂容量的原因是，它们不使用模运算，而是使用AND(&)进行截断，因为AND操作是大多数CPU上可以找到的最快操作之一(模除永远不会比AND更快，在最好的情况下，它将同样快，在大多数情况下，它要慢得多)。如果你的哈希表使用2的幂大小，你可以用AND操作替换任何模块：
x
x
x
x
...
这只适用于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);
}
你可能会想知道什么是initval。实际上，它可以是任何你想要的值。你可以把它称为盐。它会影响哈希值，但哈希值的质量不会因此变得更好或更差（至少在平均情况下是这样的，对于非常特定的数据，它可能导致更多或更少的碰撞）。例如，如果你想两次哈希相同的数据，则可以使用不同的initval值，但每次应该产生不同的哈希值（虽然没有保证它会，但如果initval不同，这是相当可能的；如果它创建相同的值，那么这将是一个非常不幸的巧合，你必须将其视为一种碰撞）。在为同一个哈希表哈希数据时，不建议使用不同的initval值（这通常会导致更多的碰撞）。
initval的另一个用途是如果你想将哈希与其他数据组合起来，那么在哈希其他数据时，已经存在的哈希将成为initval（因此，其他数据以及先前的哈希都会影响哈希函数的结果）。你甚至可以将initval设置为0，或在创建哈希表时选择一个随机值（并始终将此随机值用于这个哈希表实例，但每个哈希表都有其自己的随机值）。
关于碰撞的说明：
在实践中，碰撞通常不是太大的问题，浪费大量内存来避免它们并不划算。问题在于你如何以有效的方式处理它们。
你说你正在处理9000个单词。如果你使用未排序的数组，在平均情况下查找一个单词需要4500次比较。在我的系统上，进行4500个字符串比较（假设单词长度在3到20个字符之间）需要38微秒（0.000038秒）。因此，即使是这样一个简单而低效的算法对于大多数目的来说也足够快了。假设你正在对单词列表进行排序并使用二分搜索，那么在数组中查找一个单词只需要平均13次比较。13次比较在时间上几乎可以忽略不计，它太少了甚至无法可靠地进行基准测试。因此，如果在哈希表中查找一个单词只需要2到4次比较，我甚至不会浪费一秒钟的时间来考虑这是否可能是一个巨大的性能问题。
在您的情况下，一个有序列表结合二分查找可能会远胜过哈希表。当然，13次比较需要更多时间，但是对于哈希表来说，您必须先对输入数据进行哈希处理才能执行查找。仅仅哈希处理就可能比13次比较要久！ 哈希越好，相同数量的数据哈希处理所需的时间就越长。因此，只有在您有大量数据或需要频繁更新数据的情况下（例如不断将单词添加/删除到表中），哈希表才能在性能方面交出好成绩，因为这些操作对于有序列表而言代价更高。哈希表的
O(1) 仅意味着无论大小如何，查找都需要大致相同的时间。
O(log n)意味着查找随着单词数量的增加而对数级增长，也就是说，单词越多，查找越慢。然而，大O符号表示法并没有说明绝对速度！ 这是一个很大的误解。这并不意味着
O(1) 算法总是比
O(log n) 更快。大O符号仅告诉您，如果
O(log n) 算法在某个特定值上更快，并且您不断增加值的数量，那么
O(1) 算法某些时候肯定会超过
O(log n) 算法，但是当前的单词数量可能远低于该点。如果没有对这两种方法进行基准测试，仅仅通过大O符号表示法，您无法判断哪一种方法更快。
回到碰撞问题。如果遇到了碰撞怎么办？如果碰撞数量很少 - 我在这里指的不是总碰撞数（哈希表中发生碰撞的单词数量），而是每个索引位置的碰撞数（存储在同一个哈希表索引处的单词数量，在您的情况下可能是2-4），最简单的方法是将它们作为链接列表存储。如果这个表索引到目前为止没有发生任何碰撞，那么只有一个键/值对。如果发生了碰撞，则有一个键/值对的链接列表。在这种情况下，您的代码必须遍历链接列表并验证每个键，如果匹配则返回值。根据您的数字，这个链接列表不会有多于4个条目，在性能上做4次比较是微不足道的。因此，找到索引是O(1)，找到值（或检测此键是否不在表中）是O(n)，但是这里的n只是链接列表条目的数量（因此最多为4）。如果冲突数量增加，链表可能会变得很慢，您可以存储一个动态大小的、排序的键/值对数组，它允许查找时间为O(log n)，其中n仅是该数组中键的数量，而不是哈希表中所有键的数量。即使在一个索引处有100个冲突，找到正确的键值对也最多需要7次比较。尽管如此，如果你真的在一个索引处有100个冲突，要么你的哈希算法不适合你的键数据，要么哈希表的容量太小了。动态大小的排序数组的缺点是添加 / 删除键比链表（代码上而不是性能上）更繁琐。因此，如果您保持冲突数量足够低，使用链表通常就足够了，而且在C中自己实现这样的链表并将其添加到现有的哈希表实现中几乎是微不足道的。
我看过的大多数哈希表实现都使用这样的“回退到备用数据结构”来处理冲突。缺点是需要一些额外的内存来存储备用数据结构，并且需要更多的代码来在该结构中搜索键。还有一些解决方案将冲突存储在哈希表本身中，不需要任何额外的内存。然而，这些解决方案也有几个缺点。第一个缺点是每个冲突都增加了更多数据，从而增加了更多的冲突可能性。第二个缺点是虽然随着冲突数量的线性增加，键的查找时间线性降低（而且正如我之前所说，由于数据的添加，每个冲突都会导致更多的冲突），但是对于哈希表中没有的键的查找时间线性恶化，最终，如果您执行查找尚未在哈希表中的键（但是您无法通过执行查找来确定），则查找可能需要像整个哈希表的线性搜索一样长（YUCK!!!）。因此，如果您可以节省额外的内存，请使用备用结构来处理冲突。
