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