Введение

Хеширование

 

 

При использовании методов поиска, относящихся к двоичным деревьям, число итераций в лучшем случае пропорционально высоте дерева поиска, т.е. O(log n). Естественно, возникает желание найти такой метод поиска, при котором число итераций не зависело бы от объема хранимых данных, а в идеальном случае поиск сводился бы к одному шагу.

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

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

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

Назовем пространством ключей множество всех теоретически возможных значений ключей записи. Назовем пространством записей множество тех ячеек памяти, которые выделяются для хранения таблицы.

Таблицы прямого доступа применимы только для таких задач, в которых размер пространства записей может быть равен размеру пространства ключей. В большинстве реальных задач, однако, размер пространства записей много меньше, чем пространства ключей. Так, если в качестве ключа используется фамилия, то, даже ограничив длину ключа 10 символами кириллицы, получаем 33¹⁰ возможных значений ключей. Даже если ресурсы вычислительной системы и позволят выделить пространство записей такого размера, то значительная часть этого пространства будет заполнена пустыми записями, так как в каждом конкретном заполнении таблицы фактическое множество ключей не будет полностью покрывать пространство ключей.

Из соображений экономии памяти целесообразно назначать размер пространства записей равным размеру фактического множества записей или превосходящим его незначительно. В этом случае необходимо иметь некоторую функцию, обеспечивающую отображение точки из пространства ключей в точку в пространстве записей, то есть, преобразование ключа в адрес записи: a := h(k), где a – адрес, k – ключ. Такая функция называется функцией хеширования (другие ее названия – функция перемешивания, функция рандомизации).

Идеальной хеш-функцией является такая функция, которая для любых двух неодинаковых ключей дает неодинаковые адреса: k1 ¹ k2 Þ h(k1) ¹ h(k2).

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

Если хеш-функция, преобразующая ключ в адрес, может порождать коллизии, то однозначной обратной функции: k := h’(a), позволяющей восстановить ключ по известному адресу, существовать не может. Поэтому ключ должен обязательно входить в состав записи хешированной таблицы как одно из ее полей.

К хеш-функции в общем случае предъявляются следующие требования:

- она должна обеспечивать равномерное распределение отображений фактических ключей по пространству записей (см. рис. 4.1);

- она должна порождать как можно меньше коллизий для данного фактического множества записей;

- она не должна отображать какую-либо связь между значениями ключей в связь между значениями адресов;

- она должна быть простой и быстрой для вычисления.

 

Рисунок 4.1 – Распределение коллизий в адресном пространстве таблицы

 

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

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

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

Еще одной хеш-функцией можно назвать функцию свертки. Цифровое представление ключа разбивается на части, каждая из которых имеет длину, равную длине требуемого адреса. Над частями производятся какие-то арифметические или поразрядные логические операции, результат которых интерпретируется как адрес. Например, для сравнительно небольших таблиц с ключами – символьными строками неплохие результаты дает функция хеширования, в которой адрес записи получается в результате сложения кодов символов, составляющих строку-ключ. Аналогично, если к проектируемой системе не предъявляются особые требования к секретности и устойчивости к атакам, в качестве хеш-функции или её основы может использоваться сигнатура целостности CRC-16 (CRC-32, CRC-64).

В качестве хеш-функции также применяют функцию преобразования системы счисления. Ключ, записанный как число в некоторой системе счисления P, интерпретируется как число в системе счисления Q > P. Обычно выбирают Q = P+1. Это число переводится из системы Q обратно в систему P, приводится к размеру пространства записей и интерпретируется как адрес.