90
правок
Изменения
Нет описания правки
[[Файл:AlgoF2.gif|400px|right]]
===Добавление элементов===
Благодаря степеням двойки, мы сможем эффективно находить элементы в HAT, используя поразрядные операции(см.Пример1). Чаще всего при добалении элемента, в одном из листьев(последний незаполненный на данный момент) найдется свободное место, что позволит осуществить быструю вставку(O(1)).
Реже мы столкнемся со случаем, когда необходимо создать новый лист. Необходимо всего лишь добавить указатель в свободную ячейку главного массива, а значит также сможем произвести вставку элемента за О(1).
Самый интересный случай, когда главный массив и все листья заполнены. Сначала вычислим новый размер HAT - следующая степень двойки(главный массив и каждый лист все еще равны между собой). Далее скопируем все элементы в новый экземпляр HAT, при этом освобождая старые листья, перераспределим элементы по новым(размер листа изменился).
==Заключение==
HAT - удобная структура данных, переменной длины, позволяющая добавить N элементов за O(N) времени и требующая O(sqrt(N)) памяти. HAT обеспечивает все стадартные возможности обычных массивов, включая произвольный доступ к элементам. Она поддерживает известное колличество памяти для любого колличества элементов и не требует специальной настроки для эффективной работы приложений.
Таким образом HAT предлагает ряд сильных преимуществ над другими реализациями массивов переменной длины.
