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> количество ссылающихся ячеек. Для поиска емкости используется [[Wikipedia:Trie|цифровое дерево]].
