Реферат по дициплине: «Структуры данных и алгоритмы»

a) Линейное зондирование

Линейное зондирование решает проблему коллизий с помощью проверки следующей ячейки.
h(k, i) = (h′(k) + i) mod m,
где

• 
  i = {0, 1, ….}
  
• 
  h'(k) — новая хеш-функция
  

Если коллизия происходит в h(k, 0), тогда проверяется h(k, 1). То есть значение i увеличивается линейно.
Проблема линейного зондирования заключается в том, что заполняется кластер соседних ячеек. Это приводит к тому, что при вставке нового элемента в хеш-таблицу необходимо проводить полный обход кластера. В результате время выполнения операций с хеш-таблицами увеличивается.

b) Квадратичное зондирование

Работает оно так же, как и линейное — но есть отличие. Оно заключается в том, что расстояние между соседними ячейками больше (больше одного). Это возможно благодаря следующему отношению:
h(k, i) = (h′(k) + c₁i + c₂i²) mod m,
где 

• 
  c₁ и c₂ — положительные вспомогательные константы,
  
• 
  i = {0, 1, ….}
  

c) Двойное хэширование

Если коллизия возникает после применения хеш-функции h(k), то для поиска следующей ячейки вычисляется другая хеш-функция.
h(k, i) = (h1(k) + ih2(k)) mod m

«Хорошие» хеш-функции

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

1. Метод деления

Если k — ключ, а m — размер хеш-таблицы, то хеш-функция h() вычисляется следующим образом:
h(k) = k mod m
Например, если m = 10 и k = 112, то h(k) = 112 mod 10 = 2. То есть значение m не должно быть степенью 2. Это связано с тем, что степени двойки в двоичном формате — 10, 100, 1000… При вычислении k mod m мы всегда будем получать p-биты низшего порядка.
если m = 22, k = 17, тогда h(k) = 17 mod 22 = 10001 mod 100 = 01
если m = 23, k = 17, тогда h(k) = 17 mod 22 = 10001 mod 100 = 001
если m = 24, k = 17, тогда h(k) = 17 mod 22 = 10001 mod 100 = 0001
если m = 2p, тогда h(k) = p биты порядком ниже, чем m