Изменения

При частом добавлении новых значений в хеш-таблицу может возникнуть ситуация, когда хеш-таблица становится полностью заполненной и требуется перехешировать ее. При малых размерах хеш-таблицы полное перехеширование не вызовет трудностей. При больших размерах хеш-таблицы это требует большого количества времени, также если значения поступают очень часто, то требуется часто перехешировать таблицу либо выделять огромные объемы памяти, которые могут и не понадобиться, а следовательно они просто зарезервируются впустую. Также в стандартной хеш-таблице может произойти коллизия(два разных значения поступают в одну ячейку). Чтобы решить эти проблемы, а также чтобы не выделять много дополнительной памяти можно использовать расширяемое хеширование.== Структура и алгоритм =='''Метод расширяемого хеширования''' (англ. ''extendable extendible hashing'') заключается в том, что мы представляем хеш-таблицу в качестве нескольких групп, которые имеют определенное количество ячеектаблица представлена как '''каталог''' (англ. При переполнении группы нам не требуется перехешировать всю таблицу''directory''), а лишь перехешировать заполненную группу, разделив ее при этом каждая ячейка будет указывать на две группы'''емкость''' (англ. ''bucket'') которая имеет определенную '''вместимость''' (англ. capacity). Таким образом вся Сама хеш-таблица никогда не будет полностью заполненаиметь '''глобальную глубину''' (англ. К тому же при использовании данного метода использование памяти будет наиболее экономичным''global depth''), а каждая из емкостей имеет '''локальную глубину''' (англ.== Алгоритм ==Посмотрим, как работает алгоритм, на примере заполнения гипотетической хеш-таблицы''local depth''). Первоначально Глобальная глубина показывает сколько последних бит будут использоваться для того чтобы определить в таблице имеется одна группакакую емкость следует заносить значения. Предположим, что каждая группа будет содержать 10 хеш-значений А из разницы локальной глубины и номер записи каждого хешглобальной глубины можно понять сколько ячеек каталога ссылаются на емкость. Это можно показать формулой <tex>K = 2 </tex>^{<tex>G-значенияL</tex>} где <tex>G</tex> — глобальная глубина, <tex>L</tex> — локальная глубина, чтобы ее можно было извлечьа <tex>K</tex> количество ссылающихся ячеек. Для поиска емкости используется [[Wikipedia:Trie|цифровое дерево]].

Начнем вставлять Теперь рассмотрим сам алгоритм если нам поступило некоторое значение:#Переводим значение в двоичный вид, смотрим на последние <tex>G</tex> битов и решаем в таблицу хеш-значения вместе с номерами их записейкакую емкость отправить значение. При наличии только одной группы их можно вставить только в одно #Если емкость имеет свободное место, поэтому после 10 вставок группа заполняется. Разобьем заполненную группу то помещаем туда значение без всяких хлопот, если же емкость куда следует положить значение переполнена, то cмотрим на локальную глубину емкости: ##Если она меньше чем глобальная глубина то значит на емкость есть несколько указателей и нам достаточно перехешировать ее, разделив при этом на две группы одинаковых размеров и повторим вставку всех элементов исходной группы занести значения в новые две новые группыемкости увеличив у этих емкостей локальную глубину на <tex>1</tex>. Причем все элементы##Если же локальная глубина была равна глобальной то мы увеличиваем глобальную глубину на <tex>1</tex>, которые завершаются нулевым разрядомудваивая при этом количество ячеек, поместим в одну группуколичество указателей на емкости, а завершающиеся единичным разрядом — в другуютакже увеличиваем количество последних бит по которым мы распределяем значения. Эти Далее локальная глубина переполненной емкости становится меньше и мы повторяем предыдущий алгоритм то есть перехешируем емкость, разделим ее на две группы имеют емкости и так называемую '''разрядную глубину''' (англ. ''bit—depth''), равную одному разряду. Теперь при каждой вставке пары хеш-значение/номер записи она будет помещаться в первую или во вторую группу, в зависимости от последнего разряда хеш-значениядалее.

Со временем мы заполним еще одну группу. Предположим, что это группа, в которую мы вставляли все хеш-значения, завершающиеся 0. Снова разобьем группу ==Пример==Рассмотрим алгоритм на две отдельные группы. На этот раз все элементы, хеш-значения которых заканчиваются двумя нулевыми разрядами, т.е. 00, будут помещаться в первую группу, а завершающиеся разрядами 10 — во вторую группу. Обе группы имеют разрядную глубину, равную 2. Поэтому для определения места вставки необходимо проверять два младших разряда хеш-значения. Теперь у нас имеются три группы: в первую вставляются элементы, завершающиеся разрядами 00, во вторую — разрядами 10, а в третью — просто 1примере.

Предположим, что мы продолжаем вставку и заполняем группу 10. Мы снова разбиваем заполненную группу на две и повторяем вставку ее элементов в две новые группы. На этот раз две новые группы будут принимать элементы, завершающиеся разрядами 010 и 110. Таким образом, теперь Пусть у нас имеются четыре группы: одна с разрядной глубиной, равной 1есть некий каталог со своими указателями и мы хотим добавить значения <tex>9, в которую выполняется вставка хеш-значений20, завершающихся 126</tex> (смотри рисунок №1) где <tex>G</tex> — глобальная глубина, одна с разрядной глубиной равной 2 <tex>l1, содержащая хеш-значенияl2, которые завершаются разрядами 00l3, и две группы с разрядной глубинойl4</tex> — локальные глубины емкостей, равной а вместимость емкостей равна <tex>3, которые предназначены для хеш-значений, завершающихся разрядами 010 и 110</tex>.

Для поддержания отображения того, какие хеш-значения помещаются Первым на вход поступает значение <tex>9</tex>. Представим его в те или иные группы, используется структура, называемая каталогом двоичном виде: <tex>9 = 8+1 = 1000+1 = 1001</tex>. Окончание <tex>01</tex> соответствует второй ячейке значит смотрим на вторую емкость. В ней есть свободное место и мы просто помещаем <tex>9</tex> в нее (англ. ''catalogue''смотри рисунок №2). По существу каталог содержит список всех возможных окончаний групп и связных На этом работа с ними номеров групп. Вместо того чтобы поддерживать какой—либо причудливый набор значений разрядной глубины и номеров групп, выбранный методом проб и ошибок, каталог поддерживает собственное значение разрядной глубины, равное максимальной разрядной глубине группы, и имеет ячейку для каждого значения этой разрядной глубины<tex>9</tex> закончена.

В рассмотренном нами примере максимальная разрядная глубина группы была равна 3, поэтому разрядная глубина каталога также равна этому значениюДалее на вход поступает значение <tex>20</tex>. Три разряда позволяют образовать восемь комбинаций разрядовПредставим его в двоичном виде: 000, 001, 010, 011, <tex>20 = 16+4 = 10000+100, 101, 110 = 10100</tex>. Это значение оканчивается на <tex>00</tex> и 111. Все комбинациидолжно пойти в первую емкость, которые завершаются 1 (тно первая емкость полностью заполнена.еСледовательно мы смотрим на локальную глубину первой емкости то есть на <tex>l1</tex>. вторая<tex>l1 = G</tex> а значит следуя выше описанному алгоритму мы должны удвоить количество ячеек каталога, четвертаяувеличить глобальную глубину, шестая затем увеличить количество последних бит по которым мы раскидываем значения на <tex>1</tex> и восьмая)перехешировать первую емкость, указывают разделив ее на одну две, увеличив локальную глубину и ту же группу, принимающую элементы, хеш-разместив значения которых завершаются 1по новым емкостям (смотри рисунок №3). Аналогично, записи каталога для значений 000 и 100 указывают на одну и ту же группу, в которую помещаются элементы На этом работа с хеш-значениями, завершающимися разрядами 00<tex>20</tex> закончена.

Последним на вход поступает значение <tex>26</tex>. Представим его в двоичном виде: <tex>26 = 16+8+2 = 10000+1000+10 = 11010</tex>. Последние <tex>3</tex> бита (<tex>010</tex>) соответствуют третьей емкости, но она также полностью заполнена как и во втором случае, но ее локальная глубина меньше чем глобальная глубина, а следовательно нам надо только перехешировать емкость, разделив ее на две, увеличив локальную глубину и разместив значения по новым емкостям (смотри рисунок №4). На этом работа с <tex>26</tex> закончена.{|align="center" |-valign="top" |[[Файл:FirstStep.png|мини|250px|рисунок №1]] |[[Файл:SecondStep.png|мини|250px|рисунок №2]] |[[Файл:7_1ThirdStep.png|400pxмини|250px|рисунок №3]] |[[Файл:ForthStep.png|мини|Вставка в расширяемую хеш-таблицу250px|рисунок №4]] |}

==Использование =Примечание=== Однако эта схема не учитывает ряд особенностей. Две записи каталога, которые указывают на группу для элементов, хеш-значения которых завершаются разрядами 00, разделены тремя другими записями. Аналогично единственной группе, принимающей все элементы, хеш-значения которых завершаются 1, соответствуют четыре записи, равномерно распределенные по каталогу. При разбиении группы дополняющие друг друга группы не будут размещаться Чаще всего расширяемое хеширование используется в каталоге по соседствубазах данных так как. Для дальнейших рассуждений было бы проще предположить, что записи каталога, соответствующие одной группе, располагаются по соседству, чтобы Базы данных могут быть крайне большими и перехеширование всей базы данных займет продолжительное время при разбиении группы дополняющая первую группа помещалась непосредственно за ней. Для достижения этого следует инвертировать последние разряды хеш-значения при вычислении индексной записи каталога. Так, например, если хеш-значение завершается разрядами 001, при поиске мы обратимся не к записи 001 каталога, а этом лишая пользователей доступа к записи 100 (4, которая соответствует инвертированному значению 001). В результате использование каталога значительно упрощается. В нашем примере хеш-значения, которые завершаются разрядами 00, помещаются в запись каталога 000 (0) или 001 (1). Хеш-значения, которые завершаются разрядами 010, помещаются в запись каталога 010 (2). Хеш-значения, которые завершаются разрядами 011, помещаются в запись каталога 011 (3)базе данных. И, наконец, хеш-значения, которые завершаются разрядом 1, помещаются в записи 100, 101, 110 или 111 (4, 5, 6, 7). ===Визуализация=== Вернемся немного назад, и вставим элементы в пустую хеш-таблицу, как это было сделано ранее. Выполняемые А при этом действия показаны на рис. Мы начинаем с каталога использовании расширяемого хеширования перехешировать придется только с одной записью с индексом 0 (a). Принято считатьмалые группы, что в подобной ситуации разрядная глубина равна 0. Мы заполняем единственную группу (назовем ее <tex> A </tex> ) и теперь ее нужно разбить. Вначале мы увеличиваем разрядную глубину каталога до 1. Иначе говоря, теперь он будет содержать две записи (b). В результате будут созданы две группы, на первую из которых указывает запись 0 (исходная запись <tex> A </tex> ), а на вторую — запись 1, <tex> B </tex> (c)не сильно замедлит работу базы данных. Все элементы, хеш-значения которых завершаются разрядом 0, помещаются Также расширяемое хэширование хорошо работает в группу <tex> A </tex> , а остальные — условиях динамически изменяемого набора записей в группу <tex> B </tex> . Снова заполним группу <tex> A </tex> . Теперь разрядную глубину каталога необходимо увеличить с 1 до 2, чтобы получить четыре группы, доступных для вставки. Перед разделением заполненной группы записи каталога 00 и 01 будут указывать на исходную группу <tex> A </tex> , а записи 10 и 11 — на группу <tex> B </tex> (d). Группа <tex> A </tex> разбивается на группу, которая принимает хеш-значения с окончанием 00 (снова <tex> A </tex> ), и группу, которая принимает хеш-значения с окончанием 10, <tex> C </tex> . На группу <tex> A </tex> будет указывать запись 00 каталога, а на группу <tex> C </tex> — запись 01 (e). И, наконец, группа <tex> C </tex> (на которую указывает запись 01 каталога) заполняется. Нужно снова увеличить разрядную глубину каталога, на этот раз до трех разрядовхранимом файле.

*[http://en.wikipedia.org/wiki/Extendible_hashing Wikipedia — Extendible hashing][[Категория: Дискретная математика и алгоритмы]][[Категория: Структуры данныхХеширование]]