97
правок
Изменения
Нет описания правки
При использовании хеширования с открытой адресацией, или [[Открытое и закрытое хеширование#Закрытое хеширование|закрытого]] хеширования, операции <tex>Add(x)</tex>, <tex>Exists(x)</tex> и <tex>Delete(x)</tex> в худшем случае работают за <tex>O(k)</tex>, где <tex>k</tex> - количество уже добавленных в таблицу элементов, поэтому перехеширование надо проводить при неполном заполнении хеш-таблицы.
Будем проводить перехеширование при заполнении таблицы на <tex>\frac{1}{2}n</tex>, увеличивая размер таблицы в <tex>2</tex> раза. Аналогично случаю с открытым хешированием, для перехеширования необходимо будет потратить <tex>O(n)</tex> операций на обход таблицы, <tex>O(n)\cdot A</tex> элементарных операций добавленияна добавление элементов, где <tex>A</tex> - стоимость операции <tex>Add(x)</tex>, и <tex>O(n)</tex> операций на удаление таблицы. Так как операция добавления имеет не меньшую стоимость, чем элементарная операция<tex>A \geq 1</tex>, и между последовательными перехешированиями производится <tex>O(n)</tex> добавлений, то можно предоплатить перехеширование, увеличив стоимость операции <tex>Add(x)</tex> на <tex>O(1)</tex>, и не изменив стоимость остальных операций.
==См. также==
