Hispanopedia WikiEn informática , un árbol de matriz hash ( HAT ) es una estructura de datos de matriz dinámica publicada por Edward Sitarski en 1996 [1] 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 las matrices dinámicas simples basadas en la expansión geométrica desperdician espacio lineal (Ω( n )), donde n es el número de elementos de la matriz , los árboles de matrices con hash desperdician solo espacio de almacenamiento de orden O ( √n ). Una optimización del algoritmo permite eliminar por completo la copia de datos, a costa de aumentar el espacio desperdiciado.
Puede realizar accesos en tiempo constante ( O (1)), aunque ligeramente más lento que las matrices dinámicas simples. El algoritmo tiene un rendimiento amortizado O(1) al agregar una serie de objetos al final de un árbol de matriz hash. Al contrario de lo que sugiere su nombre, no utiliza funciones hash .
Definiciones
Según la definición de Sitarski, un árbol de matriz hash tiene un directorio de nivel superior que contiene una potencia de dos de 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 matriz hash . Un árbol de matriz hash completo puede contener m 2 elementos, donde m es el tamaño del directorio de nivel superior. [1] 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 [1] y garantiza el rendimiento amortizado O(1) de la operación de anexión en presencia de una copia de matriz global ocasional durante la expansión.
Ampliaciones y reducciones de tamaño
En un esquema de expansión geométrica de matriz dinámica habitual , la matriz se reasigna como un bloque secuencial completo de memoria con un nuevo tamaño que duplica su tamaño actual (y luego todos los datos se trasladan a la nueva ubicación). Esto garantiza O(1) operaciones amortizadas a un costo de O(n) espacio desperdiciado, ya que la matriz ampliada se llena hasta la mitad de su nueva capacidad.
Cuando un árbol de matriz hash está lleno, su directorio y sus hojas deben reestructurarse al doble de su tamaño anterior para dar cabida a operaciones de anexión adicionales. Los datos almacenados en la estructura anterior se trasladan entonces a las nuevas ubicaciones. A continuación, solo se asigna una nueva hoja y se agrega a la matriz superior, que, de este modo, se llena solo hasta una cuarta parte de su nueva capacidad. Todas las hojas adicionales aún no se asignan y solo se asignarán cuando sea necesario, desperdiciando así solo O ( √ n ) de almacenamiento. [2]
Existen múltiples alternativas para reducir el tamaño: cuando un árbol de matriz hash está lleno hasta un octavo, se puede reestructurar a un árbol de matriz hash más pequeño, lleno hasta la mitad; otra opción es solo liberar 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 se hace crecer la matriz de directorios según sea necesario, posiblemente a través de una expansión geométrica. Esto eliminará la necesidad de copiar datos por completo a costa de hacer que el espacio desperdiciado sea O ( n ), con una constante pequeña, y solo realizar la reestructuración cuando se alcance un umbral de sobrecarga establecido. [1]
Estructuras de datos relacionadas
Brodnik et al. [7] presentaron 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 dirección más complicada en comparación con los árboles de matriz hash.
Véase también
Referencias
- ^ abcd Sitarski, Edward (septiembre de 1996). "Algorithm Alley -- HATs: árboles de matrices hash". Dr. Dobb's Journal . Vol. 21, núm. 11.
- ^ Katajainen, Jyrki (5–8 de junio de 2016). "Matrices dinámicas eficientes en el peor de los casos en la práctica". En Kulikov, Alexander S.; Goldberg, Andrew V. (eds.). Algoritmos experimentales . XV Simposio internacional sobre algoritmos experimentales, SEA 2016. Apuntes de clase en informática. Vol. 9685. San Petersburgo, Rusia : Springer Science+Business Media . pág. 173. doi :10.1007/978-3-319-38851-9_12. ISBN 978-3-319-38851-9.
- ^ Keynote del día 1 - Bjarne Stroustrup: C++11 Style en GoingNative 2012 en channel9.msdn.com a partir del minuto 45 o 44
- ^ Análisis de números: Por qué nunca, nunca, NUNCA deberías volver a utilizar listas enlazadas en tu 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
- ^ abc Chris Okasaki (1995). "Listas de acceso aleatorio puramente funcionales". Actas de la Séptima Conferencia Internacional sobre Lenguajes de Programación Funcional y Arquitectura de Computadoras : 86–95. doi :10.1145/224164.224187.
- ^ 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
