Хеширование

Хеширование - один из принципов идентификации информации на ос-

нове отождествления символьного ключа с числом. Занесение в таблицу,

поиск и удаление элементов выполняется по данному числу. Его значение

вычисляется в соответствии с выбранной хеш-функцией. Примеры хеш-

функций:

- остаток от деления суммы всех кодов символов, составляющих ключ,

на размер таблицы;

- остаток от деления суммы всех кодов символов по модулю 2 на раз-

мер таблицы.

Таблица строится на основе одномерного массива. Полученное число

рассматривается как индекс, определяющий положение элемента в таблице.

Значение хеш-функции в данном случае должно не превышать размер вы-

деляемого под таблицу массива. Для этого, как правило, и выделяется оста-

ток от деления полученного числа на размер таблицы_.

Естественно, что при таком подходе к занесению элементов существу-

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

(например, хеш-функция типа "суммирование кодов символов" будет

иметь одинаковое значение для имен А2 и В1). В этом случае необходимо

осуществлять эффективное разрешение конфликтов. Среди известных мето-

дов разрешения подобных конфликтов наиболее распространены следующие:

- специальный подбор формулы для хеш-функции, обеспечивающей

более бесконфликтное размещение элементов в таблице (этот подбор явля-

ется достаточно трудоемкой задачей);

- выбор в качестве размера таблицы простого числа, что позволяет

улучшить распределение элементов, но увеличивает затраты на вычисление

хеш-функции (если размер таблицы кратен двум в степени N, то вычисление

модуля заменяется сдвигами числа).

- элемент таблицы, который соответствует полученному значению

хеш-функции, является указателем на список элементов с одинаковыми

значениями хеш-функ ции. Работа с этим списком ведется в соответствии с

алгоритмами, описанными выше;

- если существует конфликт с уже имеющимся элементом, то новый

элемент заносится в таблицу на ближайшее свободное место.

Каждый из приведенных методов разрешения конфликтов имеет свои

преимущества. Однако им также присущи определенные недостатки, одним

из которых является рост накладных расходов на организацию поиска,

включения и удаления. Например, если при поиске элемента по заданному

ключу окажется, что искомая строка в таблице имен уже занята, необходи-

мо первоначально убедиться в том, что в ней находится элемент с тем же

ключом. Если это не так, то приходится в дальнейшем последовательно пе-

ребирать все элементы ниже найденного до тех пор, пока не будет найден

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

ширования еще более усложняется, когда включение в таблицу и удаление из

нее происходят в произвольных комбинациях. В этих случаях элементы с од-

ним значением хеш-числа, для упрощения операций с ними, желательно объ-

единять в подсписок путем введения дополнительного поля_.Тогда переход

от одного элемента к другому, после нахождения начала подсписка, будет

осуществляться быстрее.

Преимущества. Быстрота формирования индексов элемента для раз-

реженных таблиц.

Недостатки. Необходимость разрешения конфликтов, что замедляет в

ряде случаев поиск элементов и их занесение в таблиц. Метод более удобен

при последующем массовом удалении элементов.