Хеш-функции для строк переменной длины

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

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

Рассмотрим для примера одну из самых простых хеш-функций для строки S (M — размер хеш-таблицы):

int h(char *S, int M)

{ int i, sum=0;

for (i=1; i<= 10; i++) sum = sum + S[i];

return sum%M;

}

В данной функции суммируются коды первых 10 символов и берётся остаток от деления этой суммы на размер хеш-таблицы. Хотелось бы знать, насколько разными получаются значения хеш-адресов при использовании этой функции.

Возьмем 100 следующих строк: “A0”, “A1”, “A2”,…,”A99”. Легко проверить, что при обработке этих 100 строк будет получено всего 28 различных хеш-адресов из 100 возможных. Это означает, что на таких специфических входных данных рассмотренная функция работает не очень эффективно, хотя для случайно взятых текстов она вполне приемлема. В [14] можно найти еще несколько вариантов более сложных хеш-функций для строк. Ниже будет разбираться пример реализации хеш-таблицы, в котором используется хеш-функция, взятая из [16], которая, по мнению авторов, гораздо более равномерно распределяет данные из реальных текстовых файлов по хеш-таблице, чем способ простого суммирования кодов символов.

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

Метод цепочек

Наиболее простой и естественный способ разрешения коллизий состоит в том, что все элементы с одинаковыми хеш-адресами объединяются в связный список (хеш-цепочку). Тогда хеш-таблица представляет собой массив из N указателей на хеш-цепочки. Такая структура показана на рис. 521.

Рис.5.21. Хеш –таблица при использовании метода цепочек

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

Если исходное множество данных состоит из K элементов, а размер массива указателей N, то средняя длина списков будет K/N элементов. Если можно оценить среднее значение K, то можно выбрать N так, чтобы в каждом списке было всего несколько элементов. Тогда время выполнения всех операций будет малой постоянной величиной. Если размер исходного множества непредсказуем или динамично изменяется, данный метод применять не рекомендуется.

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

typedef int T_key; //тип ключа, может быть любым

typedef char T_data;//тип связанных данных, любой

struct item //структура элемента данных – ключ и связанные данные

{ T_key key; //ключ

T_data data; //связанные данные

};

struct h_item //структура элемента хеш-цепочки

{ item data; // элемент данных

h_item *next; //ссылка на следующий элемент

}

h_item *h_table[размер массива указателей] //массив указателей на хеш-цепочки

Пример реализации хеш-таблицы для решения конкретной задачи будет приведен ниже.