Изменения

Перейти к: навигация, поиск

Идеальное хеширование

2938 байт добавлено, 14:59, 8 июня 2019
Теоретическое обоснование
{{Определение|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> \mod m </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>
==Выбор В таком хешировании для доступа к данным потребуется лишь вычисление хеш-функций==<tex> h_1 </tex> может быть обычной хеш-функцией(одной или нескольких), что делает данный подход наибыстрейшим для доступа к статическим данным. Однако чтобы последовательность исследования могла охватить всю таблицуДанная технология применяется в различных словарях и базах данных, <tex> h_2 </tex> должна возвращать значения:*не равные <tex> 0 </tex>*независимые от <tex> h_1 </tex>*взаимно простые с величиной хеш-таблицыв алгоритмах со статической (известной заранее) информацией.
Есть два удобных способа это сделатьБудем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне. === Первый состоит в томуровень ===Используется тот же принцип, что и в качестве размера таблицы используется простое число, а случае хеширования с цепочками: <tex> h_2 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> h_2 m</tex> возвращает нечетные значения.
Например=== Второй уровень ===На данном уровне вместо создания списка ключей будем использовать вторичную хеш-таблицу <tex>S_j</tex>, хранящую все ключи, если размер таблицы равен хешированные функцией <tex> m h</tex>, то в качестве ячейку <tex> h_2 j</tex> можно использовать функцию вида , со своей функцией <tex> h_2h_j(k) = ((a_j\cdot k + b_j) \mod (mbmod p) \bmod m_j</tex>, выбранной из множества <tex>H_{p,m_j}</tex>. Путем точного выбора хеш-функции <tex>h_j</tex> мы можем гарантировать отсутствие коллизий на этом уровне. Для этого требуется, чтобы размер <tex>m_j</tex> хеш-1) + 1 таблицы <tex>S_j</tex> был равен квадрату числа <tex>n_j</tex> ключей, хешированных функцией <tex>h</tex> в ячейку <tex>j</tex>.
[[Файл: Вставка Несмотря на квадратичную зависимость, ниже будет показано, что при двойном хэшированиикорректном выборе хеш-функции первого уровня количество требуемой для хеш-таблицы памяти будет <tex>O(n)</tex>.svg.jpeg|thumb|right|Вставка при двойном хешировании]]
==ПримерТеоретическое обоснование ==
Показана {{Теорема|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> пар ключей, которые могут вызвать коллизию. Если хеш-функция выбрана случайным образом из [[Универсальное_семейство_хеш-функций | универсального семейства хеш-функций]] <tex>H</tex>, то для каждой пары вероятность возникновения коллизии равна <tex dpi="180">{1 \over m}</tex>. Пусть <tex>X</tex> — [[Дискретная_случайная_величина |случайная величина]], которая подсчитывает количество коллизий. Если <tex>m = n^2</tex>, то [[Математическое_ожидание_случайной_величины | математическое ожидание]] числа коллизий равно<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>}}Это является очень хорошим результатом, если хотя бы вспомнить на примере [[Хеш-таблица #Введение | парадокса дней рождения]] о том, что вероятность коллизий растет крайне быстро по сравнению с размером 13 ячеек, в которой используются вспомогательные функции:хеш-таблицы.
{{Теорема|statement=Если мы сохраняем <tex>n</tex> ключей в хеш-таблице размеров <tex>m=n<center/tex>c использованием хеш-функции <tex> h(k</tex>, выбираемой случайным образом из универсального множества хеш-функций, то <tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] < 2n</tex>, где <tex>n_j</tex> — количество ключей,i) хешированных в ячейку <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} (h_1(kn_j + 2 \dbinom{n_j}{2}) \right] = </tex> <tex> E\left[ \displaystyle \sum_{j=0}^{m-1} n_j\right] + i 2E\cdot h_2(k)) left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}\mod 13 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]</centertex>
<center>Первый переход в равенстве мы совершили благодаря формуле <tex> h_1(k) a^2 = k a + 2\cdot\mod 13 dbinom{a}{2}</tex></center>. Далее мы воспользовались свойствами [[Математическое_ожидание_случайной_величины | математического ожидания]], в частности - линейности.
Очевидно, что <centertex>\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}</tex>- просто общее количество коллизий, поэтому по свойству универсального хеширования математическое ожидание значения этой суммы не превышает<texdpi="180"> h_2\binom{n}{2}{1 \over m} = {n(kn-1) \over 2m} = {n-1 + k \mod 11 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 следствия из этой теоремы.
Мы хотим вставить ключ 14. Изначально {{Теорема|statement=Если мы сохраняем <tex> i = 0 n</tex>. Тогда ключей в хеш-таблице размером <tex> h(14,0) m= (h_1(14) + 0\cdot h_2(14)) \mod 13 = 1 n</tex>. Но ячейка с индексом 1 занята, поэтому увеличиваем использованием хеш-функции <tex> i h</tex> на 1 , выбираемой случайным образом из [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], и пересчитываем значение устанавливаем размер каждой вторичной хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При таблицы равным <tex> i m_j= n_j^2 </tex> получаем <tex> h(14j=0,1,...,2m-1) </tex>, то математическое ожидание количества необходимой для вторичных хеш-таблиц в схеме идеального хеширования памяти не превышает <tex>2n</tex>.|proof=Поскольку <tex>m_j= (h_1(14) + n_j^2\cdot h_2(14)) \mod 13 </tex> для <tex>j= 9 0,1,...,m-1</tex>. Ячейка с номером 9 свободна, значит записываем туда наш ключ.согласно предыдущей теореме:
Таким образом, основная особенность двойного хеширования состоит в том, что при различных <tex> k E\left[\displaystyle \sum_{j=0}^{m-1} m_j \right] = E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] < 2n</tex> пара <tex> (h_1(k),h_2(k)) </tex> дает различные последовательности ячеек для исследованияч.т.д.
==Простая реализация==Пускай у нас есть некоторый объект <tex> item </tex>, в котором определено поле <tex> key </tex>, от которого можно вычислить хеш-функции <tex> h_1(key)</tex> и <tex> h_2(key) </tex>}}
Так же у нас есть таблица {{Теорема|statement=Если мы сохраняем <tex> table n</tex> величиной ключей в хеш-таблице размером <tex> m =n</tex> состоящая с использованием хеш-функции <tex>h</tex>, выбираемой случайным образом из объектов типа [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], и устанавливаем размер каждой вторичной хеш-таблицы равным <tex>m_j=n_j^2</tex> <tex>(j=0,1,...,m-1)</tex>, то вероятность того, что общее количество необходимой для вторичных хеш-таблиц памяти не менее <tex>4n</tex>, меньше чем <texdpi="180"> item {1 \over 2}</tex>.|proof=Применим [[Неравенство Маркова| неравенство Маркова]] <tex>P(X \geqslant t) \leqslant E[X]/t</tex>
===Вставка===Пусть <pretex>insert(item)X=\displaystyle \sum_{ x = h1(item.key) y = h2(item.key) for (i j= 0; i < m; i++){ if (table[x] == null)}^{ table[x] = item return } x = (x + y) mod m -1} error() m_j<//ошибка, требуется увеличить размер таблицы}tex> и <tex>t=4n</pretex>.
===Поиск===Тогда <pretex>contains(key)P \left \{\displaystyle \sum_{ x = h1(key) y = h2(key) for (i j= 0; i < }^{m; i++)-1} m_j \geqslant 4n \right \} \leqslant E\left[\displaystyle\sum_{ if (table[x] !j= null) if (table[x].key == key) return table[x] else return null x = (x + y) mod 0}^{m } return null-1}mj\right]</pre> ==Реализация с удалением==Что бы наша хеш-таблица поддерживала удаление, требуется добавить массив <tex>deleted</texdpi="150"> типов {1 \over 4n} <tex>bool</tex>, равный по величине массиву <tex>table</tex>. Теперь при удалении мы просто будем помечать наш объект ''как удалённый'', а при добавлении как ''не удалённый'' и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше. ===Вставка==dpi=<pre"150">insert(item){ x = h1(item.key) y = h2(item.key) for (i = 0; i < m; i++){ if (table[x] 2n \over 4n} == null || deleted[x]){ table[x] = item deleted[x] = false return } x = (x + y) mod m } error() //ошибка, требуется увеличить размер таблицы1 \over 2}</pretex===Поиск===<pre>search(key){ x = h1(key) y = h2(key) for (i = 0; i < m; i++){ if (table[x] != null) if (table[x], ч.т.key == key && !deleted[x]) return table[x] else return null x = (x + y) mod m } return null}</pre> ===Удаление===<pre>remove(key){ x = h1(key) y = h2(key) for (i = 0; i < m; i++){ if (table[x] != null) if (table[x]д.key == key) deleted[x] = true else return x = (x + y) mod m }}</pre>
==См. также==
* [[Хеширование]]
* [[Хеширование_кукушки|Хеширование кукушки]]
* [[Поиск_свободного_места_при_закрытом_хешировании|Поиск свободного места при закрытом хешированииРазрешение коллизий]] == Литература ==* Бакнелл Дж. М. '''Фундаментальные алгоритмы и структуры данных в 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.cs.ifmocmu.ruedu/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 Пример хеш таблицы с двойным хешированиемИдеальное хэширование]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Хеширование]]
Анонимный участник

Навигация