Глава 11. Хеширование

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

Хеширование (hashing) использует аналогичный подход, отображая элементы в хеш‑таблице (hash table). Алгоритм хеширования использует некоторую функцию, которая определяет вероятное положение элемента в таблице на основе значения искомого элемента.

Например, предположим, что требуется запомнить несколько записей, каждая из которых имеет уникальный ключ со значением от 1 до 100. Для этого можно создать массив со 100 ячейками и проинициализировать каждую ячейку нулевым ключом. Чтобы добавить в массив новую запись, данные из нее просто копируются в соответствующую ячейку массива. Чтобы добавить запись с ключом 37, данные из нее просто копируются в 37 позицию в массиве. Чтобы найти запись с определенным ключом, просто выбирается соответствующая ячейка массива. Для удаления записи ключу соответствующей ячейки массива просто присваивается нулевое значение. Используя эту схему, можно добавить, найти и удалить элемент из массива за один шаг.

К сожалению, в реальных приложениях значения ключа не всегда находятся в небольшом диапазоне. Обычно диапазон возможных значений ключа достаточно велик. База данных сотрудников может использовать в качестве ключа идентификационный номер социального страхования. Теоретически можно было бы создать массив, каждая ячейка которого соответствовала одному из возможных девятизначных чисел; но на практике для этого не хватит памяти или дискового пространства. Если для хранения одной записи требуется 1 килобайт памяти, то такой массив занял бы 1 терабайт (миллион мегабайт) памяти. Даже если можно было бы выделить такой объем памяти, такая схема была бы очень неэкономной. Если штат вашей компании меньше 10 миллионов сотрудников, то более 99 процентов массива будут пусты.

=======281

Чтобы справиться с этой проблемой, схемы хеширования отображают потенциально большое число возможных ключей на достаточно компактную хеш‑таблицу. Если в вашей компании работает 700 сотрудников, вы можете создать хеш‑таблицу с 1000 ячеек. Схема хеширования устанавливает соответствие между 700 записями о сотрудниках и 1000 позициями в таблице. Например, можно располагать записи в таблице в соответствии с тремя первыми цифрами идентификационного номера в системе социального страхования. При этом запись о сотруднике с номером социального страхования 123‑45‑6789 будет находиться в 123 ячейке таблицы.

Очевидно, что поскольку существует больше возможных значений ключа, чем ячеек в таблице, то некоторые значения ключей могут соответствовать одним и тем же ячейкам таблицы. Например, оба значения 123‑45‑6789 и 123­99‑9999 отображаются на одну и ту же ячейку таблицы 123. Если существует миллиард возможных номеров системы социального страхования, и таблица имеет 1000 ячеек, то в среднем каждая ячейка будет соответствовать миллиону записей.

Чтобы избежать этой потенциальной проблемы, схема хеширования должна включать в себя алгоритм разрешения конфликтов (collision resolution policy), который определяет последовательность действий в случае, если ключ соответствует позиции в таблице, которая уже занята другой записью. В следующих разделах описываются несколько различных методов разрешения конфликтов.

Все обсуждаемые здесь методы используют для разрешения конфликтов примерно одинаковый подход. Они вначале устанавливают соответствие между ключом записи и положением в хеш‑таблице. Если эта ячейка уже занята, они отображают ключ на какую‑либо другую ячейку таблицы. Если она также уже занята, то процесс повторяется снова о тех пор, пока в конце концов алгоритм не найдет пустую ячейку в таблице. Последовательность проверяемых при поиске или вставке элемента в хеш‑таблицу позиций называется последовательностью проверок, последовательностью проб --> тестовой последовательностью (probe sequence).

В итоге, для реализации хеширования необходимы три вещи:

• Структура данных (хеш‑таблица) для хранения данных;

• Функция хеширования, устанавливающая соответствие между значением ключа и положением в таблице;

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

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