Комментарии к постам Дед Нечипор
Дед Нечипор, на упомянутую мной формулу нужно наложить маску по размеру хэштейбла. Т.е. размер тейбла берется кратным степени двойки. Морочиться с делением на простое число не надо, это замедлит функцию, если число неизвестно в compile time.
Так что сдвиг N именно таки и определяет, с какого участка брать. После умножения на 0x1000193 распределение хаоса по битам будет подобно гауссиане, брать биты по краям — плохая идея.
Трудно придумать приложение, где это бы реально имелo хоть какой-то смысл. Когда размеры хэш тейбла невелики, проще бороться с коллизиями увеличением размера самого тейбла, заполнение на 50-70% по учебникам на деле нафиг не уперлось. Память ничего не стоит, пока она влезает в L1D.
Когда нужна быстрая но приличная хэш функция для значения, влезающего в 32 бита, использую обычно такой шаблон:
const uint64_t MAGIC = 0x01000193;
size_t hash = value*MAGIC >> N;
N подбирается на типовом наборе хэшируемых значений по к-ву коллизий на заданном размере тейбла, обычно оно в диапазоне 10-20.
Это не то же самое, что хэш FNV, откуда константа позаимствована. Оно работает много быстрее FNV, но при разумном применении дает небольшое к-во коллизий.