Изменения

Для проведения перехеширования необходимо произвести <tex dpi = "150">\frac{4n}{3}</tex> операций <tex>Add(x)</tex>, средняя стоимость которых составляет <tex>O(1)</tex> <ref>Анализ открытого хеширования, см. Т.Корман, второе издание, стр. 288</ref>, потратить <tex dpi = "150">\frac{4n}{3}</tex> операций на проход хеш-таблицы, и <tex dpi = "150">\frac{4n}{3}</tex> операций на удаление предыдущей таблицы. В итоге, если мы увеличим стоимость каждой операции <tex>Add(x)</tex> на <tex>6</tex>, то есть на <tex>O(1)</tex>, операция перехеширования будет полностью предоплачена. Значит, амортизационная стоимость перехеширования при открытом типе хеш-таблицы равна <tex>O(1)</tex>.

При использовании [[Открытое и закрытое хеширование#Закрытое хеширование|хеширования с открытой адресацией]] , операции <tex>Add(x)</tex>, <tex>Contains(x)</tex> и <tex>Remove(x)</tex> в худшем случае работают за <tex>O(k)</tex>, где <tex>k</tex> {{---}} количество уже добавленных в таблицу элементов, поэтому перехеширование надо проводить при неполном заполнении хеш-таблицы.