Дерево хешированных массивов - Hashed array tree

В Информатика, а дерево хешированных массивов (ШЛЯПА) это динамический массив структура данных, опубликованная Эдвардом Ситарски в 1996 году,^[1][2] сохранение массива отдельных фрагментов памяти (или «листьев») для хранения элементов данных, в отличие от простых динамических массивов, которые хранят свои данные в одной непрерывной области памяти. Его основная цель - уменьшить объем копирования элементов за счет операций автоматического изменения размера массива и улучшить шаблоны использования памяти.

Тогда как простые динамические массивы на основе геометрическое расширение отходы линейные (Ω (п)) пробел, где п количество элементов в множество, деревья хешированных массивов теряют только порядок О(√п) пространство для хранения. Оптимизация алгоритма позволяет полностью исключить копирование данных за счет увеличения бесполезного пространства.

Он может выполнять доступ в постоянном (О (1)) времени, хотя и немного медленнее, чем простые динамические массивы. Алгоритм имеет амортизированную производительность O (1) при добавлении серии объектов в конец дерева хешированного массива. Вопреки своему названию, он не использует хэш-функции.

Полное хешированное дерево массивов с 16 элементами

Определения

По определению Ситарски, дерево хешированных массивов имеет каталог верхнего уровня, содержащий сила двух количество листовых массивов. Все листовые массивы имеют тот же размер, что и каталог верхнего уровня. Эта структура внешне напоминает хеш-таблица с цепочками столкновений на основе массивов, что является основой для имени дерево хешированных массивов. Полное хешированное дерево массива может содержать м² элементы, где м это размер каталога верхнего уровня.^[2] Использование степени двойки обеспечивает более быструю физическую адресацию с помощью битовых операций вместо арифметических операций частное и остаток^[2] и обеспечивает амортизированную производительность O (1) операции добавления при наличии случайных копий глобального массива при расширении.

Расширения и уменьшение размеров

В обычном динамическом массиве геометрическое расширение По схеме массив перераспределяется как целый последовательный фрагмент памяти с новым размером, вдвое превышающим его текущий размер (и все данные затем перемещаются в новое место). Это гарантирует O (1) амортизированных операций за счет O (n) потраченного впустую пространства, поскольку расширенный массив заполняется до половины своей новой емкости.

Когда дерево хешированного массива заполнено, его каталог и листья должны быть реструктурированы так, чтобы удвоить их прежний размер, чтобы обеспечить возможность дополнительных операций добавления. Данные, хранящиеся в старой структуре, затем перемещаются в новые места. Затем выделяется только один новый лист и добавляется в верхний массив, который, таким образом, заполняется только до четверти своей новой емкости. Все лишние листья еще не распределены и будут распределяться только при необходимости, тратя только О(√п) хранения.^{[нужна цитата ]}

Существует несколько альтернатив для уменьшения размера: когда дерево хешированного массива заполнено на одну восьмую, его можно реструктурировать в меньшее, наполовину полное хешированное дерево массива; другой вариант - освобождение только неиспользуемых массивов листьев без изменения размеров листьев. Дальнейшая оптимизация включает добавление новых листьев без изменения размера при увеличении массива каталогов по мере необходимости, возможно, посредством геометрического расширения. Это устранит необходимость в копировании данных полностью за счет сокращения ненужного пространства. О(п) с небольшой константой и выполняет реструктуризацию только при достижении установленного порогового значения накладных расходов.^[2]

Связанные структуры данных

Сравнение структур данных списка

	Связанный список	Множество	Динамический массив	Сбалансированное дерево	Случайный список доступа	Дерево хешированных массивов
Индексирование	Θ (п)	Θ (1)	Θ (1)	Θ (журнал n)	Θ (журнал n)[3]	Θ (1)
Вставить / удалить в начале	Θ (1)	Нет данных	Θ (п)	Θ (журнал n)	Θ (1)	Θ (п)
Вставить / удалить в конце	Θ (1) когда последний элемент известен; Θ (п) когда последний элемент неизвестен	Нет данных	Θ (1) амортизированный	Θ (журнал п)	Нет данных [3]	Θ (1) амортизированный
Вставить / удалить в середине	время поиска + Θ (1)[4][5]	Нет данных	Θ (п)	Θ (журнал п)	Нет данных [3]	Θ (п)
Потраченное впустую пространство (средний)	Θ (п)	0	Θ (п)[6]	Θ (п)	Θ (п)	Θ (√п)

Бродник и др.^[7] представил динамический массив алгоритм с аналогичным профилем потери пространства для деревьев хешированных массивов. Реализация Бродника сохраняет ранее выделенные листовые массивы с более сложной функцией вычисления адресов по сравнению с деревьями хешированных массивов.

Смотрите также

• Динамический массив
• Развернутый связанный список
• B-дерево

Рекомендации

1. Ситарски, Эдвард (сентябрь 1996 г.), Шляпы: деревья массивов хеширования
2. Ситарски, Эдвард (сентябрь 1996 г.), «Аллея алгоритмов - HAT: деревья хешированных массивов», Журнал доктора Добба, 21 (11)
3. Крис Окасаки (1995). «Чисто функциональные списки произвольного доступа». Материалы Седьмой Международной конференции по языкам функционального программирования и компьютерной архитектуре: 86–95. Дои:10.1145/224164.224187.
4. Основной доклад дня 1 - Бьярн Страуструп: стиль C ++ 11 в GoingNative 2012 на channel9.msdn.com с 45 минут или фольги 44
5. Обработка чисел: почему вы никогда и НИКОГДА не должны использовать связанный список в своем коде снова в kjellkod.wordpress.com
6. Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт; Munro, JI; Demaine, ED (1999), Массивы с изменяемым размером в оптимальном времени и пространстве (Технический отчет CS-99-09) (PDF), Департамент компьютерных наук, Университет Ватерлоо
7. Бродник, Андрей; Карлссон, Сванте; Седжвик, Роберт; Munro, JI; Demaine, ED (1999), «Массивы с изменяемым размером в оптимальном времени и пространстве» (PDF), Технический отчет CS-99-09, Департамент компьютерных наук, Университет Ватерлоо