Изменения

'''Метод расширяемого хеширования''' (англ. ''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> количество ссылающихся ячеек. Если емкость имеет свободное место, то помещаем туда значение без всяких хлопот, если же емкость куда следует положить значение переполнена, то смотрим на локальную глубину емкости. Если она меньше чем глобальная глубина то значит на емкость есть несколько указателей и нам достаточно перехешировать ее, разделив при этом на две и занести значения в новые две емкости увеличив у этих емкостей локальную глубину на <tex>1</tex>. Если же локальная глубина была равна глобальной то мы увеличиваем глобальную глубину на <tex>1</tex>, удваивая при этом количество ячеек, количество указателей на емкости, а также увеличиваем количество последних бит по которым мы распределяем значения. Далее локальная глубина переполненной емкости становится меньше и мы повторяем предыдущий алгоритм то есть перехешируем емкость, разделим ее на две емкости и так далее. Для поиска емкости используется [[Wikipedia:Trie|цифровое дерево]].{{Определение|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]]

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