Hash array mapované trie - Hash array mapped trie

A hash array maped trie[1] (HAMT) je implementací asociativní pole který kombinuje vlastnosti a hash tabulka a pole mapováno trie.[1]Jedná se o rafinovanou verzi obecnějšího pojmu a hash strom.

Úkon

HAMT je trie mapované na pole, kde jsou klíče nejprve hašovány, aby se zajistilo rovnoměrné rozložení klíčů a konstantní délka klíče.

V typické implementaci tria mapovaného pole HAMT obsahuje každý uzel tabulku s určitým pevným počtem N slotů, přičemž každý slot obsahuje buď nulový ukazatel, nebo ukazatel na jiný uzel. N je běžně 32. Protože přidělování prostoru pro N ukazatele pro každý uzel by bylo nákladné, každý uzel místo toho obsahuje bitmapu, která je dlouhá N bitů, kde každý bit označuje přítomnost jiného ukazatele. Poté následuje pole ukazatelů stejné délky jako počet v bitmapě (jeho Hammingova hmotnost ).

Výhody HAMT

Trie mapovaná hašovací pole dosahuje téměř rychlosti podobné hašovací tabulce, zatímco využívá paměť mnohem ekonomičtěji. Může také být nutné pravidelně měnit velikost hashovací tabulky, což je nákladná operace, zatímco HAMT rostou dynamicky. Obecně je výkon HAMT vylepšen větší kořenovou tabulkou s několika násobky N slotů; některé varianty HAMT umožňují lenivě růst kořene[1] se zanedbatelným dopadem na výkon.

Podrobnosti implementace

Implementace HAMT zahrnuje použití počet obyvatel funkce, která spočítá počet jednotek v binární reprezentaci čísla. Tato operace je k dispozici v mnoho architektur instrukční sady, ale je k dispozici pouze v některých jazycích vysoké úrovně. Ačkoli počet obyvatel lze implementovat do softwaru v systému Windows O (1) čas pomocí a série směn a přidejte pokyny, může to provést operaci o řádově pomaleji.[Citace je zapotřebí ]

Implementace

Programovací jazyky Clojure,[2] Scala, a Frege[3] použijte a vytrvalý varianta mapovaných pokusů o hašovací pole pro jejich nativní typ hash mapy. The Haskell knihovna "neuspořádané kontejnery" používá totéž k implementaci trvalé mapy a nastavení datových struktur.[4] Další Haskell knihovna "kontejnery STM" upravuje algoritmus pro použití v kontextu softwarová transakční paměť.[5] A Javascript Knihovna HAMT [6] na základě implementace Clojure je také k dispozici. The Rubinius[7] implementace Rubín zahrnuje HAMT, většinou napsaný v Ruby, ale s 3[8] primitiv. Velké mapy v Erlang použijte a vytrvalý Reprezentace HAMT interně od vydání 18.0.[9] Programovací jazyk Pony používá HAMT pro hashovací mapu ve svém balíčku trvalých sbírek.[10]Přepravky im a im-rc, které poskytují trvalé typy kolekcí pro programovací jazyk Rust, používají HAMT pro své trvalé hash tabulky a sady hash.[11]

Souběžná verze bez zámku[12] volala hash trie Ctrie je proměnlivá implementace bezpečná pro vlákna, která zajišťuje pokrok. Ukázalo se, že datová struktura je správná[13] - Ukázalo se, že operace Ctrie mají atomicita, linearizovatelnost a svoboda zámku vlastnosti.

Viz také

Reference

  1. ^ A b C Phil Bagwell (2000). Ideální hašovací stromy (PDF) (Zpráva). Oddělení informačních věd, École Polytechnique Fédérale de Lausanne.
  2. ^ „clojure / clojure“. GitHub.
  3. ^ „Frege / frege“. GitHub.
  4. ^ Johan Tibell, A. Oznamování neuspořádaných kontejnerů 0.2
  5. ^ Nikita Volkov, Oznamujeme knihovnu „stm-containers“, 2014
  6. ^ "mattbierner / hamt". GitHub.
  7. ^ „Rubínový zdrojový soubor Rubiniusovy HAMT“.
  8. ^ [1]
  9. ^ „Erlang Programming Language“.
  10. ^ ": horse: Pony je open-source, herecký model, bezpečný, vysoce výkonný programovací jazyk: Ponylang / ponyc". 2018-11-26.
  11. ^ „Dokumenty API pro přepravku Rust im-rc“.
  12. ^ Prokopec, A. Implementace souběžných testů Hash na GitHubu
  13. ^ Prokopec, A. a kol. (2011) Souběžné pokusy o hashování bez mezipaměti bez zamykání. Technická zpráva, 2011.