Hash array mapped trie

A hash array mapped trie[1] (HAMT) is an implementation of an associative array that combines the characteristics of a hash table and an array mapped trie.[1] It is a refined version of the more general notion of a hash tree.

Operation

A HAMT is an array mapped trie where the keys are first hashed to ensure an even distribution of keys and a constant key length.

In a typical implementation of HAMT's array mapped trie, each node contains a table with some fixed number N of slots with each slot containing either a nil pointer or a pointer to another node. N is commonly 32. As allocating space for N pointers for each node would be expensive, each node instead contains a bitmap which is N bits long where each bit indicates the presence of a non-nil pointer. This is followed by an array of pointers equal in length to the number of ones in the bitmap (its Hamming weight).

Advantages of HAMTs

The hash array mapped trie achieves almost hash table-like speed while using memory much more economically. Also, a hash table may have to be periodically resized, an expensive operation, whereas HAMTs grow dynamically. Generally, HAMT performance is improved by a larger root table with some multiple of N slots; some HAMT variants allow the root to grow lazily[1] with negligible impact on performance.

Implementation details

Implementation of a HAMT involves the use of the population count function, which counts the number of ones in the binary representation of a number. This operation is available in many instruction set architectures, but it is available in only some high-level languages. Although population count can be implemented in software in O(1) time using a series of shift and add instructions, doing so may perform the operation an order of magnitude slower.[citation needed]

Implementations

The programming languages Clojure,[2] Scala, and Frege[3] use a persistent variant of hash array mapped tries for their native hash map type. The Haskell library "unordered-containers" uses the same to implement persistent map and set data structures.[4] Another Haskell library "stm-containers" adapts the algorithm for use in the context of software transactional memory.[5] A Javascript HAMT library [6] based on the Clojure implementation is also available. The Rubinius[7] implementation of Ruby includes a HAMT, mostly written in Ruby but with 3[8] primitives. Large maps in Erlang use a persistent HAMT representation internally since release 18.0.[9] The Pony programming language uses a HAMT for the hash map in its persistent collections package.[10] The im and im-rc crates, which provide persistent collection types for the Rust programming language, use a HAMT for their persistent hash tables and hash sets. [11]

The concurrent lock-free version[12] of the hash trie called Ctrie is a mutable thread-safe implementation which ensures progress. The data-structure has been proven to be correct[13] - Ctrie operations have been shown to have the atomicity, linearizability and lock-freedom properties.

See also

References

  1. ^ a b c Phil Bagwell (2000). Ideal Hash Trees (PDF) (Report). Infoscience Department, École Polytechnique Fédérale de Lausanne.
  2. ^ "clojure/clojure". GitHub. 8 December 2022.
  3. ^ "Frege/frege". GitHub. 7 December 2022.
  4. ^ Johan Tibell, A. Announcing unordered-containers 0.2
  5. ^ Nikita Volkov, Announcing the "stm-containers" library, 2014
  6. ^ "mattbierner/hamt". GitHub. 27 November 2022.
  7. ^ "Ruby source file of Rubinius's HAMT". GitHub.
  8. ^ https://github.com/rubinius/rubinius/blob/master/machine/builtin/system.cpp#L1724-L1802 [dead link‍]
  9. ^ "Erlang Programming Language".
  10. ^ "horse: Pony is an open-source, actor-model, capabilities-secure, high performance programming language: Ponylang/ponyc". GitHub. 2018-11-26.
  11. ^ "API docs for Rust im-rc crate".
  12. ^ Prokopec, A. Implementation of Concurrent Hash Tries on GitHub
  13. ^ Prokopec, A. et al. (2011) Cache-Aware Lock-Free Concurrent Hash Tries. Technical Report, 2011.

Read other articles:

Ibrahima Traoré

Ibrahima Traoré Informasi pribadiTanggal lahir 21 April 1988 (umur 35)Tempat lahir Villepinte, PrancisTinggi 1,76 m (5 ft 9+1⁄2 in)Posisi bermain GelandangKarier junior2001–2004 Charenton2004–2005 LevalloisKarier senior*Tahun Tim Tampil (Gol)2005–2006 Levallois 4 (0)2006–2009 Hertha BSC II 62 (12)2007–2009 Hertha BSC 1 (0)2009–2011 FC Augsburg 45 (8)2011–2014 VfB Stuttgart 75 (6)2014–2021 Borussia Mönchengladbach 100 (6)Total 287 (32)Tim nasional�...

 

Jasril Jakub

Jasril Jakub Komandan Pasukan Pengamanan PresidenMasa jabatan13 November 1993 – 24 Maret 1995 PendahuluPranowoPenggantiSirajuddin Paiyoi Informasi pribadiAlma materAkademi Militer Nasional 1965Karier militerPihak IndonesiaDinas/cabang TNI Angkatan DaratMasa dinas1965–1998Pangkat Letnan Jenderal TNISatuanCorps Polisi Militer (CPM)Sunting kotak info • L • B Letnan Jenderal TNI (Purn.) Jasril Jakub adalah seorang tokoh militer Indonesia. Putra Koto Gadang, Ag...

 

Caladi batu

Caladi batu Status konservasi Risiko Rendah (IUCN 3.1)[1] Klasifikasi ilmiah Kerajaan: Animalia Filum: Chordata Kelas: Aves Ordo: Piciformes Famili: Picidae Genus: Meiglyptes Spesies: M. tristis Nama binomial Meiglyptes tristis(Horsfield, 1821) Caladi batu adalah spesies burung pelatuk dalam famili Picidae. Penyebaran dan subspesies Terdiri dari dua subspesies, dengan daerah persebaran:[2] M. t. tristis (Horsfield, 1821), tersebar di Pulau Jawa. M. t. grammithorax (...

Resolusi 6 Dewan Keamanan Perserikatan Bangsa-Bangsa

Resolusi 6Dewan Keamanan PBBBendera Perserikatan Bangsa-BangsaTanggal17 Mei 1946Sidang no.42KodeS/RES/6 (Dokumen)TopikPendaftaran keanggotaanRingkasan hasil11 mendukungTidak ada menentangTidak ada abstainHasilDiadopsiKomposisi Dewan KeamananAnggota tetap Tiongkok (ROC) Prancis Britania Raya Amerika Serikat Uni SovietAnggota tidak tetap Australia Brasil Mesir Meksiko Belanda Polandia Resolusi 6 Dewan Keamanan Perserikatan Bangsa-...

 

Thomas Jefferson Star for Foreign Service

AwardThomas Jefferson Star for Foreign ServiceTypeMedalAwarded forDeath or a serious illness or injury that results in death, permanent incapacity or disabilityPresented byUnited States Department of StateEligibilityForeign Service, Civil ServiceStatusCurrently awardedRibbon PrecedenceNext (higher)Award for HeroismAward for Valor (obsolete)Next (lower)Distinguished Honor Award The Thomas Jefferson Star for Foreign Service is an award of the United States Department of State. It is p...

 

Vyacheslav Loginov

Russian politician In this name that follows Eastern Slavic naming customs, the patronymic is Yurievich and the family name is Loginov. You can help expand this article with text translated from the corresponding article in Russian. (February 2024) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accu...

Provinsi Villa Clara

Provinsi Villa ClaraProvinsi di Kuba LambangNegaraKubaIbukotaSanta ClaraLuas[1] • Total8.413,13 km2 (324,833 sq mi)Populasi (2010-12-31)[1] • Total803.562 • Kepadatan0,96/km2 (2,5/sq mi)Zona waktuUTC-5 (EST) Villa Clara adalah salah satu provinsi di Kuba. Provinsi tersebut terletak di kawasan tengah pulau tersebut yang berbatasan dengan Samudera Atlantik di bagian utara, Provinsi Matanzas di bagian barat, Provinsi Sa...

 

Moons of Neptune

Natural satellites of the planet Neptune An annotated picture of some of Neptune's many moons as captured by the James Webb Space Telescope. The bright blue diffraction star is Triton, Neptune's largest moon; while Hippocamp, its smallest regular moon, is too small to be seen. The planet Neptune has 16 known moons, which are named for minor water deities and a water creature in Greek mythology. By far the largest of them is Triton, discovered by William Lassell on October 10, 1846, 17 days af...

 

Plaza Moriones

This article is about the plaza in Tondo, Manila. For the plaza in Intramuros, Manila, see Plaza Moriones, Intramuros. Plaza MorionesPublic squareFor much of its length, Plaza Moriones is lined by several trees, bounded on both sides by Moriones Street.Dedicated toDomingo Moriones y MurallaOwnerCity of ManilaLocationMoriones Street, TondoManila, PhilippinesCoordinates: 14°36′35″N 120°58′04″E / 14.60984°N 120.96773°E / 14.60984; 120.96773 Plaza Moriones...

Queen of Malawi

Elizabeth II's reign in Malawi from 1964 to 1966 For the Malawi Queens, see Malawi national netball team. Queen of MalawiCoat of arms of MalawiElizabeth II DetailsStyleHer MajestyFormation6 July 1964Abolition6 July 1966 Elizabeth II was Queen of Malawi from 1964 to 1966, when Malawi was an independent sovereign state and a constitutional monarchy within the Commonwealth of Nations. She was also the sovereign of the other Commonwealth realms, including the United Kingdom. The 1964 Constitution...

 

Template talk:Kyushu Railway Company Lines

Trains: in Japan Template‑class Trains Portal This template is within the scope of WikiProject Trains, an attempt to build a comprehensive and detailed guide to rail transport on Wikipedia. If you would like to participate, you can visit the project page, where you can join the project and/or contribute to the discussion. See also: WikiProject Trains to do list and the Trains Portal.TrainsWikipedia:WikiProject TrainsTemplate:WikiProject Trainsrail transport articlesTemplateThis template do...

 

Centaur (small Solar System body)

Type of Solar System object This article is about a class of Solar system objects. For other uses, see Centaur (disambiguation). Positions of known outer Solar System objects as of 2017.The centaurs orbit generally inwards of the Kuiper belt and outside the Jupiter trojans.   Sun   Jupiter trojans (6,178)   Scattered disc (>300)   Neptune trojans (9)   Giant planets:  · Jupiter (J) · Saturn (S)...

ورم عظمي غضروفي

Osteochondroma صورة شعاعية جانبية للركبة توضح التعظم في الأنسجة المحيطة بالعضلة لدى مريض يعاني من ورم عظمي غضروفي.صورة شعاعية جانبية للركبة توضح التعظم في الأنسجة المحيطة بالعضلة لدى مريض يعاني من ورم عظمي غضروفي. تسميات أخرى Osteocartilaginous exostoses معلومات عامة الاختصاص جراحة العظام م...

 

Wilsons River (New South Wales)

Not to be confused with Wilson River (New South Wales) or Wilsons Creek, New South Wales. River in New South Wales, AustraliaWilsons RiverWilsons Creek, North Arm Richmond River[1]Wilsons River flowing through Lismore, 2023Location of the Wilsons River mouth in New South WalesEtymologyIn honour of William Wilson[1]LocationCountryAustraliaStateNew South WalesRegionNSW North Coast (IBRA), Northern RiversLGAsByron, Richmond Valley, LismoreCityLismorePhysical characteristicsS...

 

澳大利亚共产党

  此條目介紹的是1920年—1991年存在的澳大利亚共产党。关于1971年成立时取名为“澳大利亚社会党”、1996年改名为“澳大利亚共产党”的政党，请见「澳大利亚共产党 (1996年)」。 澳大利亚共产党(1920—1944年；1951年—1991年）澳大利亚的共产党（1944年—1951年）简称CPA、ACP创始人乔克·加登（英语：Jock Garden）汤姆·沃尔什（英语：Tom Walsh (trade unionist)）威廉·伊尔斯曼（...

Pacific herring

Species of fish Pacific herring Conservation status Data Deficient  (IUCN 3.1)[1] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Actinopterygii Order: Clupeiformes Family: Clupeidae Genus: Clupea Species: C. pallasii Binomial name Clupea pallasiiValenciennes in Cuvier and Valenciennes, 1847 The Pacific herring (Clupea pallasii) is a species of the herring family associated with the Pacific Ocean environment of North America and northeas...

 

Subtraction

One of the four basic arithmetic operations Subtract redirects here. For other uses, see Subtraction (disambiguation). This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Subtraction – news · newspapers · books · scholar · JSTOR (May 2018) (Learn how and when to remove this message) 5 − 2 = 3 (verbally, five m...

 

Francisco López de Gómara

Cet article est une ébauche concernant un historien et un écrivain espagnol. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Pour les articles homonymes, voir Francisco López et López. Francisco López de GómaraBiographieNaissance 2 février 1511GómaraDécès 1564GómaraFormation Université d'AlcaláActivités Chroniqueur, historienmodifier - modifier le code - modifier Wikidata Francisco López de Gómar...

علاقات بين الأشخاص

علاقة ودية بين اب وابنته العلاقات بين الأشخاص هي العلاقات بين شخصين أو أكثر تبدأ من علاقة عابرة[محل شك] وحتى العلاقات الدائمة. وقد تبنى هذه العلاقة على الاستدلال أو الحب أو التضامن الاجتماعي أو تفاعلات العمل المعتادة أو أي أنواع أخرى من العلاقات الاجتماعية. وتتشكل العل...

 

Altered chord

Musical terminology For similar terms, see Alteration (disambiguation) and Modification. Not to be confused with Leading tone. An altered dominant chord in C major[1] An altered chord is a chord that replaces one or more notes from the diatonic scale with a neighboring pitch from the chromatic scale. By the broadest definition, any chord with a non-diatonic chord tone is an altered chord. The simplest example of altered chords is the use of borrowed chords, chords borrowed from the pa...