Изменения

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

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

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

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

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

При перераспределении и копировании HAT использует мнеьше памяти, чем в стандартных подходах. Самый плохой случай для HAT - размер элементов равен размеру указателей и число элементов на один больше числа при котором происходит расширение структуры(N=ResizeValue+1). Для этого случая значени привидены в таблице: