Árbol de matriz hash - Hashed array tree
En informática , un árbol de matriz hash ( HAT ) es una estructura de datos de matriz dinámica publicada por Edward Sitarski en 1996, que mantiene una matriz de fragmentos de memoria separados (u "hojas") para almacenar los elementos de datos, a diferencia de las matrices dinámicas simples que mantienen sus datos en un área de memoria contigua. Su objetivo principal es reducir la cantidad de copia de elementos debido a las operaciones automáticas de cambio de tamaño de la matriz y mejorar los patrones de uso de la memoria.
Mientras que los arreglos dinámicos simples basados en la expansión geométrica desperdician espacio lineal (Ω ( n )), donde n es el número de elementos en el arreglo , los árboles de arreglos hash desperdician solo el orden O ( √ n ) de espacio de almacenamiento. Una optimización del algoritmo permite eliminar completamente la copia de datos, a costa de aumentar el espacio desperdiciado.
Puede realizar el acceso en un tiempo constante ( O (1)), aunque un poco más lento que las matrices dinámicas simples. El algoritmo tiene un rendimiento amortizado O (1) cuando se agrega una serie de objetos al final de un árbol de matriz con hash. Al contrario de su nombre, no utiliza funciones hash .
Definiciones
Según lo definido por Sitarski, un árbol de matriz con hash tiene un directorio de nivel superior que contiene una potencia de dos matrices de hojas. Todas las matrices de hojas tienen el mismo tamaño que el directorio de nivel superior. Esta estructura se parece superficialmente a una tabla hash con cadenas de colisión basadas en matrices, que es la base para el nombre de árbol de matrices hash . Un árbol de matriz hash completo puede contener m 2 elementos, donde m es el tamaño del directorio de nivel superior. El uso de potencias de dos permite un direccionamiento físico más rápido a través de operaciones de bits en lugar de operaciones aritméticas de cociente y resto y asegura el rendimiento amortizado O (1) de la operación de adición en presencia de copia de matriz global ocasional mientras se expande.
Expansiones y reducciones de tamaño
En un esquema de expansión geométrica de matriz dinámica habitual , la matriz se reasigna como una porción secuencial completa de memoria con el nuevo tamaño el doble de su tamaño actual (y luego todos los datos se mueven a la nueva ubicación). Esto asegura O (1) operaciones amortizadas a un costo de O (n) espacio desperdiciado, ya que la matriz ampliada se llena a la mitad de su nueva capacidad.
Cuando un árbol de matriz con hash está lleno, su directorio y sus hojas deben reestructurarse al doble de su tamaño anterior para dar cabida a operaciones de adición adicionales. Los datos almacenados en la estructura anterior se trasladan a las nuevas ubicaciones. Luego, solo se asigna una hoja nueva y se agrega a la matriz superior que, por lo tanto, se llena solo hasta una cuarta parte de su nueva capacidad. Todas las hojas adicionales aún no están asignadas y solo se asignarán cuando sea necesario, desperdiciando así solo O ( √ n ) de almacenamiento.
Existen múltiples alternativas para reducir el tamaño: cuando un árbol de matriz hash tiene un octavo de su capacidad, se puede reestructurar a un árbol de matriz hash medio completo más pequeño; otra opción es solo liberar las matrices de hojas no utilizadas, sin cambiar el tamaño de las hojas. Otras optimizaciones incluyen agregar nuevas hojas sin cambiar el tamaño mientras crece la matriz de directorios según sea necesario, posiblemente a través de la expansión geométrica. Esto eliminará la necesidad de copiar los datos por completo a costa de hacer que el espacio desperdiciado sea O ( n ), con una pequeña constante, y solo se realizará la reestructuración cuando se alcance un umbral de sobrecarga establecido.
Estructuras de datos relacionadas
| Lista enlazada | Formación | Matriz dinámica | Árbol equilibrado | Lista de acceso aleatorio | Árbol de matriz hash | |
|---|---|---|---|---|---|---|
| Indexación | Θ ( n ) | Θ (1) | Θ (1) | Θ (log n) | Θ (log n) | Θ (1) |
| Insertar / eliminar al principio | Θ (1) | N / A | Θ ( n ) | Θ (log n) | Θ (1) | Θ ( n ) |
| Insertar / eliminar al final | Θ (1) cuando se conoce el último elemento ; Θ ( n ) cuando se desconoce el último elemento |
N / A | Θ (1) amortizado | Θ (log n ) | N / A | Θ (1) amortizado |
| Insertar / eliminar en el medio | tiempo de búsqueda + Θ (1) | N / A | Θ ( n ) | Θ (log n ) | N / A | Θ ( n ) |
| Espacio desperdiciado (promedio) | Θ ( n ) | 0 | Θ ( n ) | Θ ( n ) | Θ ( n ) | Θ ( √ n ) |
Brodnik y col. presentó un algoritmo de matriz dinámica con un perfil de desperdicio de espacio similar al de los árboles de matriz hash. La implementación de Brodnik conserva las matrices de hojas asignadas previamente, con una función de cálculo de direcciones más complicada en comparación con los árboles de matrices hash.
