Изменения

Перейти к: навигация, поиск

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

44 байта добавлено, 13:05, 1 июня 2014
Нет описания правки
HAT состоит из главного массива указателей и ряда листьев(так же одномерные массивы), в которых хранятся элементы.
Число указателей в главном массиве и число элементов в каждом листе - равны между собой, и являются степенями двойки.
[[Файл:AlgoF2.gif|400px|right]]
===Добавление элементов===
Благодаря степеням двойки, мы сможем эффективно находить элементы в HAT, используя поразрядные операции(см.Пример1). Чаще всего при добалении элемента, в одном из листьев(последний незаполненный на данный момент) найдется свободное место, что позволит осуществить быструю вставку(O(1)).
===Расход памяти===
При перераспределении и копировании HAT использует мнеьше памяти, чем в стандартных подходах. Самый плохой случай для HAT - размер элементов равен размеру указателей и число элементов на один больше числа при котором происходит расширение структуры(N=ResizeValue+1). Для этого случая значени привидены в таблице:
[[Файл:Table_HAT.JPG|400px|left]]
90
правок

Навигация