Изменения

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

'''Метод расширяемого хеширования''' (англ. ''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>, удваивая при этом количество ячеек, количество указателей на емкости, а также увеличиваем количество последних бит по которым мы распределяем значения. Далее локальная глубина переполненной емкости становится меньше и мы повторяем предыдущий алгоритм то есть перехешируем емкость, разделим ее на две емкости и так далее. Для поиска емкости используется цифровое дерево.{{Определение|id=definition|definition='''Цифровое дерево поиска''' — упорядоченная структура данных, которая используется для хранения динамического множества или ассоциативного массива где ключами обычно являются строки. В отличие от двоичного дерева поиска, ни один узел в дереве не хранит ключ, связанный с этим узлом; Вместо этого, его положение в дереве определяет ключ, с которым он связан. Все потомки узла имеют общий префикс строки, связанной с этим узлом, и корень связан с пустой строкой. Значения, как правило, не связаны с каждым узлом, только с листьями и некоторыми внутренними узлами.}}

Пусть у нас есть некий каталог со своими указателями и мы хотим добавить значения <tex>9, 20, 26</tex> (см. рис1смотри рисунок №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смотри рисунок №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смотри рисунок №3). На этом работа с <tex>20</tex> закончена. Теперь рассмотрим последнее число  Последним на вход поступает значение <tex>26</tex>. Его двоичное представление — Представим его в двоичном виде: <tex>26 = 16+8+2 = 10000+1000+10 = 11010</tex>. Последние <tex>3</tex> бита (<tex>010</tex>) соответствуют третьей емкости, но она также полностью заполнена как и во втором случае, но ее локальная глубина меньше чем глобальная глубина, а следовательно нам надо только перехешировать емкость, разделив ее на две, увеличив локальную глубину и разместив значения по новым емкостям (см. рис4смотри рисунок №4). На этом работа с <tex>26</tex> закончена.

|[[Файл:FirstStep.png|мини|250px|Рис. 1рисунок №1]] |[[Файл:SecondStep.png|мини|250px|Рис. 2рисунок №2]] |[[Файл:ThirdStep.png|мини|250px|Рис. 3рисунок №3]] |[[Файл:ForthStep.png|мини|250px|Рис. 4рисунок №4]]

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

[[Категория: Дискретная математика и алгоритмы]][[Категория: Структуры данныхХеширование]]