¿Qué son las funciones hash y cómo elegir una buena función hash?

Requisito previo: hashing | Serie 1 (Introducción) 

¿Qué es una función hash? 

Una función que convierte un número de teléfono grande dado en un pequeño valor entero práctico. El valor entero asignado se utiliza como índice en la tabla hash. En términos simples, una función hash asigna un número grande o una string a un entero pequeño que se puede usar como índice en la tabla hash. 

¿Qué se entiende por buena función hash? 

Una buena función hash debe tener las siguientes propiedades: 

1. Eficientemente computable.
2. Debe distribuir uniformemente las llaves (Cada posición de la mesa es igualmente probable para cada llave)

Por ejemplo: para los números de teléfono, una mala función hash es tomar los tres primeros dígitos. Una mejor función se considera los últimos tres dígitos. Tenga en cuenta que esta puede no ser la mejor función hash. Puede haber mejores maneras. 

En la práctica, a menudo podemos emplear técnicas heurísticas para crear una función hash que funcione bien. La información cualitativa sobre la distribución de las claves puede ser útil en este proceso de diseño. En general, una función hash debe depender de cada bit individual de la clave, de modo que dos claves que difieren en un solo bit o en un grupo de bits (independientemente de si el grupo está al principio, al final o en el medio de la clave o presentes en toda la clave) hash en diferentes valores. Por lo tanto, una función hash que simplemente extrae una parte de una clave no es adecuada. De manera similar, si dos claves son simplemente dígitos o permutaciones de caracteres entre sí (como 139 y 319) , también deberían convertirse en valores diferentes. 

Los dos métodos heurísticos son hash por división y hash por multiplicación , que son los siguientes: 

1. El método mod: 
   • En este método para crear funciones hash, mapeamos una clave en una de las ranuras de la tabla tomando el resto de la clave dividido por table_size. Es decir, la función hash es 
      

h(key) = key mod table_size 

i.e. key % table_size

• Dado que solo requiere una sola operación de división, el hash por división es bastante rápido.
• Cuando usamos el método de división, generalmente evitamos ciertos valores de table_size como table_size no debería ser una potencia de un número, supongamos que r , ya que si table_size = r^p , entonces h(key) son solo los p bits de clave de orden más bajo. A menos que sepamos que todos los patrones de bits p de orden bajo son igualmente probables, es mejor diseñar la función hash para que dependa de todos los bits de la clave.
• Se ha encontrado que los mejores resultados con el método de división se logran cuando el tamaño de la tabla es primo. Sin embargo, incluso si table_size es primo, se requiere una restricción adicional. Si r es el número de posibles códigos de caracteres en una computadora, y si table_size es un número primo tal que r % table_size es igual a 1, entonces la función hash h(key) = key % table_size es simplemente la suma de la representación binaria de los caracteres en la clave mod table_size.
• Supongamos que r = 256 y table_size = 17, en el que r % table_size es decir, 256 % 17 = 1.
• Entonces, para key = 37599 , su hash es 
   

37599 % 17 = 12

• Pero para key = 573 , su función hash también es

573 % 17 = 12

• Por lo tanto, se puede ver que mediante esta función hash, muchas claves pueden tener el mismo hash. Esto se llama Colisión .
• Un número primo que no se acerque demasiado a una potencia exacta de 2 suele ser una buena opción para table_size.

1. El método de multiplicación: 
   • En el método de multiplicación, multiplicamos la clave k por un número real constante c en el rango 0 < c < 1 y extraemos la parte fraccionaria de k * c .
   • Luego multiplicamos este valor por table_size m y tomamos el piso del resultado. Se puede representar como

h(k) = floor (m * (k * c mod 1))
                     or
h(k) = floor (m * frac (k * c))

• donde la función floor(x) , disponible en la biblioteca estándar math.h , produce la parte entera del número real x, y frac(x) produce la parte fraccionaria. [frac(x) = x – suelo(x)] 
   
• Una ventaja del método de multiplicación es que el valor de m no es crítico , generalmente lo elegimos para que sea una potencia de 2 ( m = 2 ^p para algún número entero p ), ya que podemos implementar fácilmente la función en la mayoría de las computadoras
• Suponga que el tamaño de palabra de la máquina es w bits y que la clave cabe en una sola palabra.
• Restringimos c para que sea una fracción de la forma s / (2 ^w ) , donde s es un número entero en el rango 0 < s < 2 ^w . 
   
• Haciendo referencia a la figura, primero multiplicamos key por el número entero de bits w s = c * 2 ^w . El resultado es un valor de 2 bits

r1 * 2w + r0

where r1 = high-order word of the product
      r0 = lower order word of the product

• Aunque este método funciona con cualquier valor de la constante c , funciona mejor con algunos valores que con otros.

c ~ (sqrt (5) – 1) / 2 = 0.618033988 . . .

• es probable que funcione razonablemente bien.
• Suponga k = 123456, p = 14,
• m = 2^14 = 16384 y w = 32.
• Adaptando la sugerencia de Knuth , c para ser una fracción de la forma s/2^32 .
• Luego clave * s = 327706022297664 = (76300 * 2^32) + 17612864,
• Entonces r1 = 76300 y r0 = 176122864.
• Los 14 bits más significativos de r0 dan el valor h(clave) = 67.