Обсуждение участника: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)];

Рассмотрим как происходит вычисление адреса на примере. Пусть у нас есть HAT с 3-мя используемыми листьями, тогда для нашего случая [math]power = 3[/math]. Получим значения функций для элемент под номером [math]5[/math]:

• [math]topIndex(5)[/math] : в данном случае битовый сдвиг эквивалентен опреации деления(взятию по модулю) [math]j[/math] на [math]2^{3}[/math]. То есть получим [math]1[/math] — действительно элемент под номером [math]5[/math] находится в первом листе(нумерация листов с [math]0[/math]).
• [math]leafIndex(5)[/math] : в данном случае битовый сдвиг эквивалентен умножению [math]1[/math] на [math]2^{3}[/math]. Тоесть после вычитания [math]1[/math] получим число формата [math]011..11[/math], в нашем случае — [math]011[/math].
• [math]5_{10} = 101_2 - 101 \& 011 = 001[/math], то есть индекс в листе равен [math]1[/math] (в листах нумерация так же с [math]0[/math]).

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

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

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

Благодаря преимуществам, предоставляемыми HAT(так например вычисление адреса происходит приблизительно в 2 раза быстрее, чем в стандартном массиве C++ — для соответствующего [math]power[/math] мы можем сделать предвычисление выражения [math](1\lt \lt power)-1[/math] тогда для вычисления адреса в обоих массивах потребуется всего одна битовая операция), ее можно использовать в любых программах, требующих работу с массивами переменной длинны, где использование других структур данных (например списков) не удобно. На многих алгоритмах HAT работает значительно быстрее стандартных массивов, дополнительно можно ознакомиться с результатами некоторых тестов.

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

• Wikipedia — Hashed array tree
• 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.