构建一个哈希表/哈希函数 [英] Constructing a hash table/hash function
问题描述
我想建立一个哈希表中查找字节范围从1至15字节的序列(字符串)键
I would like to construct a hash table that looks up keys in sequences (strings) of bytes ranging from 1 to 15 bytes.
我要存储一个整数值,所以我想象哈希数组就足够了。我有困难的概念化如何构建一个散列函数,例如,鉴于关键会给一个索引到数组。
I would like to store an integer value, so I imagine an array for hashing would suffice. I'm having difficulty conceptualizing how to construct a hash function such that given the key would give an index into the array.
任何援助将大大AP preiated。
Any assistance would be much appreiated.
条目的散列的最大数量为:4081 * 15 + 4081 * 14 + ... 4081 = 4081((15 *(16))/ 2)= 489720
The maximum number of entries in the hash is: 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];
}
什么是散列函数的一些很好的选择,不然我怎么会去构建一个?
What are some good choices for a hash function, or how would I go about constructing one?
感谢。
推荐答案
要凑C字符串,我一直使用这个功能(拍摄效果的%哈希表的大小):
To hash C strings, I've always used this function (take the result % your hash table's size):
int hashstring(const char* s) {
int key = 0;
while (*s) {
key = key*37 + *s++;
}
return key;
}
我不记得在那里我从最初的得到它,但在许多年里,它没有让我失望。
I don't remember where I got it from initially, but in many years it hasn't let me down.
这篇关于构建一个哈希表/哈希函数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!