Хеш-таблицы: Хеш-функции, Разрешение коллизий и Универсальное хеширование

Способы разрешения коллизий

Каждая ячейка таблицы содержит связный список или сбалансированное дерево (как в Java 8+ HashMap при длине цепочки

> 8

). При факторе загрузки

\alpha = n/m

среднее время поиска составляет

\Theta(1 + \alpha)

Все элементы хранятся непосредственно в массиве таблицы. При коллизии проверяется последовательность проб

h(k, 0), h(k, 1), \dots, h(k, m-1)

Линейное пробирование (Linear Probing):

h(k, i) = (h'(k) + i) \bmod m

Проблема: Первичная кластеризация (длинные непрерывные блоки занятых ячеек).

Квадратичное пробирование (Quadratic Probing):

h(k, i) = (h'(k) + c_1 i + c_2 i^2) \bmod m

Проблема: Вторичная кластеризация.

Двойное хеширование (Double Hashing):

h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m

Лучший метод открытой адресации (порождает

m!

перестановок проб при взаимно простых

h_2(k)

m

Семейство $\mathcal{H}$ хеш-функций называется универсальным, если для любых двух различных ключей $x \ne y$ :

P_{h \in \mathcal{H}} [h(x) = h(y)] \le \frac{1}{m}