В информатике , А дерево хэшированного массива ( НАТ ) представляет собой динамический массив структуры данных , опубликованная Эдвард Sitarski в 1996 году, [1] [2] поддержание массива отдельных фрагментов памяти (или «листов») для хранения элементов данных, в отличие от простых динамических массивов, которые хранят свои данные в одной непрерывной области памяти. Его основная цель - уменьшить объем копирования элементов за счет операций автоматического изменения размера массива и улучшить шаблоны использования памяти.
В то время как простые динамические массивы, основанные на геометрическом расширении, тратят линейное (Ω ( n )) пространство, где n - количество элементов в массиве , деревья хешированных массивов тратят только пространство памяти порядка O ( √ n ). Оптимизация алгоритма позволяет полностью исключить копирование данных за счет увеличения бесполезного пространства.
Он может выполнять доступ за постоянное ( O (1)) время, хотя и немного медленнее, чем простые динамические массивы. Алгоритм имеет амортизированную производительность O (1) при добавлении серии объектов в конец дерева хешированного массива. Вопреки своему названию, он не использует хэш-функции .
Определения [ править ]
По определению Ситарски, дерево хешированных массивов имеет каталог верхнего уровня, содержащий степень двойки количества листовых массивов. Все листовые массивы имеют тот же размер, что и каталог верхнего уровня. Эта структура внешне напоминает хеш-таблицу с цепочками столкновений на основе массивов , которая является основой для дерева хешированных массивов имен . Полное дерево хешированного массива может содержать m 2 элементов, где m - размер каталога верхнего уровня. [2] Использование степеней двойки обеспечивает более быструю физическую адресацию с помощью битовых операций вместо арифметических операций с частным и остатком [2] и обеспечивает амортизированную производительность операции добавления в O (1) при наличии случайных копий глобального массива при расширении.
Расширение и уменьшение размера [ править ]
В обычной схеме геометрического расширения динамического массива массив перераспределяется как целый последовательный фрагмент памяти с новым размером, вдвое превышающим его текущий размер (и затем все данные перемещаются в новое место). Это обеспечивает O (1) амортизированных операций за счет O (n) потраченного впустую пространства, поскольку увеличенный массив заполняется до половины своей новой емкости.
Когда дерево хешированного массива заполнено, его каталог и листья должны быть реструктурированы так, чтобы удвоить их прежний размер, чтобы обеспечить дополнительные операции добавления. Данные, хранящиеся в старой структуре, затем перемещаются в новые места. Затем выделяется только один новый лист и добавляется в верхний массив, который, таким образом, заполняется только до четверти своей новой емкости. Все дополнительные листья еще не выделены и будут выделяться только при необходимости, таким образом тратя только O ( √ n ) памяти. [ необходима цитата ]
Существует несколько альтернатив для уменьшения размера: когда дерево хешированного массива заполнено на одну восьмую, его можно реструктурировать в меньшее, наполовину полное хешированное дерево массива; другой вариант - освобождение только неиспользуемых массивов листьев без изменения размеров листьев. Дальнейшая оптимизация включает добавление новых листьев без изменения размера при увеличении массива каталогов по мере необходимости, возможно, посредством геометрического расширения. Это устранит необходимость в копировании данных полностью за счет того, что потраченное впустую пространство будет равным O ( n ) с небольшой константой и выполнением реструктуризации только при достижении установленного порогового значения накладных расходов. [2]
Связанные структуры данных [ править ]
| Связанный список | Множество | Динамический массив | Сбалансированное дерево | Список произвольного доступа | Дерево хешированных массивов | |
|---|---|---|---|---|---|---|
| Индексирование | Θ ( п ) | Θ (1) | Θ (1) | Θ (журнал n) | Θ (журнал n) [3] | Θ (1) |
| Вставить / удалить в начале | Θ (1) | Нет данных | Θ ( п ) | Θ (журнал n) | Θ (1) | Θ ( п ) |
| Вставить / удалить в конце | Θ (1) когда известен последний элемент ; Θ ( n ) когда последний элемент неизвестен | Нет данных | Θ (1) с амортизацией | Θ (журнал n ) | Не указано [3] | Θ (1) с амортизацией |
| Вставить / удалить посередине | время поиска + Θ (1) [4] [5] | Нет данных | Θ ( п ) | Θ (журнал n ) | Не указано [3] | Θ ( п ) |
| Пустое пространство (в среднем) | Θ ( п ) | 0 | Θ ( n ) [6] | Θ ( п ) | Θ ( п ) | Θ ( √ п ) |
Бродник и др. [7] представили алгоритм динамического массива с аналогичным профилем потери пространства для деревьев хешированных массивов. Реализация Бродника сохраняет ранее выделенные листовые массивы с более сложной функцией вычисления адресов по сравнению с деревьями хешированных массивов.
См. Также [ править ]
Ссылки [ править ]
- ^ Sitarski, Эдвард (сентябрь 1996), HATs: Hashed массив деревьев
- ^ Б с д Sitarski, Эдвард (сентябрь 1996), "Алгоритм Alley - HATs: Hashed деревья массив" , журнал доктора Добба , 21 (11)
- ^ a b c Крис Окасаки (1995). «Чисто функциональные списки произвольного доступа». Труды Седьмой Международной конференции по языкам функционального программирования и компьютерной архитектуре : 86–95. DOI : 10.1145 / 224164.224187 .
- ^ Основной доклад дня 1 - Бьярн Страуструп: Стиль C ++ 11 на GoingNative 2012 на channel9.msdn.com с 45-й или 44-й минуты
- ^ Обработка чисел: почему вы никогда, никогда, НИКОГДА не должны использовать связанный список в своем коде снова на kjellkod.wordpress.com
- ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Munro, JI; Demaine, ED (1999), Массивы с изменяемым размером в оптимальном времени и пространстве (Технический отчет CS-99-09) (PDF) , Департамент компьютерных наук, Университет Ватерлоо
- ^ Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт ; Munro, JI; Demaine, ED (1999), «Массивы с изменяемым размером в оптимальном времени и пространстве» (PDF) , Технический отчет CS-99-09 , Департамент компьютерных наук, Университет Ватерлоо
