Универсальное недопонимание хеширования

Я пытаюсь понять, как работает универсальное хеширование. Определяется h(x) = [(a*x + b) mod p] mod m где a,b - случайные числа, m - размер хеш-таблицы, x - ключ и p - простое число. Например, у меня есть несколько разных ключей:

92333
23347
20313

И чтобы создать универсальную хеш-функцию, мне нужно следующее:

Let a = 10, b = 22, p = 313, m = 100
h(92333) = [(10 * 92333 + 22) mod 313] mod 100 = 2 mod 100 = 2
h(23347) = [(10 * 23347 + 22) mod 313] mod 100 = 307 mod 100 = 7
...

Но, вероятно, каждый раз, когда я получу число в диапазоне от 0 до 99, может случиться много столкновений.

Поэтому мой вопрос: правильно ли я понял и применил универсальное хеширование?

Источник

2 ответа

Решение

Предполагая, что числа, которые вы хэшируете, имеют равномерное распределение, ваша функция смещена в сторону сегментов от 0 до 12.

Предположим, что операция хеширования вплоть до mod 313 операция происходит. В результате этой операции вы получите значение в диапазоне 0..312. Опять же, если результат этой операции даже распределен, то возьмите mod 100 Вы получаете следующий эффект:

 result of       Occurs for these
  mod 100        mod 313 results
-----------     ------------------
     0           0, 100, 200, 300
     1           1, 101, 201, 301
     2           2, 102, 202, 302
     3           3, 103, 203, 303
     4           4, 104, 204, 304
     5           5, 105, 205, 305
     6           6, 106, 206, 306
     7           7, 107, 207, 307
     8           8, 108, 208, 308
     9           9, 109, 209, 309
    10          10, 110, 210, 310
    11          11, 111, 211, 311
    12          12, 112, 212, 312
    13          13, 113, 213
    14          14, 114, 214
    15          15, 115, 215

Заметьте, как количество возможностей получить конкретный результат падает после 12? Это твоя предвзятость. Вот еще одно свидетельство этого эффекта, полученное при подсчете результатов хеширования чисел от 0 до 5 000 000:

counts[0]: 63898
counts[1]: 63896
counts[2]: 63899
counts[3]: 63900
counts[4]: 63896
counts[5]: 63896
counts[6]: 63900
counts[7]: 63896
counts[8]: 63896
counts[9]: 63900
counts[10]: 63898
counts[11]: 63896
counts[12]: 63899
counts[13]: 47925
counts[14]: 47922
counts[15]: 47922
counts[16]: 47925

... elided similar counts ...

counts[97]: 47922
counts[98]: 47922
counts[99]: 47925
Источник

Но, вероятно, каждый раз, когда я получу число в диапазоне от 0 до 99, может случиться много столкновений.

Правильно. Но ваша хеш-таблица имеет только 100 блоков, поэтому вы не сможете избежать коллизий, если попытаетесь вставить более нескольких дюжин ключей.

Лучшее, на что вы можете надеяться, - это равномерно распределить коллизии по всей сотне сегментов, что ваша хэш-функция должна выполнять примерно. Таким образом, вы не столкнетесь с большим количеством столкновений, пока таблица не заполнится, и в столкновениях не будет слишком много вовлеченных сторон.

Если вы хотите хранить гораздо больше ключей, вам нужно увеличить таблицу.

Источник
Другие вопросы по тегам