1 / (1 – )

поскольку вероятность успеха для каждой пробы равна 1 – .

Если коэффициент заполнения отделён от единицы, теорема 4.5 предсказывает, что поиск отсутствующего элемента будет в среднем проходить за вре­мя О(1). Например, если таблица заполнена наполовину, то среднее число проб будет не больше 1/(1 – 0,5) = 2, а если на 90%, то не больше 1/(1 – 0,9) = 10.

Из теоремы 4.5 немедленно получается и оценка на стоимость операции добавления к таблице.

Следствие 4.6. В предположении равномерного хеширования математическое ожидание числа проб при добавлении нового элемента в таблицу с открытой адресацией не превосходит 1/(1 – ), где  < 1 – коэффициент заполнения.

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

Оценить среднее время успешного поиска немногим сложнее.

Теорема 4.7. Рассмотрим таблицу с открытой адресацией, коэффициент за­полнения которой равен  < 1. Пусть хеширование равномерно. Тогда матема­тическое ожидание числа проб при успешном поиске элемента в таблице не превосходит

если считать, что ключ для успешного поиска в таблице выбирается случай­ным образом и все такие выборы равновероятны.

Доказательство. Уточним, как производится усреднение: сначала мы заполняем таблицу независимо выбираемыми ключами, причём для каждого из них выполняется предположение равномерного хеширования. Затем мы усредняем по всем элементам таблицы время их поиска.

Заметим, что при успешном поиске ключа k мы делаем те же самые пробы, которые производились при помещении ключа k в таблицу. Тем самым среднее число проб при поиске (усреднение по элементам) равно общему числу проб при добавлении, делённому на число элементов в таблице, которое мы обозначаем n. Математическое ожидание общего числа проб при добавлении равно сумме математических ожиданий для каждого отдельного шага. К моменту добавления (i+1)-го элемента в таблице заполнено i позиций, коэффициент заполнения равен i/т (т – число мест в таблице), и математическое ожидание не больше

Поэтому сумма математических ожиданий не превосходит

+++…+

Эта сумма равна

и оценивается сверxy с помощью интеграла:

Вспоминая, что общее число операций надо поделить на n, получаем оценку

Если, например, таблица заполнена наполовину, то среднее число проб для успешного поиска не превосходит 1,387, а если на 90%, то 2,559.