El HAT-Trie es un tipo de trie de base que utiliza nodos de matriz para recopilar pares clave-valor individuales bajo nodos de base y cubos de hash en una matriz asociativa . A diferencia de una tabla hash simple , los intentos de HAT almacenan el valor-clave en una colección ordenada. Los inventores originales son Nikolas Askitis y Ranjan Sinha. [1] [2] El Dr. Askitis muestra que crear y acceder a la colección de claves / valores de HAT-trie es considerablemente más rápido que otros métodos de acceso ordenados y es comparable al Array Hash, que es una colección sin clasificar. [3] Esto se debe a la naturaleza compatible con la memoria caché de la estructura de datos que intenta agrupar el acceso a los datos en el tiempo y el espacio en 64 bytes.tamaño de la línea de caché de la CPU moderna.
Descripción
Un nuevo HAT-Trie comienza como un puntero NULL que representa un nodo vacío. La primera clave agregada 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 de clave / valor subsiguiente se agrega al nodo de matriz inicial hasta que se alcanza un tamaño máximo, después de lo cual el nodo se rompe redistribuyendo sus claves en un depósito de hash con nuevos nodos de matriz subyacentes, uno para cada ranura de hash ocupada en el depósito. . El cubo de hash se convierte en la nueva raíz del trie. Las cadenas de claves se almacenan en los nodos de la matriz con un byte de codificación de longitud prefijado a los bytes del valor de la clave. El valor asociado con cada clave puede almacenarse en línea alternando con las cadenas de claves, o colocado en una segunda matriz, por ejemplo, en la memoria inmediatamente después y unida al nodo de la matriz. [4]
Una vez que el trie ha crecido hasta convertirse en su primer nodo de cubo hash, el cubo hash distribuye nuevas claves de acuerdo con una función hash del valor de la clave en los nodos de matriz contenidos debajo del nodo del cubo. Se continúan agregando claves hasta que se alcanza un número máximo de claves para un nodo de depósito de hash en particular. El contenido del depósito se redistribuye luego en un nuevo nodo de base de acuerdo con el primer carácter del valor de clave almacenado, que reemplaza el nodo del depósito de hash como la raíz del trie [5] (por ejemplo, ver Burstsort [6] ). Las claves y valores existentes contenidos en el depósito de hash se acortan cada uno en un carácter y se colocan debajo del nuevo nodo de base en un conjunto de nuevos nodos de matriz.
El acceso ordenado a la colección se proporciona enumerando las claves en un cursor ramificando hacia abajo el trie de la raíz para ensamblar los caracteres principales, terminando en un cubo hash o un nodo de matriz. Los punteros a las claves contenidas en el cubo de hash o el nodo de matriz se ensamblan en una matriz que es parte del cursor para ordenar. Dado que hay un número máximo de claves en un cubo hash o un nodo de matriz, existe un límite fijo preestablecido para el tamaño del cursor en todos los momentos. Después de que las claves para el cubo de hash o el nodo de matriz se agotan mediante get-next (o get-previous) (ver Iterador ), el cursor se mueve a la siguiente entrada del nodo de base y el proceso se repite. [7]
Referencias
- ^ descrito en un artículo publicado en Proc. Trigésima Conferencia de Ciencias de la Computación de Australasia (ACSC2007), Ballarat Australia. CRPIT, 62. Dobbie, G., Ed. ACS. 97-105
- ^ https://dl.acm.org/citation.cfm?id=1273761 HAT-trie: Una estructura de datos basada en Trie consciente de la caché para cadenas
- ^ Askitis, N. & Zobel, J. (2005), Resolución de colisión consciente de caché para tablas hash de cadenas, en 'Proc. SPIRE String Processing and Information Retrieval Symp. ', Springer-Verlag, págs. 92-104
- ^ Askitis, N. y Zobel, J. 2011. Rediseño de la tabla hash de cadenas, trie de ráfagas y BST para explotar la caché. ACM J. Exp. Algor. 15, 1, artículo 1.7 (enero de 2011)
- ^ Intentos de ráfaga: una estructura de datos rápida y eficiente para claves de cadena ACM Trans. Inf. Syst., Vol. 20, No. 2. (abril de 2002), págs. 192-223, doi: 10.1145 / 506309.506312 por Steffen Heinz, Justin Zobel, Hugh E. Williams
- ^ Sinha, R. y Wirth, A. 2010. Engineering burstsort: Hacia una clasificación rápida de cuerdas en el lugar. ACM J. Exp. Algor. 15, artículo 2.5 (marzo de 2010)
- ^ http://www.siam.org/meetings/alenex03/Abstracts/rsinha.pdf Clasificación consciente de la caché de grandes conjuntos de cadenas con intentos dinámicos