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

Материал из Викиконспекты
Перейти к: навигация, поиск
(добавлен псевдокод)
Строка 26: Строка 26:
  
 
Таким образом, основная особенность двойного хеширования состоит в том, что при различных <tex> k </tex> пара <tex> (h_1(k),h_2(k)) </tex> дает различные последовательности ячеек для исследования.
 
Таким образом, основная особенность двойного хеширования состоит в том, что при различных <tex> k </tex> пара <tex> (h_1(k),h_2(k)) </tex> дает различные последовательности ячеек для исследования.
 +
 +
==Простая реализация==
 +
===Вставка===
 +
<pre>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) % m
 +
  }
 +
  error() //ошибка, требуется увеличить размер таблицы
 +
}</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) % m
 +
  }
 +
  return null
 +
}</pre>
 +
 +
==Реализация с удалением==
 +
===Вставка===
 +
<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>
 +
 +
===Поиск===
 +
<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) % 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) % m
 +
  }
 +
}</pre>
 +
 +
==См. также==
 +
* [[Хеширование]]
 +
* [[Хеширование_кукушки|Хеширование кукушки]]
 +
* [[Поиск_свободного_места_при_закрытом_хешировании|Поиск свободного места при закрытом хешировании]]
  
 
== Литература ==
 
== Литература ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''' —  Вильямс, 2010. - 1296с. — ISBN 978-5-8459-0857-4, 0-07-013151-1.
+
* Бакнелл Дж. М. '''Фундаментальные алгоритмы и структуры данных в Delphi''', ''2003''
 +
* Кнут Д. Э. '''Искусство программирования, том 3. Сортировка и поиск''', ''2-е издание, 2000''
 +
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''', ''2010''
 +
* Седжвик Р. '''Фундаментальные алгоритмы на C. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск''', ''2003''
 +
 
 +
==Ссылки==
 +
* [http://en.wikipedia.org/wiki/Double_hashing Double_hashing]
 +
* [http://rain.ifmo.ru/cat/view.php/vis/hashtables/hash-2001-2 Пример хеш таблицы]
 +
* [http://research.cs.vt.edu/AVresearch/hashing/double.php Пример хеш таблицы с двойным хешированием]
 +
 
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Хеширование]]

Версия 22:42, 3 мая 2012

Двойное хеширование (double hashing) - один из методов закрытого хеширования. Перебор ячеек хеш-таблицы, возникающий при двойном хешировании, обладает свойствами, присущими равномерному хешированию. При двойном хешировании хеш-функция [math] h [/math] имеет следующий вид:

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

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

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

Пример вставки элемента при двойном хешировании приведен на рисунке справа.

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

[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] h_2 [/math] должно быть взаимно простым с размером таблицы. Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а [math] h_2 [/math] возвращает натуральные числа, меньшие [math] m [/math]. Второй - размер таблицы является степенью двойки, а [math] h_2 [/math] возвращает нечетные значения.

Таким образом, основная особенность двойного хеширования состоит в том, что при различных [math] k [/math] пара [math] (h_1(k),h_2(k)) [/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) % m
   }
   error() //ошибка, требуется увеличить размер таблицы
}

Поиск

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) % m
   }
   return null
}

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

Вставка

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

Поиск

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) % 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) % m
   }
}

См. также

Литература

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

Ссылки