Войти
В информатике дерево хешированных массивов (HAT ) - это структура данных динамического массива , опубликованная Эдвардом Ситарски в 1996 году, поддерживающая массив отдельных фрагментов памяти (или «листьев») для хранения элементов данных, в отличие от простых динамических массивов, которые хранят свои данные. в одной непрерывной области памяти. Его основная цель - уменьшить объем копирования элементов за счет операций автоматического изменения размера массива и улучшить шаблоны использования памяти.
В то время как простые динамические массивы, основанные на геометрическом расширении тратят линейное (Ω (n)) пространство, где n - количество элементов в массиве, деревья хешированных массивов тратить только порядка O (√n) места для хранения. Оптимизация алгоритма позволяет полностью исключить копирование данных за счет увеличения бесполезного пространства.
Он может выполнять доступ за постоянное (O (1)) время, хотя и немного медленнее, чем простые динамические массивы. Алгоритм имеет амортизированную производительность O (1) при добавлении серии объектов в конец дерева хешированного массива. Вопреки своему названию, он не использует хэш-функции.
Полное дерево хешированных массивов с 16 элементами Согласно определению Ситарски, дерево хешированных массивов имеет каталог верхнего уровня, содержащий степень двойки количество листовых массивов. Все листовые массивы имеют тот же размер, что и каталог верхнего уровня. Эта структура внешне напоминает хэш-таблицу с цепочками столкновений на основе массивов, которая является основой для дерева хешированных массивов имен. Полное хешированное дерево массива может содержать m элементов, где m - размер каталога верхнего уровня. Использование степени двойки обеспечивает более быструю физическую адресацию с помощью битовых операций вместо арифметических операций частного и остатка и обеспечивает амортизированную производительность O (1) операции добавления при наличии случайных копирование глобального массива при расширении.
В обычной схеме динамического массива геометрического расширения массив перераспределяется как целый последовательный фрагмент памяти с новым размером, вдвое превышающим его текущий размер (и все данные затем перемещаются в новое место). Это обеспечивает O (1) амортизированных операций за счет O (n) потраченного впустую пространства, поскольку увеличенный массив заполняется до половины своей новой емкости.
Когда дерево хешированного массива заполнено, его каталог и листья должны быть реструктурированы так, чтобы удвоить их прежний размер, чтобы обеспечить дополнительные операции добавления. Данные, хранящиеся в старой структуре, затем перемещаются в новые места. Затем выделяется только один новый лист и добавляется в верхний массив, который, таким образом, заполняется только до четверти своей новой емкости. Все дополнительные листья еще не выделены и будут выделяться только при необходимости, тратя только O (√n) памяти.
Есть несколько альтернатив для уменьшения размера: когда дерево хешированного массива занимает одну восьмую полный, его можно реструктурировать в меньшее, наполовину полное хешированное дерево массива; другой вариант - освобождение только неиспользуемых массивов листьев без изменения размеров листьев. Дальнейшая оптимизация включает добавление новых листьев без изменения размера при увеличении массива каталогов по мере необходимости, возможно, посредством геометрического расширения. Это устранит необходимость в копировании данных полностью за счет того, что потраченное впустую пространство будет равным O (n) с небольшой константой и выполнением реструктуризации только при достижении установленного порогового значения накладных расходов.
| Связанный список | Массив | Динамический массив | Сбалансированное дерево | Дерево хэшированного массива | ||
|---|---|---|---|---|---|---|
| Индексирование | Θ (n) | Θ (1) | Θ (1) | Θ (log n) | Θ (log n) | Θ (1) |
| Вставить / удалить в начале | Θ (1) | Н / Д | Θ (n) | Θ (log n) | Θ (1) | Θ (n) |
| Вставить / удалить в конце | Θ (1) когда известен последний элемент;. Θ (n) когда последний элемент неизвестно | н / д | Θ (1) амортизировано | Θ (log n) | н / д | Θ ( 1) амортизировано |
| Вставить / удалить в середине | время поиска + Θ (1) | Н / Д | Θ (n) | Θ (log n) | N / A | Θ (n) |
| Пустое пространство (среднее) | Θ (n) | 0 | Θ (n) | Θ (n) | Θ (n) | Θ (√n) |
. Brodnik et al. представил алгоритм динамического массива с аналогичным профилем потери пространства для хешированных деревьев массивов. Реализация Бродника сохраняет ранее выделенные листовые массивы с более сложной функцией вычисления адресов по сравнению с деревьями хешированных массивов.
