Быстрая 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
Комментарии [6]