Часто при программировании своих структур данных мы прибегаем к хэш-таблицам, пулам. Их эффективность напрямую зависит от хэш-фунции, которую мы в них используем. Хочу привести одну, проверенную временем и зарекомендовшую себя с лучшей стороны
функция ставит в соотвествие 32-х битному числу key другое 32-х битное псевдослучайное число.
Сопутствующей задачей является также операция взятия остатка от деления, при нахождении индекса бакета, в который мы хотим положить очередной нод.
То есть:
bucketIndex = Hash32(key) % bucketsCount;
эту операцию можно провести крайне быстро, используя побитовое И, если bucketsCount - степень двойки:
Ну а как насчет критерия рассеивания? Будут ли у нее лучшие характеристики от додавания по модулю 2 или других простых методов? Как на сравнения рассеивания твоей ф-ции и метода деления на простое число? Скорость хеш функции не самый главный критерий.
>Хочу привести одну, проверенную временем и зарекомендовшую себя с лучшей стороны Хотелось бы услышать более предметные характеристики ну или ссылочку на источник.
функция не моя, я просто разместил объву. я встречал её в нескольких программах, кажется, она даже носит чьё-то имя, но теперь концы подобрать уже малореально.
>А чем это лучше вот этого случай из жизни : работа с хэш-функцией была узким местом одной из операций. при замене твоего варианта приведённым, при прочих равных условиях общая производительность повысилась на треть.
судя по всему, данная конкретная функция получена когда-то кем-то из эвристических соображений, достаточно наивно с вашей стороны ожидать увидеть в подсказке на форуме разработчиков игр детальный её математический анализ.
