Изменения
→Динамические хэш-таблицы
#* В случае, если все элементы оказываются размещены в одном списке, время поиска элемента достигает <tex>O(n)</tex>. Это время может быть улучшено до <tex>O(\log n)</tex>, если вместо списков использовать сбалансированные [[Дерево поиска, наивная реализация | деревья поиска]] (эта модификация была добавлена в <tex>\mathrm{Java\ 8}{}</tex> для стандартной коллекции <tex>\mathrm{HashSet}</tex>).
#<tex>\mathrm{remove}{}</tex>: <tex> n</tex> уменьшается на единицу. Тогда амортизационное время работы с учётом изменения потенциала составит:
#* <tex> a_{remove} = 1 + 2 \cdot (n - 1) - \alpha_{max} m + - (2n - \alpha_{max} m ) = -1 </tex>
Так как <tex> \Phi_i = 2 n - \alpha_{max} m = O(n)</tex>, поэтому если <tex> f(n, m) = 1 </tex>, то средняя амортизационная стоимость модифицирующих операций составит <tex> a = O(1) </tex>.
