Обсуждение участника:SergeyBud

HAT(Hashed Array Tree) — структура данных, объединяющая в себе некоторые возможности массивов, хэш-таблиц и деревьев. В действительности HAT — это эффективный способ реализовать массивы переменной длины, так как он предлагает хорошую производительность порядка [math]O(N)[/math], чтобы добавить [math]N[/math] элементов к пустому массиву, и требует всего лишь [math]O(\sqrt{N})[/math] дополнительной памяти.

Значимость

Массивы переменной длины — наиболее естественная и удобная структура данных для многих приложений, так как они обеспечивают постоянное время доступа к их элементам. Однако при их реализации мы можем столкнуться с двумя основными проблемами: чрезмерное копирование элементов и использование памяти. HAT — реализация массива переменной длины, решающая обе проблемы и предоставляющая ряд преимуществ по сравнению со стандартными реализациями.

Устройство HAT

HAT состоит из главного массива указателей [math]top[/math] и ряда листьев [math]leaf[/math] (так же одномерные массивы), в которых хранятся элементы. Возможное число указателей в главном массиве и возможное число элементов в каждом листе равны между собой и являются степенями двойки.

Добавление элементов

Благодаря использованию степеней двойки, мы можем эффективно находить элементы в HAT, используя поразрядные операции.

 topIndex(j)
   // Получить номер указателя в основном массиве
   return j >> power;
 leafIndex(j)
   // Получить номер листа
   return j & ((1<<power)-1);
 getHat(j)
   // Вернуть элемент HAT. Нет проверки на выход за пределы массива.
   return top[topIndex(j)][leafIndex(j)];

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

Расход памяти

При перераспределении и копировании HAT использует меньше дополнительной памяти, чем в стандартных подходах. Самый плохой случай для HAT — размер элементов равен размеру указателей, и число элементов на один больше числа, при котором происходит расширение структуры([math]N=ResizeValue+1[/math]). Затраты доролнительной памяти в самом плохом случае — [math](top+leaf-1) ~= 2\sqrt{N} = O(\sqrt{N})[/math]. Если последний лист будет половиной полного, то ожидаемая трата дополнительной памяти уменьшается до [math](top + leaf/2) \approx 1.5\sqrt{N}[/math] (top — главный массив, leaf — листья), а это все еще [math]O(\sqrt{N})[/math]. Сравним с другими структурами, добавляющими элементы за [math]O(1)[/math]. Например, отдельно связанные списки требуют O(N) дополнительной памяти (один указатель для каждого элемента).

Эффективность

Благодаря преимуществам, предоставляемыми HAT(так например вычисления адреса происходит приблизительно в 2 раза быстрее, чем в стандартном массиве C++), ее можно использовать в любых программах, требующих работу с массивами переменной длинны, где использование других структур данных (например списков) не удобно. На многих алгоритмах HAT работает значительно быстрее стандартных массивов, дополнительно можно ознакомиться с результатами некоторых тестов.

Заключение

HAT — удобная структура данных переменной длины, позволяющая добавить N элементов за [math]O(N)[/math] времени и требующая [math]O(\sqrt{N})[/math] дополнительной памяти. HAT обеспечивает все стандартные возможности обычных массивов, включая произвольный доступ к элементам. Она поддерживает известный объем памяти для любого количества элементов и не требует специальной настройки для эффективной работы приложений. Таким образом, HAT предлагает ряд существенных преимуществ над другими реализациями массивов переменной длины.

Источники информации

• Википедия
• Cline, M.P. and G.A. Lomow, C++ FAQs, Reading, MA: Addison-Wesley, 1995.
• Cormen, T.H., C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms, Cambridge, MA: MIT Press, 1990.