Изменения

'''Метод расширяемого хеширования''' (англ. ''extendible extendable hashing'') предусматривает изменение размеров блоков по мере роста базы данныхзаключается в том, но это компенсируется оптимальным использованием местачто мы представляем хеш-таблицу в качестве нескольких групп, которые имеют определенное количество ячеек. При переполнении группы нам не требуется перехешировать всю таблицу, а лишь перехешировать заполненную группу, разделив ее при этом на две группы. ТТаким образом вся хеш-таблица никогда не будет полностью заполнена.кК тому же при использовании данного метода использование памяти будет наиболее экономичным. за один раз разбивается не более одного блока, накладные расходы достаточно малы

Посмотрим, как работает алгоритм, на примере заполнения гипотетической хеш-таблицы. Первоначально в таблице имеется одна группа. Предположим, что каждая группа будет содержать 10 хеш-значений и номер записи каждого хеш-значения, чтобы ее можно было извлечь. Обратите внимание, что мы не помещаем в группы сами ключи. При использовании 32-разрядных хеш-значений, маловероятно, чтобы два ключа хешировались в одно и то же значение. (Фактически это будет происходить настолько редко, что для проверки ключей можно извлечь саму запись без заметного замедления всего процесса. Естественно, при этом предполагается, что используемая хеш-функция успешно справляется с рандомизацией.)

Начнем вставлять в таблицу хеш-значения вместе с номерами их записей. При наличии только одной группы их можно вставить только в одно место, поэтому после 10 вставок группа заполняется. Разобьем заполненную группу на две группы одинаковых размеров и повторим вставку всех элементов исходной группы в две новые группы. Причем все элементы, которые завершаются нулевым разрядом, поместим в одну группу, а завершающиеся единичным разрядом - — в другую. Эти две группы имеют так называемую '''разрядную глубину ''' (англ. ''bit-depthbit—depth''), равную одному разряду. Теперь при каждой вставке пары хеш-значение/номер записи она будет помещаться в первую или во вторую группу, в зависимости от последнего разряда хеш-значения.

Со временем мы заполним еще одну группу. Предположим, что это группа, в которую мы вставляли все хеш-значения, завершающиеся 0. Снова разобьем группу на две отдельные группы. На этот раз все элементы, хеш-значения которых заканчиваются двумя нулевыми разрядами, т.е. 00, будут помещаться в первую группу, а завершающиеся разрядами 10 - — во вторую группу. Обе группы имеют разрядную глубину, равную 2. Поэтому для определения места вставки необходимо проверять два младших разряда хеш-значения. Теперь у нас имеются три группы: в первую вставляются элементы, завершающиеся разрядами 00, во вторую -— разрядами 10, а в третью - — просто 1.

Для поддержания отображения того, какие хеш-значения помещаются в те или иные группы, используется структура, называемая каталогом (англ. ''catalogue''). По существу каталог содержит список всех возможных окончаний групп и связных с ними номеров групп. Вместо того чтобы поддерживать какой-либо какой—либо причудливый набор значений разрядной глубины и номеров групп, выбранный методом проб и ошибок, каталог поддерживает собственное значение разрядной глубины, равное максимальной разрядной глубине группы, и имеет ячейку для каждого значения этой разрядной глубины.

Вернемся немного назад, и вставим элементы в пустую хеш-таблицу, как это было сделано ранее. Выполняемые при этом действия показаны на рис. Мы начинаем с каталога только с одной записью с индексом 0 (аa). Принято считать, что в подобной ситуации разрядная глубина равна 0. Мы заполняем единственную группу (назовем ее А <tex> A </tex> ) и теперь ее нужно разбить. Вначале мы увеличиваем разрядную глубину каталога до 1. Иначе говоря, теперь он будет содержать две записи (b). В результате будут созданы две группы, на первую из которых указывает запись 0 (исходная запись А <tex> A </tex> ), а на вторую - — запись 1, В <tex> B </tex> (сc). Все элементы, хеш-значения которых завершаются разрядом 0, помещаются в группу А <tex> A </tex> , а остальные - — в группу В <tex> B </tex> . Снова заполним группу <tex> A</tex> . Теперь разрядную глубину каталога необходимо увеличить с 1 до 2, чтобы получить четыре группы, доступных для вставки. Перед разделением заполненной группы записи каталога 00 и 01 будут указывать на исходную группу А <tex> A </tex> , а записи 10 и 11 - — на группу В <tex> B </tex> (d). Группа А <tex> A </tex> разбивается на группу, которая принимает хеш-значения с окончанием 00 (снова А <tex> A </tex> ), и группу, которая принимает хеш-значения с окончанием 10, С <tex> C </tex> . На группу А <tex> A </tex> будет указывать запись 00 каталога, а на группу С - <tex> C </tex> — запись 01 (e). И, наконец, группа С <tex> C </tex> (на которую указывает запись 01 каталога) заполняется. Нужно снова увеличить разрядную глубину каталога, на этот раз до трех разрядов.

*Бакнелл Джулиан --- — Фундаментальные алгоритмы и структуры данных в Delphi — стр. 50.*Дейт К. Дж. — Введение в системы баз данных, 8- е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — стр. 501236.