Пробую различные алгоритмы хэширования и обнаружил следующий, так сказать, закон природы.
Если значение хэшкода h ограничено диапазоном (0 <= h) & (h < N), то при хэшировании N случайных объектов различных хэшкодов получается примерно 0.63 * N или меньше если хэшфункция совсем плохая.
Придумать хэшфункцию ограниченную числом N, которая при хэшировании N случайных объектов выдавала бы больше чем 63 процента с копейками различных хэшкодов не удаётся, почему-то.
Наиболее простая "63%" хэшфункция:
Код:
private static unsafe uint Hash (char* a, int n)
{
uint h = 0;
int i = 0;
while (i < n)
{
h = h * 2 + a[i++];
}
return h % N;
}
{
uint h = 0;
int i = 0;
while (i < n)
{
h = h * 2 + a[i++];
}
return h % N;
}
Перепробовал кучу других вариантов какие-только в голову пришли, но лучше чем 63 с копейками процентов не получается
Что это за закон природы такой?
