90
правок
Изменения
Нет описания правки
'''HAT(Hashed Array Tree)''' {{---}} структура данных, объединяющая в себе некоторые возможности массивов, хэш-таблиц и деревьев. В действительности HAT {{---}} это эффективный способ реализовать массивы переменной длины, так как он предлагает хорошую производительность порядка <math>O(N)</math>, чтобы добавить <math>N</math> элементов к пустому массиву и требует всего лишь <math>O(\sqrt{N})</math> непроизводительных затрат дополнительной памяти.
==Значимость==
HAT состоит из главного массива указателей и ряда листьев (так же одномерные массивы), в которых хранятся элементы.
Число указателей в главном массиве и число элементов в каждом листе равны между собой и являются степенями двойки.
===Добавление элементов===
Благодаря использованию степеней двойки, мы можем эффективно находить элементы в HAT, используя поразрядные операции. topIndex(j) // Получить номер указателя в основном массиве return j >> power; leafIndex(j) // Получить номер листа return j & ((1<<power)-1); getHat(j) // Вернуть элемент HAT. Нет проверки на выход за пределы массива. return top[topIndex(j)][leafIndex(j)];[[Файл:AlgoF2.gif|400px|left]]Чаще всего при добавлении элемента в одном из листьев (последнем незаполненном на данный момент) найдется свободное место, что позволит осуществить быструю вставку(<math>O(1)</math>).
Реже мы столкнемся со случаем, когда необходимо создать новый лист. Достаточно всего лишь добавить указатель в свободную ячейку главного массива, что также позволит произвести вставку элемента за <math>O(1)</math>.
Самый интересный случай {{---}} когда главный массив и все листья заполнены. Сначала вычислим новый размер HAT {{---}} следующая степень двойки (главный массив и каждый лист все еще равны между собой). Далее скопируем все элементы в новый экземпляр HAT, при этом освобождая старые листья, перераспределим элементы по новым(размер листа изменился).
===Расход памяти===
При перераспределении и копировании 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) памяти (один указатель для каждого элемента).
==Заключение==
HAT {{---}} удобная структура данных переменной длины, позволяющая добавить N элементов за <math>O(N)</math> времени и требующая <math>O(\sqrt{N})</math> дополнительной памяти. HAT обеспечивает все стандартные возможности обычных массивов, включая произвольный доступ к элементам. Она поддерживает известный объем памяти для любого количества элементов и не требует специальной настройки для эффективной работы приложений.
Таким образом, HAT предлагает ряд существенных преимуществ над другими реализациями массивов переменной длины.
