О 14.3 Разработайте хеш-функцию для строковых ключей, основанную на идее одновременной загрузки 4 байт с последующим выполнением арифметических операций сразу над 32 разрядами. Сравните время выполнения этой функции со временем выполнения программы 14.1 для 4-, 8-, 16- и 32-байтовых ключей.

14.4 Создайте программу для определения значений а и М при минимально возможном значении М, чтобы хеш-функция а*х % М создавала различные (несовпадающие) значения для ключей, представленных на рис. 14.2. Результат является примером совершенной хеш-функции.

о 14.5 Создайте программу для вычисления функции статистического распределения для хеш-значений N ключей при размере таблицы, равном М. Это число определяется равенством

2 м V

-V 0</<Af

N М

где fi - количество ключей с хеш-значением /. Если хеш-значения являются случайными, значение этой функции статистического распределения для N > сЛ/должно быть равно М ±-\[М вероятностью 1 - 1/с.

14.6 Воспользуйтесь программой из упражнения 14.5 для вычисления хеш-функции 618033*х % 10000 для ключей, которые являются случайными положительными целыми числами, меньшими 10.

14.7 Используйте программу из упражнения 14.5 для вычисления хеш-функции из программы 14.1 для различных строковых ключей, полученных из какого-либо большого файла в системе, например, словаря.

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

14.9 Рассмотрите идею реализации модульного хеширования для целочисленных ключей с помощью соотношения (а*х) % М, где а - произвольное фиксированное простое число. Приводит ли это изменение к достаточному перемешиванию разрядов, чтобы можно было использовать значение М, не являющееся простым числом?

14.10 Докажите, что

{{{ах) mod М) + b) mod М - {ах + Ь) mod М,

при условии, что о, Ь, X W М - неотрицательные целые числа.

1> 14.11 Если в упражнении 14.7 использовать слова из текстового файла, например книги, вряд ли удастся получить хорошую функцию статистического распределения Обоснуйте справедливость этого утверждения.

14.12 Воспользуйтесь программой из упражнения 14.5 для вычисления хеш-функции 97*х % М для всех размеров таблицы в диапазоне от 100 до 200, используя в качестве ключей 10 случайных положительных целых чисел, меньших 10.

14.13 Воспользуйтесь программой из упражнения 14.5 для вычисления хеш-функции 97*х % М для всех размеров таблицы в диапазоне от 100 до 200, используя в качестве ключей целые числа в диапазоне между 10 и lOl

14.14 Воспользуйтесь программой из упражнения 14.5 для вычисления хеш-функции 100*х % М для всех размеров таблицы в диапазоне от 100 до 200, используя в качестве ключей 10 случайных положительных целых чисел, меньших 10.

14.15 Выполните упражнения 14.12 и 14.14, но реализуйте более простой критерий отбрасывания хеш-функций, которые создают любое значение более ЗЛ/Л/ раз.

14.2 Раздельное связывание

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

Программа 14.3 Хеширование с помощью раздельного связывания

Эта реализация таблицы символов сводится к замене конструктора ST, функций search и insert в основанный на связном списке таблице символов из программы 12.6 на приведенные здесь функции и к замене связи head на массив связей heads. В этой программе используются такие же рекурсивные процедуры поиска и удаления в списке, как и в программе 12.6, но при этом поддерживается М списков с заглавными связями в heads, с использованием хеш-функции для выбора между списками. Конструктор устанавливает М так, что каждый список должен содержать около пяти элементов; поэтому для выполнения остальных операций требуется всего несколько проверок.

private:

link* heads;

int N, M; public:

ST(int maxN) {

N = 0; M = maxN/5; heads = new link[M] ;

for (int i = 0; i < M; i++) heads[i] = 0;

Item search(Key v)

{ return searchR(heads[hash (v, M)], v); } void insert(Item item)

{ int i = hash (item, key 0 , M) ;

heads[i] = new node(item, heads[i]); N++; }

Метод Традиционно называется раздельным связыванием (separate chaining), поскольку конфликтующие элементы объединяются в отдельные связные списки (см. рис. 14.6).

Как и в случае элементарного последовательного поиска, эти списки можно хранить упорядоченными или оставить неупорядоченными. При этом приходится идти на те же основные компромиссы, что и описанные в разделе 12.3, но для раздельного связывания экономия времени имеет меньшее значение (поскольку списки невелики), а экономия памяти - более важна (поскольку имеется много списков).

Для упрощения кода вставки в упорядоченный список можно было бы использовать начальный узел, но применение М начальных узлов для отдельных списков при раздельном связывании может быть нежелательно. Действительно, можно было бы даже исключить М связей на эти списки, объединив первые узлы списков в таблицу (см. упражнение 14.20).

Для случая промаха при поиске можно считать, что хеш-функция достаточно равномерно перемешивает значения ключей, чтобы поиск в каждом из М списков был равновероятным. Тогда характеристики производительности, рассмотренные в разделе 12.3, применимы к каждому списку.

Лемма 14.1 Раздельное связывание уменьшает количество выполняемых при последовательном поиске сравнений в М раз (в среднем) при использовании дополнительного объема памяти для М связей.

ASERCH I NGXMPL 0204442212433

РИСУНОК 14.6 ХЕШИРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ РАЗДЕЛЬНОГО СВЯЗЫВАНИЯ

На диаграмме показан результат вставки ключей А S ER CHINGXMPLe первоначально пустую хеш-таблицу с помош,ью раздельного связывания (неупорядоченных списков) с использованием хеш-значений, приведенных на верхнем рисунке. А помещается в список О, затем S помещается в список 2, Е ~ в список О (в его начало, с целью поддержания постоянства времени вставки), R - в список 4 и т.д.

Средняя длина списков равна N/M. Как было описано в главе 12, ожидается, что успешные поиски будут доходить приблизительно до середины какого-либо списка. Безрезультатные поиски будут доходить до конца списка, если списки неупорядо-чены, и до половины списка, если они угюрядочены.

Чаще всего для раздельного связывания используются неупорядоченные списки, поскольку этот подход прост в реализации и эффективен: для выполнения операции insert требуется постоянное время, а для выполнения операции searcli - время, пропорциональное N/M. Если ожидается очень большое количество промахов при поиске, обнаружение промахов можно ускорить в два раза, храня списки в упорядоченном виде, ценой замедления операции insert.

В приведенном виде лемма 14.1 тривиальна, поскольку средняя длина списков равна N/M независимо от распределения элементов по спискам. Например, предположим, что все элементы попадают в первый список. Тогда средняя длина списков рав-на (jV + О + О + ... + 0) / Л/ = jV / Л/. Истинная причина практической полезности хеширования заключается в toM, что вероятность наличия в каждом списке около N/M элементов очень высока.