Comencemos analizando brevemente qué es una función hash y qué hace que el algoritmo del cuadrado medio sea una de las mejores opciones para el mismo.
Una función hash, en el más simple de los términos, es una forma de mapear ciertos datos (léase: valores) para que puedan acomodarse dentro de un rango fijo de direcciones (llamadas claves), que durante un tiempo posterior se pueden usar para identificar de forma única esos valores y posiblemente ayudan en una búsqueda de tiempo constante, generalmente lograda modulando el valor final con el tamaño de la estructura de datos en consideración.
Ahora, ¿por qué requerimos métodos efectivos para almacenar estos valores dentro de una estructura de datos (tabla hash)? Bueno, debido a posibles colisiones, por eso.
- ¿Cuál es la diferencia entre O (n!) Vs O (2 ^ n) complejidad de tiempo?
- ¿Cuál es el papel de la memoria de montón?
- Cómo resolver el problema del "número mínimo de cortes"
- ¿Cómo hacemos que una selección sea estable?
- ¿Hay un paquete de Python que calcule la complejidad del tiempo?
¿Qué son las colisiones? Bueno, digamos que, dado que no consideramos muy amable a alguien que invade nuestro espacio personal, los valores también se sienten de la misma manera. Intentar colocar un valor en una ubicación (colocada de manera diferente, contra una clave específica) donde ya reside otro valor conduce a esta condición de colisión.
Y para asegurarnos de que los datos (los valores) se inserten de manera única en las ranuras dentro de la tabla hash, requerimos algoritmos eficientes y efectivos para mapear los valores con las claves de una manera [matemática] 1: 1 [/ matemática] y resolver Estas colisiones.
Ahí es donde entran en juego las funciones de hash. De muchos enfoques disponibles, uno de los más destacados es el método del cuadrado medio. No tiene sentido continuar sin mirar un ejemplo donde este método salva el día, ¿no es así? Así que, aquí vamos.
Considere una tabla hash de tamaño [math] 11 [/ math], por la presente designada como [math] L [/ math]. Y considere este conjunto [math] S [/ math] de los posibles valores que se insertarán en él:
[matemáticas] S = \ {93, 61, 48, 77, 54, 75, 42 \} [/ matemáticas]
Ahora considere, si lo desea, una función hash [math] h_1 (n) [/ math] como:
[matemáticas] h_1 (n) = n \% L [/ matemáticas]
donde [math] \% [/ math] se refiere a la operación del módulo, [math] n [/ math] es la entrada y [math] L [/ math] es el tamaño. Aplicando [math] h_1 [/ math] al conjunto de valores, obtenemos los índices donde se almacena cada uno de ellos (la clave correspondiente):
[matemáticas] h_1 (93) \ Flecha derecha 93 \% 11 = 5 [/ matemáticas]
[matemáticas] h_1 (61) \ Flecha derecha 61 \% 11 = 6 [/ matemáticas]
[matemáticas] h_1 (48) \ Flecha derecha 48 \% 11 = 4 [/ matemáticas]
[matemáticas] h_1 (77) \ Flecha derecha 77 \% 11 = 0 [/ matemáticas]
[matemáticas] h_1 (54) \ Flecha derecha 54 \% 11 = 10 [/ matemáticas]
[matemáticas] h_1 (75) \ Flecha derecha 75 \% 11 = 9 [/ matemáticas]
Hasta aquí todo bien. Cada uno de los valores ha sido mapeado con una clave única. Consideremos el último y terminemos con esta aburrida respuesta pronto.
[matemáticas] h_1 (42) \ Flecha derecha 42 \% 11 = 9 [/ matemáticas]
Espere. ¿Qué? ¿Cómo puede funcionar esto? ¿No está [math] 42 [/ math] asignado a la misma clave a la que [math] 75 [/ math] ya ha estado?
Ahí es exactamente donde el método del cuadrado medio vendrá a nuestro rescate.
Ahora, considere otra función hash [math] h_2 (n) [/ math] definida como:
[matemáticas] h_2 (n) = f [/ matemáticas] [matemáticas] (n, r) \% L [/ matemáticas]
donde [matemática] f [/ matemática] [matemática] (n, r) [/ matemática] es donde ocurre toda la magia, y [matemática] L [/ matemática] es el tamaño de la tabla hash.
Seleccionamos un valor para [math] r [/ math] de antemano, y luego extraemos [math] r [/ math] dígitos más intermedios de [math] n ^ 2 [/ math] para formar un número que luego se modula con [matemáticas] L [/ matemáticas]. Esto es esencialmente de lo que se trata este método.
En pocas palabras, [math] f (n, r) [/ math] se traduce en: square [math] n [/ math] y extrae sus dígitos más medios [math] r [/ math].
¿Confuso? Intentemos encontrar las nuevas claves [math] \ forall x \ en S [/ math], considerando [math] r = 2 [/ math]:
[matemáticas] h_2 (93) \ Flecha derecha f (93, 2) = 93 ^ 2 = 8649 [/ matemáticas] [matemáticas] \ flecha derecha 64 = 64 \% 11 = 9 [/ matemáticas]
[matemáticas] h_2 (61) \ Flecha derecha f (61, 2) = 61 ^ 2 = 3721 [/ matemáticas] [matemáticas] \ flecha derecha 72 = 72 \% 11 = 6 [/ matemáticas]
[matemáticas] h_2 (48) \ Flecha derecha f (48, 2) = 48 ^ 2 = 2304 [/ matemáticas] [matemáticas] \ flecha derecha 30 = 30 \% 11 = 8 [/ matemáticas]
[matemáticas] h_2 (77) \ Flecha derecha f (77, 2) = 77 ^ 2 = 5929 \ flecha derecha [/ matemáticas] [matemáticas] 92 = 92 \% 11 = 4 [/ matemáticas]
[matemáticas] h_2 (54) \ Flecha derecha f (54, 2) = 54 ^ 2 = 2916 [/ matemáticas] [matemáticas] \ flecha derecha 91 = 91 \% 11 = 3 [/ matemáticas]
[matemáticas] h_2 (75) \ Flecha derecha f (75, 2) = 75 ^ 2 = 5625 [/ matemáticas] [matemáticas] \ flecha derecha 62 = 62 \% 11 = 7 [/ matemáticas]
[matemáticas] h_2 (42) \ Flecha derecha f (42, 2) = 42 ^ 2 = 1764 [/ matemáticas] [matemáticas] \ flecha derecha 76 = 76 \% 11 = 10 [/ matemáticas]
¡Uf! Finalmente tenemos todos los valores asignados a claves únicas, y todo gracias al método del cuadrado medio. Matemáticamente hablando, [matemáticas] h_2 (n) [/ matemáticas] es una mejor función hash que [matemáticas] h_1 (n) [/ matemáticas].
Pero como habrás notado, a pesar de que pudimos lograr nuestro objetivo utilizando el cuadrado medio en este caso, ese no siempre es el caso. ¿Qué hubiera pasado si tuviéramos que meter [math] 89 [/ math] allí? Piénsalo.
Este método, como muchos otros, no está exento de sus propias deficiencias, y existen métodos mucho más precisos (eche un vistazo aquí y aquí) para lograr el hash adecuado.
Esto, esto y esto podría interesarle si desea saber más sobre el enfoque de la cuadratura media del hash.
Espero que haya ayudado.
