При частом добавлении новых значений в хеш-таблицу может возникнуть ситуация, когда хеш-таблица становится полностью заполненной и требуется перехешировать ее. Но при При малых размерах хеш-таблицы полное перехеширование не вызовет трудностей. При больших размерах хеш-таблицы это требует большого количества времени, также если значения поступают очень часто, то требуется часто перехешировать таблицу либо выделять огромные объемы памяти, которые могут и не понадобиться, а следовательно они просто зарезервируются впустую. Также в стандартной хеш-таблице может произойти коллизия(два разных значения поступают в одну ячейку). Чтобы решить эту проблемуэти проблемы, а также чтобы не выделять много дополнительной памяти можно использовать расширяемое хеширование.== Структура и алгоритм =='''Метод расширяемого хеширования''' (англ. ''extendible hashing'') заключается в том, что хеш-таблица представлена как '''каталог''' (англ. ''directory''), а каждая ячейка будет указывать на '''емкость''' (англ. ''bucket'') которая имеет определенную '''вместимость''' (англ. capacity). Сама хеш-таблица будет иметь '''глобальную глубину''' (англ. ''global depth''), а каждая из емкостей имеет '''локальную глубину''' (англ. ''local depth''). Глобальная глубина показывает сколько последних бит будут использоваться для того чтобы определить в какую емкость следует заносить значения. А из разницы локальной глубины и глобальной глубины можно понять сколько ячеек каталога ссылаются на емкость. Это можно показать формулой <tex>K = 2 </tex><sup><tex>G-L</tex></sup> где <tex>G</tex> — глобальная глубина, <tex>L</tex> — локальная глубина, а <tex>K</tex> количество ссылающихся ячеек. Для поиска емкости используется [[Wikipedia:Trie|цифровое дерево]].
'''Метод расширяемого хеширования''' (англ. ''extendible hashing'') заключается Теперь рассмотрим сам алгоритм если нам поступило некоторое значение:#Переводим значение в томдвоичный вид, что мы представляем хеш-таблицу смотрим на последние <tex>G</tex> битов и решаем в качестве нескольких группкакую емкость отправить значение.#Если емкость имеет свободное место, которые имеют определенное количество ячеек. При переполнении группы то помещаем туда значение без всяких хлопот, если же емкость куда следует положить значение переполнена, то cмотрим на локальную глубину емкости: ##Если она меньше чем глобальная глубина то значит на емкость есть несколько указателей и нам не требуется достаточно перехешировать всю таблицу, а лишь перехешировать заполненную группуее, разделив ее при этом на две группыи занести значения в новые две емкости увеличив у этих емкостей локальную глубину на <tex>1</tex>. Таким образом вся хеш-таблица никогда не будет полностью заполнена. К тому ##Если же локальная глубина была равна глобальной то мы увеличиваем глобальную глубину на <tex>1</tex>, удваивая при использовании данного метода использование памяти будет наиболее экономичным.== Алгоритм ==В начале у нас есть хеш-таблица с первоначальным количеством этом количество ячеек, количество указателей на емкости, а также увеличиваем количество последних бит по которым мы распределяем значения. Все эти ячейки будут являться первой группой. Каждая группа будет содержать некоторый набор значений Далее локальная глубина переполненной емкости становится меньше и номер записи каждого значениямы повторяем предыдущий алгоритм то есть перехешируем емкость, чтобы разделим ее можно было извлечьна две емкости и так далее.
Когда группа заполнится разобьем ее ==Пример==Рассмотрим алгоритм на две группы одинаковых размеров и повторим вставку всех элементов исходной группы в две новые группы. Причем все элементы, которые завершаются нулевым разрядом, поместим в одну группу, а завершающиеся единичным разрядом — в другую. Эти две группы имеют так называемую '''разрядную глубину''' (англ. ''bit—depth''), равную одному разряду. Теперь при каждой вставке пары значение/номер записи она будет помещаться в первую или во вторую группу, в зависимости от последнего разряда значения. При заполнении группы с глубиной <tex>1</tex> будет использоваться предпоследний разряд, при заполнении группы с глубиной <tex>2</tex> пред-предпоследний разряд и так далеепримере.
Для поддержания отображения того, какие Пусть у нас есть некий каталог со своими указателями и мы хотим добавить значения помещаются в те или иные группы<tex>9, используется структура20, называемая каталогом. По существу каталог содержит список всех возможных окончаний групп и связных с ними номеров групп. Вместо того чтобы поддерживать какой—либо причудливый набор значений разрядной глубины и номеров групп26</tex> (смотри рисунок №1) где <tex>G</tex> — глобальная глубина, выбранный методом проб и ошибок <tex>l1, каталог поддерживает собственное значение разрядной глубиныl2, равное максимальной разрядной глубине группыl3, и имеет ячейку для каждого значения этой разрядной l4</tex> — локальные глубиныемкостей, а вместимость емкостей равна <tex>3</tex>.
[[ФайлПервым на вход поступает значение <tex>9</tex>. Представим его в двоичном виде:7_1<tex>9 = 8+1 = 1000+1 = 1001</tex>.png|400px|мини|Вставка Окончание <tex>01</tex> соответствует второй ячейке значит смотрим на вторую емкость. В ней есть свободное место и мы просто помещаем <tex>9</tex> в расширяемую хеш-таблицу]]нее (смотри рисунок №2). На этом работа с <tex>9</tex> закончена.
При разбиении группы дополняющие друг друга группы не будут размещаться Далее на вход поступает значение <tex>20</tex>. Представим его в каталоге по соседствудвоичном виде: <tex>20 = 16+4 = 10000+100 = 10100</tex>. Для дальнейших рассуждений было бы проще предположитьЭто значение оканчивается на <tex>00</tex> и должно пойти в первую емкость, что записи но первая емкость полностью заполнена. Следовательно мы смотрим на локальную глубину первой емкости то есть на <tex>l1</tex>. <tex>l1 = G</tex> а значит следуя выше описанному алгоритму мы должны удвоить количество ячеек каталога, соответствующие одной группеувеличить глобальную глубину, располагаются затем увеличить количество последних бит по соседствукоторым мы раскидываем значения на <tex>1</tex> и перехешировать первую емкость, чтобы при разбиении группы дополняющая первую группа помещалась непосредственно за нейразделив ее на две, увеличив локальную глубину и разместив значения по новым емкостям (смотри рисунок №3). На этом работа с <tex>20</tex> закончена.
Для достижения этого следует инвертировать последние разряды значения при вычислении индексной записи каталога. Так, например, если Последним на вход поступает значение завершается разрядами <tex>00126</tex>, при поиске мы обратимся не к записи . Представим его в двоичном виде: <tex>00126 = 16+8+2 = 10000+1000+10 = 11010</tex> каталога, а к записи . Последние <tex>1003</tex> бита (<tex>4010</tex>) соответствуют третьей емкости, которая соответствует инвертированному значению но она также полностью заполнена как и во втором случае, но ее локальная глубина меньше чем глобальная глубина, а следовательно нам надо только перехешировать емкость, разделив ее на две, увеличив локальную глубину и разместив значения по новым емкостям (смотри рисунок №4). На этом работа с <tex>00126</tex>)закончена.{|align="center" |-valign="top" |[[Файл:FirstStep. В результате использование каталога значительно упрощаетсяpng|мини|250px|рисунок №1]] |[[Файл:SecondStep.png|мини|250px|рисунок №2]] |[[Файл:ThirdStep.png|мини|250px|рисунок №3]]==Пример== |[[Файл:ForthStep.png|мини|250px|рисунок №4]] |}
Рассмотрим выполнение алгоритма на примере, выполняемые при этом действия показаны на рис. Мы начинаем с каталога только с одной записью с индексом <tex>0</tex> (a). Принято считать, что в подобной ситуации разрядная глубина равна <tex>0</tex>. Мы заполняем единственную группу (назовем ее <tex> A </tex> ) и теперь ее нужно разбить. Вначале мы увеличиваем разрядную глубину каталога до <tex>1</tex>. Иначе говоря, теперь он будет содержать две записи (b). В результате будут созданы две группы, на первую из которых указывает запись <tex>0</tex> (исходная запись <tex> A </tex> ), а на вторую — запись <tex>1</tex>, <tex> B </tex> (c). Все элементы, значения которых завершаются разрядом <tex>0</tex>, помещаются в группу <tex> A </tex> , а остальные — в группу <tex> B </tex> . Снова заполним группу <tex> A </tex> . Теперь разрядную глубину каталога необходимо увеличить с <tex>1</tex> до <tex>2</tex>, чтобы получить четыре группы, доступных для вставки. Перед разделением заполненной группы записи каталога <tex>00</tex> и <tex>01</tex> будут указывать на исходную группу <tex> A </tex> , а записи <tex>10</tex> и <tex>11</tex> — на группу <tex> B </tex> (d). Группа <tex> A </tex> разбивается на группу, которая принимает значения с окончанием <tex>00</tex> (снова <tex> A </tex> ), и группу, которая принимает значения с окончанием <tex>10</tex>, <tex> C </tex> . На группу <tex> A </tex> будет указывать запись <tex>00</tex> каталога, а на группу <tex> C </tex> — запись <tex>01</tex> (e). И, наконец, группа <tex> C </tex> (на которую указывает запись 01 каталога) заполняется. Нужно снова увеличить разрядную глубину каталога, на этот раз до трех разрядов.
== Использование ==
Чаще всего расширяемое хеширование используется в базах данных ттак как.к. БД Базы данных могут быть крайне большими и перехеширование всей БД базы данных займет продолжительное время при этом лишая пользователей доступа к БДбазе данных. А при использовании расширяемого хеширования перехешировать придется только малые группы, что не сильно замедлит работу БДбазы данных. Также расширяемое хэширование хорошо работает в условиях динамически изменяемого набора записей в хранимом файле.
== См. также ==
*[[Хеш-таблица]]
*Бакнелл Джулиан — Фундаментальные алгоритмы и структуры данных в Delphi — стр. 50.
*Дейт К. Дж. — Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 1236.
*[http://en.wikipedia.org/wiki/Extendible_hashing Wikipedia — Extendible hashing][[Категория: Дискретная математика и алгоритмы]][[Категория: Хеширование]][[Категория: Структуры Базы данных]]
