Хеширование

Этот метод называется еще методом перемешанных таблиц. Он представляет собой расширение метода прямого доступа на случай отсутствия взаимно однозначного соответствия между ключом и адресом записи. Существует адресная функция (хеш-функция), которая по ключу формирует адрес, однако, не исключено, что один и тот же адрес выделится разным ключам. Эта ситуация называется коллизией, а соответствующие ключи – синонимами. Алгоритм хеширования включает в себя механизм разрешения коллизий. Эффективность данного метода доступа во многом зависит от эффективности этого механизма. Кроме того, существенно влияет распределение ключей и размер таблицы. Чем больше размер таблицы по отношению к информационным строкам, тем меньше обычно вероятность коллизий, тем выше ЭД. Простейшая реализация метода заключается в том, что исходя из предположения о равномерном распределении значения ключей, функция хеширования отображает их равномерно на множество допустимых адресов. Простейший способ разрешения коллизий следующий. Если при попытке размещения по указанному адресу выясняется, что там уже что-то лежит, последовательно ищется первое свободное место, при прохождении через конец таблицы указатель возвращается на начало. Если свободная запись найдена – хорошо, в противном случае считается, что таблица переполнена. Аналогично ищутся данные при выборке. Если по указанному адресу есть данные, проверяется их ключ. При несовпадении регистрируется коллизия, которая разрешается, как указано ранее. Если данных нет, поиск неудачен. Этот алгоритм прост, но неэффективен по времени при заполнении таблицы более чем наполовину. Кроме того, при неравномерном распределении ключей этот алгоритм приводит к локальным сгущениям записей и увеличению числа коллизий при относительно свободной таблице. Если есть априорные сведения о распределении ключей, можно построить хеш-функцию, отображающую их опять же равномерно. Это заметно повысит эффективность даже для простого алгоритма разрешения коллизий.

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

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