Hashing en espiral

El hash en espiral , también conocido como almacenamiento en espiral, es un algoritmo de hash extensible. ^{[1] [2] [3] [4] [5]} Como en todos los esquemas de hash, el hash en espiral almacena registros en un número variable de contenedores, utilizando una clave de registro para direccionar. En un archivo de hash lineal en expansión , los contenedores se dividen en un orden predefinido. Esto da como resultado la adición de un nuevo contenedor al final del archivo. Si bien esto permite la reorganización gradual del archivo, el número esperado de registros en el contenedor recién creado y el contenedor del que se divide cae a la mitad del número anterior. Se hicieron varios intentos para aliviar esta caída repentina en la utilización del espacio. El almacenamiento en espiral de Martin utiliza un enfoque diferente. El archivo consta de un número de contenedores numerados continuamente. Los contenedores con números más bajos (izquierda) tienen un número esperado de registros más alto. Cuando el archivo se expande, el contenedor más a la izquierda se reemplaza por dos contenedores a la derecha. Existen algunas variantes de esta idea. ^{[6] [7] [8]}

El hash en espiral requiere una función hash uniforme de las claves de los registros en el intervalo unitario . Si el archivo hash comienza en el depósito , la clave se asigna a un número real . La dirección final se calcula entonces como donde es el "factor de extensión". Cuando se incrementa , se crean aproximadamente nuevos depósitos a la derecha. Larson ^[9] realizó experimentos que demostraron que el hash lineal todavía tenía un rendimiento superior al hash en espiral. ${\displaystyle [0,1]}$ ${\displaystyle S}$ ${\displaystyle k}$ ${\displaystyle x=S+h(k)\in [S,S+1]}$ ${\displaystyle \lfloor d^{x}\rfloor }$ ${\displaystyle d}$ ${\displaystyle S}$ ${\displaystyle d}$

Véase también

• Hashing extensible
• Hashing lineal

Referencias

1. Martin, GN (1979), "Almacenamiento en espiral", Tech. Rep. 27, Univ. de Warwick, Coventry, Reino Unido
2. Mullin, James K. (1981), "Hash lineal estrictamente controlado sin almacenamiento de desbordamiento separado", BIT Numerical Mathematics , 21 (4): 390–400, doi :10.1007/BF01932837, S2CID  43311559
3. Mullin, James K. (1985), "Almacenamiento en espiral: Hashing dinámico eficiente con rendimiento constante", The Computer Journal , 28 (3): 330–334, doi : 10.1093/comjnl/28.3.330
4. Chu, JH.; Knott, GD (1994), "Un análisis del hash en espiral", The Computer Journal , 37 (8): 715-719, doi : 10.1093/comjnl/37.8.715
5. Enbody, Richard; Du, HC (junio de 1988), "Esquemas de hash dinámicos", ACM Computing Surveys , 20 (2): 85–113, doi : 10.1145/46157.330532 , S2CID  1437123
6. Mullin, James K. (1984), "Unified Dynamic Hashing", Actas de la 10.ª Conferencia internacional sobre bases de datos de gran tamaño (VLDB)
7. Kawagoe, K. (1985), "Modified Dynamic Hashing", Actas de la conferencia internacional SIGMOD sobre gestión de datos
8. Chang, Ye-In; Lee, Chien-I; ChangLiaw, Wann-Bay (1999), "Hash espiral lineal para archivos expansibles", IEEE Transactions on Knowledge and Data Engineering , 11 (6)
9. Larson, Per-Åke (abril de 1988), "Tablas hash dinámicas", Communications of the ACM , 31 (4): 446–457, doi : 10.1145/42404.42410 , S2CID  207548097