106
правок
Изменения
Нет описания правки
===При хеширования с открытой адресацией===
При использовании [[Открытое и закрытое хеширование#Закрытое хешированиеРазрешение коллизий|хеширования с открытой адресациейцепочками]] , операции <tex>\mathrm{add}(x)</tex>, <tex>\mathrm{contains}(x)</tex> и <tex>\mathrm{remove(x)}</tex> в худшем случае работают за <tex>O(k)</tex>, где <tex>k</tex> {{---}} количество уже добавленных в таблицу элементов, поэтому перехеширование надо проводить при неполном заполнении хеш-таблицы.
Будем проводить перехеширование при заполнении таблицы на <tex dpi = "150">\frac{n}{2}</tex>, увеличивая размер таблицы в <tex>2</tex> раза. Аналогично случаю с открытым хешированием, для перехеширования необходимо будет потратить <tex>O(n)</tex> операций на обход таблицы, <tex>O(n)\cdot A</tex> элементарных операций на добавление элементов, где <tex>A</tex> {{---}} стоимость операции <tex>\mathrm{add(x)}</tex>, и <tex>O(n)</tex> операций на удаление таблицы. Так как <tex>A \geqslant 1</tex>, и между последовательными перехешированиями производится <tex>O(n)</tex> добавлений, то можно предоплатить перехеширование, увеличив стоимость операции <tex>\mathrm{add(x)}</tex> на <tex>O(1)</tex>, и не изменив стоимость остальных операций.
