При частом добавлении новых значений в хеш-таблицу может возникнуть ситуация, когда хеш-таблица становится полностью заполненной и требуется перехешировать ее. Но при больших размерах хеш-таблицы это требует большого количества времени. Чтобы решить эту проблему, а также чтобы не выделять много дополнительной памяти можно использовать расширяемое хеширование.
== Структура и алгоритм ==
'''Метод расширяемого хеширования''' (англ. ''extendible hashing'') заключается в том, что хеш-таблица представлена как каталог (англ. ''directory''), а каждая ячейка будет указывать на емкость (англ. ''bucket'') которая имеет определенную вместимость (англ. capacity). Сама хеш-таблица будет иметь глобальную глубину (англ. ''global depth''), а каждая из емкостей имеет локальную глубину (англ. ''local depth''). Значения будут заноситься в емкости в зависимости от своих последних битов. Если емкость куда следует положить значение переполнена, то смотрим на локальную глубину емкости. Если она меньше чем глобальная глубина то значит на емкость есть несколько указателей и нам достаточно перехешировать ее, разделив при этом на две и занести значения в новые две емкости увеличив у этих емкостей локальную глубину на 1. Если же локальная глубина была равна глобальной то мы увеличиваем глобальную глубину на 1, удваивая при этом количество ячеек, количество указателей на емкости, а также увеличиваем количество последних бит по которым мы распределяем значения. Далее локальная глубина переполненной емкости становится меньше и мы знаем что дальше делать.
==Пример==
<div class="tright" style="clear:none">[[Файл:SecondStep.png|мини|250px|рис2]]</div>
<div class="tright" style="clear:none">[[Файл:FirstStep.png|мини|250px|рис1]]</div>
'''Метод расширяемого хеширования''' (англ. ''extendible hashing'') заключается в том, что мы представляем хеш-таблицу в качестве нескольких групп, которые имеют определенное количество ячеек. При переполнении группы нам не требуется перехешировать всю таблицу, а лишь перехешировать заполненную группу, разделив ее при этом на две группы. Таким образом вся хеш-таблица никогда не будет полностью заполнена. К тому же при использовании данного метода использование памяти будет наиболее экономичным.== Алгоритм ==В начале у нас есть хеш-таблица с первоначальным количеством ячеек. Все эти ячейки будут являться первой группой. Каждая группа будет содержать некоторый набор значений и номер записи каждого значения, чтобы ее можно было извлечь. Когда группа заполнится разобьем ее Рассмотрим алгоритм на две группы одинаковых размеров и повторим вставку всех элементов исходной группы в две новые группы. Причем все элементы, которые завершаются нулевым разрядом, поместим в одну группу, а завершающиеся единичным разрядом — в другую. Эти две группы имеют так называемую '''разрядную глубину''' (англ. ''bit—depth''), равную одному разряду. Теперь при каждой вставке пары значение/номер записи она будет помещаться в первую или во вторую группу, в зависимости от последнего разряда значения. При заполнении группы с глубиной <tex>1</tex> будет использоваться предпоследний разряд, при заполнении группы с глубиной <tex>2</tex> пред-предпоследний разряд и так далее. Для поддержания отображения того, какие значения помещаются в те или иные группы, используется структура, называемая каталогом. По существу каталог содержит список всех возможных окончаний групп и связных с ними номеров групп. Вместо того чтобы поддерживать какой—либо причудливый набор значений разрядной глубины и номеров групп, выбранный методом проб и ошибок, каталог поддерживает собственное значение разрядной глубины, равное максимальной разрядной глубине группы, и имеет ячейку для каждого значения этой разрядной глубины. [[Файл:7_1.png|400px|мини|Вставка в расширяемую хеш-таблицу]] При разбиении группы дополняющие друг друга группы не будут размещаться в каталоге по соседству. Для дальнейших рассуждений было бы проще предположить, что записи каталога, соответствующие одной группе, располагаются по соседству, чтобы при разбиении группы дополняющая первую группа помещалась непосредственно за ней. Для достижения этого следует инвертировать последние разряды значения при вычислении индексной записи каталога. Так, например, если значение завершается разрядами <tex>001</tex>, при поиске мы обратимся не к записи <tex>001</tex> каталога, а к записи <tex>100</tex> (<tex>4</tex>, которая соответствует инвертированному значению <tex>001</tex>). В результате использование каталога значительно упрощаетсяпримере. ==Пример==
Рассмотрим выполнение алгоритма на примереПусть у нас есть некий каталог со своими указателями и мы хотим добавить значения 9, выполняемые при этом действия показаны на рис. Мы начинаем с каталога только с одной записью с индексом <tex>0</tex> (a). Принято считать20, что в подобной ситуации разрядная глубина равна <tex>0</tex>. Мы заполняем единственную группу 26 (назовем ее <tex> A </tex> ) и теперь ее нужно разбить. Вначале мы увеличиваем разрядную глубину каталога до <tex>1</tex>см. Иначе говоря, теперь он будет содержать две записи (bрис1). В результате будут созданы две группы, на первую из которых указывает запись где <tex>0G</tex> (исходная запись <tex> A </tex> ), а на вторую — запись <tex>1</tex>глобальная глубина, <tex> B </tex> (c). Все элементыl1, l2, значения которых завершаются разрядом <tex>0</tex>l3, помещаются в группу <tex> A l4</tex> — локальные глубины емкостей, а остальные — в группу вместимость емкостей равна <tex> B 3</tex> . Снова заполним группу <tex> A </tex> Рассмотрим число 9. Теперь разрядную глубину каталога необходимо увеличить с <tex>1</tex> до <tex>2</tex>, чтобы получить четыре группы, доступных для вставкиВ двоичном коде оно равно 1001. Перед разделением заполненной группы записи каталога <tex>00</tex> и <tex>Окончание 01</tex> будут указывать соответствует второй ячейке значит смотрим на исходную группу <tex> A </tex> , а записи <tex>10</tex> вторую емкость. В ней есть свободное место и <tex>11</tex> — на группу <tex> B </tex> мы просто помещаем 9 в нее (dсм. рис2). Группа <tex> A </tex> разбивается Далее идет значение 20. В двоичном виде оно представляется как 10100. Это значение оканчивается на группу, которая принимает значения с окончанием <tex>00</tex> (снова <tex> A </tex> ), и группудолжно пойти в первую емкость, которая принимает значения с окончанием <tex>10</tex>, <tex> C </tex> но первая емкость полностью заполнена. Следовательно мы смотрим на l1. На группу <tex> A </tex> будет указывать запись <tex>00</tex> l1 = G а значит мы должны удвоить количество ячеек каталога, а увеличить глобальную глубину, затем увеличить количество последних бит по которым мы раскидываем значения на 1 и перехешировать первую емкость, разделив ее на группу <tex> C </tex> — запись <tex>01</tex> две, увеличив локальную глубину и разместив значения по новым емкостям (eсм. рис3). ИТеперь рассмотрим последнее число 26. Его двоичное представление — 11010. Последние 3 бита соответствуют третьей емкости, наконецно она также полностью заполнена как и во втором случае, группа <tex> C </tex> но ее локальная глубина меньше чем глобальная а следовательно нам надо только перехешировать емкость и т.д. (на которую указывает запись 01 каталогасм. рис4) заполняется. Нужно снова увеличить разрядную глубину каталога, на этот раз до трех разрядов.
== Использование ==
Чаще всего расширяемое хеширование используется в базах данных т.к. БД могут быть крайне большими и перехеширование всей БД займет продолжительное время при этом лишая пользователей доступа к БД. А при использовании расширяемого хеширования перехешировать придется только малые группы, что не сильно замедлит работу БД.
