Изменения

{{Определение|definition='''Идеальная хеш-функция'''Двойное хеширование (double hashing)англ. ''perfect hash function'' ) — [[Хеш- один из методов закрытого хеширования. Перебор ячеек таблица#Хеширование|хеш-таблицыфункция]], возникающий при двойном хешировании, обладает свойствами, присущими равномерному хешированию. При двойном хешировании хеш-функция которая без [[Разрешение коллизий|коллизий]] отображает различные элементы из множества объектов на множество ключей за <tex> h O(1)</tex> имеет следующий вид:времени в худшем случае.}}

<center>== Основная идея ==<tex> hИдеальное хеширование используется в задачах со статическим множеством ключей (kт.е. после того,iкак все ключи сохранены в таблице, их множество никогда не изменяется) = (h_1(k) + i\cdot h_2(k)) \; mod \; m </tex></center>для обеспечения хорошей асимптотики даже в худшем случае. При этом мы можем дополнительно хотеть, чтобы размер таблицы зависел от количества ключей линейно.

[[Файл: Вставка при двойном хэшированииВ таком хешировании для доступа к данным потребуется лишь вычисление хеш-функций (одной или нескольких), что делает данный подход наибыстрейшим для доступа к статическим данным.svgДанная технология применяется в различных словарях и базах данных, в алгоритмах со статической (известной заранее) информацией.jpeg|thumb|right|Вставка при двойном хешировании]]

где Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.=== Первый уровень ===Используется тот же принцип, что и в случае хеширования с цепочками: <tex> h_1 n</tex> и ключей хешируются в <tex> h_2 m</tex> - вспомогательные ячеек с использованием хеш-функции, <tex> h(k) = ((a\cdot k+b) \bmod p) \bmod m </tex> , случайно выбранной из [[Универсальное_семейство_хеш- размер функций | семейства универсальных хеш-таблицы. Иными словами, последовательность индексов исследуемых ячеек при работе с ключом <tex> k </tex> представляет собой арифметическую прогрессию (по модулю функций]] <tex> H_{p,m }</tex>) с первым членом , где <tex> h_1(k) p</tex> и шагом — простое число, превышающее <tex> h_2(k) m</tex>. Следовательно, в данном случае последовательность исследования зависит от ключа k по двум параметрам - выбор начальной исследуемой ячейки и расстояние между двумя исследуемыми ячейками, так как оба параметра зависят от значения ключа.

Пример вставки элемента при двойном хешировании приведен === Второй уровень ===На данном уровне вместо создания списка ключей будем использовать вторичную хеш-таблицу <tex>S_j</tex>, хранящую все ключи, хешированные функцией <tex>h</tex> в ячейку <tex>j</tex>, со своей функцией <tex>h_j(k)=((a_j\cdot k + b_j) \bmod p) \bmod m_j</tex>, выбранной из множества <tex>H_{p,m_j}</tex>. Путем точного выбора хеш-функции <tex>h_j</tex> мы можем гарантировать отсутствие коллизий на рисунке справаэтом уровне. Для этого требуется, чтобы размер <tex>m_j</tex> хеш-таблицы <tex>S_j</tex> был равен квадрату числа <tex>n_j</tex> ключей, хешированных функцией <tex>h</tex> в ячейку <tex>j</tex>.

Показана Несмотря на квадратичную зависимость, ниже будет показано, что при корректном выборе хеш-таблица размером 13 ячеек, в которой используются вспомогательные функции:первого уровня количество требуемой для хеш-таблицы памяти будет <tex>O(n)</tex>.

<center><tex> h_1(k) = k \; mod \; 13 </tex></center>= Теоретическое обоснование ==

{{Теорема|statement=Если <tex>n</tex> ключей сохраняются в хеш-таблице размером <tex>m=n^2</tex> c использованием хеш-функции <tex>h<center/tex>, случайно выбранной из [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], то [[Математическое_ожидание_случайной_величины | математическое ожидание]] числа коллизий не превышает <tex dpi="180">{1 \over 2}</tex>.|proof=Всего имеется <tex> h_2(k) \dbinom{n}{2}</tex> пар ключей, которые могут вызвать коллизию. Если хеш-функция выбрана случайным образом из [[Универсальное_семейство_хеш-функций | универсального семейства хеш-функций]] <tex>H</tex>, то для каждой пары вероятность возникновения коллизии равна <tex dpi= "180">{1 + k \; mod \; 11 over m}</tex>. Пусть <tex>X</tex> — [[Дискретная_случайная_величина |случайная величина]], которая подсчитывает количество коллизий. Если <tex>m = n^2</tex>, то [[Математическое_ожидание_случайной_величины | математическое ожидание]] числа коллизий равно<tex>E[X] = </centertex> <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>}}Это является очень хорошим результатом, если хотя бы вспомнить на примере [[Хеш-таблица#Введение | парадокса дней рождения]] о том, что вероятность коллизий растет крайне быстро по сравнению с размером хеш-таблицы.

Мы хотим вставить ключ 14. Изначально {{Теорема|statement=Если мы сохраняем <tex>n</tex> ключей в хеш-таблице размеров <tex> i m= 0 n</tex>. Тогда c использованием хеш-функции <tex> h(14</tex>, выбираемой случайным образом из универсального множества хеш-функций,0) = (h_1(14) + 0то <tex>E\cdot h_2(14)) left[\; mod displaystyle \; 13 sum_{j= 0}^{m-1 } n_j^2 \right] < 2n</tex>. Но ячейка с индексом 1 занята, поэтому увеличиваем где <tex> i n_j</tex> на 1 и пересчитываем значение хеш-функции. Делаем так— количество ключей, пока не дойдем до пустой ячейкихешированных в ячейку <tex>j</tex>. При |proof=<tex> i E\left[\displaystyle \sum_{j= 0}^{m-1} n_j^2 \right] =</tex> получаем <tex> hE\left[ \displaystyle \sum_{j=0}^{m-1} (14,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] = (h_1(14) </tex> <tex> E\left[n\right] + 2E\left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}\cdot h_2(14)) right] = n + 2E\left[\; mod displaystyle \; 13 sum_{j= 9 0}^{m-1} \dbinom{n_j}{2} \right]</tex>. Ячейка с номером 9 свободна, значит записываем туда наш ключ.

Для того, чтобы последовательность исследования могла охватить всю таблицу, значение Первый переход в равенстве мы совершили благодаря формуле <tex> h_2 a^2 = a + 2\cdot\dbinom{a}{2}</tex> должно быть взаимно простым с размером таблицы. Есть два удобных способа это сделать. Первый состоит в томДалее мы воспользовались свойствами [[Математическое_ожидание_случайной_величины | математического ожидания]], что в качестве размера таблицы используется простое число, а <tex> h_2 </tex> возвращает натуральные числа, меньшие <tex> m </tex>. Второй частности - размер таблицы является степенью двойки, а <tex> h_2 </tex> возвращает нечетные значениялинейности.

Таким образом, основная особенность двойного хеширования состоит в томОчевидно, что при различных <tex> k \displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}</tex> пара - просто общее количество коллизий, поэтому по свойству универсального хеширования математическое ожидание значения этой суммы не превышает<texdpi="180"> \binom{n}{2}{1 \over m} = {n(h_1(kn-1)\over 2m} = {n-1 \over 2}</tex>А так как <tex>m = n</tex>,h_2(k)) то<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</tex> <pretex>insert(item){ x j= h1(item0,1,..key) y = h2(item.key,m-1) for (i = 0; i < m; i++){ /tex>, то математическое ожидание количества необходимой для вторичных хеш-таблиц в схеме идеального хеширования памяти не превышает <tex>2n</tex>. if (table[x] |proof== null){ table[x] Поскольку <tex>m_j= item return } x n_j^2</tex> для <tex>j= (x + y) % 0,1,...,m } error() //ошибка, требуется увеличить размер таблицы}-1</pretex>, согласно предыдущей теореме:

===Поиск===<pretex>search(key)E\left[\displaystyle \sum_{ x = h1(key) y = h2(key) for (i j= 0; i < }^{m; i++){ if (table[x-1} m_j \right] != null) if (tableE\left[x].key \displaystyle \sum_{j== key) return table[x] else return null x = (x + y) % 0}^{m } return null-1}n_j^2 \right] < 2n</pretex>, ч.т.д.

==Реализация с удалением=====Вставка===<pre>insert(item){ x = h1(item.key) y = h2(item.key) for (i = 0; i < m; i++){ if (table[x] == null || deleted[x]){ table[x] = item deleted[x] = false return } x = (x + y) % m } error() //ошибка, требуется увеличить размер таблицы}</pre>

===Поиск=={{Теорема|statement=Если мы сохраняем <tex>n<pre/tex>search(key){ x ключей в хеш-таблице размером <tex>m= h1(key) y n</tex> с использованием хеш-функции <tex>h</tex>, выбираемой случайным образом из [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], и устанавливаем размер каждой вторичной хеш-таблицы равным <tex>m_j= h2n_j^2</tex> <tex>(key) for (i j= 0; i < ,1,...,m; i++-1)</tex>, то вероятность того, что общее количество необходимой для вторичных хеш-таблиц памяти не менее <tex>4n</tex>, меньше чем <tex dpi="180">{ 1 \over 2}</tex>. if (table[x] !|proof= null) if (tableПрименим [[xНеравенство Маркова| неравенство Маркова].key == key && !deleted[x]<tex>P(X \geqslant t) return table\leqslant E[xX] else return null x = (x + y) % m } return null}/t</pretex>

Пусть <tex>X=\displaystyle \sum_{j=0}^{m-1} m_j</tex> и <tex>t=Удаление===4n</tex>. Тогда <pretex>remove(key)P \left \{ x = h1(key) y = h2(key) for (i \displaystyle \sum_{j= 0; i < }^{m; i++)-1} m_j \geqslant 4n \right \} \leqslant E\left[\displaystyle\sum_{ if (table[x] !j= null) if (table[x0}^{m-1} mj\right].key </tex> <tex dpi="150"> {1 \over 4n} < </tex> <tex dpi= key) deleted[x] "150">{2n \over 4n} = true else return x = (x + y) % m }{1 \over 2}</pretex>, ч.т.д.}}

* [[Поиск_свободного_места_при_закрытом_хешировании|Поиск свободного места при закрытом хешированииРазрешение коллизий]] == Литература ==* Бакнелл Дж. М. '''Фундаментальные алгоритмы и структуры данных в Delphi''', ''2003''* Кнут Д. Э. '''Искусство программирования, том 3. Сортировка и поиск''', ''2-е издание, 2000''* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''', ''2010''* Седжвик Р. '''Фундаментальные алгоритмы на C. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск''', ''2003''

==СсылкиИсточники информации==* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 11.5, стр. 308* Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 6.4, стр. 563* [http://en.wikipedia.org/wiki/Double_hashing Double_hashingPerfect_hash_function Wikipedia — 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 Пример хеш таблицы с двойным хешированиемИдеальное хэширование]