构建哈希表/哈希函数

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;
}

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