简单哈希函数

Question

我正在尝试编写一个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，因为我不知道它们接受的参数(key、len、seed)是什么。

即使使用djb2，冲突率超过35%是正常的吗？还是我做错了什么？key、len和seed值是什么？

Answer 1

尝试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。增加容量意味着创建一个具有更高容量的新哈希表，将当前哈希表中的所有值添加到新哈希表中（因此，它们必须全部重新哈希，因为它们的新索引在大多数情况下会有所不同），新的哈希表数组替换旧的哈希表数组，并释放/释放旧的哈希表数组。如果你计划哈希1000个单词，哈希表的容量至少建议在1250，更好的1400甚至1500。

哈希表不应该被“填满”，至少如果哈希表应该是快速和高效的（因此，哈希表总是应该有剩余的容量），那么哈希表就不应该被“填满”。这就是哈希表的缩减，它们是快速的(O(1))，但是它们通常会浪费更多的空间，而不是将相同的数据存储在另一个结构中所需要的空间（当您将它们存储为排序数组时，您只需要1000个字的容量；缩减的地方是在这种情况下查找速度不能超过O(logn))。任何一种情况下，无冲突哈希表在大多数情况下都是不可能的。几乎所有的哈希表实现都期望发生冲突，并且通常有某种方法来处理它们（通常冲突会使查找慢一些，但是哈希表仍然可以工作，并且在许多情况下仍然胜过其他数据结构）。

还要注意，如果您使用的是一个相当好的哈希函数，如果哈希表具有2次方的容量（如果您最终使用模(%)裁剪哈希值），则没有任何要求，甚至没有任何优势。许多哈希表实现总是使用power of 2容量的原因是，它们不使用modulo，而是使用AND(&)进行裁剪，因为AND(&)操作是大多数CPU上最快的操作之一（modulo从来不会比AND(&)快，在最好的情况下，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的endpoint，但这并不是一个真正的问题，它会在大小endpointCPU上工作。只需记住，它不会在大小endian 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次比较更长的时间！散列越好，对相同数量的数据进行散列所需的时间就越长。因此，只有当您有大量的数据或者您必须频繁更新数据时，哈希表才会在性能方面得到回报（例如，不断地向表中添加字词或从表中删除字词，因为这些操作对哈希表的开销比对排序列表的开销小）。hashatble是O(1)这一事实仅仅意味着无论它有多大，查找都将大约为。总是需要同样多的时间。o(logn)仅表示查找量与字数成对数增长，即字数越多，查找速度越慢。然而大O符号并没有说明绝对速度！这是一个很大的误解。并没有说O(1)算法总是比O(logn)算法执行得快。大O表示法只是告诉您，如果O(log n)算法对于一定数量的值更快，并且您不断增加值的数量，O(1)算法肯定会在某个时间点超过O(log n)算法，但您当前的字数可能远低于那个点。如果不对这两种方法进行基准测试，您就无法通过查看大O符号来判断哪种方法更快。

回到碰撞。如果遇到碰撞，你该怎么办？如果冲突的数量很少，这里我指的不是总的冲突数量（哈希表中冲突的单词数量），而是每个索引（存储在同一哈希表索引中的单词数量，因此在您的例子中可能是2-4个），那么最简单的方法就是将它们存储为链表。如果到目前为止这个表索引没有冲突，那么只有一个键/值对。如果发生冲突，则存在键/值对的链表。在这种情况下，您的代码必须遍历链表并验证每个键，如果匹配则返回值。根据您的数字，这个链表不会有超过4个条目，并且进行4个比较在性能方面是无关紧要的。所以找到索引是O(1)，找到值（或者检测到这个键不在表中）是O(n)，但这里n只是链表条目的数量（所以最多是4个）。

如果冲突数增加，链表可能会变慢，您还可以存储一个动态大小的、排序的键/值对数组，这允许查找o(logn)并且n只是该数组中的键数，而不是hastable中的所有键数。即使在一个索引上有100个冲突，找到正确的键/值对最多需要7次比较。那还是近乎一无所获。尽管在一个索引上确实有100个冲突，但您的哈希算法不适合关键数据，或者哈希表的容量太小。动态大小排序的数组的缺点是添加/删除键比使用链表（代码方面，不一定是性能方面）要多一些。因此，使用链表通常是足够的，如果您保持足够低的冲突数量，几乎是微不足道的实现这样的链表自己在C和添加到一个现有的哈希表实现。

我所见过的大多数哈希表实现似乎都使用这样的“回退到另一个数据结构”来处理冲突。缺点是需要一点额外的内存来存储替代的数据结构，并且需要更多的代码来搜索该结构中的键。还有一些解决方案将冲突存储在哈希表本身中，并且不需要任何额外的内存。然而，这些解决方案有几个缺点。第一个缺点是，每次冲突都会增加更多冲突的机会，因为添加了更多的数据。第二个缺点是，虽然键的查找时间与到目前为止的冲突数量呈线性减少（正如我前面所说的，每次冲突都会随着数据的添加导致更多的冲突），但不在哈希表中的键的查找时间减少得更厉害，最后，如果您对不在哈希表中的键执行查找（但不执行查找您就无法知道），查找可能需要在整个哈希表中进行线性搜索所需的时间（糟糕！！！）。因此，如果您可以节省额外的内存，可以使用另一种结构来处理冲突。