Tabla hash en C ++: programas para implementar tablas hash y mapas hash

hash table c programs implement hash table

Este tutorial explica las tablas hash y los mapas hash de C ++. También aprenderá sobre las aplicaciones y la implementación de tablas hash en C ++:

El hash es una técnica mediante la cual podemos asignar una gran cantidad de datos a una tabla más pequeña utilizando una 'función hash'.

Usando la técnica de hash, podemos buscar los datos de manera más rápida y eficiente en comparación con otras técnicas de búsqueda como la búsqueda lineal y binaria.

Entendamos la técnica de hash con un ejemplo en este tutorial.

=> Lea la serie de formación Easy C ++.

Lo que vas a aprender:

• Hash en C ++
  • Función hash
  • Tabla hash C ++
  • Colisión
  • Técnicas de resolución de colisiones
    • Encadenamiento separado (hash abierto)
    • Palpado lineal (direccionamiento abierto / hash cerrado)
    • Palpado cuadrático
    • Hash doble
  • Diferencia entre encadenamiento (hash abierto) y sondeo lineal (direccionamiento abierto)
• Implementación de tabla hash de C ++
• Aplicaciones de hash
• Conclusión
  • Lectura recomendada

Hash en C ++

Tomemos un ejemplo de una biblioteca universitaria que alberga miles de libros. Los libros están ordenados por materias, departamentos, etc. Pero aún así, cada sección tendrá numerosos libros, lo que dificulta la búsqueda de libros.

Así, para superar esta dificultad asignamos un número o clave único a cada libro para que sepamos instantáneamente la ubicación del libro. De hecho, esto se logra mediante hash.

Continuando con nuestro ejemplo de biblioteca, en lugar de identificar cada libro en función de su departamento, tema, sección, etc.que puede resultar en una cadena muy larga, calculamos un valor entero único o clave para cada libro de la biblioteca utilizando una función única y guarde estas llaves en una mesa separada.

mejor software de gestión de tareas para windows

La función única mencionada anteriormente se llama 'función Hash' y la tabla separada se llama 'Tabla Hash'. Se utiliza una función hash para asignar el valor dado a una clave única particular en la tabla hash. Esto da como resultado un acceso más rápido a los elementos. Cuanto más eficiente sea la función hash, más eficiente será la asignación de cada elemento a la clave única.

Consideremos una función hash h (x) que mapea el valor ' x ' a ' x%10 ”En la matriz. Para los datos dados, podemos construir una tabla hash que contenga claves o códigos hash o hash como se muestra en el siguiente diagrama.

En el diagrama anterior, podemos ver que las entradas de la matriz se asignan a sus posiciones en la tabla hash mediante una función hash.

Por lo tanto, podemos decir que el hash se implementa mediante dos pasos como se menciona a continuación:

#1) El valor se convierte en una clave entera única o hash mediante una función hash. Se utiliza como índice para almacenar el elemento original, que cae en la tabla hash.

En el diagrama anterior, el valor 1 en la tabla hash es la clave única para almacenar el elemento 1 de la matriz de datos dada en el lado izquierdo del diagrama.

#2) El elemento de la matriz de datos se almacena en la tabla hash, donde se puede recuperar rápidamente utilizando la clave hash. En el diagrama anterior, vimos que hemos almacenado todos los elementos en la tabla hash después de calcular sus respectivas ubicaciones usando una función hash. Podemos usar las siguientes expresiones para recuperar valores hash e index.

Función hash

Ya mencionamos que la eficiencia del mapeo depende de la eficiencia de la función hash que usamos.

Una función hash básicamente debe cumplir los siguientes requisitos:

• Fácil de calcular: Una función hash debería ser fácil de calcular las claves únicas.
• Menos colisión: Cuando los elementos equivalen a los mismos valores clave, se produce una colisión. Debe haber un mínimo de colisiones en la medida de lo posible en la función hash que se utiliza. Como es probable que se produzcan colisiones, tenemos que utilizar técnicas de resolución de colisiones adecuadas para solucionar las colisiones.
• Distribución uniforme: La función hash debería dar como resultado una distribución uniforme de los datos en la tabla hash y, por lo tanto, evitar la agrupación.

Tabla hash C ++

La tabla hash o un mapa hash es una estructura de datos que almacena punteros a los elementos de la matriz de datos original.

En nuestro ejemplo de biblioteca, la tabla hash de la biblioteca contendrá punteros a cada uno de los libros de la biblioteca.

Tener entradas en la tabla hash facilita la búsqueda de un elemento particular en la matriz.

Como ya se vio, la tabla hash usa una función hash para calcular el índice en la matriz de cubos o ranuras con las que se puede encontrar el valor deseado.

Considere otro ejemplo con la siguiente matriz de datos:

Supongamos que tenemos una tabla hash de tamaño 10 como se muestra a continuación:

Ahora usemos la función hash que se proporciona a continuación.

Esto equivaldrá a Hash_code = Key_value% 10

Usando la función anterior, asignamos los valores clave a las ubicaciones de la tabla hash como se muestra a continuación.

Usando la tabla anterior, podemos representar la tabla hash de la siguiente manera.

Por lo tanto, cuando necesitamos acceder a un elemento de la tabla hash, solo tomará O (1) tiempo para realizar la búsqueda.

Colisión

Por lo general, calculamos el código hash utilizando la función hash para poder asignar el valor de la clave al código hash en la tabla hash. En el ejemplo anterior de la matriz de datos, insertemos un valor 12. En ese caso, el código hash para el valor clave 12 será 2. (12% 10 = 2).

Pero en la tabla hash, ya tenemos una asignación al valor clave 22 para hash_code 2 como se muestra a continuación:

Como se muestra arriba, tenemos el mismo código hash para dos valores, 12 y 22, es decir, 2. Cuando uno o más valores clave equivalen a la misma ubicación, se produce una colisión. Por lo tanto, la ubicación del código hash ya está ocupada por un valor clave y hay otro valor clave que debe colocarse en la misma ubicación.

En el caso del hash, incluso si tenemos una tabla hash de un tamaño muy grande, es probable que haya una colisión. Esto se debe a que encontramos un valor único pequeño para una clave grande en general, por lo que es completamente posible que uno o más valores tengan el mismo código hash en cualquier momento.

Dado que una colisión es inevitable en el hash, siempre debemos buscar formas de prevenir o resolver la colisión. Existen varias técnicas de resolución de colisiones que podemos emplear para resolver la colisión que ocurre durante el hash.

Técnicas de resolución de colisiones

Las siguientes son las técnicas que podemos emplear para resolver la colisión en la tabla hash.

Encadenamiento separado (hash abierto)

Ésta es la técnica de resolución de colisiones más común. Esto también se conoce como hash abierto y se implementa mediante una lista vinculada.

¿Cuál es el mejor programa de descarga de música para Android?

En la técnica de encadenamiento independiente, cada entrada en la tabla hash es una lista enlazada. Cuando la clave coincide con el código hash, se ingresa en una lista correspondiente a ese código hash en particular. Por lo tanto, cuando dos claves tienen el mismo código hash, ambas entradas se ingresan en la lista vinculada.

Para el ejemplo anterior, el encadenamiento separado se representa a continuación.

El diagrama anterior representa el encadenamiento. Aquí usamos la función mod (%). Vemos que cuando dos valores clave equivalen al mismo código hash, vinculamos estos elementos a ese código hash mediante una lista vinculada.

Si las claves se distribuyen uniformemente en la tabla hash, el costo promedio de buscar la clave en particular depende del número promedio de claves en esa lista vinculada. Por lo tanto, el encadenamiento separado sigue siendo efectivo incluso cuando hay un aumento en el número de entradas que las ranuras.

El peor de los casos para el encadenamiento por separado es cuando todas las claves equivalen al mismo código hash y, por lo tanto, se insertan en una sola lista vinculada. Por lo tanto, necesitamos buscar todas las entradas en la tabla hash y el costo que son proporcionales al número de claves en la tabla.

Palpado lineal (direccionamiento abierto / hash cerrado)

En la técnica de sondeo lineal o direccionamiento abierto, todos los registros de entrada se almacenan en la propia tabla hash. Cuando el valor clave se asigna a un código hash y la posición a la que apunta el código hash no está ocupada, el valor clave se inserta en esa ubicación.

Si la posición ya está ocupada, utilizando una secuencia de sondeo, el valor clave se inserta en la siguiente posición que está desocupada en la tabla hash.

Para el sondeo lineal, la función hash puede cambiar como se muestra a continuación:

hash = hash% hashTableSize
hash = (hash + 1)% hashTableSize
hash = (hash + 2)% hashTableSize
hash = (hash + 3)% hashTableSize

Vemos que en caso de sondeo lineal, el intervalo entre ranuras o sondas sucesivas es constante, es decir, 1.

En el diagrama anterior, vemos que en el 0^thubicación ingresamos 10 usando la función hash 'hash = hash% hash_tableSize'.

Ahora, el elemento 70 también equivale a la ubicación 0 en la tabla hash. Pero esa ubicación ya está ocupada. Por lo tanto, usando el palpado lineal encontraremos la siguiente ubicación que es 1. Como esta ubicación está desocupada, colocamos la llave 70 en esta ubicación como se muestra con una flecha.

La tabla hash resultante se muestra a continuación.

El sondeo lineal puede sufrir el problema de la “agrupación primaria” en el que existe la posibilidad de que las celdas continuas se ocupen y la probabilidad de insertar un nuevo elemento se reduzca.

Además, si dos elementos obtienen el mismo valor en la primera función hash, ambos elementos seguirán la misma secuencia de sondeo.

Palpado cuadrático

El palpado cuadrático es el mismo que el palpado lineal, con la única diferencia del intervalo utilizado para el palpado. Como sugiere el nombre, esta técnica utiliza una distancia no lineal o cuadrática para ocupar espacios cuando se produce una colisión en lugar de una distancia lineal.

En el sondeo cuadrático, el intervalo entre las ranuras se calcula agregando un valor polinomial arbitrario al índice ya hash. Esta técnica reduce la agrupación primaria en un grado significativo pero no mejora la agrupación secundaria.

Hash doble

La técnica de doble hash es similar al sondeo lineal. La única diferencia entre el doble hash y el sondeo lineal es que en la técnica de doble hash, el intervalo utilizado para el sondeo se calcula mediante dos funciones hash. Dado que aplicamos la función hash a la clave una tras otra, elimina la agrupación primaria y secundaria.

Diferencia entre encadenamiento (hash abierto) y sondeo lineal (direccionamiento abierto)

Implementación de tabla hash de C ++

Podemos implementar hash mediante el uso de matrices o listas vinculadas para programar las tablas hash. En C ++ también tenemos una función llamada 'mapa hash' que es una estructura similar a una tabla hash, pero cada entrada es un par clave-valor. En C ++ se llama mapa hash o simplemente mapa. El mapa hash en C ++ generalmente no está ordenado.

Hay un encabezado definido en la biblioteca de plantillas estándar (STL) de C ++ que implementa la funcionalidad de los mapas. Nosotros hemos cubierto Mapas STL en detalle en nuestro tutorial sobre STL.

La siguiente implementación es para hash utilizando las listas enlazadas como estructura de datos para la tabla hash. También utilizamos el 'encadenamiento' como técnica de resolución de colisiones en esta implementación.

Producción:

Tabla hash creada:

0 –> 21 –> 14
1 –> 15
2
3
4 –> 11
5 –> 12
6

Tabla hash después de eliminar la clave 12:

0 –> 21 –> 14
1 –> 15
2
3
4 –> 11
5
6

La salida muestra una tabla hash que se crea de tamaño 7. Usamos encadenamiento para resolver la colisión. Mostramos la tabla hash después de eliminar una de las claves.

Aplicaciones de hash

# 1) Verificación de contraseñas: La verificación de contraseñas generalmente se realiza mediante funciones de hash criptográficas. Cuando se ingresa la contraseña, el sistema calcula el hash de la contraseña y luego se envía al servidor para su verificación. En el servidor, se almacenan los valores hash de las contraseñas originales.

# 2) Estructuras de datos: Diferentes estructuras de datos como unordered_set y unordered_map en C ++, diccionarios en Python o C #, HashSet y hash map en Java, todos utilizan un par clave-valor en el que las claves son valores únicos. Los valores pueden ser los mismos para diferentes claves. El hash se utiliza para implementar estas estructuras de datos.

# 3) Resumen de mensajes: Esta es otra aplicación que utiliza un hash criptográfico. En los resúmenes de mensajes, calculamos un hash para los datos que se envían y reciben o incluso los archivos y los comparamos con los valores almacenados para asegurarnos de que los archivos de datos no sean manipulados. El algoritmo más común aquí es 'SHA 256'.

cómo ver archivos dat en windows

# 4) Operación del compilador: Cuando el compilador compila un programa, las palabras clave para el lenguaje de programación se almacenan de manera diferente a las otras identificaciones. El compilador usa una tabla hash para almacenar estas palabras clave.

# 5) Indexación de bases de datos: Las tablas hash se utilizan para la indexación de bases de datos y las estructuras de datos basadas en disco.

# 6) Matrices asociativas: Las matrices asociativas son matrices cuyos índices son de tipo de datos distintos de las cadenas de tipo entero u otros tipos de objetos. Las tablas hash se pueden utilizar para implementar matrices asociativas.

Conclusión

El hash es la estructura de datos más utilizada, ya que lleva un tiempo constante O (1) para las operaciones de inserción, eliminación y búsqueda. El hash se implementa principalmente mediante el uso de una función hash que calcula un valor clave único más pequeño para entradas de datos grandes. Podemos implementar hash utilizando matrices y listas enlazadas.

Siempre que una o más entradas de datos equivalen a los mismos valores de claves, se produce una colisión. Hemos visto varias técnicas de resolución de colisiones, incluido el sondeo lineal, el encadenamiento, etc. También hemos visto la implementación de hash en C ++.

Para concluir, podemos decir que el hash es, con mucho, la estructura de datos más eficiente en el mundo de la programación.

=> Busque toda la serie de formación en C ++ aquí.

Lectura recomendada

• Cómo escribir escenarios de prueba de lógica empresarial complejos mediante la técnica de tabla de decisiones
• Tabla de validación de campo (FVT): una técnica de diseño de prueba para la validación de campo
• Tutorial de QTP n. ° 15: uso de puntos de control de área de texto, tabla y página en QTP
• MAPAS en STL
• Todo sobre los enrutadores: tipos de enrutadores, tabla de enrutamiento y enrutamiento IP
• Las 40 mejores preguntas y respuestas de las entrevistas de MySQL (preguntas de 2021)
• Las 90 preguntas y respuestas principales de la entrevista SQL (ÚLTIMA)
• Comandos de programas de utilidades de Unix: Which, Man, Find Su, Sudo (Parte D)