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

Question

Я пытаюсь понять, как работает универсальное хэширование. Определяется 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, и может быть много столкновений.

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

Answer 1

Предполагая, что номера вы хеширования имеют равномерное распределение, ваша функция смещается в сторону ведрами от 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 

Answer 2

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

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

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

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