Коллизии. Метод цепочек

Алла: А часто вообще коллизии возникают на практике?
Тимофей: Чтобы ответить на этот вопрос, рассмотрим пример. Вы слышали про парадокс дней рождений?
Алла: Нет, расскажи, пожалуйста.
Сколько нужно взять человек, чтобы вероятность совпадения дней рождений хотя бы двух превышала 50%?
Вычислим вероятность, что все дни рождения будут в разные даты. Для этого посчитаем произведение вероятностей того, что день рождение каждого человека не совпадёт ни с чьим другим.
Для первого человека такая вероятность будет равна 1. Для второго человека — 1−13651 - \frac{1}{365}, так как один день уже занят. Для второго занято будет уже 2 дня. И так далее.
p~(n)=1⋅(1−1365)⋅(1−2365)⋯(1−n−1365)=365⋅364⋯(365−n+1)365n=365!365n(365−n)!\displaystyle \tilde{p}(n)=1 \cdot\left(1-\frac{1}{365}\right) \cdot\left(1-\frac{2}{365}\right) \cdots\left(1-\frac{n-1}{365}\right)=\frac{365 \cdot 364 \cdots(365-n+1)}{365^{n}}=\frac{365 !}{365^{n}(365-n) !} .
Нас интересует событие, обратное этому.
p(n)=1−p~(n).p(n) = 1 - \tilde{p}(n).
Посмотрим на график зависимости вероятности минимум двух совпадений от количества людей:
image
Если взять 23 человека, вероятность будет 50%.
Значит, что если взять таблицу, в которой 365 значений, и расположить в ней 23 ключа, то уже в этом случае вероятность коллизии будет 50%.
Построить хеш-таблицу, в которой никогда не будет коллизий, — сложно, поэтому нужно уметь бороться с ними.
image
Коллизия — это ситуация, когда для разных данных функция возвращает одно и то же значение.
Гоша: А что же делать в таком случае?
Тимофей: Существуют разные способы решения этой проблемы. Например, метод цепочек.
Вам хорошо знакома такая структура данных как связный список. Её используют в методе цепочек при разрешении коллизий.
image
Допустим, нужно добавить ключ:
  1. Вычисляем значение хеш-функции xx от добавляемого ключа.
  2. Находим H[x]H[x] — указатель на список ключей.
  3. Вставляем элемент в связный список.
Куда бы вы добавили элемент в хеш-таблицу в связном списке?
При удалении ключа нужно:
  1. Вычислить значение хеш-функции xx от ключа.
  2. Найти H[x]H[x] — указатель на список ключей.
  3. Выполнить поиск ключа в связном списке и удалить его.
Какая сложность операции удаления в лучшем случае?
Какая сложность операции удаления в худшем случае?
Гоша: А какое среднее время работы всех операций?
Тимофей: Среднее время работы операции удаления, поиска и вставки в хеш-таблицу, реализованную с использованием метода цепочек, равно O(1+a)O(1+a), где aa — коэффициент заполненности таблицы (англ. fill factor).
a=NMa =\displaystyle \frac{N}{M}, где NN — количество элементов в таблице, а MM — размер таблицы.
Гоша: А почему именно O(1+a)O(1+a)?
Тимофей: Найдём ожидаемое время работы в зависимости от исходного ключа.
Время обработки T(k)T(k) ключа kk зависит от длины цепочки и равно O(1+Ni(k))O(1 + N_i(k)), где NiN_i — длина i-й цепочки. Единица затратится на вычисление значения хеш-функции, Ni(k)N_i(k) — на поиск элемента в цепочке. Предполагаем, что хеш-функция равномерная, то есть все значения равновероятны. Тогда:
Tcp(M,N)=E(T(k)),T_{cp}(M,N) = E(T(k)),
где EE — математическое ожидание времени работы в зависимости от ключа kk.
В каждую ячейку попадём с вероятностью 1M\displaystyle \frac {1}{M}.
E(T(k))=∑i=0M−11M(1+Ni)\displaystyle E(T(k))=\sum_{i=0}^{M-1} \frac{1}{M}\left(1+N_{i}\right).
Если попадаем в ячейку ii, то время работы 1+Ni1+N_{i} — именно столько потребуется, чтобы пройти всю цепочку.
E(T(k))=∑i=0M−11M(1+Ni)=1M∑i=0M−1(1+Ni)\displaystyle E(T(k))=\sum_{i=0}^{M-1} \frac{1}{M}\left(1+N_{i}\right)=\frac{1}{M} \sum_{i=0}^{M-1}\left(1+N_{i}\right).
Единица суммируется MM раз, суммарная длина всех цепочек равна NN.
1M∑i=0M−1(1+Ni)=1M⋅(M+N)=M+NM=1+NM=1+α\displaystyle \frac{1}{M} \sum_{i=0}^{M-1}\left(1+N_{i}\right)=\frac{1}{M} \cdot (M+N) = \frac{M+N}{M}= 1+\frac{N}{M} = 1+\alpha.
Среднее время можно регулировать. В зависимости от объёма данных, которые предполагается хранить в хеш-таблице, можно выбирать размер таблицы так, чтобы значение a не превышало определённый порог.
Допустим, планируется хранить около 1000 элементов в таблице. Нужно, чтобы Tcp(N,M)T_{cp}(N,M) не превышало 3. Какой выберете размер хеш-таблицы?