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

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

Значимость

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

Устройство HAT

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

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

Благодаря использованию степеней двойки, мы можем эффективно находить элементы в 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]. Самый интересный случай — когда главный массив и все листья заполнены. Сначала вычислим новый размер HAT — следующая степень двойки (главный массив и каждый лист все еще равны между собой). Далее скопируем все элементы в новый экземпляр HAT, при этом освобождая старые листья, перераспределим элементы по новым(размер листа изменился). Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивов переменной длины. Копировать элементы мы будем только тогда, когда главный массив полон(достигли соответствующей степени двойки). Например, для N=4, общая сумма перекопирования будет равна 1+4+16+64+256+...+N. Воспользуемся тождеством: [math](x^{n+1} -1)=(x-1)(1+x+x^2+x^3+... + x^n)[/math], тогда для нашего случая: [math]1 +4+4^2+4^3+...+4^n = (4^{n+1} -1)/(4-1) = (4N-1)/3[/math], или около [math]4N/3[/math]. Это означает, что среднее число дополнительных операций копирования - [math]O(N)[/math] для последовательного добавления N элементов, а не [math]O(N^2)[/math].

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

При перераспределении и копировании HAT использует меньше памяти, чем в стандартных подходах. Самый плохой случай для HAT — размер элементов равен размеру указателей, и число элементов на один больше числа, при котором происходит расширение структуры(N=ResizeValue+1). Для этого случая значения приведены в таблице. Затраты памяти в самом плохом случае — [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) памяти (один указатель для каждого элемента).

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

Сравнивая со стандартным массивом переменной длины, реализованным в стандартной библиотеке С++, мы получаем, что благодаря предвычислению (1<<power)-1, разыменование элементов в HAT происходит приблизительно в два раза быстрее, чем разыменование в стандартном массиве С++. Рассмотрим несколько графиков, показывающих скорость работы HAT на некоторых алгоритмах:

• 1) Быстрая сортировка(QuickSort). График сравнивает HAT и стандартный массив в С++(левый график).
• 2) Добавление и сортировка(правый график).

Все стандартные тесты были выполнены на 100Mhz HP 700 series PA-RISC workstation running HPUX 9.01 with 256 MB of memory.

Заключение

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.