специализированная хеш-таблица c ++

Question

Мне нужно сосчитать много разных предметов. Я обрабатываю список пар, таких как:

A34223,34
B23423,-23
23423212,16

То, что я планировал сделать, - это хэшировать первое значение (ключ) в 32-битное целое число, которое затем будет ключом к разреженной структуре, где «значение» будет добавлено (все начинаются с нуля) и станет отрицательным .

Учитывая, что их ключи являются короткими и буквенно-цифровыми, есть ли способ сгенерировать алгоритм хеширования, быстрый на 32-битных архитектурах x86? Или есть подходящий подходящий хеш?

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

Answer 1

Поскольку вы используете C ++, первое, что вы должны сделать, это создать тривиальную имплиментацию с использованием std :: map. Это достаточно быстро (вероятно, будет)? Если так, придерживайтесь этого, иначе исследуйте, обеспечивает ли Ваша реализация C ++ хэш-таблицу. Если это так, используйте его, чтобы создать тривиальную реализацию, протестируйте его. Это достаточно быстро (почти наверняка да)?

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

Answer 2

Проверьте на сайте Боба Дженкина для хороших хэш-функций. IIRC это тот же хеш, который используется в Perl.

Answer 3

Гарантия отсутствия столкновений трудна.

В вашем случае ключи

A34223
B23423
23423212

можно преобразовать в 32-разрядные целые числа без особых усилий.

А вот хорошая функция, которая генерирует хэши из строк:

/**
 *  "The Practice of Programming", Hash Tables, section 2.9, pg. 57
 *
 *  computes hash value of string
 */
DWORD
strhash( char* str )
{
  //#define MULTIPLIER 31 or 37
  unsigned int   h;
  unsigned char* p;

  h = 0;
  for ( p=(unsigned char*)str; *p != '\0'; p++ )
    h = 31 * h + *p; // <- FIXED MULTIPLIER

  return h;
}