Un trie mapeado en una matriz hash [1] ( HAMT ) es una implementación de una matriz asociativa que combina las características de una tabla hash y un trie mapeado en una matriz . [1] Es una versión refinada de la noción más general de un árbol hash .
Un HAMT es un trie mapeado en una matriz donde las claves primero se codifican para asegurar una distribución uniforme de claves y una longitud de clave constante.
En una implementación típica del trie mapeado en matriz de HAMT, cada nodo contiene una tabla con un número fijo N de ranuras, y cada ranura contiene un puntero nulo o un puntero a otro nodo. N es comúnmente 32. Como asignar espacio para N punteros para cada nodo sería costoso, cada nodo contiene en cambio un mapa de bits que tiene una longitud de N bits, donde cada bit indica la presencia de un puntero distinto de nulo. A esto le sigue una matriz de punteros con una longitud igual a la cantidad de unos en el mapa de bits (su peso Hamming ).
El trie mapeado en matriz hash logra una velocidad similar a la de una tabla hash mientras utiliza la memoria de manera mucho más económica. Además, es posible que sea necesario redimensionar periódicamente una tabla hash, una operación costosa, mientras que las HAMT crecen de manera dinámica. En general, el rendimiento de las HAMT mejora con una tabla raíz más grande con algunos múltiplos de N ranuras; algunas variantes de las HAMT permiten que la raíz crezca de manera diferida [1] con un impacto insignificante en el rendimiento.
La implementación de una 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 está disponible en algunos lenguajes de alto nivel . Aunque el conteo de población se puede implementar en software en tiempo O(1) utilizando una serie de instrucciones de desplazamiento y adición , al hacerlo, la operación puede ser un orden de magnitud más lenta. [ cita requerida ]
Los lenguajes de programación Clojure , [2] Scala y Frege [3] utilizan una variante persistente de intentos 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 HAMT de Javascript [6] basada en la implementación de Clojure. La implementación Rubinius [7] de Ruby incluye una HAMT, escrita 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 una HAMT para el mapa hash en su paquete de colecciones persistentes. [10] Las cajas im e im-rc, que proporcionan tipos de colecciones persistentes para el lenguaje de programación Rust, utilizan una HAMT para sus tablas hash y conjuntos hash persistentes. [11]
La versión concurrente sin bloqueos [12] del hash trie, 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 demostrado que las operaciones Ctrie tienen propiedades de atomicidad , linealización y ausencia de bloqueos .