Un archivo hash es un archivo organizado en un método de almacenamiento hash, también conocido como archivo de acceso directo, es decir, diseñar una función hash para procesarlo según las características del palabras clave en el archivo en conflicto.
El método codifica el registro en el dispositivo de almacenamiento.
Comparación de tablas hash y archivos hash
Depósito inferior y depósito de desbordamiento
La unidad de almacenamiento de un archivo hash se denomina depósito. Si un depósito puede almacenar m registros, cuando ya haya m sinónimos en el depósito, se almacenará el m+ésimo sinónimo.
Para generar desbordamiento, el m+ésimo sinónimo debe almacenarse en otro depósito, generalmente llamado depósito de desbordamiento. El depósito que almacena los primeros m sinónimos se denomina depósito base.
Nota
① El depósito de desbordamiento y el depósito inferior son del mismo tamaño y están vinculados entre sí mediante punteros.
(2) Cuando el registro a verificar no se encuentra en el depósito base, siga el puntero hasta el depósito de desbordamiento, por lo que se espera que el depósito de desbordamiento y el depósito base con la misma dirección hash sean en el disco.
Las ubicaciones físicas no pueden estar demasiado separadas, preferiblemente en el mismo cilindro.
Un archivo tiene un registro cuya clave es depósito.
Capacidad m = número de depósitos b = función hash H(clave) =% clave usando división. El archivo hash resultante se muestra a continuación.
Operación de búsqueda de archivos hash
El proceso de búsqueda en archivos hash.
() Encuentra la dirección del depósito de hash según el valor dado.
() Busca secuencialmente en la memoria del lector de registros de un depósito básico.
() Si se encuentra un registro con una clave igual al valor dado, la recuperación es exitosa; de lo contrario, el lector continúa buscando registros que desborden el depósito.
Operación de eliminación de archivos hash
Para eliminar registros en un archivo hash, solo necesita marcar los registros eliminados para su eliminación.
Características de los archivos hash
Ventajas de los archivos hash
No es necesario ordenar los registros almacenados aleatoriamente de los archivos ().
()Fácil de insertar y eliminar
()El acceso es rápido; no se necesita área de índice para ahorrar espacio de almacenamiento.
Desventajas de los archivos hash
No se puede acceder a () de forma secuencial, solo se puede acceder aleatoriamente por palabra clave.
() El método de consulta se limita a una consulta simple.
() Después de repetidas inserciones y eliminaciones, la estructura del archivo puede no ser razonable y es necesario reorganizarlo.
Lishi Xinzhi/Article/program/sjjg/201311/23536