我想构建一个哈希表,在 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;
}
我不记得我最初是从哪里得到它的,但多年来它并没有让我失望。
关于构建哈希表/哈希函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2962207/