Este artículo explica qué es el pensamiento hash y la construcción de tablas hash

Hash, generalmente traducido como hash, hash o transliterado como hash, consiste en transformar una entrada de cualquier longitud (también denominada preimagen preasignada) en una salida de longitud fija a través de un algoritmo hash, y la salida es el valor hash .

Hoy exploraremos juntos el misterio de la capa inferior del hashing.

Construya una estructura de almacenamiento, a través de una determinada función, para que se pueda establecer una relación de mapeo uno a uno entre la ubicación de almacenamiento de su elemento y su código clave, luego el elemento correspondiente se puede encontrar rápidamente a través de esta función al buscar.

En resumen, es establecer una función fija (hashFunc), y usar esta función para hacer que el valor del elemento insertado corresponda a la posición del elemento. Posteriormente, cuando necesitemos encontrar este elemento, podemos usar esta función ( hashFunc) para encontrar el valor.

Una función hash (inglés: función hash), también conocida como algoritmo hash o función hash, es un método para crear pequeñas "huellas dactilares" digitales a partir de cualquier tipo de datos. La función hash comprime el mensaje o los datos en un resumen, lo que reduce la cantidad de datos y corrige el formato de los datos.

Esta función codifica los datos para recrear una huella digital llamada valores hash (valores hash, códigos hash, sumas hash o hashes). El valor hash generalmente se representa mediante una cadena corta de letras y números aleatorios.

La función hash hace que las direcciones calculadas se distribuyan uniformemente por todo el espacio.

De acuerdo con el código clave del elemento a insertar, su ubicación de almacenamiento se calcula de acuerdo con la función hash.

Usamos la función hash del método del resto para introducir:

Ejemplo:  Hay 1, 3, 4, 5, 6 y 9 números para almacenar, y el resultado de la operación de módulo n%10 se utiliza como dirección hash para la inserción de elementos.

Si desea encontrar un elemento, solo necesita realizar una operación de función hash en el elemento de búsqueda para obtener su dirección de almacenamiento, y puede encontrar el elemento.

Cuando se inserta un elemento, su dirección calculada según la función hash ya está ocupada por otros elementos, lo que se denomina colisión hash.

Ejemplo:

Para identificar mejor si la ubicación actual está ocupada, debemos marcar cada ubicación

enum state{EMPTY,FULL,DELETE}; Nota: Si queremos eliminar un elemento, no podemos eliminarlo directamente, si lo hacemos directamente, afectará la estructura actual y causará errores en la búsqueda de otros elementos, por lo que cuando queremos eliminar Un elemento debe estar marcado para su eliminación, no vacío.

El hashing abierto también se denomina método de dirección de cadena. En primer lugar, la función hash se utiliza para calcular la dirección hash para el conjunto de códigos clave. El nodo principal de se almacena en la tabla hash.

Ahora, deberías entender la idea de hash y la construcción de una tabla hash, ¿verdad? ¡Bienvenido a compartir sus pensamientos con nosotros en el área de comentarios!

Tags：

Precio de Ethereum USD