90
правок
Изменения
Нет описания правки
Реже мы столкнемся со случаем, когда необходимо создать новый лист. Необходимо всего лишь добавить указатель в свободную ячейку главного массива, а значит также сможем произвести вставку элемента за О(1).
Самый интересный случай, когда главный массив и все листья заполнены. Сначала вычислим новый размер HAT - следующая степень двойки(главный массив и каждый лист все еще равны между собой). Далее скопируем все элементы в новый экземпляр HAT, при этом освобождая старые листья, перераспределим элементы по новым(размер листа изменился).
Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивв переменной длины. Копировать элементы мы будем только тогда, когда главный массив полон, то есть число элементов превышает квадрат степени 2. Например, для N=4, общая сумма перекопирования будет равна 1+4+16+64+256+...+N. Воспользуемся тождеством: <math>(x^(n+1)-1)=(x-1)(1+x+x^2+x^3+... + x^n)</math>, тогда для нашего случая: 1 +4+4^2+4^3+...+4^n = (4^(n+1) -1)/(4-1) = (4N-1)/3, или около 4/3N. Это означает это, что среднее число дополнительных операций копирования - O(N) для последовательного добавления N элементов, а не O(N^2). =Расход памяти=При перераспределении и копировании HAT использует мнеьше памяти, чем в стандартных подходах. Самый плохой случай для HAT - размер элементов равен размеру указателей и число элементов на один больше числа при котором происходит расширение структуры(N=ResizeValue+1). Для этого случая значени привидены в таблице:
