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