Страница 5

Хеш-таблица

Свойства хеш-таблицы

Хеш-таблицы являются одним из способов хранения данных при помощи ассоциативного массива [12].

Хеш-таблицы решают несколько главных проблем при оперировании с данными:

• Создание отношения (связи) между ключом и абсолютно любым значением.
• Решение проблем коллизий.

Для большего понимания материала требуется ознакомиться с новыми терминами хеш-таблицы:

Ключ или сообщение

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

Бункер или корзина

произвольный элемент, который хранит данные хеш-таблицы.

Коэффициент заполнения

отношение количества заполненных бункеров на количество возможных ключей.

Исходя из определений, бункер - это условная единица хранимой информации в хеш-таблице (ассоциативном массиве данных).

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

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

Из этого можно выделить несколько особенностей хеш-таблиц:

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

Решение второй проблемы. Хеш-таблицы используют в качестве алгоритма поиска элемента контейнера (бункера) хеш-функцию, которая по принципу Дирихле гарантированно создаст коллизии в ситуации, когда количество ключей больше, чем количество бункеров, а обычно так бывает всегда.

Хеш-таблицы решают данную проблему двумя способами: 

• Метод цепочек или прямым связыванием.
• Открытой адресацией.