(открытое хеширование)
Пусть T – хеш-таблица с m позициями, в которую занесено n элементов/
Коэффициент заполнениятаблицы α = n / m
Худший случай – θ (n)
Средняя стоимость поиска
Гипотеза равномерного хеширования – предполагаем, что каждый данный элемент может попасть в любую из позиций таблицы с равной вероятностью, независимо от того, куда попал другой элемент.
Теорема 1. Пусть T - хеш-таблица с цепочками, имеющая коэффициент заполнения α. Предположим, что хеширование равномерно. Тогда при поиске элемента, отсутствующего в таблице, будет просмотрено в среднем α элементов таблицы, а среднее время такого поиска (включая время на вычисление хеш-функции) будет равно θ (1+ α)
Теорема 2. При равномерном хешировании среднее время успешного поиска в хеш-таблице с цепочками есть θ (1+ α), где α - коэффициент заполнения.