146
правок
Изменения
Нет описания правки
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.
=== Первый уровень ===
Используется тот же принцип, что и в случае хеширования с цепочками: <tex>n</tex> ключей хешируются в <tex>m</tex> ячеек с использованием хеш-функции <tex>h(k) = ((a\cdot k+b) \bmod p) \bmod m</tex>, случайно выбранной из [[Универсальное_семейство_хеш-функций | семейства универсальных хеш-функций]] <tex>H_{p,m}</tex>, где <tex>p</tex> - — простое число, превышающее <tex>m</tex>.
=== Второй уровень ===
{{Теорема
|statement=
Если мы сохраняем <tex>n</tex> ключей в хеш-таблице в хеш-таблице размеров <tex>m=n</tex> c использованием хеш-функции <tex>h</tex>, выбираемой случайным образом из универсального множества хеш-функций, то <tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] < 2n</tex>, где <tex>n_j</tex> — количество ключей, хешированных в ячейку <tex>j</tex>.
|proof=
<tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] =</tex> <tex> E\left[ \displaystyle \sum_{j=0}^{m-1} (n_j + 2 \dbinom{n_j}{2})\right] = </tex> <tex> E\left[ \displaystyle \sum_{j=0}^{m-1} n_j\right] + 2E\left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}\right] = </tex> <tex> E\left[n\right] + 2E\left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}\right] = n + 2E\left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2} \right]</tex>
