Trie mapeado a matriz hash

Un trie mapeado a matriz hash ^{[ 1 ]} ( HAMT , / ˈ h æ m t / ) es una implementación de una matriz asociativa que combina las características de una tabla hash y un trie mapeado a matriz . ^{[ 1 ]} Es una versión refinada de la noción más general de un árbol hash .

Un HAMT es un trie mapeado a una matriz donde las claves se someten primero a una función hash para garantizar una distribución uniforme de las claves y una longitud de clave constante.

En una implementación típica del trie mapeado por matriz de HAMT, cada nodo contiene una tabla con un número fijo N de ranuras, donde cada ranura contiene un puntero nulo o un puntero a otro nodo. N suele ser 32. Dado que asignar espacio para N punteros en cada nodo sería costoso, cada nodo contiene en su lugar un mapa de bits de N bits de longitud, donde cada bit indica la presencia de un puntero no nulo. A continuación, se encuentra una matriz de punteros cuya longitud es igual al número de unos en el mapa de bits (su peso de Hamming ).

El trie mapeado por matriz hash alcanza una velocidad casi idéntica a la de una tabla hash, utilizando la memoria de forma mucho más económica. Además, una tabla hash puede requerir un redimensionamiento periódico, una operación costosa, mientras que los HAMT crecen dinámicamente. En general, el rendimiento de los HAMT mejora con una tabla raíz más grande, con un número de ranuras que sea múltiplo de N; algunas variantes de HAMT permiten que la raíz crezca de forma diferida ^{[ 1 ]} con un impacto mínimo en el rendimiento.

La implementación de una función HAMT implica el uso de la función de conteo de población , que cuenta la cantidad de unos en la representación binaria de un número. Esta operación está disponible en muchas arquitecturas de conjuntos de instrucciones , pero solo en algunos lenguajes de alto nivel . Si bien el conteo de población se puede implementar en software en tiempo O(1) mediante una serie de instrucciones de desplazamiento y suma , hacerlo puede ralentizar la operación considerablemente.

Los lenguajes de programación Clojure , ^{[ 2 ]} Scala y Frege ^{[ 3 ]} utilizan una variante persistente de tries mapeados en matrices hash para su tipo de mapa hash nativo. La biblioteca Haskell "unordered-containers" utiliza la misma para implementar estructuras de datos de mapas y conjuntos persistentes. ^{[ 4 ]} Otra biblioteca Haskell, "stm-containers", adapta el algoritmo para su uso en el contexto de la memoria transaccional de software . ^{[ 5 ]} También está disponible una biblioteca JavaScript HAMT ^{[ 6 ]} basada en la implementación de Clojure. La implementación Rubinius ^{[ 7 ]} de Ruby incluye un HAMT, escrito principalmente en Ruby pero con 3 ^{[ 8 ]} primitivas. Los mapas grandes en Erlang utilizan una representación HAMT persistente internamente desde la versión 18.0. ^{[ 9 ]} El lenguaje de programación Pony utiliza un HAMT para el mapa hash en su paquete de colecciones persistentes. ^{[ 10 ]} Las crates im e im-rc, que proporcionan tipos de colecciones persistentes para el lenguaje de programación Rust, utilizan un HAMT para sus tablas hash persistentes y conjuntos hash. ^{[ 11 ]}

La versión concurrente sin bloqueo ^{[ 12 ]} del árbol de prefijos hash, denominada Ctrie, es una implementación mutable y segura para subprocesos que garantiza el progreso. Se ha demostrado que la estructura de datos es correcta ^{[ 13 ]} : se ha comprobado que las operaciones de Ctrie poseen las propiedades de atomicidad , linealizabilidad y ausencia de bloqueo .

En 2017, Michael Steindorfer presentó CHAMP (Compressed Hash-Array Mapped Prefix-tree) ^{[ 14 ]} , una evolución de HAMT que utiliza menos espacio y mejora el rendimiento para algunas operaciones, principalmente la iteración y la prueba de igualdad (comparación de dos colecciones). La principal diferencia es que, mientras que un nodo HAMT utiliza un único mapa de bits y vector de almacenamiento tanto para los elementos como para los nodos hijos, CHAMP utiliza mapas de bits separados para los elementos y los nodos hijos (no deben tener bits 1 en común) y almacena los elementos y los nodos hijos en diferentes regiones del vector.

• Arreglo de Judy
• Árbol de raíz