Хеширование
При использовании методов поиска, относящихся к двоичным деревьям, число итераций в лучшем случае пропорционально высоте дерева поиска, т.е. O (log n). Естественно, возникает желание найти такой метод поиска, при котором число итераций не зависело бы от объема хранимых данных, а в идеальном случае поиск сводился бы к одному шагу.
Простейшей организацией таблицы, обеспечивающей идеально быстрый поиск, является таблица прямого доступа. В такой таблице ключ является адресом записи в таблице или может быть преобразован в адрес, причем таким образом, что никакие два разных ключа не преобразуются в один и тот же адрес. При создании таблицы выделяется память для хранения всей таблицы и заполняется пустыми записями. Затем записи вносятся в таблицу – каждая на свое место, определяемое ее ключом. При поиске ключ используется как адрес и по этому адресу выбирается запись, если выбранная запись пустая, то записи с таким ключом вообще нет в таблице. Таблицы прямого доступа очень эффективны в использовании, но, к сожалению, область их применения весьма ограничена.
|
|
Хеш-таблицы применяются тогда, когда требуются функциональность динамического множества, поддерживающего только словарные операции (добавление, поиск и удаление элемента).
Хеш-таблицу можно рассматривать как обобщение обычного массива. Если у нас достаточно памяти для массива, число элементов которого равно числу всех возможных ключей, для каждого возможного ключа можно отвести ячейку в этом массиве и тем самым иметь возможность добраться до любой записи за время О (1). Однако, если реальное количество записей значительно меньше, чем количество возможных ключей, то эффективнее применить хеширование: вычислять позицию записи в массиве, исходя из ключа. В худшем случае поиск в хеш-таблице может занимать столько же времени, сколько поиск в списке (Q(n)), но на практике хеширование весьма эффективно. При выполнении некоторых естественных условий математическое ожидание времени поиска элемента в хеш-таблице есть О (1).
Назовем пространством ключей множество всех теоретически возможных значений ключей записи. Назовем пространством записей множество тех ячеек памяти, которые выделяются для хранения таблицы.
Таблицы прямого доступа применимы только для таких задач, в которых размер пространства записей может быть равен размеру пространства ключей. В большинстве реальных задач, однако, размер пространства записей много меньше, чем пространства ключей. Так, если в качестве ключа используется фамилия, то, даже ограничив длину ключа 10 символами кириллицы, получаем 3310 возможных значений ключей. Даже если ресурсы вычислительной системы и позволят выделить пространство записей такого размера, то значительная часть этого пространства будет заполнена пустыми записями, так как в каждом конкретном заполнении таблицы фактическое множество ключей не будет полностью покрывать пространство ключей.
|
|
Из соображений экономии памяти целесообразно назначать размер пространства записей равным размеру фактического множества записей или превосходящим его незначительно. В этом случае необходимо иметь некоторую функцию, обеспечивающую отображение точки из пространства ключей в точку в пространстве записей, то есть, преобразование ключа в адрес записи: a:= h (k), где a – адрес, k – ключ. Такая функция называется функцией хеширования (другие ее названия – функция перемешивания, функция рандомизации).
Идеальной хеш-функцией является такая функция, которая для любых двух неодинаковых ключей дает неодинаковые адреса: k 1 ¹ k 2 Þ h (k 1) ¹ h (k 2).
При попытке отображения точек из некоторого широкого пространства в узкое неизбежны ситуации, когда разные точки в исходном пространстве отобразятся в одну и ту же точку в целевом пространстве. Ситуация, при которой разные ключи отображаются в один и тот же адрес записи, называется коллизией или переполнением, а такие ключи называются синонимами. Коллизии составляют основную проблему для хеш-таблиц и способы её разрешения будут рассмотрены отдельно.
Если хеш-функция, преобразующая ключ в адрес, может порождать коллизии, то однозначной обратной функции: k:= h ’(a), позволяющей восстановить ключ по известному адресу, существовать не может. Поэтому ключ должен обязательно входить в состав записи хешированной таблицы как одно из ее полей.
К хеш-функции в общем случае предъявляются следующие требования:
- она должна обеспечивать равномерное распределение отображений фактических ключей по пространству записей (см. рис. 4.1);
- она должна порождать как можно меньше коллизий для данного фактического множества записей;
- она не должна отображать какую-либо связь между значениями ключей в связь между значениями адресов;
- она должна быть простой и быстрой для вычисления.
Рисунок 4.1 – Распределение коллизий в адресном пространстве таблицы
Приведем обзор и анализ некоторых наиболее простых из применяемых на практике хеш-функций.
Простейшей хеш-функцией является деление по модулю числового значения ключа на размер пространства записи. Результат интерпретируется как адрес записи. Следует иметь в виду, что такая функция плохо соответствует первым трем требованиям к хеш-функции и сама по себе может быть применена лишь в очень ограниченном диапазоне реальных задач. Однако, операция деления по модулю обычно применяется как последний шаг в более сложных функциях хеширования, обеспечивая приведение результата к размеру пространства записей.
Следующей хеш-функцией является функция середины квадрата. Значение ключа преобразуется в число, это число затем возводится в квадрат, из него выбираются несколько средних цифр, и интерпретируются как адрес записи.
Еще одной хеш-функцией можно назвать функцию свертки. Цифровое представление ключа разбивается на части, каждая из которых имеет длину, равную длине требуемого адреса. Над частями производятся какие-то арифметические или поразрядные логические операции, результат которых интерпретируется как адрес. Например, для сравнительно небольших таблиц с ключами – символьными строками неплохие результаты дает функция хеширования, в которой адрес записи получается в результате сложения кодов символов, составляющих строку-ключ. Аналогично, если к проектируемой системе не предъявляются особые требования к секретности и устойчивости к атакам, в качестве хеш-функции или её основы может использоваться сигнатура целостности CRC-16 (CRC-32, CRC-64).
|
|
В качестве хеш-функции также применяют функцию преобразования системы счисления. Ключ, записанный как число в некоторой системе счисления P, интерпретируется как число в системе счисления Q > P. Обычно выбирают Q = P +1. Это число переводится из системы Q обратно в систему P, приводится к размеру пространства записей и интерпретируется как адрес.