HAT-trie

El HAT-trie es un tipo de radix trie que utiliza nodos de matriz para recopilar pares clave-valor individuales bajo nodos radix y cubetas hash en una matriz asociativa . A diferencia de una tabla hash simple , los HAT-tries almacenan clave-valor en una colección ordenada. Los inventores originales son Nikolas Askitis y Ranjan Sinha. ^{[ 1 ] [ 2 ]} Askitis y Zobel demostraron que construir y acceder a la colección clave/valor HAT-trie es considerablemente más rápido que otros métodos de acceso ordenados y es comparable al hash de matriz que es una colección no ordenada. ^{[ 3 ]} Esto se debe a la naturaleza amigable de la caché de la estructura de datos que intenta agrupar el acceso a los datos en tiempo y espacio en el tamaño de línea de caché de 64 bytes de la CPU moderna.

Un nuevo trie HAT comienza como un puntero NULL que representa un nodo vacío. La primera clave añadida asigna el nodo de matriz 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 de matriz inicial hasta alcanzar un tamaño máximo, tras lo cual el nodo se expande redistribuyendo sus claves en un cubo hash con nuevos nodos de matriz subyacentes, uno por cada ranura hash ocupada en el cubo. El cubo hash se convierte en la nueva raíz del trie. Las cadenas de clave se almacenan en los nodos de matriz con un byte de codificación de longitud antepuesto a los bytes de valor de la clave. El valor asociado a cada clave puede almacenarse en línea alternando con las cadenas de clave, o bien colocarse en una segunda matriz, por ejemplo, en la memoria inmediatamente posterior y unirse al nodo de matriz. ^{[ 4 ]}

Una vez que el trie ha crecido hasta su primer nodo de cubo hash, el cubo hash distribuye nuevas claves según una función hash del valor de la clave en nodos de matriz contenidos debajo del nodo del cubo. Se siguen agregando claves hasta que se alcanza un número máximo de claves para un nodo de cubo hash en particular. El contenido del cubo se redistribuye entonces en un nuevo nodo radix según el primer carácter del valor de la clave almacenada, que reemplaza al nodo del 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 debajo del nuevo nodo radix en un conjunto de nuevos nodos de matriz.

El acceso ordenado a la colección se proporciona enumerando las claves en un cursor mediante la ramificación del árbol de prefijos radix para ensamblar los caracteres iniciales, terminando en un cubo hash o un nodo de matriz. Los punteros a las claves contenidas en el cubo hash o el nodo de matriz se ensamblan en una matriz que forma parte del cursor para la ordenación. Dado que existe un número máximo de claves en un cubo hash o un nodo de matriz, hay un límite fijo preestablecido para el tamaño del cursor en todo momento. Después de que las claves del cubo hash o del nodo de matriz se agotan mediante get-next (o get-previous) (ver Iterador ), el cursor se mueve a la siguiente entrada del nodo radix y el proceso se repite. ^{[ 7 ]}

• Implementación de HAT-Trie de referencia en C
• Implementación en C++ de un HAT-trie rápido y eficiente en memoria.