构造哈希表/哈希函数

Question

我想构建一个哈希表，在从1到15字节的字节序列(字符串)中查找关键字。

我想存储一个整数值，所以我想一个用于散列的数组就足够了。我很难概念化如何构造一个哈希函数，这样给定的键就可以给数组一个索引。

任何帮助都会很受欢迎。

哈希的最大条目数为: 4081*15 + 4081*14 + ... 4081 = 4081((15*(16))/2) = 489720。

举个例子：

int table[489720];

int lookup(unsigned char *key)
{
    int index = hash(key);
    return table[index];
}

哈希函数有哪些好的选择，或者我该如何去构建一个？

谢谢。

Answer 1

为了散列C字符串，我一直使用这个函数(取你的散列表大小的结果)：

int hashstring(const char* s) {
  int key = 0;
  while (*s) {
    key = key*37 + *s++;
  }
  return key;
}

我不记得最初是从哪里得到它的，但多年来它从未让我失望过。

Answer 2

您的密钥空间很大(大约2^(8*15))，所以如果您想要一个完美的散列，您需要知道预先显示的489720个实际密钥。即使这样，实际上也不可能为这些键找到一个完美的散列，即使您允许使用更大的表(也称为非常低的负载率)。据我所知，找到完美散列的唯一方法是反复试验，除非你的表有接近489720^2个条目，否则随机散列很可能会失败。

我强烈建议使用regular (non-perfect) hash和deal with collisions appropriately，例如使用链接：

struct entry {
  unsigned char *key;
  int value;
  struct entry *next;
} *table[1<<20];
int lookup(unsigned char *key) {
  int index = hash(key) % (1<<20);
  for (struct entry *e = table[index]; e != NULL; e = e->next) {
    if (!strcmp(key, e->key)) return e->value;
  }
  // not found
}

我也建议你不要自己实现它--使用像c++ hashmap这样的标准库。

Answer 3

如果你想要一个完美的散列，那么你可以从阅读perfect hashing上的维基百科文章开始。如果你遇到困难，你可以在这里寻求帮助。