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

Question

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

Я хотел бы создать хеш-таблицу, которая ищет ключи в последовательностях (строки) байтов в пределах от 1 - 15 байтов.

Я хотел бы сохранить целочисленное значение, таким образом, я предполагаю, что массив для хеширования был бы достаточен. Я испытываю затруднения при осмыслении, как создать хеш-функцию, таким образом, который, учитывая ключ дал бы индекс в массив.

Любая помощь была бы большим количеством appreiated.

Максимальное количество записей в хеше: 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];
}

Каковы некоторые хорошие варианты для хеш-функции, или как я пошел бы о построении того?

Спасибо.

5

c string hash hashtable hash-function

задан 2 revs 3 June 2010 в 01:37

3 ответа

Другие вопросы по тегам:

c string hash hashtable hash-function

Похожие вопросы:

score 2 · Answer 1

У вас большое пространство для ключей (примерно 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 .

score 0 · Answer 2

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

score 0 · Answer 3

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

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

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