Изменения

При частом добавлении новых значений в хеш-таблицу может возникнуть ситуация, когда хеш-таблица становится полностью заполненной и требуется перехешировать ее. Но при При малых размерах хеш-таблицы полное перехеширование не вызовет трудностей. При больших размерах хеш-таблицы это требует большого количества времени, также если значения поступают очень часто, то требуется часто перехешировать таблицу либо выделять огромные объемы памяти, которые могут и не понадобиться, а следовательно они просто зарезервируются впустую. Также в стандартной хеш-таблице может произойти коллизия(два разных значения поступают в одну ячейку). Чтобы решить эту проблемуэти проблемы, а также чтобы не выделять много дополнительной памяти можно использовать расширяемое хеширование.

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

<div class="tright" style="clear:none">[[Файл:SecondStepРассмотрим алгоритм на примере.png|мини|250px|рис2]]</div><div class="tright" style="clear:none">[[Файл:FirstStep.png|мини|250px|рис1]]</div>

Рассмотрим алгоритм Пусть у нас есть некий каталог со своими указателями и мы хотим добавить значения <tex>9, 20, 26</tex> (смотри рисунок №1) где <tex>G</tex> — глобальная глубина, <tex>l1, l2, l3, l4</tex> — локальные глубины емкостей, а вместимость емкостей равна <tex>3</tex>. Первым на вход поступает значение <tex>9</tex>. Представим его в двоичном виде: <tex>9 = 8+1 = 1000+1 = 1001</tex>. Окончание <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>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]] |[[Файл:ThirdStep.png|мини|250px|рисунок №3]] |[[Файл:ForthStep.png|мини|250px|рисунок №4]] |}

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

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