Построение хеш-таблицы / хеш-функции

Question

Я хотел бы создать хеш-таблицу, которая ищет ключи в последовательностях (строках) байтов в диапазоне от 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];
}

Каков хороший выбор для хэш-функции или как мне ее создать?

Спасибо.

Answer 1

Для хеширования C-строк я всегда использовал эту функцию (берут результат% от размера вашей хеш-таблицы):

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

Я не помню, откуда я взял это изначально, но за многие годы это не подводило меня.

Answer 2

Ваше пространство клавиш велико (примерно 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 .

Answer 3

Если среднее число строк в таблице невелико - например, менее 10000 записей - разумным подходом будет ассоциативный массив, даже если используется линейный поиск, если он работает на современной архитектуре ЦП.

В противном случае построение «идеального хэша» требует проверки каждого символа строки и вычисления уникального значения на основе возможного диапазона. Например, если в ключе разрешены только 26 символов A..Z, это будет работать:

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

Answer 4

Если вам нужен идеальный хеш, то вы можете начать с чтения статьи в Википедии о идеальном хешировании . Если вы столкнулись с трудностями, вы можете обратиться за помощью здесь.