构建哈希表/哈希函数

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 个条目，否则随机哈希可能会失败。

我强烈建议使用 常规（非完美）哈希 和 适当处理冲突，例如使用链接：

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++ 哈希映射。

Answer 3

如果您想要一个完美的哈希，那么您可以首先阅读关于完美哈希的维基百科文章。如果您遇到困难，可以在这里寻求帮助。

Answer 4

如果表中驻留的字符串平均数量较低（例如低于 10,000 个条目），则关联数组将是一种合理的方法，即使在现代 CPU 架构上使用线性搜索也是如此。

否则，构建“完美哈希”需要检查字符串的每个字符并根据可能的范围计算唯一值。例如，如果密钥中只允许使用 26 个字符 A..Z，则以下方法有效：

int
hash (const char *key)
{
   int h = 0;
   while (key && *key)
       h = h * 26 + (*key++ - 'A');
   return h;
}