5

我想构建一个哈希表,它在 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];
}

哈希函数有哪些不错的选择,或者我将如何构建一个?

谢谢。

4

4 回答 4

3

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

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

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

于 2011-02-22T08:03:23.113 回答
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++ hashmap这样的标准库。

于 2010-06-02T23:43:07.663 回答
0

如果你想要一个完美的散列,那么你可以从阅读关于完美散列的维基百科文章开始。如果你遇到障碍,你可以在这里寻求帮助。

于 2010-06-02T23:02:49.573 回答
0

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

否则,构建“完美哈希”需要检查字符串的每个字符并根据可能的范围计算唯一值。例如,如果键中只允许包含 26 个字符 A..Z,则可以这样:

int
hash (const char *key)
{
   int h = 0;
   while (key && *key)
       h = h * 26 + (*key++ - 'A');
   return h;
}
于 2010-06-02T23:07:20.153 回答