构建一个哈希表/哈希函数 [英] 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屋！