Войти
ПрограммированиеПодсказкиОбщееОбщее

Быстрая hash-функция

Автор:

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

 inline_ int Hash32(int key)
 {
  key += ~(key << 15);
  key ^=  (key >> 10);
  key +=  (key << 3);
  key ^=  (key >> 6);
  key += ~(key << 11);
  key ^=  (key >> 16); 
  return key;
 }
функция ставит в соотвествие 32-х битному числу key другое 32-х битное псевдослучайное число.


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

bucketIndex = Hash32(key) % bucketsCount;
эту операцию можно провести крайне быстро, используя побитовое И, если bucketsCount - степень двойки:
bucketIndex = Hash32(key) & (bucketsCount - 1);

#hash, #оптимизация

16 октября 2009

Комментарии [6]

#1
0:52, 17 окт. 2009

А чем это лучше вот этого:

 inline_ int Hash32(int key)
 {
   return key;
 }

Я знаю, зачем нужны hash функции, но у меня вопрос - в каких ситуациях эта дает более равномерный разброс?

#2
1:38, 17 окт. 2009

Ну а как насчет критерия рассеивания? Будут ли у нее лучшие характеристики от додавания по модулю 2 или других простых методов? Как на сравнения рассеивания твоей ф-ции и метода деления на простое число?  Скорость хеш функции не самый главный критерий.

#3
13:44, 17 окт. 2009

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

#4
17:30, 17 окт. 2009

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

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

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

#5
18:09, 17 окт. 2009

Вот здесь вроде есть математическое обоснование:
http://www.concentric.net/~Ttwang/tech/inthash.htm

#6
14:50, 21 окт. 2009

Конишуа
спасибо за ссылку.

ПрограммированиеПодсказкиОбщееОбщее

Тема в архиве.