(Закрытое хеширование)
Все записи хранятся в самой хэш-таблице. Каждая ячейка таблицы содержит либо элемент динамического множества, либо NIL.
h:U × {0, 1, …, m-1} ® {0, 1, …, m-1}
Последовательность испробованных мест для данного ключа k имеет вид
‹h(k,0), h(k,1), . . . , h(k,m-1)›
Функция h должна быть такой, чтобы каждое из чисел от 0 до m - 1 встретилось в этой последовательности ровно один раз.
Пусть h’:U ® {0, 1, …, m-1} – обычная хеш-функция.
Линейная последовательность проб
h(k,i) = (h’(k) + i) mod m
Квадратичная последовательность проб
h(k,i) = (h’(k) +с1i + c2i2 ) mod m
Двойное хеширование
h(k,i) = (h’1(k) +i h’2(k) ) mod m
Анализ хеширования с открытой адресацией
Теорема 3. Математическое ожидание числа проб при поиске в таблице с открытой адресацией отсутствующего в ней элемента не превосходит 1/(1- α ) (хеширование предполагается равномерным)
Теорема 4. Математическое ожидание числа проб при успешном поиске элемента в таблице с открытой адресацией 1/ α * ln (1/(1- α ) )