Изменения
→При закрытом типе
При использовании хеширования с открытой адресацией, или закрытого[http://neerc.ifmo.ru/mediawiki/index.php/%D0%9E%D1%82%D0%BA%D1%80%D1%8B%D1%82%D0%BE%D0%B5_%D0%B8_%D0%B7%D0%B0%D0%BA%D1%80%D1%8B%D1%82%D0%BE%D0%B5_%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#.D0.97.D0.B0.D0.BA.D1.80.D1.8B.D1.82.D0.BE.D0.B5_.D1.85.D0.B5.D1.88.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B5] хеширования, операции <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)</tex> операций добавления, и <tex>O(n)</tex> операций на удаление таблицы. Так как операция добавления имеет не меньшую стоимость, чем элементарная операция, и между последовательными перехешированиями производится <tex>O(n)</tex> добавлений, то можно предоплатить перехеширование, не увеличив амортизационной стоимости стоимость операции <tex>Add(x)</tex> на <tex>O(1)</tex>, и не изменив стоимость остальных операций.
==См. также==
