Tutorial de estructura de datos de tabla hash

En informática, la palabra "mapa" significa vincular un elemento en un conjunto a otro elemento en otro conjunto. Imagine que en una página, hay palabras en un círculo a la izquierda, y en el lado derecho de la misma página, hay otro círculo dentro del cual hay otras palabras. Suponga que en cada círculo, las palabras están escritas al azar, dispersas dentro del círculo. Además, suponga que las palabras en el círculo izquierdo se llaman claves, y las palabras en el círculo derecho se llaman valores. Si se extrae una flecha de cada palabra a la izquierda a cada palabra a la derecha, entonces se diría que las teclas se han asignado a los valores.

Suponga que usted es el propietario de una gran tienda de provisiones en el condado donde vive. Suponga que vive en un área grande, que no es un área comercial. No eres el único con una tienda de provisiones en el área; tienes algunos competidores. Y luego se le ocurre que debe registrar los números de teléfono de sus clientes en un libro de ejercicios. Por supuesto, el libro de ejercicios es pequeño y no puede grabar todos los números de teléfono para todos sus clientes.

Entonces, decide grabar solo los números de teléfono de sus clientes habituales. Y entonces tienes una tabla con dos columnas. La columna de la izquierda tiene los nombres de los clientes, y la columna a la derecha tiene los números de teléfono correspondientes. De esta manera, hay una asignación entre los nombres de los clientes y los números de teléfono. La columna derecha de la tabla puede considerarse como la tabla de hash central. Los nombres de los clientes ahora se llaman claves, y los números de teléfono se denominan valores. Tenga en cuenta que cuando un cliente se transfiera, tendrá que cancelar su fila, permitiendo la fila vacía o ser reemplazada por la de un nuevo cliente regular. También tenga en cuenta que con el tiempo, el número de clientes regulares puede aumentar o disminuir, por lo que la tabla puede crecer o encogerse.

Como otro ejemplo de mapeo, suponga que hay un club de agricultores en un condado. Por supuesto, no todos los agricultores serán miembros del club. Algunos miembros del club no serán miembros regulares (asistencia y contribución). El Bar-Man puede decidir registrar los nombres de los miembros y su elección de bebida. Desarrolla una tabla de dos columnas. En la columna izquierda, escribe los nombres de los miembros del club. En la columna derecha, escribe la opción correspondiente de bebida.

Aquí hay un problema: hay duplicados en la columna correcta. Es decir, el mismo nombre de una bebida se encuentra más de una vez. En otras palabras, diferentes miembros beben la misma bebida dulce o la misma bebida alcohólica, mientras que otros miembros beben una bebida dulce o alcohólica diferente. El hombre de la barra decide resolver este problema insertando una columna estrecha entre las dos columnas. En esta columna intermedia, comenzando desde arriba, él cuenta las filas que comienzan desde cero (i.mi. 0, 1, 2, 3, 4, etc.), bajando, un índice por fila. Con esto, su problema se resuelve, ya que el nombre de un miembro ahora se mapea a un índice, y no al nombre de una bebida. Entonces, como se identifica una bebida por un índice, el nombre de un cliente se asigna al índice correspondiente.

La columna de valores (bebidas) solo forma la tabla de hash básica. En la tabla modificada, la columna de índices y sus valores asociados (con o sin duplicados) forman una tabla de hash normal: la definición completa de una tabla hash se da a continuación a continuación. Las teclas (primera columna) no necesariamente forman parte de la tabla hash.

Como otro ejemplo nuevamente, considere un servidor de red donde un usuario de su computadora con el cliente puede agregar información, eliminar alguna información o modificar alguna información. Hay muchos usuarios para el servidor. Cada nombre de usuario corresponde a una contraseña almacenada en el servidor. Aquellos que mantienen el servidor pueden ver los nombres de usuario y la contraseña correspondiente, por lo que pueden corromper el trabajo de los usuarios.

Entonces, el propietario del servidor decide producir una función que cifre una contraseña antes de almacenarse. Un usuario inicia sesión en el servidor, con su contraseña normal entendida. Sin embargo, ahora, cada contraseña se almacena en forma cifrada. Si alguien ve una contraseña encriptada e intenta iniciar sesión en el uso de ella, no funcionará, porque iniciar sesión recibe una contraseña entendida por el servidor, y no una contraseña encriptada.

En este caso, la contraseña entendida es la clave, y la contraseña cifrada es el valor. Si la contraseña cifrada está en una columna de contraseñas cifradas, entonces esa columna es una tabla hash básica. Si esa columna está precedida por otra columna con índices que comienzan desde cero, de modo que cada contraseña encriptada está asociada con un índice, entonces tanto la columna de índices como la columna de contraseña cifrada, forman una tabla hash normal. Las llaves no son necesariamente parte de la tabla hash.

Tenga en cuenta, en este caso, que cada clave, que es una contraseña entendida, corresponde a un nombre de usuario. Entonces, hay un nombre de usuario que corresponde a una clave que se asigna a un índice, que está asociado con un valor que es una clave cifrada.

La definición de una función hash, la definición completa de una tabla hash, el significado de una matriz y otros detalles se dan a continuación a continuación. Debe tener conocimiento en punteros (referencias) y listas vinculadas, para apreciar el resto de este tutorial.

Significado de la función hash y la tabla hash

Formación

Una matriz es un conjunto de ubicaciones de memoria consecutivas. Todas las ubicaciones son del mismo tamaño. Se accede al valor en la primera ubicación con el índice, 0; Se accede al valor en la segunda ubicación con el índice, 1; Se accede al tercer valor con el índice, 2; cuarto con índice, 3; etcétera. Una matriz normalmente no puede aumentar o encogerse. Para cambiar el tamaño (longitud) de una matriz, se debe crear una nueva matriz y los valores correspondientes copiados a la nueva matriz. Los valores de una matriz siempre son del mismo tipo.

Función hash

En el software, una función hash es una función que toma una clave y produce un índice correspondiente para una celda de matriz. La matriz es de tamaño fijo (longitud fija). El número de claves es de tamaño arbitrario, generalmente mayor que el tamaño de la matriz. El índice resultante de la función hash se denomina valor hash o un resumen o un código hash o simplemente un hash.

Tabla de picadillo

Una tabla hash es una matriz con valores, a cuyos índices, las claves están asignadas. Las teclas se asignan indirectamente a los valores. De hecho, se dice que las claves están asignadas a los valores, ya que cada índice está asociado con un valor (con o sin duplicados). Sin embargo, la función que hace mapeo (i.mi. hash) relata las claves con los índices de matriz y no con los valores, ya que puede haber duplicados en los valores. El siguiente diagrama ilustra una tabla hash para los nombres de las personas y sus números de teléfono. Las celdas de matriz (ranuras) se llaman cubos.

Observe que algunos cubos están vacíos. Una tabla hash no necesariamente debe tener valores en todos sus cubos. Los valores en los cubos no deben estar necesariamente en orden ascendente. Sin embargo, los índices con los que están asociados están en orden ascendente. Las flechas indican el mapeo. Observe que las teclas no están en una matriz. No tienen que estar en ninguna estructura. Una función hash toma cualquier clave y hashes un índice para una matriz. Si no hay valor en el cubo asociado con el índice de hash, se puede poner un nuevo valor en ese cubo. La relación lógica es entre la clave y el índice, y no entre la clave y el valor asociado con el índice.

Los valores de una matriz, como los de esta tabla hash, son siempre del mismo tipo de datos. Una tabla hash (cubos) puede conectar claves a los valores de diferentes tipos de datos. En este caso, los valores de la matriz son todos punteros, que apuntan a diferentes tipos de valor.

Una tabla hash es una matriz con una función hash. La función toma una clave y hashes un índice correspondiente, por lo que conecta las teclas a los valores, en la matriz. Las teclas no tienen que ser parte de la mesa hash.

Por qué matriz y no una lista de enlace para la tabla hash

La matriz para una tabla hash puede ser reemplazada por una estructura de datos de lista vinculada, pero habría un problema. El primer elemento de una lista vinculada es naturalmente en el índice, 0; El segundo elemento está naturalmente en el índice, 1; El tercero está naturalmente en el índice, 2; etcétera. El problema con la lista vinculada es que para recuperar un valor, la lista debe ser iterada, y esto lleva tiempo. Acceder a un valor en una matriz es por acceso aleatorio. Una vez que se conoce el índice, el valor se obtiene sin iteración; Este acceso es más rápido.

Colisión

La función hash toma una clave y hashas el índice correspondiente, para leer el valor asociado o para insertar un nuevo valor. Si el propósito es leer un valor, no hay problema (no hay problema), hasta ahora. Sin embargo, si el propósito es insertar un valor, el índice de hash ya puede tener un valor asociado, y eso es una colisión; El nuevo valor no se puede poner donde ya hay un valor. Hay formas de resolver la colisión: ver más abajo.

Por qué ocurre la colisión

En el ejemplo de la tienda de provisiones anterior, los nombres de los clientes son las claves, y los nombres de las bebidas son los valores. Observe que los clientes son demasiados, mientras que la matriz tiene un tamaño limitado y no puede llevar a todos los clientes. Entonces, solo las bebidas de los clientes regulares se almacenan en la matriz. La colisión ocurriría cuando un cliente no regular se vuelva regular. Los clientes para la tienda forman un conjunto grande, mientras que el número de cubos para los clientes en la matriz es limitado.

Con las tablas hash, son los valores para las claves que son muy probables, los que se registran. Cuando una clave que no era probable, es probable, probablemente habría una colisión. De hecho, la colisión siempre ocurre con tablas hash.

Conceptos básicos de resolución de colisión

Dos enfoques para la resolución de colisión se denominan encadenamiento separado y direccionamiento abierto. En teoría, las claves no deben estar en la estructura de datos o no deben ser parte de la tabla hash. Sin embargo, ambos enfoques requieren que la columna clave precede a la tabla hash y se convierte en parte de la estructura general. En lugar de que las teclas estén en la columna de teclas, los punteros a las teclas pueden estar en la columna de teclas.

Una tabla de hash práctica incluye una columna de llaves, pero esta columna clave no es oficialmente parte de la tabla hash.

Cualquiera de los enfoques para la resolución puede tener cubos vacíos, no necesariamente al final de la matriz.

Encadenamiento separado

En el encadenamiento separado, cuando ocurre una colisión, el nuevo valor se agrega a la derecha (no arriba o abajo) del valor colisionado. Entonces, dos o tres valores terminan teniendo el mismo índice. Rara vez más de tres deberían tener el mismo índice.

¿Puede más de un valor tener el mismo índice en una matriz?? - No. Entonces, en muchos casos, el primer valor para el índice es un puntero a una estructura de datos de lista vinculada, que contiene el uno, dos o tres valores colisionados. El siguiente diagrama es un ejemplo de una tabla hash para encadenamiento por separado de los clientes y sus números de teléfono:

Los cubos vacíos están marcados con la letra x. El resto de las máquinas tragamonedas tienen punteros a las listas vinculadas. Cada elemento de la lista vinculada tiene dos campos de datos: uno para el nombre del cliente y el otro para el número de teléfono. El conflicto ocurre para las teclas: Peter Jones y Suzan Lee. Los valores correspondientes consisten en dos elementos de una lista vinculada.

Para claves conflictivas, el criterio para insertar el valor es el mismo criterio utilizado para ubicar (y leer) el valor.

Direccionamiento abierto

Con el direccionamiento abierto, todos los valores se almacenan en la matriz de cubos. Cuando se produce conflicto, el nuevo valor se inserta en un cubo vacío nuevo el valor correspondiente para el conflicto, siguiendo algún criterio. El criterio utilizado para insertar un valor en el conflicto es el mismo criterio utilizado para ubicar (buscar y leer) el valor.

El siguiente diagrama ilustra la resolución de conflictos con direccionamiento abierto:

La función hash toma la clave, Peter Jones y hashes el índice, 152, y almacena su número de teléfono en el cubo asociado. Después de un tiempo, la función hash ha haz homenaje el mismo índice, 152 de la clave, Suzan Lee, colisionando con el índice de Peter Jones. Para resolver esto, el valor para Suzan Lee se almacena en el cubo del siguiente índice, 153, que estaba vacío. La función hash hahes al índice, 153 para la clave, Robin Hood, pero este índice ya se ha utilizado para resolver el conflicto para una clave anterior. Entonces, el valor para Robin Hood se coloca en el siguiente cubo vacío, que es el del índice 154.

Métodos para resolver conflictos para encadenar y abordar el direccionamiento

El encadenamiento por separado tiene sus métodos para resolver conflictos, y el direccionamiento abierto también tiene sus propios métodos para resolver conflictos.

Métodos para resolver conflictos de encadenamiento separados

Los métodos para las tablas de hash de encadenamiento separadas se explican brevemente ahora:

Encadenamiento separado con listas vinculadas

Este método es como se explicó anteriormente. Sin embargo, cada elemento de la lista vinculada no necesariamente debe tener el campo clave (e.gramo. campo de nombre del cliente arriba).

Encadenamiento separado con las celdas de la cabeza de la lista

En este método, el primer elemento de la lista vinculada se almacena en un cubo de la matriz. Esto es posible, si el tipo de datos para la matriz, es el elemento de la lista vinculada.

Encadenamiento separado con otras estructuras

Cualquier otra estructura de datos, como el árbol de búsqueda binaria de equilibrio que admite las operaciones requeridas, puede usarse en lugar de la lista vinculada; ver más tarde.

Métodos para resolver los conflictos de direccionamiento abierto

Un método para resolver conflictos en el direccionamiento abierto se llama secuencia de la sonda. Tres secuencias de sonda bien conocidas se explican brevemente ahora:

Sondeo lineal

Con el sondeo lineal, cuando ocurre un conflicto, se busca el cubo vacío más cercano debajo del cubo en conflicto. Además, con sondeo lineal, tanto la clave como su valor se almacenan en el mismo cubo.

Sondeo cuadrático

Suponga que el conflicto ocurre en el índice H. La siguiente ranura vacía (cubo) en el índice H + 1² se usa; Si eso ya está ocupado, entonces el siguiente vacío en H + 2² se usa, si eso ya está ocupado, entonces el siguiente vacío en H + 3² se usa, y así sucesivamente. Hay variantes en esto.

Asiento doble

Con doble hashing, hay dos funciones hash. El primero calcula (hash) el índice. Si se produce un conflicto, el segundo usa la misma clave para determinar qué tan abajo se debe insertar el valor. Hay más en esto - ver más tarde.

Función de hash perfecta

Una función hash perfecta es una función hash que no puede dar lugar a ninguna colisión. Esto puede suceder cuando el conjunto de teclas es relativamente pequeño, y cada llave se asigna a un entero particular en la tabla hash.

En el conjunto de caracteres ASCII, los caracteres de mayúsculas se pueden asignar a sus letras minúsculas correspondientes utilizando una función hash. Las letras se representan en la memoria de la computadora como números. En el conjunto de caracteres ASCII, A es 65, B es 66, C es 67, etc. y A es 97, B es 98, C es 99, etc. Para mapear de A a A, agregue 32 a 65; Para mapear de B a B, agregue 32 a 66; Para mapear de C a C, agregue 32 a 67; etcétera. Aquí, las letras mayúsculas son las claves, y las letras minúsculas son los valores. La tabla hash para esto puede ser una matriz cuyos valores son los índices asociados. Recuerde, los cubos de la matriz pueden estar vacíos. Entonces los cubos en la matriz de 64 a 0 pueden estar vacíos. La función hash simplemente agrega 32 al número de código de la caja superior para obtener el índice y, por lo tanto, la carta de minúsculas. Tal función es una función hash perfecta.

Hashing de índices enteros a enteros

Existen diferentes métodos para el hash entero. Uno de ellos se llama método de división de módulo (función).

La función de hash de la división de módulo

Una función en el software de la computadora no es una función matemática. En la computación (software), una función consiste en un conjunto de declaraciones precedidas por argumentos. Para la función de división de módulo, las teclas son enteros y se asignan a los índices de la matriz de cubos. El conjunto de claves es grande, por lo que solo se mapearían las claves que es muy probable que ocurran en la actividad. Entonces, las colisiones ocurren cuando se deben asignar las teclas poco probables.

En la declaración,

20/6 = 3R2

20 es el dividendo, 6 es el divisor, y 3 resto 2 es el cociente. El resto 2 también se llama módulo. Nota: es posible tener un módulo de 0.

Para este hashing, el tamaño de la tabla suele ser una potencia de 2, e.gramo. 64 = 2⁶ o 256 = 2⁸, etc. El divisor para esta función de hashing es un número primo cercano al tamaño de la matriz. Esta función divide la clave por el divisor y devuelve el módulo. El módulo es el índice de la matriz de cubos. El valor asociado en el cubo es un valor de su elección (valor para la clave).

Teclas de longitud variable de hash

Aquí, las claves del conjunto de teclas son textos de diferentes longitudes. Se pueden almacenar diferentes enteros en la memoria utilizando el mismo número de bytes (el tamaño de un carácter inglés es un byte). Cuando diferentes claves son de diferentes tamaños de bytes, se dice que son de longitud variable. Uno de los métodos para las longitudes variables de hash se llama Radix Conversion Hashing.

Radix Conversion Hashing

En una cadena, cada personaje de la computadora es un número. En este método,

Código hash (índice) = x₀a^{K - 1}+X₁a^{K - 2}+… +X_{K - 2}a¹+X_{K - 1}a⁰

Donde (x0, x1, ..., xk - 1) están los caracteres de la cadena de entrada y A es una radix, e.gramo. 29 (ver más tarde). k es el número de caracteres en la cadena. Hay más en esto - ver más tarde.

Claves y valores

En un par de clave/valor, un valor puede no ser necesariamente un número o texto. También puede ser un registro. Un registro es una lista escrita horizontalmente. En un par de clave/valor, cada clave puede referirse a algún otro texto o número o registro.

Matriz asociativa

Una lista es una estructura de datos, donde los elementos de la lista están relacionados, y hay un conjunto de operaciones que operan en la lista. Cada elemento de la lista puede consistir en un par de elementos. La tabla de hash general con sus claves puede considerarse como una estructura de datos, pero es más un sistema que una estructura de datos. Las claves y sus valores correspondientes no dependen muy del otro. No están muy relacionados entre sí.

Por otro lado, una matriz asociativa es algo similar, pero las claves y sus valores dependen muy del otro; Están muy relacionados entre sí. Por ejemplo, puede tener una variedad asociativa de frutas y sus colores. Cada fruta naturalmente tiene su color. El nombre de la fruta es la clave; El color es el valor. Durante la inserción, cada clave se inserta con su valor. Al eliminar, cada clave se elimina con su valor.

Una matriz asociativa es una estructura de datos de tabla hash compuesta por pares de clave/valor, donde no hay duplicado para las teclas. Los valores pueden tener duplicados. En esta situación, las teclas son parte de la estructura. Es decir, las claves deben almacenarse, mientras que, con la mesa general, las teclas no tienen que almacenarse. El problema de los valores duplicados se resuelve naturalmente por los índices de la matriz de cubos. No confunda entre valores duplicados y colisión en un índice.

Dado que una matriz asociativa es una estructura de datos, IS tiene al menos las siguientes operaciones:

Operaciones de matriz asociativa

insertar o agregar

Esto inserta un nuevo par de clave/valor en la colección, asignando la clave a su valor.

reasignar

Esta operación reemplaza el valor de una clave particular a un nuevo valor.

eliminar o quitar

Esto elimina una clave más su valor correspondiente.

buscar

Esta operación busca el valor de una clave en particular y devuelve el valor (sin eliminarlo).

Conclusión

Una estructura de datos de tabla hash consiste en una matriz y una función. La función se llama función hash. La función mapea las teclas de los valores en la matriz a través de los índices de la matriz. Las claves no deben ser necesariamente parte de la estructura de datos. El conjunto de teclas suele ser más grande que los valores almacenados. Cuando se produce una colisión, se resuelve por el enfoque de encadenamiento separado o el enfoque de direccionamiento abierto. Una matriz asociativa es un caso especial de la estructura de datos de la tabla hash.