El hash extensible es un tipo de sistema de hash que trata un hash como una cadena de bits y usa un trie para la búsqueda de cubos. [1] Debido a la naturaleza jerárquica del sistema, el cambio de hash es una operación incremental (se realiza un depósito a la vez, según sea necesario). Esto significa que las aplicaciones urgentes se ven menos afectadas por el crecimiento de la tabla que por los refritos estándar de la tabla completa.
Dispersión extensible fue descrita por Ronald Fagin en 1979. Prácticamente todos los sistemas de archivos modernos utilizan hash ya sea extensible o árboles B . En particular, el sistema de archivos global , ZFS y el sistema de archivos SpadFS utilizan hash ampliable. [2]
Ejemplo
Suponga que la función hash devuelve una cadena de bits. Los primeros i bits de cada cadena se utilizarán como índices para averiguar dónde irán en el "directorio" (tabla hash). Además, i es el número más pequeño, de modo que el índice de cada elemento de la tabla es único.
Claves a utilizar:
Supongamos que para este ejemplo en particular, el tamaño del depósito es 1. Las dos primeras claves que se insertarán, k 1 y k 2 , se pueden distinguir por el bit más significativo y se insertarían en la tabla de la siguiente manera:
Ahora, si k 3 fuera a agregarse a la tabla, no sería suficiente distinguir las tres claves por un bit (porque tanto k 3 como k 1 tienen 1 como su bit más a la izquierda). Además, debido a que el tamaño del cubo es uno, la mesa se desbordaría. Debido a que comparar los dos primeros bits más significativos daría a cada clave una ubicación única, el tamaño del directorio se duplica de la siguiente manera:
Y así, ahora k 1 y k 3 tienen una ubicación única, que se distingue por los dos primeros bits más a la izquierda. Debido a que k 2 está en la mitad superior de la tabla, tanto 00 como 01 apuntan a ella porque no hay otra clave con la que comparar que comience con un 0.
El ejemplo anterior es de Fagin et al. (1979) error de harvtxt: múltiples objetivos (2 ×): CITEREFFaginNievergeltPippengerStrong1979 ( ayuda ) .
Más detalles
Ahora, es necesario insertar k 4 , y tiene los dos primeros bits como 01 .. (1110), y usando una profundidad de 2 bits en el directorio, esto se asigna de 01 al Bucket A. El Bucket A está lleno (tamaño máximo 1 ), por lo que debe dividirse; debido a que hay más de un puntero al Bucket A, no es necesario aumentar el tamaño del directorio.
Lo que se necesita es información sobre:
- El tamaño de la clave que asigna el directorio (la profundidad global) y
- El tamaño de la clave que asignó previamente el depósito (la profundidad local)
Para distinguir los dos casos de acción:
- Duplicar el directorio cuando un depósito se llena
- Crear un nuevo depósito y redistribuir las entradas entre el depósito antiguo y el nuevo.
Al examinar el caso inicial de una estructura hash extensible, si cada entrada de directorio apunta a un depósito, entonces la profundidad local debe ser igual a la profundidad global.
El número de entradas de directorio es igual a 2 de profundidad global y el número inicial de depósitos es igual a 2 de profundidad local .
Por lo tanto, si la profundidad global = la profundidad local = 0, entonces 2 0 = 1, entonces un directorio inicial de un puntero a un cubo.
Volviendo a los dos casos de acción; si el balde está lleno:
- Si la profundidad local es igual a la profundidad global, entonces solo hay un puntero al depósito y no hay otros punteros de directorio que se puedan asignar al depósito, por lo que el directorio debe duplicarse.
- Si la profundidad local es menor que la profundidad global, entonces existe más de un puntero desde el directorio al depósito y el depósito se puede dividir.
La clave 01 apunta al Bucket A, y la profundidad local del Bucket A de 1 es menor que la profundidad global del directorio de 2, lo que significa que las claves hash al Bucket A solo han usado un prefijo de 1 bit (es decir, 0), y el bucket debe tener su contenido dividido usando las claves 1 + 1 = 2 bits de longitud; en general, para cualquier profundidad local d donde d es menor que D, la profundidad global, entonces d debe incrementarse después de una división de cubeta, y la nueva d debe usarse como el número de bits de la clave de cada entrada para redistribuir las entradas de la anterior. cubo en los nuevos cubos.
Ahora,
se intenta de nuevo, con 2 bits 01 .., y ahora la clave 01 apunta a un nuevo depósito, pero todavía hay en eso ( y también comienza con 01).
Si hubiera sido 000110, con clave 00, no habría habido problema, porque habría permanecido en el nuevo cubo A 'y el cubo D habría estado vacío.
(Este habría sido, con mucho, el caso más probable cuando los depósitos tienen un tamaño mayor que 1 y es muy poco probable que los depósitos recién divididos se desborden, a menos que todas las entradas se vuelvan a convertir en un depósito. Pero solo para enfatizar la función de la información de profundidad, el ejemplo se seguirá lógicamente hasta el final).
Por lo tanto, el Bucket D debe dividirse, pero una verificación de su profundidad local, que es 2, es lo mismo que la profundidad global, que es 2, por lo que el directorio debe dividirse nuevamente para contener claves con suficiente detalle, p. Ej. 3 bits.
- El cubo D debe dividirse debido a que está lleno.
- Como la profundidad local de D = la profundidad global, el directorio debe duplicarse para aumentar el detalle de bits de las claves.
- La profundidad global se ha incrementado después de que el directorio se dividió a 3.
- La nueva entrada se cambia la clave con profundidad global 3 bits y termina en D, que tiene profundidad local 2, que ahora se puede incrementar a 3 y D se puede dividir en D 'y E.
- El contenido del cubo dividido D, , se ha vuelto a introducir con 3 bits y termina en D.
- Se vuelve a intentar K4 y termina en E, que tiene una ranura de repuesto.
Ahora, está en D y se intenta de nuevo, con 3 bits 011 .., y apunta al cubo D que ya contiene por lo que está lleno; La profundidad local de D es 2, pero ahora la profundidad global es 3 después de duplicar el directorio, por lo que ahora D se puede dividir en el cubo D 'y E, el contenido de D, tiene su reintentado con una nueva máscara de bits de profundidad global de 3 y termina en D ', luego la nueva entrada se reintenta con enmascarado usando el nuevo recuento de bits de profundidad global de 3 y esto da 011 que ahora apunta a un nuevo cubo E que está vacío. Entonces va en el Cubo E.
Implementación de ejemplo
A continuación se muestra el algoritmo de hash extensible en Python , con la asociación del bloque de disco / página de memoria, el almacenamiento en caché y los problemas de coherencia eliminados. Tenga en cuenta que existe un problema si la profundidad excede el tamaño de bits de un número entero, porque entonces la duplicación del directorio o la división de un depósito no permitirá que las entradas se vuelvan a aplicar a distintos depósitos.
El código usa los bits menos significativos , lo que hace que sea más eficiente expandir la tabla, ya que el directorio completo se puede copiar como un bloque ( Ramakrishnan & Gehrke (2003) ).
Ejemplo de Python
PAGE_SZ = 10class Página : def __init__ ( self ) -> None : self . m = [] yo . d = 0 def full ( self ) -> bool : return len ( self . m ) > = PAGE_SZ def put ( self , k , v ) -> None : para i , ( clave , valor ) en enumerate ( self . m ): if key == k : del self . m [ i ] ruptura auto . m . añadir (( k , v )) def get ( self , k ): para clave , valor en self . m : si clave == k : valor de retorno clase EH : def __init__ ( self ) -> None : self . gd = 0 propio . pp = [ Página ()] def get_page ( self , k ): h = hash ( k ) return self . pp [ h & (( 1 << auto . gd ) - 1 )] def put ( self , k , v ) -> Ninguno : p = self . get_page ( k ) full = p . completo () pág . poner ( k , v ) si está lleno : si p . d == yo . gd : self . pp * = 2 uno mismo . gd + = 1 p0 = Página () p1 = Página () p0 . d = p1 . d = p . d + 1 bit = 1 << p . d para k2 , v2 en p . m : h = hash de ( K2 ) new_p = p1 si h y se mordió otro p0 new_p . poner ( k2 , v2 ) para i en rango ( hash ( k ) & ( bit - 1 ), len ( self . pp ), bit ): self . pp [ i ] = p1 si i & bit else p0 def get ( self , k ): return self . get_page ( k ) . obtener ( k )if __name__ == "__main__" : eh = EH () N = 10088 l = lista ( rango ( N )) importar al azar al azar . barajar ( l ) para x en l : eh . poner ( x , x ) imprimir ( l ) para i en el rango ( N ): imprimir ( eh . obtener ( i ))
Notas
- ^ Fagin, R .; Nievergelt, J .; Pippenger, N .; Strong, HR (septiembre de 1979), "Hashing extensible: un método de acceso rápido para archivos dinámicos", Transacciones de ACM en sistemas de base de datos , 4 (3): 315–344, doi : 10.1145 / 320083.320092 , S2CID 2723596
- ^ Mikuláš Patocka. "Diseño e Implementación del Sistema de Archivos Spad" . Sección "4.1.6 Hash ampliable: ZFS y GFS" y "Tabla 4.1: Organización de directorios en sistemas de archivos". 2006.
Ver también
Referencias
- Fagin, R .; Nievergelt, J .; Pippenger, N .; Strong, HR (septiembre de 1979), "Hashing extensible: un método de acceso rápido para archivos dinámicos", Transacciones de ACM en sistemas de base de datos , 4 (3): 315–344, doi : 10.1145 / 320083.320092 , S2CID 2723596
- Ramakrishnan, R .; Gehrke, J. (2003), Sistemas de gestión de bases de datos, 3ª edición: Capítulo 11, Indexación basada en hash , págs. 373–378
- Silberschatz, Avi; Korth, Henry; Sudarshan, S., Conceptos del sistema de base de datos, Sexta edición: Capítulo 11.7, Hash dinámico
enlaces externos
- Este artículo incorpora material de dominio público del documento NIST : Negro, Paul E. "Hash extensible" . Diccionario de algoritmos y estructuras de datos .
- Notas de hash extensibles en la Universidad Estatal de Arkansas
- Notas hash extensibles
- Diapositivas del libro Conceptos del sistema de bases de datos sobre hash extensible para índices dinámicos basados en hash