Идеальное хеширование — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Поиск)
Строка 1: Строка 1:
'''Двойное хеширование''' {{---}} метод борьбы с возникающими коллизиями при [[Открытое_и_закрытое_хеширование#Закрытое хеширование|закрытом хешировании]], в котором хеш-таблица заполняется равномерней чем при [[Открытое_и_закрытое_хеширование#Линейное разрешение коллизий|линейном разрешении коллизий]] коллизий, что способствует уменьшению размеров кластеров.
+
'''Двойное хеширование''' {{---}} метод борьбы с коллизиями, возникающими при [[Открытое_и_закрытое_хеширование#Закрытое хеширование|закрытом хешировании]], основанный на использовании двух хеш-функций для построения различных последовательностей исследования хеш-таблицы.
  
 
==Принцип двойного хеширования==
 
==Принцип двойного хеширования==
При двойном хешировании используются две независимые хеш-функции <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(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 : \Pr(h_1(x)=h_1(y))> \Pr((h_1(x)=h_1(y))\cap(h_2(x)=h_2(y)))</tex>
 +
</center>
  
 
==Выбор хеш-функций==
 
==Выбор хеш-функций==
Строка 37: Строка 44:
  
 
==Простая реализация==
 
==Простая реализация==
Пускай у нас есть некоторый объект <tex> item </tex>, в котором определено поле <tex> key </tex>, от которого можно вычислить хеш-функции <tex> h_1(key)</tex> и <tex> h_2(key) </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>.
+
Так же у нас есть таблица <tex> table </tex> величиной <tex> m </tex>, состоящая из объектов типа <tex> item </tex>.
  
 
===Вставка===
 
===Вставка===
<pre>insert(item){
+
<pre>insert(item)
 
   x = h1(item.key)
 
   x = h1(item.key)
 
   y = h2(item.key)
 
   y = h2(item.key)
   for (i = 0; i < m; i++){   
+
   for (i = 0; i < m; i++)  
       if (table[x] == null){
+
       if table[x] == null
 
         table[x] = item
 
         table[x] = item
         return
+
         return    
      }
+
       x = (x + y) mod m  
       x = (x + y) mod m
+
   table.resize() //ошибка, требуется увеличить размер таблицы</pre>
   }
 
  error() //ошибка, требуется увеличить размер таблицы
 
}</pre>
 
  
 
===Поиск===
 
===Поиск===
<pre>search(key){
+
<pre>search(key)
 
   x = h1(key)
 
   x = h1(key)
 
   y = h2(key)
 
   y = h2(key)
   for (i = 0; i < m; i++){
+
   for (i = 0; i < m; i++)
       if (table[x] != null)
+
       if table[x] != null
         if (table[x].key == key)
+
         if table[x].key == key
 
             return table[x]
 
             return table[x]
 
       else
 
       else
 
         return null
 
         return null
       x = (x + y) mod m
+
       x = (x + y) mod m  
  }
+
   return null</pre>
   return null
 
}</pre>
 
  
 
==Реализация с удалением==
 
==Реализация с удалением==
Строка 74: Строка 76:
  
 
===Вставка===
 
===Вставка===
<pre>insert(item){
+
<pre>insert(item)
 
   x = h1(item.key)
 
   x = h1(item.key)
 
   y = h2(item.key)
 
   y = h2(item.key)
   for (i = 0; i < m; i++){   
+
   for (i = 0; i < m; i++)  
       if (table[x] == null || deleted[x]){
+
       if table[x] == null || deleted[x]
 
         table[x] = item
 
         table[x] = item
 
         deleted[x] = false
 
         deleted[x] = false
         return
+
         return    
      }
+
       x = (x + y) mod m  
       x = (x + y) mod m
+
   table.resize() //ошибка, требуется увеличить размер таблицы</pre>
   }
 
  error() //ошибка, требуется увеличить размер таблицы
 
}</pre>
 
  
 
===Поиск===
 
===Поиск===
<pre>search(key){
+
<pre>search(key)
 
   x = h1(key)
 
   x = h1(key)
 
   y = h2(key)
 
   y = h2(key)
   for (i = 0; i < m; i++){
+
   for (i = 0; i < m; i++)  
       if (table[x] != null)
+
       if table[x] != null
         if (table[x].key == key && !deleted[x])
+
         if table[x].key == key && !deleted[x]
 
             return table[x]
 
             return table[x]
 
       else
 
       else
 
         return null
 
         return null
       x = (x + y) mod m
+
       x = (x + y) mod m  
  }
+
   return null</pre>
   return null
 
}</pre>
 
  
 
===Удаление===
 
===Удаление===
<pre>remove(key){
+
<pre>remove(key)
 
   x = h1(key)
 
   x = h1(key)
 
   y = h2(key)
 
   y = h2(key)
   for (i = 0; i < m; i++){
+
   for (i = 0; i < m; i++)
       if (table[x] != null)
+
       if table[x] != null
         if (table[x].key == key)
+
         if table[x].key == key
 
             deleted[x] = true
 
             deleted[x] = true
 
       else  
 
       else  
 
         return
 
         return
       x = (x + y) mod m
+
       x = (x + y) mod m</pre>
  }
 
}</pre>
 
  
 
==См. также==
 
==См. также==

Версия 16:48, 7 мая 2012

Двойное хеширование — метод борьбы с коллизиями, возникающими при закрытом хешировании, основанный на использовании двух хеш-функций для построения различных последовательностей исследования хеш-таблицы.

Принцип двойного хеширования

При двойном хешировании используются две независимые хеш-функции [math] h_1(k) [/math] и [math] h_2(k) [/math]. Пусть [math] k [/math] — это наш ключ, [math] m [/math] — размер нашей таблицы, [math]n \mod m [/math] — остаток от деления [math] n [/math] на [math] m [/math], тогда сначала исследуется ячейка с адресом [math] h_1(k) [/math], если она уже занята, то рассматривается [math] (h_1(k) + h_2(k)) \mod m [/math], затем [math] (h_1(k) + 2 \cdot h_2(k)) \mod m [/math] и так далее. В общем случае идёт проверка последовательности ячеек [math] (h_1(k) + i \cdot h_2(k)) \mod m [/math] где [math] i = (0, 1, \; ... \;, m - 1) [/math]

Таким образом, операции вставки, удаления и поиска в лучшем случае выполняются за [math]O(1)[/math], в худшем — за [math]O(m)[/math], что не отличается от обычного линейного разрешения коллизий. Однако в среднем, при грамотном выборе хеш-функций, двойное хеширование будет выдавать лучшие результаты, за счёт того, что вероятность совпадения значений сразу двух независимых хеш-функций ниже, чем одной.

[math]\forall x \neq y \; \exists h_1,h_2 : \Pr(h_1(x)=h_1(y))\gt \Pr((h_1(x)=h_1(y))\cap(h_2(x)=h_2(y)))[/math]

Выбор хеш-функций

[math] h_1 [/math] может быть обычной хеш-функцией. Однако чтобы последовательность исследования могла охватить всю таблицу, [math] h_2 [/math] должна возвращать значения:

  • не равные [math] 0 [/math]
  • независимые от [math] h_1 [/math]
  • взаимно простые с величиной хеш-таблицы

Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а [math] h_2 [/math] возвращает натуральные числа, меньшие [math] m [/math]. Второй — размер таблицы является степенью двойки, а [math] h_2 [/math] возвращает нечетные значения.

Например, если размер таблицы равен [math] m [/math], то в качестве [math] h_2 [/math] можно использовать функцию вида [math] h_2(k) = k \mod (m-1) + 1 [/math]

Вставка при двойном хешировании

Пример

Показана хеш-таблица размером 13 ячеек, в которой используются вспомогательные функции:

[math] h(k,i) = (h_1(k) + i \cdot h_2(k)) \mod 13 [/math]

[math] h_1(k) = k \mod 13 [/math]

[math] h_2(k) = 1 + k \mod 11 [/math]

Мы хотим вставить ключ 14. Изначально [math] i = 0 [/math]. Тогда [math] h(14,0) = (h_1(14) + 0\cdot h_2(14)) \mod 13 = 1 [/math]. Но ячейка с индексом 1 занята, поэтому увеличиваем [math] i [/math] на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При [math] i = 2 [/math] получаем [math] h(14,2) = (h_1(14) + 2\cdot h_2(14)) \mod 13 = 9 [/math]. Ячейка с номером 9 свободна, значит записываем туда наш ключ.

Таким образом, основная особенность двойного хеширования состоит в том, что при различных [math] k [/math] пара [math] (h_1(k),h_2(k)) [/math] дает различные последовательности ячеек для исследования.

Простая реализация

Пусть у нас есть некоторый объект [math] item [/math], в котором определено поле [math] key [/math], от которого можно вычислить хеш-функции [math] h_1(key)[/math] и [math] h_2(key) [/math]

Так же у нас есть таблица [math] table [/math] величиной [math] m [/math], состоящая из объектов типа [math] item [/math].

Вставка

insert(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() //ошибка, требуется увеличить размер таблицы

Поиск

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

Реализация с удалением

Что бы наша хеш-таблица поддерживала удаление, требуется добавить массив [math]deleted[/math] типов [math]bool[/math], равный по величине массиву [math]table[/math]. Теперь при удалении мы просто будем помечать наш объект как удалённый, а при добавлении как не удалённый и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.

Вставка

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) mod m   
   table.resize() //ошибка, требуется увеличить размер таблицы

Поиск

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

Удаление

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

См. также

Литература

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

Ссылки