Расширяемое хеширование

При частом добавлении новых значений в хеш-таблицу может возникнуть ситуация, когда хеш-таблица становится полностью заполненной и требуется перехешировать ее. Но при больших размерах хеш-таблицы это требует большого количества времени. Чтобы решить эту проблему, а также чтобы не выделять много дополнительной памяти можно использовать расширяемое хеширование.

Структура и алгоритм

Метод расширяемого хеширования (англ. extendible hashing) заключается в том, что хеш-таблица представлена как каталог (англ. directory), а каждая ячейка будет указывать на емкость (англ. bucket) которая имеет определенную вместимость (англ. capacity). Сама хеш-таблица будет иметь глобальную глубину (англ. global depth), а каждая из емкостей имеет локальную глубину (англ. local depth). Значения будут заноситься в емкости в зависимости от своих последних битов. Если емкость куда следует положить значение переполнена, то смотрим на локальную глубину емкости. Если она меньше чем глобальная глубина то значит на емкость есть несколько указателей и нам достаточно перехешировать ее, разделив при этом на две и занести значения в новые две емкости увеличив у этих емкостей локальную глубину на [math]1[/math]. Если же локальная глубина была равна глобальной то мы увеличиваем глобальную глубину на [math]1[/math], удваивая при этом количество ячеек, количество указателей на емкости, а также увеличиваем количество последних бит по которым мы распределяем значения. Далее локальная глубина переполненной емкости становится меньше и мы знаем что дальше делать.

Пример

Рассмотрим алгоритм на примере.

Пусть у нас есть некий каталог со своими указателями и мы хотим добавить значения [math]9, 20, 26[/math] (см. рис1) где [math]G[/math] — глобальная глубина, [math]l1, l2, l3, l4[/math] — локальные глубины емкостей, а вместимость емкостей равна [math]3[/math]. Рассмотрим значение [math]9[/math]. В двоичном коде оно равно [math]1001[/math]. Окончание [math]01[/math] соответствует второй ячейке значит смотрим на вторую емкость. В ней есть свободное место и мы просто помещаем [math]9[/math] в нее (см. рис2). Далее идет значение [math]20[/math]. В двоичном виде оно представляется как [math]10100[/math]. Это значение оканчивается на [math]00[/math] и должно пойти в первую емкость, но первая емкость полностью заполнена. Следовательно мы смотрим на [math]l1[/math]. [math]l1 = G[/math] а значит мы должны удвоить количество ячеек каталога, увеличить глобальную глубину, затем увеличить количество последних бит по которым мы раскидываем значения на [math]1[/math] и перехешировать первую емкость, разделив ее на две, увеличив локальную глубину и разместив значения по новым емкостям (см. рис3). Теперь рассмотрим последнее число [math]26[/math]. Его двоичное представление — [math]11010[/math]. Последние [math]3[/math] бита соответствуют третьей емкости, но она также полностью заполнена как и во втором случае, но ее локальная глубина меньше чем глобальная а следовательно нам надо только перехешировать емкость и т.д. (см. рис4).

рис1

рис2

рис3

рис4

Использование

Чаще всего расширяемое хеширование используется в базах данных т.к. БД могут быть крайне большими и перехеширование всей БД займет продолжительное время при этом лишая пользователей доступа к БД. А при использовании расширяемого хеширования перехешировать придется только малые группы, что не сильно замедлит работу БД.

См. также

• Хеш-таблица
• Разрешение коллизий
• Хеширование кукушки
• Идеальное хеширование
• Перехеширование

Источники информации

• Бакнелл Джулиан — Фундаментальные алгоритмы и структуры данных в Delphi — стр. 50.
• Дейт К. Дж. — Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 1236.