Función hash
En esta sección, analizaremos la función hash que ayuda a ejecutar el código hash de la clave relacionada del elemento de datos en la estructura de datos como se menciona a continuación:
elemento hash int ( En t llave ){
devolver llave % tamaño de la mesa ;
}
El proceso de ejecutar el índice de una matriz se llama hash. A veces, se ejecuta el mismo tipo de código para generar el mismo índice utilizando las mismas claves llamadas colisiones, que se maneja mediante diferentes encadenamientos (creación de listas vinculadas) e implementación de estrategias de direccionamiento abierto.
Funcionamiento de la tabla hash en C++
Los punteros a los valores reales se guardan en la tabla hash. Utiliza una clave para buscar el índice de una matriz en la que los valores de las claves deben almacenarse en la ubicación deseada de una matriz. Tomamos la tabla hash de tamaño 10 como se menciona a continuación:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Tomemos aleatoriamente cualquier dato con diferentes claves y almacenemos estas claves en una tabla hash simplemente calculando el índice. Entonces, los datos se almacenan contra las claves en el índice calculado con la ayuda de una función hash. Supongamos que tomamos datos = {14,25,42,55,63,84} y claves =[15,9,5,25,66,75].
Calcule el índice de estos datos usando la función hash. El valor del índice se menciona a continuación:
| Llave | 15 | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Calcular índice | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Datos | 14 | 25 | 42 | 55 | 63 | 84 |
Después de crear el índice de una matriz, coloque los datos junto a la clave en el índice exacto de una matriz determinada como se describió anteriormente.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Después de eso, podemos ver que se produce una colisión si dos o más claves tienen el mismo código hash, lo que da como resultado el mismo índice de los elementos de la matriz. Tenemos una solución para evitar las posibilidades de colisión: seleccionar un buen método hash e implementar las estrategias precisas.
Ahora, analicemos las diferentes técnicas de implementación con la ayuda de ejemplos adecuados.
Ejemplo: agregar datos en una tabla hash utilizando una técnica de hash abierta
En este ejemplo, tomamos una técnica de implementación como Open Hashing para evitar colisiones en la tabla hash. En hashing o encadenamiento abierto, creamos una lista vinculada para encadenar los valores de la tabla hash. El fragmento de código de este ejemplo se adjunta a continuación y describe la técnica de hash abierto:
#incluir#incluir
clase Tabla de picadillo {
privado :
estático constante En t tamaño de la mesa = 10 ;
enfermedad de transmisión sexual :: lista < En t > mesaTiene [ tamaño de la mesa ] ;
En t hashFunc ( En t llave ) {
devolver llave % tamaño de la mesa ;
}
público :
vacío insertar ( En t llave ) {
En t índice = hashFunc ( llave ) ;
mesaTiene [ índice ] . hacer retroceder ( llave ) ;
}
vacío verTabla ( ) {
para ( En t i = 0 ; i < tamaño de la mesa ; ++ i ) {
enfermedad de transmisión sexual :: corte << '[' << i << ']' ;
para ( auto él = mesaTiene [ i ] . comenzar ( ) ; él ! = mesaTiene [ i ] . fin ( ) ; ++ él ) {
enfermedad de transmisión sexual :: corte << ' -> ' << * él ;
}
enfermedad de transmisión sexual :: corte << enfermedad de transmisión sexual :: fin ;
}
}
} ;
En t principal ( ) {
HashTable tieneTabla ;
tieneTable. insertar ( 15 ) ;
tieneTable. insertar ( 33 ) ;
tieneTable. insertar ( 23 ) ;
tieneTable. insertar ( 65 ) ;
tieneTable. insertar ( 3 ) ;
tieneTable. verTabla ( ) ;
devolver 0 ;
}
Este es un ejemplo muy interesante: construimos una lista vinculada e insertamos los datos en la tabla hash. En primer lugar, definimos las bibliotecas al inicio del programa. El < lista > La biblioteca se utiliza para la implementación de la lista vinculada. Después de eso, construimos una clase llamada 'HashTable' y creamos los atributos de la clase que son privados como el tamaño de la tabla y la matriz de la tabla usando la palabra clave 'privada:'. Recuerde que los atributos privados no se pueden utilizar fuera de la clase. Aquí, tomamos el tamaño de la tabla como '10'. Inicializamos el método hash usando esto y calculamos el índice de la tabla hash. En la función hash, pasamos la clave y el tamaño de la tabla hash.
Construimos algunas funciones requeridas y las hacemos públicas en la clase. Recuerde que las funciones públicas se pueden utilizar fuera de la clase en cualquier lugar. Usamos la palabra clave 'público:' para iniciar la parte pública de la clase. . Como queremos agregar nuevos elementos a la tabla hash, creamos una función llamada 'InsertHash' con una clave como argumento de la función. En la función 'insertar', inicializamos la variable de índice. Pasamos la función hash a la variable de índice. Después de eso, pase la variable de índice a la lista vinculada tableHas[]usando el método 'push' para insertar un elemento en la tabla.
Después de eso, creamos una función 'viewHashTab' para mostrar la tabla hash y ver los datos recién insertados. En esta función, tomamos un bucle 'for' que busca los valores hasta el final de la tabla hash. Asegúrese de que los valores se almacenen en el mismo índice que se desarrollan utilizando una función hash. En el bucle, pasamos los valores en su índice respectivo y finalizamos la clase aquí. En la función 'principal', tomamos el objeto de una clase llamada 'hasTable'. Con la ayuda de este objeto de clase, podemos acceder al método de inserción pasando la clave en el método. La clave que pasamos en la función 'principal' se calcula en la función 'insertar' que devuelve la posición del índice en la tabla hash. Mostramos la tabla hash llamando a la función 'ver' con la ayuda de un objeto 'Clase'.
El resultado de este código se adjunta a continuación:
Como podemos ver, la tabla hash se crea correctamente utilizando la lista vinculada en C++. El encadenamiento abierto se utiliza para evitar la colisión del mismo índice.
Conclusión
En última instancia, llegamos a la conclusión de que una tabla hash es la técnica más emergente para almacenar y obtener claves con pares de valores para manejar grandes cantidades de datos de manera eficiente. Las posibilidades de colisión son muy altas en la tabla hash, destruyendo los datos y su almacenamiento. Podemos superar esta colisión utilizando diferentes técnicas de gestión de tablas hash. Al desarrollar la tabla hash en C++, los desarrolladores pueden aumentar el rendimiento utilizando la técnica más adecuada para almacenar los datos en la tabla hash. Esperamos que este artículo sea útil para comprender la tabla hash.