Изменения

При частом добавлении новых значений в хеш-таблицу может возникнуть ситуация, когда хеш-таблица становится полностью заполненной и требуется перехешировать ее. При малых размерах хеш-таблицы полное перехеширование не вызовет трудностей. При больших размерах хеш-таблицы это требует большого количества времени, также если значения поступают очень часто, то требуется часто перехешировать таблицу либо выделять огромные объемы памяти, которые могут и не понадобиться, а следовательно они просто зарезервируются впустую. Также в стандартной хеш-таблице может произойти коллизия(два разных значения поступают в одну ячейку). Чтобы решить эти проблемы, а также чтобы не выделять много дополнительной памяти можно использовать расширяемое хеширование.== Структура и алгоритм =='''Метод расширяемого хеширования''' (англ. ''extendible hashing'') предусматривает изменение размеров блоков по мере роста базы данныхзаключается в том, но это компенсируется оптимальным использованием места. Т.к. за один раз разбивается не более одного блока, накладные расходы достаточно малы== Алгоритм ==Посмотрим, как работает алгоритм, на примере заполнения гипотетической что хеш-таблицытаблица представлена как '''каталог''' (англ. Первоначально в таблице имеется одна группа. Предположим''directory''), что а каждая группа ячейка будет содержать 10 указывать на '''емкость''' (англ. ''bucket'') которая имеет определенную '''вместимость''' (англ. capacity). Сама хеш-значений и номер записи каждого хеш-значениятаблица будет иметь '''глобальную глубину''' (англ. ''global depth''), чтобы ее можно было извлечьа каждая из емкостей имеет '''локальную глубину''' (англ. Обратите внимание, что мы не помещаем в группы сами ключи''local depth''). При использовании 32-разрядных хеш-значений, маловероятно, Глобальная глубина показывает сколько последних бит будут использоваться для того чтобы два ключа хешировались определить в одно какую емкость следует заносить значения. А из разницы локальной глубины и то же значениеглобальной глубины можно понять сколько ячеек каталога ссылаются на емкость. (Фактически это будет происходить настолько редко, что для проверки ключей Это можно извлечь саму запись без заметного замедления всего процесса. Естественнопоказать формулой <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 (а). Принято считатьмалые группы, что в подобной ситуации разрядная глубина равна 0. Мы заполняем единственную группу (назовем ее А) и теперь ее нужно разбить. Вначале мы увеличиваем разрядную глубину каталога до 1. Иначе говоря, теперь он будет содержать две записи (b)не сильно замедлит работу базы данных. В результате будут созданы две группы, на первую из которых указывает запись 0 (исходная запись А), а на вторую - запись 1, В (с). Все элементы, хеш-значения которых завершаются разрядом 0, помещаются Также расширяемое хэширование хорошо работает в группу А, а остальные - условиях динамически изменяемого набора записей в группу В. Снова заполним группу A. Теперь разрядную глубину каталога необходимо увеличить с 1 до 2, чтобы получить четыре группы, доступных для вставки. Перед разделением заполненной группы записи каталога 00 и 01 будут указывать на исходную группу А, а записи 10 и 11 - на группу В (d). Группа А разбивается на группу, которая принимает хеш-значения с окончанием 00 (снова А), и группу, которая принимает хеш-значения с окончанием 10, С. На группу А будет указывать запись 00 каталога, а на группу С - запись 01 (e). И, наконец, группа С (на которую указывает запись 01 каталога) заполняется. Нужно снова увеличить разрядную глубину каталога, на этот раз до трех разрядовхранимом файле.

*[http://src-codeБакнелл Джулиан — Фундаментальные алгоритмы и структуры данных в Delphi — стр.net/rasshiryaemyj-metod-xeshirovaniya/ http://src-code50.net - Расширяемый метод хеширования]*Дейт К. Дж., — Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 1236.*[http://en.wikipedia.org/wiki/Extendible_hashing Wikipedia — Extendible hashing][[Категория: Дискретная математика и алгоритмы]][[Категория: Хеширование]][[Категория: Структуры Базы данных]]