Hash array mappad försök
En hash array mappad trie ( HAMT ) är en implementering av en associativ array som kombinerar egenskaperna hos en hashtabell och en array mappad trie . Det är en förfinad version av det mer allmänna begreppet hashträd .
Drift
En HAMT är ett arraymappat försök där nycklarna först hashas för att säkerställa en jämn fördelning av nycklar och en konstant nyckellängd.
I en typisk implementering av HAMT:s arraymappade försök innehåller varje nod en tabell med något fast antal N luckor där varje lucka innehåller antingen en nollpekare eller en pekare till en annan nod. N är vanligtvis 32. Eftersom att allokera utrymme för N pekare för varje nod skulle vara dyrt, innehåller varje nod istället en bitmapp som är N bitar lång där varje bit indikerar närvaron av en icke-noll-pekare. Detta följs av en uppsättning pekare lika långa som antalet ettor i bitmappen (dess Hamming-vikt ) .
Fördelar med HAMTs
Den hash-arraymappade försöket uppnår nästan hashtabellliknande hastighet samtidigt som minnet används mycket mer ekonomiskt. Dessutom kan en hashtabell behöva ändras med jämna mellanrum, en dyr operation, medan HAMT växer dynamiskt. Generellt sett förbättras HAMT-prestandan av en större rottabell med någon multipel av N platser; vissa HAMT-varianter låter roten växa lat med försumbar påverkan på prestandan.
Genomförande detaljer
Implementering av en HAMT involverar användningen av populationsräkningsfunktionen , som räknar antalet ettor i den binära representationen av ett tal. Denna operation är tillgänglig i många instruktionsuppsättningsarkitekturer , men den är endast tillgänglig på vissa högnivåspråk . Även om befolkningsräkning kan implementeras i mjukvara på O(1) -tid med hjälp av en serie skift- och tilläggsinstruktioner , kan detta utföra operationen en storleksordning långsammare. [ citat behövs ]
Genomföranden
Programmeringsspråken Clojure , Scala och Frege använder en beständig variant av hash-arraymappade försök för sin inhemska hashkartatyp. Haskell - biblioteket "oordnade-behållare" använder detsamma för att implementera beständiga kartor och ställa in datastrukturer. Ett annat Haskell-bibliotek "stm-containers" anpassar algoritmen för användning i samband med mjukvarutransaktionsminne . Ett Javascript HAMT-bibliotek baserat på Clojure-implementeringen är också tillgängligt. Rubinius - implementeringen av Ruby inkluderar en HAMT, mestadels skriven i Ruby men med 3 primitiver. Stora kartor i Erlang använder en beständig HAMT-representation internt sedan release 18.0. Ponny-programmeringsspråket använder en HAMT för hashkartan i sitt beständiga samlingspaket. im- och im-rc-lådorna, som tillhandahåller beständiga samlingstyper för programmeringsspråket Rust, använder en HAMT för sina beständiga hashtabeller och hashuppsättningar.
Den samtidiga låsfria versionen av hash-försöket som heter Ctrie är en föränderlig trådsäker implementering som säkerställer framsteg. Datastrukturen har visat sig vara korrekt - Ctrie-operationer har visat sig ha egenskaperna atomicitet , linjärisering och låsfrihet .