Изменения
Нет описания правки
Введём значение <tex>\alpha_{max}</tex>, при превышении которого таблица будет пересоздана с увеличением размера и все элементы будут перераспределены по-новому(rehashing). Аналогично будем пересоздавать таблицу с уменьшением размера при удалении элемента.
Из-за этого сложность операции <tex>\mathrm{add}{}</tex> из <tex> O(1) </tex> станет в худшем случае <tex> O(n) </tex>, так как для пересоздания таблицы нам требуется <tex> O(n) </tex> операций.
Стоит отметить, что изменение размера массива всегда должно быть геометрическим(в <tex> k </tex> раз), потому как при изменении размера на константу нам потребуется <tex>O(n)</tex> раз пересоздать таблицу, что приведёт к сложности операции <tex>\mathrm{add}{}</tex> в <tex> O(n^2) </tex>.
Введём такую потенциальную функцию, что она будет "запасать" время по мере удаления фактора загруженности от <tex dpi = "130">\genfrac{}{}{}{}{1}{2}</tex>:
