LINUX.ORG.RU

Зачем в хеш-функции простые числа?

 


0

4

Есть такая примитивная хеш-функция для строки:

const char *c = "Hello World Sobaka";
uint32_t h = 0;
const int PRIME = ...;
while (*c) {
  h = h * PRIME + *c;
}

h; // our hash

В чём прикол того, что PRIME будет простым числом? Кому это выгодно?



Последнее исправление: hlamotron (всего исправлений: 2)

чтобы минимизировать вероятность появления общих множителей

Bobby_
()

На самом деле важно, чтобы у PRIME не было общих делителей с модулем, который в данном случае получается равен 2^32, так как это будет более предсказуемо стирать информацию из хеша. Например, если бы основания хеша делилось на 2, то все символы дальше 32 с конца гарантированно не вносили бы никакого вклада в результат.

Но такой хеш (у которого модуль является степенью 2) в любом случае плохой: http://codeforces.com/blog/entry/4898?locale=ru

vzzo ★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.