Идеальное хеширование
Двойное хеширование – метод борьбы с возникающими коллизиями при закрытом хешировании, в котором хеш-таблица заполняется равномерней чем при линейном разрешении коллизий коллизий, что способствует уменьшению размеров кластеров.
Содержание
Принцип двойного хеширования
При двойном хешировании используются две независимые хеш-функции и . Пускай это наш ключ, размер нашей таблицы, это остаток от деления на , тогда сначала исследуется ячейка с адресом , если она уже занята рассматривается , затем и т.д. В общем случае идёт проверка последовательности ячеек где
Выбор хеш-функций
может быть обычной хеш-функцией. Однако что бы в случаях коллизий была проверенна вся хеш-таблица, должна возвращать значения:
- не равные
- независимые от
- взаимно простые с величиной хеш-таблицы
Например, если размер таблицы равен , то в качестве можно использовать функцию вида
Пример
Показана хеш-таблица размером 13 ячеек, в которой используются вспомогательные функции:
Мы хотим вставить ключ 14. Изначально . Тогда . Но ячейка с индексом 1 занята, поэтому увеличиваем на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При получаем . Ячейка с номером 9 свободна, значит записываем туда наш ключ.
Для того, чтобы последовательность исследования могла охватить всю таблицу, значение должно быть взаимно простым с размером таблицы. Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а возвращает натуральные числа, меньшие . Второй - размер таблицы является степенью двойки, а возвращает нечетные значения.
Таким образом, основная особенность двойного хеширования состоит в том, что при различных пара дает различные последовательности ячеек для исследования.
Простая реализация
Пускай у нас есть некоторый объект , в котором определено поле , от которого можно вычислить хеш-функции и
Так же у нас есть таблица величиной состоящая из объектов типа .
Вставка
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
}
Реализация с удалением
Что бы наша хеш-таблица поддерживала удаление, требуется добавить массив типов , равный по величине массиву . Теперь при удалении мы просто будем помечать наш объект как удалённый, а при добавлении как не удалённый и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.
Вставка
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
