Изменения

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

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

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

Для поддержания отображения того, какие Пусть у нас есть некий каталог со своими указателями и мы хотим добавить значения помещаются в те или иные группы<tex>9, используется структура20, называемая каталогом 26</tex> (англ. ''catalogue''смотри рисунок №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]]==Пример== |}

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

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