Building a hash table / hash function

Question

I would like to build a hash table that looks for keys in sequences (strings) of bytes in the range of 1 to 15 bytes.

I would like to keep the integer value, so I assume that the array for hashing will be sufficient. It’s hard for me to understand how to construct a hash function in such a way that the given key returns an index to the array.

Any help would be greatly improved.

The maximum number of entries in the hash: 4081 * 15 + 4081 * 14 + ... 4081 = 4081 ((15 * (16)) / 2) = 489720.

So for example:

int table[489720];

int lookup(unsigned char *key)
{
    int index = hash(key);
    return table[index];
}

What are some good options for a hash function, or how can I build it?

Thank.

Answer 1

hash C ( % your hash table size):

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

, , .

Answer 2

( 2 ^ (8 * 15)), , , , 489720 . , (a.k.a. ). , , - , , , , 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
}

- , ++ hashmap.

Answer 3

, . , .

Answer 4

, , - , 10 000 - , , .

Otherwise, building an “ideal hash” requires checking each character of the string and calculating a unique value based on the possible range. For example, if only 26 A..Z characters are allowed in the key, this will work:

int
hash (const char *key)
{
   int h = 0;
   while (key && *key)
       h = h * 26 + (*key++ - 'A');
   return h;
}