Изменения

Перейти к: навигация, поиск

Перехеширование

40 байт добавлено, 19:39, 5 мая 2012
См. также
Будем проводить перехеширование при заполнении таблицы на <tex dpi = "150">\frac{n}{2}</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>, и не изменив стоимость остальных операций.
 
==Примечания==
</references>
==См. также==
Анонимный участник

Навигация