Открытое хеширование

Принцип организации хеш-таблицы методом открытого хеширования заключается в реализации связанных цепочек, начинающихся в ячейках хеш-таблицы. Под цепочками подразумеваются связанные списки, указатели на которые хранятся в ячейках хеш-таблицы. Каждый элемент связанного списка – блок данных, и если с некоторым указателем, хранящимся по адресу i, связаны n таких блоков (n >1), то это свидетельствует о том, что n ключей получили одно и то же хеш-значение i, т. е. имеет место коллизия. Но метод открытого хеширования устраняет конфликт, поскольку данные хранятся не в самой таблице, а в связных списках, которые увеличиваются при возникновении конфликта.

Ниже (рис. 1.1) изображены связанные списки со ссылающейся на них хеш-таблицей размером m. Первый столбец таблицы содержит хешированные значения ключей, второй – ссылки на списки. Количество списков ограничено лишь числом элементов исходного массива (он не показан, но предполагается). Состоят списки из трех (последний элемент подсписка – из двух) полей: & - адрес элемента списка, $ - данные, * - указатель на следующий список.

Рисунок 1.1 – Хеш-таблица

Если в исходном массиве было всего n элементов (столько же будут содержать в совокупности и все списки), то средняя длина списков будет равна α = n / m, где m – число элементов хеш-таблицы, α – коэффициент заполнения хеш-таблицы. Предположив, например, что в списке на рисунке выше m =5 (заклеив 4-ую по счету строку), получим среднее число списков α =2.

Чтобы увеличить скорость работы операций поиска, вставки и удаления нужно, зная n, подобрать m примерно равное ему, т. к. тогда α будет равняться 1-ому или ≈1, следовательно, можно рассчитывать на оптимальное время, в лучшем случае равное O (1). В худшем случае все n элементов окажутся в одном списке, и тогда, например, операция нахождения элемента (в худшем случае) потребует O (n) времени.