构造哈希表/哈希函数
我想构建一个哈希表，查找从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]; } 哈希函数有什么好的选择，或者我将如何构建一个？
谢谢。
为了散列C字符串，我总是使用这个函数（取结果％你的散列表的大小）：
int hashstring(const char* s) { int key = 0; while (*s) { key = key*37 + *s++; } return key; }
我不记得我最初从哪里得到它，但多年来它并没有让我失望。
你的密钥空间很大（大约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这样的标准库。
如果你想要一个完美的哈希，那么你可以从阅读完整哈希的维基百科文章开始。 如果遇到障碍，可以在这里寻求帮助。
如果表中驻留的字符串的平均数量很少 – 就像10,000个条目一样 – 关联数组将是一种合理的方法，即使使用线性搜索，如果它在现代CPU架构上也是如此。
否则，构造“完美散列”需要检查字符串的每个字符并基于可能的范围计算唯一值。 例如，如果密钥中只允许使用26个字符A..Z，则可以使用：
int hash (const char *key) { int h = 0; while (key && *key) h = h * 26 + (*key++ - 'A'); return h; }