Introducción a la función de hash en C
Este artículo tiene una breve nota sobre el hash (tabla hash y función hash). El concepto más importante es "buscar", que determina la complejidad del tiempo. Para reducir la complejidad de tiempo que cualquier otra estructura de datos, se introduce el concepto de hashing que tiene tiempo O (1) en el caso promedio y en el peor de los casos tomará tiempo O (n).
El hash es una técnica con acceso más rápido a elementos que mapea los datos dados con una clave menor para las comparaciones. En general, en esta técnica, las claves se rastrean utilizando la función hash en una tabla conocida como tabla hash.
¿Qué es la función hash?
La función hash es una función que utiliza la operación de tiempo constante para almacenar y recuperar el valor de la tabla hash, que se aplica a las teclas como enteros y se usa como la dirección para los valores en la tabla hash.
Tipos de una función hash
Los tipos de funciones hash se explican a continuación:
1. Método de división
En este método, la función hash depende del resto de una división.
Ejemplo: los elementos que se colocarán en una tabla hash son 42, 78, 89, 64 y tomemos el tamaño de la tabla como 10.
Hash (clave) = Elementos% tamaño de tabla;
2 = 42% 10;
8 = 78% 10;
9 = 89% 10;
4 = 64% 10;
La representación de la tabla se puede ver a continuación:
2. Método del cuadrado medio
En este método, la parte media del elemento cuadrado se toma como índice.
Los elementos que se colocarán en la tabla hash son 210, 350, 99, 890 y el tamaño de la tabla será 100.
210 * 210 = 44100, índice = 1 ya que la parte media del resultado (44100) es 1.
350 * 350 = 122500, índice = 25 ya que la parte media del resultado (122500) es 25.
99 * 99 = 9801, índice = 80 ya que la parte central del resultado (9801) es 80.
890 * 890 = 792100, índice = 21 ya que la parte central del resultado (792100) es 21.
3. Método de plegado de dígitos
En este método, el elemento que se colocará en la tabla uh es sing hash key, que se obtiene dividiendo los elementos en varias partes y luego combinando las partes realizando algunas operaciones matemáticas simples.
El elemento a colocar es 23576623, 34687734.
- hash (clave) = 235 + 766 + 23 = 1024
- clave hash) = 34 + 68 + 77 + 34 = 213
En estos tipos de hash supongamos que tenemos números del 1 al 100 y el tamaño de la tabla hash = 10. Elementos = 23, 12, 32
Hash (clave) = 23% 10 = 3;
Hash (clave) = 12% 10 = 2;
Hash (clave) = 32% 10 = 2;
En el ejemplo anterior, observe que ambos elementos 12 y 32 apuntan al segundo lugar de la tabla, donde no es posible escribir ambos en el mismo lugar, dicho problema se conoce como colisión. Para evitar este tipo de problemas, existen algunas técnicas de funciones hash que se pueden utilizar.
Tipos de técnicas de resolución de colisiones
Discutamos los tipos de técnicas de resolución de colisiones:
1. Encadenamiento
En este método, como su nombre lo indica, proporciona una cadena de cuadros para el registro en la tabla que tiene dos entradas de elementos. Entonces, cada vez que ocurren tales colisiones, los cuadros actúan como una lista vinculada que se formará.
Ejemplo: 23, 12, 32 con tamaño de mesa 10.
Hash (clave) = 23% 10 = 3;
Hash (clave) = 12% 10 = 2;
Hash (clave) = 32% 10 = 2;
2. Direccionamiento abierto
- Sondeo lineal
Este es otro método para resolver problemas de colisión. Como su nombre lo indica cada vez que se produce una colisión, se deben colocar dos elementos en la misma entrada de la tabla, pero mediante este método, podemos buscar el siguiente espacio vacío o entrada en la tabla y colocar el segundo elemento. Esto nuevamente puede conducir a otro problema; Si no encontramos ninguna entrada vacía en la tabla, entonces esto conduce a la agrupación. Por lo tanto, esto se conoce como un problema de agrupamiento, que puede resolverse mediante el siguiente método.
Ejemplo: 23, 12, 32 con tamaño de mesa 10
Hash (clave) = 23% 10 = 3;
Hash (clave) = 12% 10 = 2;
Hash (clave) = 32% 10 = 2;
En este diagrama, 12 y 32 se pueden colocar en la misma entrada con el índice 2, pero mediante este método, se colocan linealmente.
- Sondeo cuadrático
Este método es una resolución para el problema de agrupamiento durante el sondeo lineal. En este método, la función hash con clave hash se calcula como hash (clave) = (hash (clave) + x * x)% del tamaño de la tabla (donde x = 0, 1, 2 …).
Ejemplo: 23, 12, 32 con tamaño de mesa 10
Hash (clave) = 23% 10 = 3;
Hash (clave) = 12% 10 = 2;
Hash (clave) = 32% 10 = 2;
En esto, podemos ver que 23 y 12 se pueden colocar fácilmente, pero 32 no puede, ya que 12 y 32 comparten la misma entrada con el mismo índice en la tabla, según este método hash (clave) = (32 + 1 * 1) % 10 = 3. Pero en este caso, la entrada de la tabla con el índice 3 se coloca con 23, por lo que tenemos que incrementar el valor x en 1. Hash (clave) = (32 + 2 * 2)% 10 = 6. Por lo tanto, ahora podemos colocar 32 en la entrada con índice 6 en la tabla.
- Doble hashing
Este método tenemos que calcular 2 funciones hash para resolver el problema de colisión. El primero se calcula utilizando un método de división simple. El segundo tiene que satisfacer dos reglas; no debe ser igual a 0 y las entradas deben ser probadas.
- 1 (clave) = clave% tamaño de la tabla.
- 2 (clave) = p - (clave mod p), donde p son números primos <tamaño de la tabla.
Ejemplo: 23, 12, 32 con tamaño de mesa 10
Hash (clave) = 23% 10 = 3;
Hash (clave) = 12% 10 = 2;
Hash (clave) = 32% 10 = 2;
En esto nuevamente, el elemento 32 se puede colocar usando hash2 (clave) = 5 - (32% 5) = 3. Por lo tanto, 32 se puede colocar en el índice 5 en la tabla que está vacía, ya que tenemos que saltar 3 entradas para colocarlo.
Conclusión: función hash en C
El hash es una de las técnicas importantes en términos de búsqueda de datos proporcionados con métodos muy eficientes y rápidos que utilizan la función hash y las tablas hash. Cada elemento se puede buscar y colocar utilizando diferentes métodos de hashing. Esta técnica es muy más rápida que cualquier otra estructura de datos en términos de coeficiente de tiempo.
Artículos recomendados
Esta es una guía de la función Hashing en C. Aquí discutimos la introducción de la función Hashing en C, Qué es la función Hashing, Tipos de funciones hash, etc. También puede consultar nuestros otros artículos sugeridos para obtener más información.
- Hashing en DBMS
- Proceso de cifrado
- ¿Cómo instalar CakePHP?
- Cómo funciona Blockchain
- Función de hash en Java
- Función de hash en PHP | ¿Como trabajar?