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

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

В данном случае h(key) = key mod 1000;

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

Рассмотренный метод создания хеш-таблицы имеет один недостаток.

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

В примере с записями о деталях коллизия при хешировании произойдет, если в таблицу будет добавлена запись с ключом 0596397.

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

Совершенная хеш-функция - эта функция, которая не порождает коллизий.

Разрешить коллизии при хешировании можно 2 методами:

методом открытой адресации;

методом цепочек.

Основная трудность, связанная с преобразованием ключей, заключается в том, что множество возможных значений значительно шире множества допустимых адресов памяти (индексов массива). Возьмем в качестве примера имена, включающие до 16 букв и представляющие собой ключи, идентифицирующие отдельные индивиды из множества в тысячу персон. Следовательно, мы имеем дело с 2616 возможными ключами, которые нужно отобразить в 103 возможных индексов. Поэтому функция Н будет функцией класса «много значений в одно значение». Если дан некоторый ключ k, то первый шаг операции поиска — вычисление связанного с ним индекса h = H(k), а второй (совершенно необходимый) — проверка, действительно ли h идентифицирует в массиве (таблице) Т элемент с ключом k.

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