En informática , un árbol de matriz hash ( HAT ) es una estructura de datos de matriz dinámica publicada por Edward Sitarski en 1996, [1] [2] que mantiene una matriz de fragmentos de memoria separados (u "hojas") para almacenar los elementos de datos, a diferencia de los arreglos dinámicos simples que mantienen sus datos en un área de memoria contigua. Su objetivo principal es reducir la cantidad de copias 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 un orden O ( √ n ) de espacio de almacenamiento. Una optimización del algoritmo permite eliminar por completo 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 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 del 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. [2] 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 [2] 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. [ cita requerida ]
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. [2]
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) [3] | Θ (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 [3] | Θ (1) amortizado |
Insertar / eliminar en el medio | tiempo de búsqueda + Θ (1) [4] [5] | N / A | Θ ( n ) | Θ (log n ) | N / A [3] | Θ ( n ) |
Espacio desperdiciado (promedio) | Θ ( n ) | 0 | Θ ( n ) [6] | Θ ( n ) | Θ ( n ) | Θ ( √ n ) |
Brodnik y col. [7] 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.
Ver también
Referencias
- ^ Sitarski, Edward (septiembre de 1996), HATs: Hashed Array Trees
- ^ a b c d Sitarski, Edward (septiembre de 1996), "Algorithm Alley - HATs: Hashed array trees" , Dr. Dobb's Journal , 21 (11)
- ^ a b c Chris Okasaki (1995). "Listas de acceso aleatorio puramente funcionales". Actas de la Séptima Conferencia Internacional sobre Lenguajes de Programación Funcionales y Arquitectura de Computadoras : 86–95. doi : 10.1145 / 224164.224187 .
- ^ Presentación del día 1 - Bjarne Stroustrup: Estilo C ++ 11 en GoingNative 2012 en channel9.msdn.com desde el minuto 45 o foil 44
- ^ Procesamiento de números: por qué nunca, nunca, NUNCA debería volver a usar la lista vinculada en su código en kjellkod.wordpress.com
- ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert ; Munro, JI; Demaine, ED (1999), Matrices redimensionables en tiempo y espacio óptimos (Informe técnico CS-99-09) (PDF) , Departamento de Ciencias de la Computación, Universidad de Waterloo
- ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert ; Munro, JI; Demaine, ED (1999), "Matrices redimensionables en tiempo y espacio óptimos" (PDF) , Informe técnico CS-99-09 , Departamento de Ciencias de la Computación, Universidad de Waterloo