Дерево, отображаемое хеш-массивом

массива Сопоставленное дерево хеш- ^[1] ( HAMT ) — это реализация ассоциативного массива , которая сочетает в себе характеристики хэш-таблицы и дерева, сопоставленного с массивом . ^[1]Это усовершенствованная версия более общего понятия хеш-дерева .

Операция

HAMT — это дерево с отображением массива, в котором ключи сначала хешируются, чтобы обеспечить равномерное распределение ключей и постоянную длину ключа.

В типичной реализации дерева, сопоставленного с массивом HAMT, каждый узел содержит таблицу с некоторым фиксированным числом N слотов, причем каждый слот содержит либо нулевой указатель, либо указатель на другой узел. N обычно равно 32. Поскольку выделение места для N указателей для каждого узла было бы дорогостоящим, каждый узел вместо этого содержит битовую карту длиной N бит, где каждый бит указывает на наличие ненулевого указателя. За ним следует массив указателей, длина которого равна количеству единиц в растровом изображении (его вес Хэмминга ).

Преимущества ХАМТ

Дерево, отображаемое в хэш-массиве, обеспечивает скорость, почти подобную хеш-таблице, при гораздо более экономичном использовании памяти. Кроме того, возможно, придется периодически изменять размер хеш-таблицы, что является дорогостоящей операцией, тогда как HAMT-таблицы растут динамически. Как правило, производительность HAMT повышается за счет увеличения корневой таблицы с количеством слотов, кратным N; некоторые варианты HAMT позволяют корню лениво расти ^[1] с незначительным влиянием на производительность.

Детали реализации

Реализация HAMT предполагает использование функции подсчета населения , которая подсчитывает количество единиц в двоичном представлении числа. Эта операция доступна во многих архитектурах набора команд , но доступна только в некоторых языках высокого уровня . Хотя подсчет населения можно реализовать программно за время O(1) с использованием серии инструкций сдвига и сложения , при этом операция может выполняться на порядок медленнее. ^{[ нужна ссылка ]}

Реализации

Языки программирования Clojure , ^[2] Скала и Фреге ^[3] используйте постоянный вариант попыток сопоставления хеш-массива для их собственного типа хеш-карты. Библиотека Haskell «неупорядоченные контейнеры» использует то же самое для реализации постоянной карты и установки структур данных. ^[4] Другая библиотека Haskell «stm-containers» адаптирует алгоритм для использования в контексте программной транзакционной памяти . ^[5] Библиотека Javascript HAMT ^[6] на основе реализации Clojure также доступен. Рубиниус ^[7] реализация Ruby включает HAMT, в основном написанный на Ruby, но с 3 ^[8] примитивы. Большие карты в Erlang используют постоянное внутреннее представление HAMT, начиная с версии 18.0. ^[9] Язык программирования Pony использует HAMT для хэш-карты в своем пакете постоянных коллекций. ^[10]Крейты im и im-rc, которые предоставляют постоянные типы коллекций для языка программирования Rust, используют HAMT для своих постоянных хеш-таблиц и хэш-наборов. ^[11]

Параллельная версия без блокировки ^[12] хэш-дерева под названием Ctrie — это изменяемая потокобезопасная реализация, обеспечивающая прогресс. Доказано, что структура данных правильна. ^[13] - Было показано, что операции Ctrie обладают свойствами атомарности , линеаризуемости и свободы блокировок .

См. также

Ссылки

↑ Перейти обратно: Перейти обратно: ^а ^б ^с Фил Бэгвелл (2000). Идеальные хэш-деревья (PDF) (Отчет). Факультет информационных наук Федеральной политехнической школы Лозанны .
^ «кложур/кложур» . Гитхаб . 8 декабря 2022 г.
^ «Фреге/Фреге» . Гитхаб . 7 декабря 2022 г.
^ Йохан Тибелл, А. Анонс неупорядоченных контейнеров 0.2
↑ Никита Волков, Анонс библиотеки «stm-containers» , 2014 г.
^ "маттбирнер/хамт" . Гитхаб . 27 ноября 2022 г.
^ «Исходный файл Ruby HAMT Рубиниуса» . Гитхаб .
^ https://github.com/rubinius/rubinius/blob/master/machine/builtin/system.cpp#L1724-L1802 ^{[ мертвая ссылка ]}
^ «Язык программирования Эрланг» .
^ «horse: Pony — это высокопроизводительный язык программирования с открытым исходным кодом, модель актера, безопасный и высокопроизводительный: Ponylang/ponyc» . Гитхаб . 2018-11-26.
^ «Документация API для крейта Rust im-rc» .
^ Прокопец, А. Реализация параллельных попыток хеширования на GitHub
^ Прокопец, А. и др. (2011) Параллельные попытки хеширования без блокировки с учетом кэша . Технический отчет, 2011.

[bagwell-1] Перейти обратно: Перейти обратно: ^а ^б ^с Фил Бэгвелл (2000). Идеальные хэш-деревья (PDF) (Отчет). Факультет информационных наук Федеральной политехнической школы Лозанны .

[2] «кложур/кложур» . Гитхаб . 8 декабря 2022 г.

[3] «Фреге/Фреге» . Гитхаб . 7 декабря 2022 г.

[4] Йохан Тибелл, А. Анонс неупорядоченных контейнеров 0.2

[5] Никита Волков, Анонс библиотеки «stm-containers» , 2014 г.

[6] "маттбирнер/хамт" . Гитхаб . 27 ноября 2022 г.

[7] «Исходный файл Ruby HAMT Рубиниуса» . Гитхаб .

[8] ttps://github.com/rubinius/rubinius/blob/master/machine/builtin/system.cpp#L1724-L1802 ^{[ мертвая ссылка ]}

[9] «Язык программирования Эрланг» .

[10] «horse: Pony — это высокопроизводительный язык программирования с открытым исходным кодом, модель актера, безопасный и высокопроизводительный: Ponylang/ponyc» . Гитхаб . 2018-11-26.

[11] «Документация API для крейта Rust im-rc» .

[12] Прокопец, А. Реализация параллельных попыток хеширования на GitHub

[13] Прокопец, А. и др. (2011) Параллельные попытки хеширования без блокировки с учетом кэша . Технический отчет, 2011.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]