Изменения

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

Со временем мы заполним еще одну группу. Предположим, что это Когда группа, в которую мы вставляли все значения, завершающиеся 0. Снова заполнится разобьем группу ее на две отдельные группы одинаковых размеров и повторим вставку всех элементов исходной группы в две новые группы. На этот раз Причем все элементы, значения которых заканчиваются двумя нулевыми разрядамикоторые завершаются нулевым разрядом, т.е. <tex>00</tex>, будут помещаться поместим в первую одну группу, а завершающиеся разрядами <tex>10</tex> единичным разрядом — во вторую группув другую. Обе Эти две группы имеют так называемую '''разрядную глубину''' (англ. ''bit—depth''), равную 2. Поэтому для определения места вставки необходимо проверять два младших разряда значенияодному разряду. Теперь у нас имеются три группы: при каждой вставке пары значение/номер записи она будет помещаться в первую вставляются элементы, завершающиеся разрядами <tex>00</tex>, или во вторую — разрядами группу, в зависимости от последнего разряда значения. При заполнении группы с глубиной <tex>101</tex>будет использоваться предпоследний разряд, а в третью — просто при заполнении группы с глубиной <tex>12</tex>. И пред-предпоследний разряд и так далее.

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

Для достижения этого следует инвертировать последние разряды хеш-значения при вычислении индексной записи каталога. Так, например, если хеш-значение завершается разрядами <tex>001</tex>, при поиске мы обратимся не к записи <tex>001</tex> каталога, а к записи <tex>100</tex> (<tex>4</tex>, которая соответствует инвертированному значению <tex>001</tex>). В результате использование каталога значительно упрощается.