Хеширование — один из способов увеличения эффективности поиска [9]. Основная идея хеширования — подобрать некий способ преобразования значения ключа сразу в адрес записи. Таким образом, поиск становится вообще ненужным.
Поясним это на примере. Пусть в файле прямого доступа лежит структура со следующими полями (табл. 3.2): 1) номер накладной, 2) грузоотправитель, 3) грузополучатель, 4) груз, 5) количество единиц груза. Номер накладной обычно
представляет собой довольно длинное целое число; в нашем примере это ключ. Если массив структур снабжен дополнительной таблицей индексов (табл. 3.3), в которой значения ключей отсортированы, например, по возрастанию, и для каждого значения ключа в таблице имеется номер соответствующей записи, то поиск нужной записи выполняется следующим образом: сначала проводим поиск в левой части таблицы индексов, а найдя заданный ключ, получаем номер записи — т. е. прямой доступ к ней.
Таблица 3.2 Поля структуры
| Поля | Конкретные значения |
| Номер накладной | |
| Грузоотправитель | Computer ltd |
| Грузополучатель | АО «Теледейта» |
| Груз | AS-400 |
| Количество единиц груза |
Таблица 3.3 Дополнительная таблица индексов
| Ключ | Номер записи |
Попробуем упростить процесс. Пусть мы имеем не более 1000 записей. Если бы значения ключа лежали в диапазоне 1 до 1000, то таблицу индексов можно построить иначе, а именно — заносить номер записи в ячейку таблицы, номер которой равен ключу (табл. 3.4). Ясно, что теперь для поиска записи с ключом, например, 282, достаточно было бы сразу обратиться к ячейке с номером 282 (прямой доступ), извлечь оттуда значение 23 и прочитать запись номер 23 в массиве (снова прямой доступ). Таким образом, поиск не нужен.
Хеширование есть способ перехода от длинных ключей к целым значениям, лежащим в диапазоне номеров записей. На практике хеширование проводят, подбирая некоторую функцию, отображающую все множество значений исходного ключа во множество индексов (адресов). Ясно, что диапазон значений
исходного ключа шире, чем диапазон индексов; поэтому хеширующая функция (хеш-функция) не может быть взаимно однозначной. Это порождает ряд проблем.
Таблица 3.4 Таблица
| Номер ячейки | Номер записи |
Вернемся к примеру.Если внимательно посмотреть на последнюю таблицу, то станет ясно, что в качестве хеш-функции мы взяли просто усечение номера накладной до последних трех цифр (это не худший метод хеширования). Однако, что делать, если имеется накладная с номером 207008282, а приходит документ с номером 010550282? Эта ситуация весьма типична и называется коллизией хеширования.
Имеется достаточное количество методов разрешения конфликтов. Возможно сформировать вторичный индекс. В частности можно для повторяющихся значений усеченного ключа использовать связный список. В основную запись можно было бы включить исходный ключ и проводить поиск по списку вторичных ключей до обнаружения нужного исходного. Известны и другие методы разрешения конфликтов.