|
|
| Строка 1: |
Строка 1: |
| − | '''Двойное хеширование''' {{---}} метод борьбы с коллизиями, возникающими при [[Открытое_и_закрытое_хеширование#Закрытое хеширование|закрытом хешировании]], основанный на использовании двух хеш-функций для построения различных последовательностей исследования хеш-таблицы.
| |
| − |
| |
| − | ==Принцип двойного хеширования==
| |
| − | При двойном хешировании используются две независимые хеш-функции <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>
| |
| − |
| |
| − | Таким образом, операции вставки, удаления и поиска в лучшем случае выполняются за <tex>O(1)</tex>, в худшем {{---}} за <tex>O(m)</tex>, что не отличается от обычного [[Открытое_и_закрытое_хеширование#Линейное разрешение коллизий|линейного разрешения коллизий]].
| |
| − | Однако в среднем, при грамотном выборе хеш-функций, двойное хеширование будет выдавать лучшие результаты, за счёт того, что вероятность совпадения значений сразу двух независимых хеш-функций ниже, чем одной.
| |
| − |
| |
| − | <center>
| |
| − | <tex>\forall x \neq y \; \exists h_1,h_2 : p(h_1(x)=h_1(y))> p((h_1(x)=h_1(y)) \land (h_2(x)=h_2(y)))</tex>
| |
| − | </center>
| |
| − |
| |
| − | ==Выбор хеш-функций==
| |
| − | <tex> h_1 </tex> может быть обычной хеш-функцией. Однако чтобы последовательность исследования могла охватить всю таблицу, <tex> h_2 </tex> должна возвращать значения:
| |
| − | *не равные <tex> 0 </tex>
| |
| − | *независимые от <tex> h_1 </tex>
| |
| − | *взаимно простые с величиной хеш-таблицы
| |
| − |
| |
| − | Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а <tex> h_2 </tex> возвращает натуральные числа, меньшие <tex> m </tex>. Второй {{---}} размер таблицы является степенью двойки, а <tex> h_2 </tex> возвращает нечетные значения.
| |
| − |
| |
| − | Например, если размер таблицы равен <tex> m </tex>, то в качестве <tex> h_2 </tex> можно использовать функцию вида <tex> h_2(k) = k \mod (m-1) + 1 </tex>
| |
| − |
| |
| − | [[Файл: Вставка при двойном хэшировании.svg.jpeg|thumb|right|Вставка при двойном хешировании]]
| |
| − |
| |
| − | ==Пример==
| |
| − |
| |
| − | Показана хеш-таблица размером 13 ячеек, в которой используются вспомогательные функции:
| |
| − |
| |
| − | <center>
| |
| − | <tex> h(k,i) = (h_1(k) + i \cdot h_2(k)) \mod 13 </tex>
| |
| − | </center>
| |
| − |
| |
| − | <center>
| |
| − | <tex> h_1(k) = k \mod 13 </tex>
| |
| − | </center>
| |
| − |
| |
| − | <center>
| |
| − | <tex> h_2(k) = 1 + k \mod 11 </tex>
| |
| − | </center>
| |
| − |
| |
| − | Мы хотим вставить ключ 14. Изначально <tex> i = 0 </tex>. Тогда <tex> h(14,0) = (h_1(14) + 0\cdot h_2(14)) \mod 13 = 1 </tex>. Но ячейка с индексом 1 занята, поэтому увеличиваем <tex> i </tex> на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При <tex> i = 2 </tex> получаем <tex> h(14,2) = (h_1(14) + 2\cdot h_2(14)) \mod 13 = 9 </tex>. Ячейка с номером 9 свободна, значит записываем туда наш ключ.
| |
| − |
| |
| − | Таким образом, основная особенность двойного хеширования состоит в том, что при различных <tex> k </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>
| |
| − |
| |
| − | Так же у нас есть таблица <tex> table </tex> величиной <tex> m </tex>, состоящая из объектов типа <tex> item </tex>.
| |
| − |
| |
| − | ===Вставка===
| |
| − | <pre>add(item)
| |
| − | x = h1(item.key)
| |
| − | y = h2(item.key)
| |
| − | for (i = 0; i < m; i++)
| |
| − | if table[x] == null
| |
| − | table[x] = item
| |
| − | return
| |
| − | x = (x + y) mod m
| |
| − | table.resize() //ошибка, требуется увеличить размер таблицы</pre>
| |
| − |
| |
| − | ===Поиск===
| |
| − | <pre>search(key)
| |
| − | x = h1(key)
| |
| − | y = h2(key)
| |
| − | for (i = 0; i < m; i++)
| |
| − | if table[x] != null
| |
| − | if table[x].key == key
| |
| − | return table[x]
| |
| − | else
| |
| − | return null
| |
| − | x = (x + y) mod m
| |
| − | return null</pre>
| |
| − |
| |
| − | ==Реализация с удалением==
| |
| − | Что бы наша хеш-таблица поддерживала удаление, требуется добавить массив <tex>deleted</tex> типов <tex>bool</tex>, равный по величине массиву <tex>table</tex>. Теперь при удалении мы просто будем помечать наш объект ''как удалённый'', а при добавлении как ''не удалённый'' и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.
| |
| − |
| |
| − | ===Вставка===
| |
| − | <pre>add(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) mod m
| |
| − | table.resize() //ошибка, требуется увеличить размер таблицы</pre>
| |
| − |
| |
| − | ===Поиск===
| |
| − | <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>
| |
| | | | |
| | ==См. также== | | ==См. также== |
| Строка 116: |
Строка 4: |
| | * [[Хеширование_кукушки|Хеширование кукушки]] | | * [[Хеширование_кукушки|Хеширование кукушки]] |
| | * [[Поиск_свободного_места_при_закрытом_хешировании|Поиск свободного места при закрытом хешировании]] | | * [[Поиск_свободного_места_при_закрытом_хешировании|Поиск свободного места при закрытом хешировании]] |
| − |
| |
| − | == Литература ==
| |
| − | * Бакнелл Дж. М. '''Фундаментальные алгоритмы и структуры данных в Delphi''', ''2003''
| |
| − | * Кнут Д. Э. '''Искусство программирования, том 3. Сортировка и поиск''', ''2-е издание, 2000''
| |
| − | * Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''', ''2010''
| |
| − | * Седжвик Р. '''Фундаментальные алгоритмы на C. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск''', ''2003''
| |
| | | | |
| | ==Ссылки== | | ==Ссылки== |
| − | * [http://en.wikipedia.org/wiki/Double_hashing Wikipedia {{---}} Double_hashing] | + | * [http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0215.pdf Universal and Perfect Hashing] |
| − | * [http://rain.ifmo.ru/cat/view.php/vis/hashtables/hash-2001-2 Пример хеш таблицы]
| |
| − | * [http://research.cs.vt.edu/AVresearch/hashing/double.php Пример хеш таблицы с двойным хешированием]
| |
| | | | |
| | [[Категория:Дискретная математика и алгоритмы]] | | [[Категория:Дискретная математика и алгоритмы]] |
| | [[Категория:Хеширование]] | | [[Категория:Хеширование]] |
