Дерево , отображаемое хеш-массивом [1] ( HAMT ) — это реализация ассоциативного массива , который сочетает в себе характеристики хеш-таблицы и дерева, отображаемого в виде массива . [1] Это усовершенствованная версия более общего понятия хеш-дерева .
HAMT — это дерево с отображением массива, в котором ключи сначала хешируются, чтобы обеспечить равномерное распределение ключей и постоянную длину ключа.
В типичной реализации дерева, сопоставленного с массивом HAMT, каждый узел содержит таблицу с некоторым фиксированным числом N слотов, причем каждый слот содержит либо нулевой указатель, либо указатель на другой узел. N обычно равно 32. Поскольку выделение места для N указателей для каждого узла было бы дорогостоящим, каждый узел вместо этого содержит битовую карту длиной N бит, где каждый бит указывает на наличие ненулевого указателя. За ним следует массив указателей, длина которого равна количеству единиц в растровом изображении (его вес Хэмминга ).
Сопоставленное дерево с хеш-массивом обеспечивает скорость, почти подобную хеш-таблице, при гораздо более экономичном использовании памяти. Кроме того, возможно, придется периодически изменять размер хеш-таблицы, что является дорогостоящей операцией, тогда как HAMT-таблицы растут динамически. Как правило, производительность HAMT повышается за счет увеличения корневой таблицы с количеством слотов, кратным N; некоторые варианты HAMT позволяют корню расти лениво [1] с незначительным влиянием на производительность.
Реализация HAMT предполагает использование функции подсчета населения , которая подсчитывает количество единиц в двоичном представлении числа. Эта операция доступна во многих архитектурах набора команд , но доступна только в некоторых языках высокого уровня . Хотя подсчет населения можно реализовать программно за время O(1) с использованием серии инструкций сдвига и сложения , при этом операция может выполняться на порядок медленнее. [ нужна цитата ]
Языки программирования Clojure , [2] Scala и Frege [3] используют постоянный вариант попыток отображения хеш-массива для своего собственного типа хэш-карты. Библиотека Haskell «неупорядоченные контейнеры» использует то же самое для реализации постоянной карты и установки структур данных. [4] Другая библиотека Haskell «stm-containers» адаптирует алгоритм для использования в контексте программной транзакционной памяти . [5] Также доступна библиотека Javascript HAMT [6], основанная на реализации Clojure . Реализация Ruby в Rubinius [7] включает HAMT, в основном написанный на Ruby, но с тремя [8] примитивами. Большие карты в Erlang используют постоянное внутреннее представление HAMT, начиная с версии 18.0. [9] Язык программирования Pony использует HAMT для хеш-карты в своем пакете постоянных коллекций. [10] Крейты im и im-rc, которые предоставляют постоянные типы коллекций для языка программирования Rust, используют HAMT для своих постоянных хеш-таблиц и хэш-наборов. [11]
Параллельная версия хеш-три [12] без блокировки, называемая Ctrie , представляет собой изменяемую поточно-безопасную реализацию, которая обеспечивает прогресс. Доказано, что структура данных правильна [13] — было показано, что операции Ctrie обладают свойствами атомарности , линеаризуемости и свободы блокировок .