HAT-trie 📖 Wikipedia

El HAT-trie es un tipo de radix trie que utiliza nodos array para indexar pares clave-valor individuales bajo nodos radix y cubos de hash en un array asociativo. A diferencia de una tabla hash simple, los HAT-tries almacenan los pares clave-valor en una colección ordenada. Los inventores originales fueron Nikolas Askitis y Ranjan Sinha.^[1]​^[2]​ Askitis y Zobel demostraron que la creación y el acceso a la colección clave-valor del HAT-trie son considerablemente más rápidos que otros métodos de acceso ordenado y son comparables al array hash, que es una colección desordenada.^[3]​ Esto se debe a la amigabilidad con la caché de la estructura de datos, que intenta ofrecer el acceso a los datos en tiempo y espacio dentro del tamaño de línea de caché de 64 bytes de las CPU modernas.

Un nuevo trie HAT recién inicializado comienza siendo un puntero nulo que representa un nodo vacío. La primera clave añadida asigna el nodo array más pequeño y copia en él el par clave-valor, que se convierte en la primera raíz del trie. Cada par clave-valor subsiguiente se añade al nodo array inicial hasta alcanzar un tamaño máximo, tras lo cual el nodo se desborda redistribuyendo sus claves en un cubo hash con nuevos nodos array subyacentes, uno por cada ranura hash ocupada en el cubo hash. El cubo hash se convierte en la nueva raíz del trie. Las cadenas de clave se almacenan en los nodos array con un byte de codificación de longitud prefijada a los bytes del valor de la clave. El valor asociado a cada clave puede almacenarse en línea — alternándose con las cadenas de clave — o colocarse en un segundo array — por ejemplo, en la memoria inmediatamente después — y unirse al nodo array.^[4]​

Una vez que el trie ha crecido hasta su primer nodo de cubo hash, este distribuye nuevas claves según una función hash basada en su valor de la clave en los nodos array contenidos bajo el nodo de cubo de hash. Se siguen añadiendo claves hasta alcanzar el número máximo de claves que puede contener un cubo hash. El contenido del cubo se redistribuye entonces en un nuevo nodo de base según el primer carácter del valor de la clave almacenada, reemplazando al nodo de cubo hash como raíz del trie^[5]​ (por ejemplo, véase Burstsort^[6]​). Las claves y los valores existentes contenidos en el cubo hash se acortan en un carácter cada uno y se colocan bajo el nuevo nodo radix en un conjunto de nuevos nodos array.

El acceso ordenado a la colección se proporciona enumerando las claves en un cursor mediante el descenso por el trie radix para ensamblar los caracteres iniciales, terminando en un cubo hash o en un nodo array. Los punteros a las claves contenidas en el cubo hash o en el nodo array se ensamblan en una array para ordenación y forman parte del cursor. Dada la existencia de un número máximo de claves en un contenedor hash o nodo de matriz, existe también un límite fijo preestablecido para el tamaño del cursor en todo momento. Una vez que las claves del cubo hash o nodo array se agotan mediante get-next (o get-previous, implementando las funciones de un iterador), el cursor se mueve a la siguiente entrada del nodo de base y el proceso se repite.^[7]​

• «HatTrie». GitHub (en inglés). Consultado el 15 de agosto de 2025. 
• «A C++ implementation of a fast and memory efficient HAT-trie». GitHub (en inglés). Consultado el 15 de agosto de 2025.