8. Хеширование

Хеш-таблица

Пусть мы хотим поддерживать множество $A$ элементов - ключей, то есть уметь добавлять ключ в $A$, удалять ключ из $A$, а также искать ключ в $A$. Мы будем считать, что все ключи берутся из множества $U=\{0,1, \ldots,|U|-1\}$.

✍️ В общем случае ключами могут быть какие угодно объекты, которым можно каким-либо образом сопоставить числа (например, строки).

Если $|U|$ не очень велико, можно просто создать массив размера $|U|$ и хранить каждый ключ в ячейке с номером, равным этому ключу. Чтобы понимать, каких ключей в $A$ нет, в соответствующих ячейках будем хранить специальное значение, не равное ни одному из ключей, например, -1 . Тогда все операции можно осуществлять за $O(1)$.

Недостаток этого подхода в том, что он он использует $|U|$ памяти, и поэтому работает, только если множество $U$ не слишком велико. Кроме того, если в любой момент времени $|A| \leqslant n$, и $n$ намного меньше $|U|$, то большая часть массива никак не будет использоваться, что непрактично.

Хеш-таблица позволяет решить ту же задачу, используя $\Theta(n)$ памяти, и осуществляя все операции в среднем за $O(1)$. Идея состоит в том, чтобы использовать массив размера $m$, где $m$ намного меньше $|U|$, и ключ $x$ хранить в ячейке с номером $h(x)$, пользуясь хеш-функцией $h: U \rightarrow M=\{0,1, \ldots, m-1\}$.

Может случиться так, что $x \neq y$, но $h(x)=h(y)$. Такую ситуацию мы будем называть коллизией. Хеш-функцию стараются выбрать так, чтобы минимизировать число коллизий. Тем не менее, поскольку $m<|U|$, всегда найдётся пара ключей из $U$ с одинаковым значением хеш-функции, то есть какой бы хорошей ни была хеш-функция, коллизии иногда будут происходить.

Метод цепочек

Самый простой способ разрешения коллизий - в каждой ячейке массива хранить “цепочку” - список всех ключей, попавших в эту ячейку. Этот список можно реализовывать как с помощью связного списка, так и с помощью динамического массива, или даже ещё одной внутренней хеш-таблицы (чуть позже мы увидим пример, когда именно такой способ оказывается полезен).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


vector<int> T[m] # хеш-таблица
find(x): # возвращает True, если x лежит в хеш-таблице
    p = h(x)
    for i = 0..(T[p].size() - 1):
            if T[p][i] == x:
            return True
    return False

insert(x):
    if not find(x):
        T[h(x)].push_back(x)

delete(x):
    p = h(x)
    for i = 0..(T[p].size() - 1):
        if T[p][i] == x:
            swap(T[p][i], T[p].back())
            T[p].pop_back()
            break

Все операции работают за время, пропорциональное длине списка в соответствующей ячейке, то есть за $O(|T[h(x)]|+1)$. Если ключи распределены по таблице равномерно, то есть в каждом списке оказалось примерно $\frac{n}{m}$ элементов, то операции будут работать в среднем за $O\left(\frac{n}{m}+1\right)$, то есть за $O(1)$ при $m=\Omega(n)$ (мы докажем подобное утверждение более формально, когда будем рассматривать технику универсального хеширования).

Как добиться равномерного распределения? Подобрать “хорошую” хеш-функцию. Иногда это можно сделать, пользуясь информацией о том, с какими ключами придётся работать.

Так, если известно, что ключи выбираются из множества $U$ случайно равновероятно, и $|U|$ делится на $m$, то подойдёт хеш-функция $h(x)=x \bmod m$ : каждый ключ попадёт в каждую ячейку таблицы с равной вероятностью.

На практике часто используют хеш-функцию $h(x)=x \bmod m$, даже если о ключах, с которыми придётся работать, ничего не известно. При этом $m$ обычно стараются выбирать простым.

Открытая адресация

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

Более формально, теперь мы будем работать с хеш-функцией от двух аргументов $h: U \times\{0, \ldots, m-1\} \rightarrow\{0, \ldots, m-1\}$, и при поиске $x$ перебирать ячейки в порядке $h(x, 0), h(x, 1), \ldots, h(x, m-1)$. При этом мы будем требовать, чтобы эта последовательность (будем называть её последовательностью проб) была перестановкой чисел от 0 до $m-1$ (чтобы не проверять одну ячейку несколько раз, и чтобы рано или поздно проверить каждую ячейку).

Последовательность проб чаще всего строят одним из следующих трёх способов (здесь $h^{\prime}, h_{1}, h_{2}: U \rightarrow\{0, \ldots, m-1\}$ - вспомогательные хеш-функции):

Линейное пробирование. $h(x, i)=\left(h^{\prime}(x)+c \cdot i\right) \bmod m$. Обычно используют $c=1$.
Квадратичное пробирование. $h(x, i)=\left(h^{\prime}(x)+c_{1} \cdot i+c_{2} \cdot i^{2}\right) \bmod m$.
Двойное хеширование. $h(x, i)=\left(h_{1}(x)+i \cdot h_{2}(x)\right) \bmod m$.

При этом $c$ в первом способе и $h_{2}(x)$ в третьем должны быть взаимно просты с $m$ (чтобы последовательность пробегала все ячейки). Во втором способе по тем же причинам тоже подойдут не все $c_{1}, c_{2}$.

Линейное пробирование самое простое и имеет наименьшую константу во времени работы, но страдает от кластеризации: блоки из лежащих в таблице подряд ключей со временем становятся всё больше и больше (потому что всё больше и больше становится вероятность попасть в такой блок).

Двойное хеширование отличается тем, что может дать $\Theta\left(m^{2}\right)$ различных последовательностей (в первых двух способах вся последовательность проб однозначно определяется по $h^{\prime}(x)$, поэтому всего возможно $\Theta(m)$ различных последовательностей), поэтому менее подвержено кластеризации. Квадратичное пробирование - некий компромисс между линейным пробированием и двойным хешированием.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


int T[m] # Хеш-таблица
# считаем, что ключи - неотрицательные целые числа,
# в пустых ячейках лежит -1
getIndex(x): # возвращает индекс ячейки, в которой лежит x,
            # или индекс первой встретившейся пустой ячейки
    for i = 0..(m-1):
        p = h(x, i)
        if T[p] == x or T[p] == -1:
            return p
    error "Hash table is full"
find(x): # возвращает True, если x лежит в хеш-таблице
    return T[getIndex(x)] == x
insert(x):
    p = getIndex(x)
    if T[p] != -1:
        return # x уже есть в таблице
    T[p] = x

Удалить ключ из хеш-таблицы теперь не так просто. Если просто пометить ячейку, где лежал ключ, как свободную, то поиск других ключей может перестать работать корректно (потому что при вставке другого ключа мы могли проходить через эту ячейку при поиске свободного места). Можно при удалении специальным образом помечать ячейку и пропускать её при дальнейшей работе с таблицей, но такую ячейку никогда нельзя будет переиспользовать.

1
2
3
4


delete(x):
    p = getIndex(x)
    if T[p] != -1:
        T[p] = -2 # getIndex всегда будет пропускать такую ячейку

$$ 1+\alpha(1+\alpha(1+\alpha(1+\cdots))) \leqslant \frac{1}{1-\alpha} $$

Мы эвристически оценили время работы операций в среднем как $O\left(\frac{1}{1-\alpha}\right)$. На практике хеш-таблицы с открытой адресацией действительно работают быстро, пока $\alpha$ достаточно далеко от единицы. Когда $\alpha$ приближается к единице (скажем, когда $\alpha>\frac{2}{3}$ ), можно построить новую таблицу вдвое большего размера, и перенести все элементы в неё (удалённые элементы при этом, конечно, переносить не надо).

Ассоциативный массив

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

В С++ есть встроенные реализации хеш-таблицы и ассоциативного массива - это std::unordered_set, std::unordered_map.

Отметим, что множество ключей хеш-таблицы (и реализации ассоциативного массива через хеш-таблицу) никак не упорядочено.

В С++ есть и реализации упорядоченного множества и ассоциативного массива с упорядоченными ключами - std::set, std::map. Эти структуры позволяют совершать больше различных операций (например, находить следующий по значению ключ). Однако они устроены сильно сложнее (мы поговорим об их устройстве позже), а операции работают медленнее: даже поиск ключа требует в худшем случае $\Theta(\log n)$ времени.

Сортировка Киркпатрика-Рейша

С помощью хеш-таблицы можно соптимизировать поразрядную сортировку, улучшив время работы до $O(n \log \log C)$ на массиве из $n$ целых чисел от 0 до $C-1$.

Алгоритм (Kirkpatrick, Reisch, 1984) выглядит следующим образом: пусть $C=2^{2^{k}}$ (если надо, округлим $C$ вверх до ближайшего числа такого вида, при этом $\log \log C$ увеличится не более, чем на один). Если $C \leqslant n$, просто отсортируем числа подсчётом за $O(n)$, иначе представим каждое число в $\sqrt{C}$-ичной системе счисления; при этом каждое число будет состоять из двух $2^{k-1}$-битных цифр ( $\sqrt{C}=2^{2^{k-1}}$ ). Осталось отсортировать числа по старшей цифре, а при равенстве по младшей рекурсивными вызовами.

Хеш-таблицы (точнее, ассоциативные массивы) нужны, чтобы сгруппировать числа в блоки с равной старшей цифрой.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


sort(vector<int> a, int k):
    n = a.size()
    if n >= 2 ** (2 ** k):
        countingSort(a)
        return
    vector<int> l # сюда запишем все встретившиеся старшие цифры
    unordered_map<int, vector<int> > t
    # ассоциативный массив: в t[x] будем хранить список всех таких у,
    # что a[i] = x * 2 ** (2 ** (k - 1)) + y для некоторого i
    for i = 0..(n - 1):
        x = a[i] / (2 ** (2 ** (k - 1))) # x - старшие 2 ** (k - 1) 6ит a[i]
        y = a[i] % (2 ** (2 ** (k - 1))) # y - младшиие 2 ** (k - 1) бит а[i]
        if t.find(x) == t.end(): # x встретилось впервые
            l.push_back(x)
        t[x].push_back(y)
    sort(l, k - 1) # отсортировали старшие цифры
    a.clear()
    for (x in l): # перебираем старшие цифры в порядке возрастания
        r = t[x]
        i = maxElementIndex(r) # найдём индекс максимального элемента в r
        rmax = r[i]
        swap(r[i], r.back())
        r.pop_back()
        sort(r, k - 1) # отсортировали все младшие цифры, кроме максимальной
        for (y in r):
            a.push_back(x * 2 ** (2 ** (k - 1)) + y)
        a.push_back(x * 2 ** (2 ** (k - 1)) + rmax)

Получаем рекуррентное соотношение

$$ T(n)=\Theta(n)+T(|l|)+\sum_{x \in l} T(|t[x]|-1) $$

Заметим, что

$$ |l|+\sum_{x \in l}(|t[x]|-1)=|l|-|l|+\sum_{x \in l}|t[x]|=n, $$

то есть на каждом уровне рекурсии суммарный размер подзадач равен $n$. При этом глубина рекурсии не превышает $k$, значит суммарно на всех уровнях совершено $O(k n)=$ $O(n \log \log C)$ действий. Отметим, что это оценка времени работы в среднем, поскольку мы используем хеш-таблицы.

На практике из-за большой константы во времени работы хеш-таблиц алгоритм как правило оказывается не быстрее обычных алгоритмов сортировки.

✍️ На похожей идее основано дерево ван Эмде Боаса (van Emde Boas, 1975), позволяющее делать те же операции, что и двоичная куча, на целых числах от 0 до $C-1$ в среднем за $O(\log \log C)$. На практике оно практически не используется по тем же причинам

Универсальное хеширование

Можно ли раз и навсегда выбрать для хеш-таблицы фиксированную хеш-функцию $h: U \rightarrow M$, которая будет хорошо работать на любых входных данных? Нет: поскольку $|U|>|M|$, всегда найдутся $\lceil|U| /|M|\rceil$ ключей с одинаковым значением хеш-функции (причём отношение $|U| /|M|$, как правило, достаточно велико). Тогда, если в запросах будет встречаться много таких ключей (например, если злоумышленник, знающий хеш-функцию, будет специально посылать такие запросы), эти запросы будут обрабатываться долго.

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

Определение

Семейство $\mathcal{H}$ хеш-функций, действующих из множества $U$ во множество $M=\{0,1, \ldots, m-1\}$, называется универсальным, если для любой пары различных ключей $k, l \in U$ количество таких хеш-функций $h \in \mathcal{H}$, что $h(k)=h(l)$, не превосходит $\frac{|\mathcal{H}|}{m}$.

Теорема Универсальное хеширование

Пусть хеш-функция $h \in \mathcal{H}, h: U \rightarrow\{0,1, \ldots, m-1\}$ была случайно выбрана из универсального семейства $\mathcal{H}$, и использована при работе хеш-таблицы размера $m$. Пусть в хеш-таблицу уже были добавлены $n$ ключей $l_{1}, \ldots, l_{n}$, коллизии разрешались методом цепочек. Тогда для любого ключа $k \in U$ математическое ожидание длины списка в ячейке с индексом $h(k)$ не превосходит $1+\frac{n}{m}$.

Доказательство

Для каждой пары ключей $a, b \in U$ введём величину $\chi(h, a, b)$, равную единице, если $h(a)=h(b)$, и нулю иначе. $\chi(h, a, a)=1$ для любой $h$. При этом для $a \neq b$ математическое ожидание $\chi(h, a, b)$ не превосходит $\frac{1}{m}$ по определению универсального семейства:

$$ \mathbb{E}(\chi(h, a, b))=\frac{1}{|\mathcal{H}|} \sum_{h \in \mathcal{H}} \chi(h, a, b) \leqslant \frac{1}{|\mathcal{H}|} \cdot \frac{|\mathcal{H}|}{m}=\frac{1}{m} $$

Обозначим $L=\left\{l_{1}, \ldots, l_{n}\right\}$. Математическое ожидание длины списка в ячейке с индексом $h(k)$ равняется

$$ \mathbb{E}\left(\sum_{l \in L} \chi(h, k, l)\right)=\sum_{l \in L} \mathbb{E}(\chi(h, k, l)) \leqslant 1+\sum_{l \in L \backslash\{k\}} \mathbb{E}(\chi(h, k, l)) \leqslant 1+\frac{n}{m} $$

Следствие

Пусть хеш-таблица размера $m$ использует технику универсального хеширования и метод цепочек для разрешения коллизий. Математическое ожидание суммарного времени работы $k$ операций $\operatorname{insert}$, $\operatorname{find}$, $\operatorname{delete}$, среди которых $O(m)$ операций $\operatorname{insert}$, есть $\Theta(k)$.

Доказательство

В любой момент времени в таблице лежат не более $O(m)$ элементов. Время работы любой операции не превосходит времени вычисления хеш-функции (которое мы считаем константным) и времени прохода по списку в ячейке с индексом, равным значению хеш-функции. По предыдущей теореме, математическое ожидание времени выполнения каждой операции не превосходит $O\left(1+\frac{O(m)}{m}\right)=O(1)$. Тогда математическое ожидание суммарного времени работы всех операций не превосходит $O(k)$, то есть равняется $\Theta(k)$.

Ещё раз отметим, что теорема и следствие выполняются для любых последовательностей запросов; математическое ожидание берётся не по входным данным, а по случайному выбору хеш-функции.

Построение универсального семейства хеш-функций

Построим универсальное семейство хеш-функций для чисел, влезающих в машинное слово (считаем, что арифметические операции над числами выполняются за $O(1)$ ).

Теорема

Пусть $p$ - такое простое, что $U \subset\{0,1, \ldots, p-1\}$; пусть $m < p$. Для любых целых $1 \leqslant a < p, 0 \leqslant b < p$ определим хеш-функцию

$$ h_{a, b}(k)=((a k+b) \bmod p) \bmod m $$

Тогда семейство хеш-функций

$$ \mathcal{H}_{p, m}=\left\{h_{a, b}: 1 \leqslant a < p, 0 \leqslant b < p\right\} $$

является универсальным.

Доказательство

Пусть $k \neq l$ - два различных ключа. Поймём, для каких $a, b$ верно $h_{a, b}(k)=h_{a, b}(l)$.

Заметим сначала, что если $r=(a k+b) \bmod p, s=(a l+b) \bmod p$, то $r \neq s$, так как $r-s \equiv a(k-l) \not \equiv 0(\bmod p)$.

Более того, разным парам $(a, b)$ соответствуют разные пары $(r, s)$, так как по $(r, s)$ можно восстановить $(a, b): a \equiv(r-s)(k-l)^{-1}(\bmod p), b \equiv(r-a k)(\bmod p)$.

Различных пар $(a, b)$ с $1 \leqslant a < p, 0 \leqslant b < p$ всего $(p-1) \cdot p$. Различных пар $(r, s)$ с $0 \leqslant r \neq s < p$ всего $p^{2}-p$, то есть столько же. Значит, мы установили взаимно однозначное соответствие между множествами пар ( $a, b$ ) и пар $(r, s)$.

Остаётся заметить, что $h_{a, b}(k)=h_{a, b}(l)$ тогда и только тогда, когда $r \equiv s(\bmod m)$. Для фиксированного $0 \leqslant r < p$ количество $0 \leqslant s < p$ таких, что $s \neq r$, но $r \equiv s(\bmod m)$, не превосходит $\left\lceil\frac{p}{m}\right\rceil-1 \leqslant \frac{p+m-1}{m}-1=\frac{p-1}{m}$.

Тогда количество хеш-функций $h_{a, b} \in \mathcal{H}_{p, m}$, для которых $h_{a, b}(k)=h_{a, b}(l)$ равняется количеству пар $(r, s)$ таких, что $0 \leqslant r \neq s < p, r \equiv s(\bmod m)$, которое не превосходит $p \cdot \frac{p-1}{m}=\frac{\left|\mathcal{H}_{p, m}\right|}{m}$.

Совершенное хеширование

Если множество используемых ключей известно заранее (например, в языках программирования множество зарезервированных слов фиксировано), то можно построить хеш-таблицу, операции в которой будут работать за $O(1)$ в худшем случае. При этом можно добиться того, чтобы хеш-таблица имела размер $O(n)$, где $n$ - число используемых ключей.

Снова считаем, что все ключи - целые неотрицательные числа, меньшие некоторого простого $p$. Построим хеш-таблицу с $m=n$ ячейками, при этом хеш-функцию аккуратно выберем из универсального семейства $\mathcal{H}_{p, m}$. В каждой ячейке этой таблицы вместо списка мы заведём хеш-таблицу второго уровня, причём, если в ячейку с индексом $j$ попало $n_{j}$ ключей, то внутреннюю хеш-таблицу в этой ячейке сделаем размера $m_{j}=n_{j}^{2}$. Хешфункцию для внутренней таблицы мы аккуратно выберем из универсального семейства $\mathcal{H}_{p, m_{j}}$.

Оказывается, можно подобрать такие хеш-функции, что во внутренних таблицах не будет коллизий, а суммарный размер всех таблиц будет оцениваться как $O(n)$.

В доказательстве оценок мы будем пользоваться следующим фактом (под $\mathbb{P}(A)$ имеется в виду вероятность того, что произошло событие $A$ ):

Неравенство Маркова

Пусть $X$ - неотрицательная случайная величина с конечным математическим ожиданием. Тогда для любого $a>0$ верно

$$ \mathbb{P}(X \geqslant a) \leqslant \frac{\mathbb{E} X}{a} $$

Доказательство

Поскольку $X$ неотрицательно, $\mathbb{E} X \geqslant 0 \cdot \mathbb{P}(X < a)+a \cdot \mathbb{P}(X \geqslant a)$, откуда следует требуемое неравенство.

Теорема

Пусть в хеш-таблице размера $m=n^{2}$ хранятся $n$ ключей, причём хешфункция $h(\cdot)$ была случайно выбрана из $\mathcal{H}_{p, m}$. Тогда с вероятностью более чем $\frac{1}{2}$ коллизий нет (все ключи хранятся в разных ячейках).

Доказательство

Для каждой пары различных ключей введём величину $\chi(h, a, b)$, равную единице, если $h(a)=h(b)$, и нулю иначе. Как и в теореме Универсального хеширования 8.6.1, $\mathbb{E}(\chi(h, a, b)) \leqslant \frac{1}{m}=\frac{1}{n^{2}}$. Рассмотрим случайную величину $X$ - количество коллизий. Тогда

$$ \mathbb{E} X=\mathbb{E}\left(\sum_{a \neq b}(\chi(h, a, b))\right)=\sum_{a \neq b} \mathbb{E}(\chi(h, a, b)) \leqslant \frac{n(n-1)}{2} \cdot \frac{1}{n^{2}}<\frac{1}{2} $$

Поскольку $X$ принимает только целые неотрицательные значения, по неравенству Маркова

$$ \mathbb{P}(X>0)=\mathbb{P}(X \geqslant 1) \leqslant \mathbb{E} X<\frac{1}{2} $$

Из этой теоремы сразу же следует, что если мы можем позволить себе использовать хеш-таблицу размера $n^{2}$, то, сделав несколько попыток, мы подберём такую хеш-функцию, что все ключи попадут в разные ячейки таблицы (вероятность того, что мы не найдём такую хеш-функцию за $s$ попыток, меньше $2^{-s}$; в среднем понадобится не более двух попыток). Наша двухуровневая схема нужна, чтобы уменьшить количество используемой памяти до $O(n)$.

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

Теорема

Пусть в хеш-таблице размера $m=n$ хранятся $n$ ключей, причём хешфункция $h(\cdot)$ была случайно выбрана из $\mathcal{H}_{p, m}$. Пусть в $j$-ю ячейку попало $n_{j}$ ключей, которые были помещены во внутреннюю хеш-таблицу размера $m_{j}=n_{j}^{2}$. Тогда математическое ожидание суммарного размера внутренних хеш-таблиц меньше $2 n$.

Доказательство

Заметим сначала, что

$$ \begin{aligned} & \mathbb{E}\left(\sum_{j=0}^{m-1} m_{j}\right)=\mathbb{E}\left(\sum_{j=0}^{m-1} n_{j}^{2}\right)=\mathbb{E}\left(\sum_{j=0}^{m-1}\left(n_{j}+2 \cdot \frac{n_{j}\left(n_{j}-1\right)}{2}\right)\right)= \\ = & \mathbb{E}\left(\sum_{j=0}^{m-1} n_{j}\right)+2 \cdot \mathbb{E}\left(\sum_{j=0}^{m-1} \frac{n_{j}\left(n_{j}-1\right)}{2}\right)=n+2 \cdot \mathbb{E}\left(\sum_{j=0}^{m-1} \frac{n_{j}\left(n_{j}-1\right)}{2}\right) . \end{aligned} $$

Теперь заметим, что $\sum_{j=0}^{m-1} \frac{n_{j}\left(n_{j}-1\right)}{2}$ - это суммарное количество случившихся коллизий. Из доказательства предыдущей теоремы мы знаем, что математическое ожидание количества коллизий не превосходит $\frac{n(n-1)}{2} \cdot \frac{1}{m}=\frac{n-1}{2}$, так как $m=n$. Получаем

$$ \mathbb{E}\left(\sum_{j=0}^{m-1} m_{j}\right) \leqslant n+2 \cdot \frac{n-1}{2}=2 n-1<2 n . $$

Следствие

В предположениях теоремы суммарный размер внутренних хеш-таблиц окажется больше или равен $4 n$ с вероятностью меньше $\frac{1}{2}$.

Доказательство

Воспользуемся неравенством Маркова:

$$ \mathbb{P}\left(\sum_{j=0}^{m-1} m_{j} \geqslant 4 n\right) \leqslant \frac{\mathbb{E}\left(\sum_{j=0}^{m-1} m_{j}\right)}{4 n}<\frac{2 n}{4 n}=\frac{1}{2} $$

Снова получаем, что за $s$ попыток с вероятностью хотя бы $1-2^{-s}$ (и не больше чем за две попытки в среднем) мы подберём такую хеш-функцию для внешней хеш-таблицы, что суммарный размер всех внутренних хеш-таблиц будет оцениваться как $O(n)$ (будет меньше $4 n$ ).