Для одного самописного балансировщика нагрузки необходимо выбрать алгоритм (не криптографический) для подсчёта контрольных сумм. Входные данные (строковые ключи) всегда точно больше 32 байт.
Очень хотелось бы услышать мнение разработчиков с глубоким пониманием темы. Какой из следующих алгоритмов вы бы порекомендовали или предостерегли от использования?
То, что удалось найти самому:
— fnv-1a — самый распространенный по описанию в сети;
— lookup3 — то, к чему склоняюсь сам; на мой взгляд — наиболее оптимальный, но смущает отсутствие ссылок на успешное применение в проектах, как у fnv;
— MurmurHash2 — судя по доступным тестам — самый быстрый, есть истории применения (libmemcached, Hadoop); но какая-то неадекватная ситуация с коллизиями на определенных тестовых наборах — simon-says.vox.com/library/post/murmur-hash-very-f... — "...one pathological input sequence of 2^32 values causes the algorithm to suffer from a rate of hash collision as high as 97.6%"
Если не сильно заморачиваться, то в книге Кернигана и Пайка «Практика программирования» есть довольно простой алгоритм:
enum { MULTIPLIER = 31 };
/* hash: вычислить
хэш-функцию строки */
unsigned int hash(char *str)
{
unsigned int h;
unsigned char *p;
h = 0;
for (p = (unsigned char *)
str; *p != '\0'; p++)
h = MULTIPLIER * h +
*p; return h % NHASH; }
My<cod/>.net
