Расширяемое хеширование
При частом добавлении новых значений в хеш-таблицу может возникнуть ситуация, когда хеш-таблица становится полностью заполненной и требуется перехешировать ее. При малых размерах хеш-таблицы полное перехеширование не вызовет трудностей. При больших размерах хеш-таблицы это требует большого количества времени, также если значения поступают очень часто, то требуется часто перехешировать таблицу либо выделять огромные объемы памяти, которые могут и не понадобиться, а следовательно они прост. Чтобы решить эту проблему, а также чтобы не выделять много дополнительной памяти можно использовать расширяемое хеширование.
Структура и алгоритм
Метод расширяемого хеширования (англ. extendible hashing) заключается в том, что хеш-таблица представлена как каталог (англ. directory), а каждая ячейка будет указывать на емкость (англ. bucket) которая имеет определенную вместимость (англ. capacity). Сама хеш-таблица будет иметь глобальную глубину (англ. global depth), а каждая из емкостей имеет локальную глубину (англ. local depth). Глобальная глубина показывает сколько последних бит будут использоваться для того чтобы определить в какую емкость следует заносить значения. А из разницы локальной глубины и глобальной глубины можно понять сколько ячеек каталога ссылаются на емкость. Это можно показать формулой где — глобальная глубина, — локальная глубина, а количество ссылающихся ячеек. Для поиска емкости используется цифровое дерево.
Теперь рассмотрим сам алгоритм если нам поступило некоторое значение:
- Переводим значение в двоичный вид, смотрим на последние битов и решаем в какую емкость отправить значение.
- Если емкость имеет свободное место, то помещаем туда значение без всяких хлопот, если же емкость куда следует положить значение переполнена, то cмотрим на локальную глубину емкости:
- Если она меньше чем глобальная глубина то значит на емкость есть несколько указателей и нам достаточно перехешировать ее, разделив при этом на две и занести значения в новые две емкости увеличив у этих емкостей локальную глубину на .
- Если же локальная глубина была равна глобальной то мы увеличиваем глобальную глубину на , удваивая при этом количество ячеек, количество указателей на емкости, а также увеличиваем количество последних бит по которым мы распределяем значения. Далее локальная глубина переполненной емкости становится меньше и мы повторяем предыдущий алгоритм то есть перехешируем емкость, разделим ее на две емкости и так далее.
Пример
Рассмотрим алгоритм на примере.
Пусть у нас есть некий каталог со своими указателями и мы хотим добавить значения (смотри рисунок №1) где — глобальная глубина, — локальные глубины емкостей, а вместимость емкостей равна .
Первым на вход поступает значение . Представим его в двоичном виде: . Окончание соответствует второй ячейке значит смотрим на вторую емкость. В ней есть свободное место и мы просто помещаем в нее (смотри рисунок №2). На этом работа с закончена.
Далее на вход поступает значение . Представим его в двоичном виде: . Это значение оканчивается на и должно пойти в первую емкость, но первая емкость полностью заполнена. Следовательно мы смотрим на локальную глубину первой емкости то есть на . а значит следуя выше описанному алгоритму мы должны удвоить количество ячеек каталога, увеличить глобальную глубину, затем увеличить количество последних бит по которым мы раскидываем значения на и перехешировать первую емкость, разделив ее на две, увеличив локальную глубину и разместив значения по новым емкостям (смотри рисунок №3). На этом работа с закончена.
Последним на вход поступает значение . Представим его в двоичном виде: . Последние бита () соответствуют третьей емкости, но она также полностью заполнена как и во втором случае, но ее локальная глубина меньше чем глобальная глубина, а следовательно нам надо только перехешировать емкость, разделив ее на две, увеличив локальную глубину и разместив значения по новым емкостям (смотри рисунок №4). На этом работа с закончена.
Использование
Чаще всего расширяемое хеширование используется в базах данных так как. Базы данных могут быть крайне большими и перехеширование всей базы данных займет продолжительное время при этом лишая пользователей доступа к базе данных. А при использовании расширяемого хеширования перехешировать придется только малые группы, что не сильно замедлит работу базы данных.
См. также
Источники информации
- Бакнелл Джулиан — Фундаментальные алгоритмы и структуры данных в Delphi — стр. 50.
- Дейт К. Дж. — Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 1236.
- Wikipedia — Extendible hashing
