Tabla hash: ¿Qué es una tabla hash?

La tabla hash es una estructura de datos ~

La tabla hash puede almacenar varios tipos de datos. Cuando buscamos los datos requeridos en la tabla hash, idealmente sin ninguna comparación, el registro consultado. se puede obtener en un acceso, entonces se debe establecer una cierta correspondencia f entre la ubicación de almacenamiento del registro y sus palabras clave, de modo que cada palabra clave y un valor único en la estructura correspondiente a la ubicación de almacenamiento. (La palabra clave son los datos que se almacenarán y la ubicación de almacenamiento es equivalente al índice de la matriz)

Por supuesto, la tabla hash puede entenderse como una matriz. Cada índice corresponde a una ubicación de almacenamiento. , y el índice de la tabla hash no es como el índice de una matriz ordinaria, de 0 a longitud-1, sino que se obtiene mediante la clave (los datos en sí) a través de la función hash

Por ejemplo, ¿almacenar 26 letras minúsculas en la matriz? int [26] a.

a corresponde a a[0], b corresponde a a[1], c corresponde a a[3]... y así sucesivamente.

¡Entonces, la matriz int [26] a es una tabla hash!

En el ejemplo 1, ¿cómo obtienen las palabras clave (letras minúsculas) sus índices correspondientes (ubicaciones de almacenamiento)?

El valor ASCII de la palabra clave menos el valor ASCII de a!

Como se mencionó anteriormente, las palabras clave se indexan mediante funciones hash, por lo que f(ch) es la función hash de esta pregunta de ejemplo.

De esta manera, hemos establecido una correspondencia definida f entre la palabra clave y el número (ubicación de almacenamiento).

Existe una correspondencia uno a uno entre las palabras clave y los números. Dado que la matriz en sí admite el acceso aleatorio, cuando se buscan palabras clave, solo se requiere la operación de búsqueda O(1), lo que significa que no hay comparación. realizado, puede obtener los registros verificados de una sola vez.

El diseño de la función hash en la tabla hash es muy importante y también es una de las cuestiones clave en el proceso de construcción de una tabla hash.

Si la clave del dato que queremos almacenar es el número del DNI de una persona (18 dígitos), ¿cómo debemos calcular el índice correspondiente a la clave en este momento?

Por ejemplo, si el número de identificación de una persona es 411697199702076425, nos resulta difícil establecer directamente una correspondencia uno a uno entre palabras clave y números como en el Ejemplo 1, y asegurarnos de que los números sean adecuados como índices de la matriz.

En este caso, el índice calculado por la función hash puede ser el mismo incluso si las palabras clave son diferentes. Esto es un conflicto de hash

¿Cómo debemos almacenar datos cuando los índices son los mismos? Cómo resolver conflictos hash es otra cuestión clave cuando construimos una tabla hash.

La tabla hash encarna plenamente la idea algorítmica clásica de intercambiar espacio por tiempo.

Cuando la palabra clave es un número entero grande, como en el ejemplo del número de identificación que dimos anteriormente, 411697199702076425

Si podemos abrir un espacio tan grande como 999999999999999999, podemos agregar directamente el Número de identificación Guárdelo en una matriz como clave, de modo que cada operación pueda completarse en O(1) tiempo

Si solo tenemos 1 espacio, necesitamos almacenar toda la información en este espacio (es decir , todos los datos ocurrirán una colisión Hash), solo podemos completar cada operación en O (n) tiempo

De hecho, es imposible para nosotros abrir un espacio tan grande, ni podemos abrir tal un espacio pequeño

Cuando hay un espacio infinito, el tiempo es O(1)

Cuando hay 1 espacio, el tiempo es O(n)

Y la tabla hash se genera entre los dos. Un equilibrio, un equilibrio de espacio y tiempo.

1. Diseño de la función hash

2. Resolver conflictos de hash

3. La tabla hash logra el equilibrio entre el tiempo y el espacio

Estos Tres cuestiones clave se explicarán en detalle más adelante ~