Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Подсказки / Быстрая hash-функция

Быстрая 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);

16 октября 2009

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

Комментарии:
dipПостоялецwww17 окт. 20090:52#1
А чем это лучше вот этого:
 inline_ int Hash32(int key)
 {
   return key;
 }

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

RomПостоялецwww17 окт. 20091:38#2
Ну а как насчет критерия рассеивания? Будут ли у нее лучшие характеристики от додавания по модулю 2 или других простых методов? Как на сравнения рассеивания твоей ф-ции и метода деления на простое число?  Скорость хеш функции не самый главный критерий.
doc.Постоялецwww17 окт. 200913:44#3
>Хочу привести одну, проверенную временем и зарекомендовшую себя с лучшей стороны
Хотелось бы услышать более предметные характеристики ну или ссылочку на источник.
SuslikМодераторwww17 окт. 200917:30#4
функция не моя, я просто разместил объву. я встречал её в нескольких программах, кажется, она даже носит чьё-то имя, но теперь концы подобрать уже малореально.

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

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

КонишуаПостоялецwww17 окт. 200918:09#5
Вот здесь вроде есть математическое обоснование:
http://www.concentric.net/~Ttwang/tech/inthash.htm
AndreyПостоялецwww21 окт. 200914:50#6
Конишуа
спасибо за ссылку.

/ Форум / Программирование игр / Общее

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

2001—2017 © GameDev.ru — Разработка игр