Прямое связывание
В массиве хранятся указатели на списки, в которых может быть несколько элементов.
…
Есть множество пар \((k, v)\) — ключ-значение. Необходимо построить структуру хранения этих пар так, чтобы на ней были определены операции:
set(k, v)get(k)delete(k)Выделим массив для хранения пар размера \(N\), при этом допустимое множество ключей \(K\) такое, что \(|K| \gg N\). Определим функциональное отображение
с помощью которого будем определять позицию пары. Это отображение называется хеш-функцией.
В массиве хранятся указатели на списки, в которых может быть несколько элементов.
Преимущества: локальность данных.
Недостатки: удаление, рехеширование при переполнении.
где \(g(k)\) равномерно распределено.
Для избежания коллизии по попыткам \(h(k, i) = h(k, j)\) для \(i \neq j\), достаточно, чтобы \(g(k) \perp N\). Достаточно чтобы \(N\) было простым.
Пусть искомый ключ находится в конце цепочки длинны \(L\). Тогда сложность его нахождения равна:
Определим функцию коллизии следующим образом:
Перейдём к мат. ожиданию:
Тогда
Аналогично можно посчитать мат. ожидание сложности операции get
где \(\mathrm{get}_i\) — вставка \(i\)-го ключа, то есть
где \(H_i = \ln i + \gamma\) — гармоническая функция (\(\gamma\) — постоянная Эйлера).
| \(\alpha\) | Общий сл. | Лин. пробы |
|---|---|---|
| 0.1 | 1.05 | 1.06 |
| 0.25 | 1.15 | 1.17 |
| 0.5 | 1.39 | 1.5 |
| 0.75 | 1.85 | 2.5 |
| 0.9 | 2.56 | 5.5 |
| 0.95 | 3.15 | 10.5 |
| 0.99 | 4.66 | — |
\(h\colon K \to N\) — случайные величины.
Пусть \(\mathscr H = {h\colon K \to N}\) — некоторое семейство хеш-функций. И пусть существует равномерная вероятностная мера выбора \(h \in \mathscr H\).
Для сохранения оценок \(ET(\mathrm{get / set}) = O(1 + \alpha)\) необходимо, чтобы
То есть мы переносим рандомизацию с построения \(h(k)\) на выбор \(h \in \mathscr H\).
Без ограничения общности будем считать, что \(K \subset {0, \ldots, p - 1}\), где \(p\) — простое число. Тогда
То есть выбор \(h\) сводится к выбору \(a\) и \(b\).