29
правок
Изменения
Нет описания правки
При частом добавлении новых значений в хеш-таблицу может возникнуть ситуация, когда хеш-таблица становится полностью заполненной и требуется перехешировать ее. Но при При малых размерах хеш-таблицы полное перехеширование не вызовет трудностей. При больших размерах хеш-таблицы это требует большого количества времени, также если значения поступают очень часто то требуется часто перехешировать таблицу либо выделять огромные объемы памяти, которые могут и не понадобиться. Чтобы решить эту проблему, а также чтобы не выделять много дополнительной памяти можно использовать расширяемое хеширование.
== Структура и алгоритм ==
'''Метод расширяемого хеширования''' (англ. ''extendible hashing'') заключается в том, что хеш-таблица представлена как каталог (англ. ''directory''), а каждая ячейка будет указывать на емкость (англ. ''bucket'') которая имеет определенную вместимость (англ. capacity). Сама хеш-таблица будет иметь глобальную глубину (англ. ''global depth''), а каждая из емкостей имеет локальную глубину (англ. ''local depth''). Глобальная глубина показывает сколько последних бит будут использоваться для того чтобы определить в какую емкость следует заносить значения. А из разницы локальной глубины и глобальной глубины можно понять сколько ячеек каталога ссылаются на емкость. Это можно показать формулой <tex>K = 2 </tex><sup><tex>G-L</tex></sup> где <tex>G</tex> — глобальная глубина, <tex>L</tex> — локальная глубина, а <tex>K</tex> количество ссылающихся ячеек. Если емкость куда следует положить значение переполнена, то смотрим на локальную глубину емкости. Если она меньше чем глобальная глубина то значит на емкость есть несколько указателей и нам достаточно перехешировать ее, разделив при этом на две и занести значения в новые две емкости увеличив у этих емкостей локальную глубину на <tex>1</tex>. Если же локальная глубина была равна глобальной то мы увеличиваем глобальную глубину на <tex>1</tex>, удваивая при этом количество ячеек, количество указателей на емкости, а также увеличиваем количество последних бит по которым мы распределяем значения. Далее локальная глубина переполненной емкости становится меньше и мы знаем что дальше делать. Для поиска емкости используется цифровое дерево.
|id=definition
|definition=
'''Цифровое дерево поиска''' — упорядоченная структура данных, которая используется для хранения динамического множества или ассоциативного массив массива где ключами обычно являются строки. В отличие от двоичного дерева поиска, ни один узел в дереве не хранит ключ, связанный с этим узлом; Вместо этого, его положение в дереве определяет ключ, с которым он связан. Все потомки узла имеют общий префикс строки, связанной с этим узлом, и корень связан с пустой строкой. Значения, как правило, не связаны с каждым узлом, только с листьями и некоторыми внутренними узлами.
}}
==Пример==
*Бакнелл Джулиан — Фундаментальные алгоритмы и структуры данных в Delphi — стр. 50.
*Дейт К. Дж. — Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 1236.
*[http://en.wikipedia.org/wiki/Extendible_hashing Wikipedia — Extendible hashing]
[[Категория: Дискретная математика и алгоритмы]][[Категория: Структуры данных]]
