Следовательно, для разделения страницы мы создаем новую страницу, затем помещаем все элементы, для которых данный разряд равен О, на старую страницу, а все элементы, для которых он равен 1 - на новую страницу, и, наконец, устанавливаем значение счетчика разрядов равным к + 1 для обоих страниц. Возможен случай, когда все ключи имеют одинаковое значение разряда к, что привело бы к наличию заполненного узла. В этом случае мы просто перешли бы к следующему разряду, продолжая процесс до тех пор, пока каждая страница не будет содержать, по меньшей мере, один элемент. Со временем процесс должен завершиться, если только не имеется М значений одного и того же ключа. Вскоре мы рассмотрим и этот случай.

Как и в случае В-деревьев, на каждой странице остается свободное место, чтобы можно было выполнять разделение после вставки; это упрощает код. Следует снова отметить, что эта технология имеет небольшое практическое значение, и ее влиянием можно пренебречь при анализе.

При создании новой страницы в каталог необходимо вставить указатель на нее. Выполняющий эту вставку код представлен в программе 16.8. Простейшим является случай, когда перед вставкой каталог содержит ровно два указателя на страницу, которая разделяется. В этом случае нужно всего лишь обеспечить, чтобы второй указатель ссылался на новую страницу. Если количество разрядов к, которое требуется для различения ключей на новой странице, превышает количество разрядов d, имеющееся для доступа к каталогу, размер каталога нужно увеличить, чтобы в нем могла поместиться новая запись. И, в завершение, указатели каталога обновляются соответствующим образом.

Программа 16.8 Ваавка в каталог расширяемого хеширования

Этот обманчиво простой код лежит в основе процесса расширяемого хеширования. У нас имеется связь t с узлом, содержащим элементы, первые к разрядов которых совпадают, которую требуется вставить в каталог. В простейшем случае, когда значения d и к равны, достаточно просто поместить t в d[x3, где х - значение первых d разрядов t->b[0] (и всех остальных элементов на странице). Если к больше d, размер каталога следует удвоить, пока не будет достигнуто равенство значений d и к. Если к меньше d, необходимо установить более одного указателя - в первом цикле for вычисляется количество указателей, которые необходимо установить (2 *), а во втором выполняется собственно установка.

void insertDIR(link t, int к) { int i, m, X = bits (t->b[0] .key 0 , 0, k) ; while (d < k)

{ link *old = dir; d += 1; D += D; dir = new link[D];

for (i = 0; i < D; i++) dir[i] = old[i/2] ; if (d < k) dir[bits(x, 0, d) 1] = new node;

for (m = 1; к < d; k++) m *= 2;

for (i = 0; i < m; i++) dir[x*m+i] = t;

Если более М элементов имеют дублированные ключи, таблица переполняется и программа 16.7 входит в бесконечный цикл, пытаясь найти способ различения ключей. С этим же тесно связана проблема, заключающаяся в том, что каталог может

оказаться неоправданно большим, если ключи имеют излишнее количество совпадающих ведущих разрядов. Для файлов, которые имеют большое количество дублированных ключей или длинные цепочки разрядных позиций, в которых они совпадают, эта ситуация сродни излишнему времени, требуемому для выполнения поразрядной сортировки сначала по старшей цифре. Для преодоления этих проблем приходится рассчитывать на рандомизацию, обеспечиваемую хеш-функцией (см. упражнение 16.43). При наличии большого количества дублированных ключей, даже при использовании хеширования, приходится предпринимать экстраординарные действия, поскольку хеш-функции отображают равные ключи на равные хеш-значения. Дублированные ключи могут сделать каталог неестественно большим; кроме того, алгоритм полностью разрушается при наличии большего количества равных ключей, чем помещается на одной странице. Следовательно, прежде чем использовать этот код, необходимо добавить проверки, предотвращающие возникновение упомянутых условий (см. упражнение 16.35).

С точки зрения произродительности наибольший интерес представляют количество используемых страниц (как и в случае В-деревьев) и размер каталога. Для этого алгоритма рандомизация обеспечивается хеш-функциями, поэтому характеристики производительности, определенные для среднего случая, сохраняются для любой последовательности N различных вставок.

Лемма 16.5 При использовании страниц, которые могут содержать М элементов, для реализации расширяемого хеширования для файла, содержаиего N элементов, в среднем требуется около \.AA{N/M) страниц. Ожидаемое количество записей в каталоге приблизительно равно 3.92(N ){N/M).

Этот (достаточно обоснованный) результат дополняет анализ trie-деревьев, кратко рассмотренный в предыдущей главе {см. раздел ссылок). Точные значения констант для количества страниц и размера каталога соответственно равны Ige = 1/1п2 и elge = е/1п2, поэтому точные значения величин колеблются вокруг указанных средних значений. Это не должно вызывать удивления, поскольку, например, размер каталога должен являться степенью 2 - факт, который в результате должен приниматься во внимание.

Обратите внимание, что размер каталога возрастает быстрее, нежели линейно по отношению к Л, особенно при малых значениях М. Однако, для значений N и М, представляющих практический интерес, значение достаточно близко к 1, поэтому реально можно ожидать, что каталог будет иметь около 4{N/Af) записей.

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

Подобно тому, как это делалось для В-деревьев, реализация остальных операций таблицы символов оставлена в качестве упражнений (см. упражнения 16.38 и 16.41). Так же как и в случае В-деревьев, правильная реализация операции remove представляет собой сложную задачу, но разрешение наличия незаполненных страниц - легко реализуемая альтернатива, которая может оказаться эффективной во многих возникающих на практике ситуациях.

Упражнения

t> 16.27 Сколько страниц были бы пустыми, если бы на рис. 16.10 использовался каталог, размер которого равен 32?

16.28 Постройте рисунки, соответствующие рис. 16.11-16.13, иллюстрирующие процесс вставки ключей 562, 221, 240, 771, 274, 233, 401, 273 и 201 в указанном порядке в первоначально пустое дерево, при Л/ = 5.

о 16.29 Постройте рисунки, соответствующие рис. 16.11-16.13, иллюстрирующие процесс вставки ключей 562, 221, 240, 771, 274, 233, 401, 273 и 201 в обратном порядке в первоначально пустое дерево, при Л/ = 5.

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

16.31 Создайте программу, которая строит расширяемую хеш-таблицу из массива упорядоченных элементов, выполняя два прохода по элементам: один для определения размера каталога (см. упражнение 16.30) и второй для распределения элементов по страницам и заполнения каталога.

о 16.32 Приведите набор ключей, для которого соответствующая расширяемая хеш-таблица имеет каталог размером 16 при размещении восьми указателей на одной странице.

16.33 Создайте для расширяемого хеширования рисунок, подобный рис. 16.8.

16.34 Создайте программу для вычисления среднего количества внешних страниц и среднего размера каталога для расширяемой хеш-таблицы, построенной в результате N случайных вставок в первоначально пустое дерево, при емкости страницы М. Вычислите долю пустого пространства в процентах при М = 10, 100 и 1000 иЛГ= 10 10\ 10Ч 10

16.35 Добавьте в программу 16.7 соответствующие проверки с целью предотвращения неправильной работы в случае вставки в таблицу слишком большого количества дублированных ключей или ключей, у которых совпадет слишком много ведущих разрядов.

16.36 Измените реализацию расширяемого хеширования, приведенную в программах 16.5-16.7, чтобы в ней использовался двухуровневый каталог, в каждом узле которого содержится не более М указателей. Обратите особое внимание на действия, предпринимаемые, когда каталог впервые разрастается с одноуровневого до двухуровневого.

16.37 Измените реализацию расширяемого хеширования, приведенную в программах 16.5-16.7, чтобы в структуре данных на одной странице могло существовать М элементов.

о 16.38 Реализуйте операцию sort для расширяемой хеш-таблицы.

о 16.39 Реализуйте операцию select для расширяемой хеш-таблицы.

16.40 Реализуйте операцию remove для расширяемой хеш-таблицы.

о 16.41 Реализуйте операцию remove для расширяемой хеш-таблицы, используя метод, указанный в упражнении 16.25.