Изменения

При добавлении в хеш-таблицу большого количества элементов могут возникнуть ухудшения в ее работе. Обработка любого вызова будет занимать больше времени из-за увеличения размеров цепочек при хешировании на списках или кластеризации при хешировании с открытой адресацией, также, при хешировании с открытой адресацией может произойти переполнение таблицы. Для избежания таких ситуаций используется выбор новой хеш-функции и (или) хеш-таблица большего размера. Этот процесс называется '''перехеширование''' (''rehashing'').

==Перехеширование при разных типах хеширования==

При использовании [[Открытое и закрытое хеширование#Открытое хеширование|хеширования цепочками]] , элементы с одинаковым результатом хеш-функции помещают в список. Так как операции <tex>\mathrm{add(x)}</tex>, <tex>\mathrm{contains(x)}</tex> и <tex>\mathrm{remove(x)}</tex> работают за <tex>O(l)</tex>, где <tex>l</tex> {{---}} длина списка, то с некоторого момента выгодно увеличить размер хеш-таблицы, чтобы поддерживать амортизационную стоимость операции <tex>O(1)</tex>.

Рассмотрим следующий алгоритм перехеширования: когда в хеш-таблицу добавлено <tex dpi = "150">\frac{4n}{3}</tex> элементов, где <tex>n</tex> {{---}} размер хеш-таблицы, создадим новую хеш-таблицу размера <tex>2n</tex>, и последовательно переместим в нее все элементы первой таблицы. При этом, сменим хеш-функцию так, чтобы она выдавала значения <tex>[0..2n-1]</tex>.

Для проведения перехеширования необходимо произвести <tex dpi = "150">\frac{4n}{3}</tex> операций <tex>\mathrm{add}(x)</tex>, средняя стоимость которых составляет <tex>O(1)</tex> , потратить <tex dpi = "150">\frac{4n}{3}</tex> операций на проход хеш-таблицы, и <tex dpi = "150">\frac{4n}{3}</tex> операций на удаление предыдущей таблицы. В итоге, если мы увеличим стоимость каждой операции <tex>\mathrm{add}(x)</tex> на <tex>6</tex>, то есть на <tex>O(1)</tex>, операция перехеширования будет полностью предоплачена. Значит, амортизационная стоимость перехеширования при открытом типе хеш-таблицы равна <tex>O(1)</tex>.

===При хеширования с открытой адресацией===