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