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

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

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

При двойном хешировании используются две независимые хеш-функции [math] h_1(k) [/math] и [math] h_2(k) [/math]. Пускай [math] k [/math] это наш ключ, [math] m [/math] размер нашей таблицы, [math] mod \; m [/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] h_1 [/math] может быть обычной хеш-функцией. Однако что бы в случаях коллизий была проверенна вся хеш-таблица, [math] h_2 [/math] должна возвращать значения:

• не равные [math] 0 [/math]
• независимые от [math] h_1 [/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] 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] дает различные последовательности ячеек для исследования.

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

Пускай у нас есть некоторый объект [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
   }
   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) 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
   }
   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) 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

Ссылки

• Double_hashing
• Пример хеш таблицы
• Пример хеш таблицы с двойным хешированием