Хеширование

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

Рассмотрим возможность такой организации. Если каждый ключ должен быть извлечен за один доступ, то положение записи внутри такой таблицы может зависеть только от данного ключа. Оно не может зависеть от расположения других ключей, как это имеет место в дереве [3].

Наиболее эффективным способом организации такой таблицы является массив, где каждая запись хранится по некоторому конкретному смещению по отношению к базовому адресу таблицы. Если ключи записей являются целыми числами, то сами ключи могут использоваться как индексы в массиве. До трех цифр ключа такой подход применим, но если ключ должен состоять из 7 цифр. Как быть в этом случае? Необходим некоторый метод преобразования ключа в какое-либо целое число внутри ограниченного диапазона. В идеале в одно и то же число не должны преобразовываться два различных ключа. К сожалению, такого идеального метода не существует.

Рассмотрим подходы, которые приближаются к идеальному. Вернемся к задаче поиска по ключу, состоящему из 7 цифр. Если использовать массив для записей, то в качестве индекса записи в этом массиве попробуем использовать три последние цифры.

Рис. 4.7. Записи, хранящиеся в массиве

Такой подход целесообразен, когда в массиве не более 1000 записей. Функция, которая трансформирует ключ в некоторый индекс таблицы, называется хеш-функцией. Если h — хеш-функция, а key — некоторый ключ, то h(key) — значение хеш-функции от ключа key и является индексом, по которому должна быть размещенна запись с ключом key. Если обозначить остаток от деления xна yкак mod(x,y), то хеш-функция для вышеприведенного примера есть h(key) = mod(key, 1000). Значения, которые выдает функция h, должны покрывать все множество индексов в таблице.

Этот метод имеет один недостаток. Предположим, что существуют два ключа k1 и k2 такие, что h(k1) = h(k2). Когда запись с ключом k1 вводится в таблицу, она вставляется в позицию h(k1). Но когда хешируется ключ k2, получаемая позиция является той же позицией, в которой хранится запись с ключом k1. Ясно, что две записи не могут занимать одну и ту же позицию. Такая ситуация называется коллизией при хешировании или столкновением. В примере, рассмотренном выше, коллизия при хешировании произойдет, если в таблицу будет добавлена запись с ключом 0596396. Далее рассмотрим возможности, как найти выход из такой ситуации. Следует отметить, что хорошей функцией является такая функция, которая минимизирует коллизии и распределяет записи равномерно по всей таблице. Поэтому желательно иметь массив размером больше, чем число реальных записей. Отметим, что определенная хеш – функция используется для заполнения информационной таблицы и по ней же потом идет поиск и, при необходимости, вставка данных.