Изменения
→Теоретическое обоснование
{{Определение|definition='''Идеальная хеш-функция''Двойное хеширование'(англ. '' {{perfect hash function'') — [[Хеш-таблица#Хеширование|хеш--}} метод борьбы с коллизиямифункция]], возникающими при которая без [[Открытое_и_закрытое_хеширование#Закрытое хешированиеРазрешение коллизий|закрытом хешированииколлизий]], основанный отображает различные элементы из множества объектов на использовании двух хеш-функций для построения различных последовательностей исследования хеш-таблицымножество ключей за <tex>O(1)</tex> времени в худшем случае.}}
==Принцип двойного хешированияОсновная идея ==При двойном хешировании используются две независимые хеш-функции <tex> h_1Идеальное хеширование используется в задачах со статическим множеством ключей (kт.е. после того, как все ключи сохранены в таблице, их множество никогда не изменяется) </tex> и <tex> h_2(k) </tex>для обеспечения хорошей асимптотики даже в худшем случае. Пусть <tex> k </tex> {{---}} это наш ключПри этом мы можем дополнительно хотеть, <tex> m </tex> {{---}} чтобы размер нашей таблицы, <tex>n \mod m </tex> {{---}} остаток зависел от деления <tex> n </tex> на <tex> m </tex>, тогда сначала исследуется ячейка с адресом <tex> h_1(k) </tex>, если она уже занята, то рассматривается <tex> (h_1(k) + h_2(k)) \mod m </tex>, затем <tex> (h_1(k) + 2 \cdot h_2(k)) \mod m </tex> и так далее. В общем случае идёт проверка последовательности ячеек <tex> (h_1(k) + i \cdot h_2(k)) \mod m </tex> где <tex> i = (0, 1, \; количества ключей линейно... \;, m - 1) </tex>
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.=== Первый уровень ===Используется тот же принцип, что и в случае хеширования с цепочками: <centertex>n</tex> ключей хешируются в <tex>m</tex> ячеек с использованием хеш-функции <tex>\forall x \neq y \; \exists h_1,h_2 : \Prh(h_1(xk)=h_1(y(a\cdot k+b))> \Pr((h_1(x)=h_1(y)bmod p)\cap(h_2(x)=h_2(y)))bmod m</tex>, случайно выбранной из [[Универсальное_семейство_хеш-функций | семейства универсальных хеш-функций]] <tex>H_{p,m}</tex>, где <tex>p</tex>— простое число, превышающее <tex>m</centertex>.
==Выбор хеш-функций= Второй уровень ===На данном уровне вместо создания списка ключей будем использовать вторичную хеш-таблицу <tex>S_j</tex>, хранящую все ключи, хешированные функцией <tex>h</tex> h_1 в ячейку <tex>j</tex> может быть обычной хеш-, со своей функцией. Однако чтобы последовательность исследования могла охватить всю таблицу<tex>h_j(k)=((a_j\cdot k + b_j) \bmod p) \bmod m_j</tex>, выбранной из множества <tex> h_2 H_{p,m_j}</tex> должна возвращать значения:*не равные . Путем точного выбора хеш-функции <tex> 0 h_j</tex>*независимые от мы можем гарантировать отсутствие коллизий на этом уровне. Для этого требуется, чтобы размер <tex> h_1 m_j</tex>*взаимно простые с величиной хеш-таблицы<tex>S_j</tex> был равен квадрату числа <tex>n_j</tex> ключей, хешированных функцией <tex>h</tex> в ячейку <tex>j</tex>.
{{Теорема|statement=Если <tex>n</tex> ключей сохраняются в хеш-таблице размером <tex>m=n^2</tex> c использованием хеш-функции <tex>h</tex>, случайно выбранной из [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], то [[Файл: Вставка при двойном хэшированииМатематическое_ожидание_случайной_величины | математическое ожидание]] числа коллизий не превышает <tex dpi="180">{1 \over 2}</tex>.|proof=Всего имеется <tex>\dbinom{n}{2}</tex> пар ключей, которые могут вызвать коллизию.svgЕсли хеш-функция выбрана случайным образом из [[Универсальное_семейство_хеш-функций | универсального семейства хеш-функций]] <tex>H</tex>, то для каждой пары вероятность возникновения коллизии равна <tex dpi="180">{1 \over m}</tex>.jpegПусть <tex>X</tex> — [[Дискретная_случайная_величина |thumbслучайная величина]], которая подсчитывает количество коллизий. Если <tex>m = n^2</tex>, то [[Математическое_ожидание_случайной_величины |rightматематическое ожидание]] числа коллизий равно<tex>E[X] = </tex> <tex dpi="180"> \binom{n}{2} \cdot {1 \over n^2} = {n^2-n \over 2} \cdot {1 \over n^2} < {1 \over 2}</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>
Очевидно, что <tex>\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}<center/tex>- просто общее количество коллизий, поэтому по свойству универсального хеширования математическое ожидание значения этой суммы не превышает<texdpi="180"> h(k,i) \binom{n}{2}{1 \over m} = {n(h_1(kn-1) + i \cdot h_2(k)) over 2m} = {n-1 \mod 13 over 2}</tex>А так как <tex>m = n</centertex>, то<tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] \leqslant </tex> <tex dpi="150"> n + 2 \cdot {n-1 \over 2} = 2n - 1 < 2n</tex>, ч.т.д.}}Теперь выведем 2 следствия из этой теоремы.
{{Теорема|statement=Если мы сохраняем <tex>n</tex> ключей в хеш-таблице размером <tex>m=n</tex> с использованием хеш-функции <tex>h</tex>, выбираемой случайным образом из [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], и устанавливаем размер каждой вторичной хеш-таблицы равным <tex>m_j=n_j^2<center/tex><tex> h_1(kj=0,1,...,m-1) </tex>, то математическое ожидание количества необходимой для вторичных хеш-таблиц в схеме идеального хеширования памяти не превышает <tex>2n</tex>.|proof=Поскольку <tex>m_j= k \mod 13 n_j^2</tex>для <tex>j=0,1,...,m-1</centertex>, согласно предыдущей теореме:
==См. также==
* [[Хеширование]]
* [[Хеширование_кукушки|Хеширование кукушки]]
* [[Поиск_свободного_места_при_закрытом_хешировании|Поиск свободного места при закрытом хешированииРазрешение коллизий]] == Литература ==* Бакнелл Дж. М. '''Фундаментальные алгоритмы и структуры данных в Delphi''', ''2003''* Кнут Д. Э. '''Искусство программирования, том 3. Сортировка и поиск''', ''2-е издание, 2000''* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''', ''2010''* Седжвик Р. '''Фундаментальные алгоритмы на C. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск''', ''2003''
==СсылкиИсточники информации==* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 11.5, стр. 308* Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 6.4, стр. 563* [http://en.wikipedia.org/wiki/Double_hashing Perfect_hash_function Wikipedia {{---}} Double_hashing— Perfect hash function]* [http://rainwww.ifmocs.rucmu.edu/catafs/view.phpcs/visacademic/hashtablesclass/hash15451-2001-2 Пример хеш таблицыs07/www/lecture_notes/lect0215.pdf Universal and Perfect Hashing]* [http://researchnord.csorg.vt.eduua/static/AVresearchcourse/hashingalgo_2009/doublelecture8.pdf Универсальное хэширование.php Пример хеш таблицы с двойным хешированиемИдеальное хэширование]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Хеширование]]