Хеш - массива отображается Trie [1] ( HAMT ) является реализация ассоциативного массива , который сочетает в себе характеристики в хэш - таблице и массив отображается синтаксического дерева . [1] Это усовершенствованная версия более общего понятия хеш-дерева .
Операция
HAMT - это дерево с отображением массива, в котором ключи сначала хешируются, чтобы гарантировать равномерное распределение ключей и постоянную длину ключа.
В типичной реализации отображаемого дерева массива HAMT каждый узел содержит таблицу с некоторым фиксированным числом N слотов, причем каждый слот содержит либо нулевой указатель, либо указатель на другой узел. N обычно равно 32. Поскольку выделение пространства для N указателей для каждого узла было бы дорогостоящим, каждый узел вместо этого содержит битовую карту длиной N бит, где каждый бит указывает на наличие указателя, отличного от нуля. За ним следует массив указателей, равный по длине количеству единиц в битовой карте (его вес Хэмминга ).
Преимущества HAMT
Преобразованное дерево в хэш-массив обеспечивает почти такую же скорость, как у хэш-таблицы, при гораздо более экономном использовании памяти. Кроме того, может потребоваться периодически изменять размер хеш-таблицы, что является дорогостоящей операцией, тогда как HAMT-таблицы растут динамически. Как правило, производительность HAMT улучшается за счет более крупной корневой таблицы с некоторым количеством N слотов; некоторые варианты HAMT позволяют корню расти лениво [1] с незначительным влиянием на производительность.
Детали реализации
Реализация HAMT включает использование функции подсчета населения , которая подсчитывает количество единиц в двоичном представлении числа. Эта операция доступна во многих архитектурах набора команд , но доступна только на некоторых языках высокого уровня . Хотя подсчет населения может быть реализован программно за время O (1) с использованием серии инструкций сдвига и добавления , выполнение этого может выполнить операцию на порядок медленнее. [ необходима цитата ]
Реализации
Языки программирования Clojure , [2] Scala и Frege [3] используют постоянный вариант попыток сопоставления хэш-массива для своего родного типа хэш-карты. Haskell библиотека «неупорядоченные-контейнеры» использует тот же реализовать постоянную карту и набор структур данных. [4] Другая библиотека Haskell «stm-container» адаптирует алгоритм для использования в контексте программной транзакционной памяти . [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 обладают свойствами атомарности , линеаризуемости и свободы от блокировок .
Смотрите также
Рекомендации
- ^ a b c Фил Багвелл (2000). Идеальные хеш-деревья (PDF) (Отчет). Информационно-научный отдел Федеральной политехнической школы Лозанны .
- ^ "закрытие / закрытие" . GitHub .
- ^ «Фреге / фреге» . GitHub .
- ^ Йохан Тибелл, А. Объявление неупорядоченных контейнеров 0.2
- ↑ Никита Волков, Анонс библиотеки "Стм-контейнеры" , 2014 г.
- ^ "матбирнер / хамт" . GitHub .
- ^ "Исходный файл Ruby HAMT Рубиниуса" .
- ^ [1]
- ^ «Язык программирования Erlang» .
- ^ ": horse: Pony - это язык программирования с открытым исходным кодом, модели акторов, безопасный по возможностям, высокопроизводительный язык программирования: Ponylang / ponyc" . 2018-11-26.
- ^ «Документация API для Rust im-rc crate» .
- ^ Прокопек, А. Реализация одновременных попыток хеширования на GitHub
- ^ Prokopec, A. et al. (2011) Cache-Aware Lock-Free Concurrent Hash Tries . Технический отчет, 2011 г.