✈️31. Хеш-таблицы. Коллизии. Способы разрешения коллизий. Открытая адресация

(линейное пробирование, квадратичное пробирование, двойное хеширование).

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

data_1["BMSTU"] = "МГТУ"
DATA_2[3.14] = "Pi"

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

h("a") -> 1
h("b") -> 2
h("c") -> 3

Преимущества хэш-таблиц:

• Сложность алгоритма: О(n)

• Быстрый поиск

• Равномерное распределение в памяти

Недостатки хэш-таблиц:

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

Коллизия хэш-функции - получение одинакового индекса для разных ключей.

Существует 2 основных типа борьбы с коллизиями:

• Метод цепочек

• Открытая адресация(3 типа)

Линейное зондирование(пробирование) Линейное опробование сводится к последовательному перебору сегментов таблицы с некоторым фиксированным шагом

h'(k, i) = (h(k) + i) % size;

Минус: метод приводит к образованию кластеров (когда несколько ячеек подряд заняты). Кластер приводит к тому, что увеличивается время доступа к данным.

Квадратичное зондирование(пробирование)

Квадратичное опробование отличается от линейного тем, что шаг перебора сегментов нелинейно зависит от номера попытки найти свободный сегмент:

h'(k, i) = (h(k) + a*i + b*i*i) % size;

Минус: относительно небольшое число проб может быстро при­вести к выходу за адресное пространство небольшой таблицы вслед­ствие квадратичной зависимости адреса от номера попытки.

Двойное хеширование

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

h'(k, i) = (h1(k) + i*h2(k)) % size;

Минус: нерациональное использование огромного количества памяти.