Funciones hash y lista/tipos de funciones hash

Hashing es el proceso de generar un valor a partir de un texto o una lista de números utilizando una función matemática conocida como función hash .

Una función Hash es una función que convierte una clave numérica o alfanumérica determinada 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 significativo o una string a un entero pequeño que se puede usar como índice en la tabla hash.

El par es de la forma (clave, valor) , donde para una clave dada, uno puede encontrar un valor usando algún tipo de «función» que asigna claves a valores. La clave para un objeto dado se puede calcular usando una función llamada función hash. Por ejemplo, dada una array A, si i es la clave, entonces podemos encontrar el valor simplemente buscando A[i].

Tipos de funciones hash

Hay muchas funciones hash que usan claves numéricas o alfanuméricas. Este artículo se centra en discutir diferentes funciones hash:

1. Método de división.
2. Método del cuadrado medio.
3. Método de plegado.
4. Método de multiplicación.

Comencemos discutiendo estos métodos en detalle.

1. Método de división:

Este es el método más simple y fácil para generar un valor hash. La función hash divide el valor k por M y luego usa el resto obtenido.

Fórmula:

h(K) = k mod M

Aquí,
k es el valor clave y 
M es el tamaño de la tabla hash.

Lo más adecuado es que M sea un número primo, ya que eso puede garantizar que las claves se distribuyan de manera más uniforme. La función hash depende del resto de una división. 

Ejemplo:

k = 12345
M = 95
h(12345) = 12345 módulo 95 
               = 90

k = 1276
M = 11
h(1276) = 1276 módulo 11 
             = 

Ventajas:

1. Este método es bastante bueno para cualquier valor de M.
2. El método de división es muy rápido ya que requiere una sola operación de división.

Contras:

1. Este método conduce a un bajo rendimiento ya que las claves consecutivas se asignan a valores hash consecutivos en la tabla hash.
2. A veces, se debe tener especial cuidado al elegir el valor de M.

2. Método del cuadrado medio:

El método del cuadrado medio es un muy buen método hash. Se trata de dos pasos para calcular el valor hash:

1. Elevar al cuadrado el valor de la clave k es decir k ²
2. Extraiga los dígitos r del medio como el valor hash.

Fórmula:

h(K) = h(kxk)

Aquí,
k es el valor clave. 

El valor de r se puede decidir en función del tamaño de la tabla.

Ejemplo:

Suponga que la tabla hash tiene 100 ubicaciones de memoria. Entonces, r = 2 porque se requieren dos dígitos para asignar la clave a la ubicación de la memoria.

k = 60
k xk = 60 x 60
        = 3600
h(60) = 60

El valor hash obtenido es 60

Ventajas:

1. El rendimiento de este método es bueno ya que la mayoría o todos los dígitos del valor clave contribuyen al resultado. Esto se debe a que todos los dígitos de la clave contribuyen a generar los dígitos del medio del resultado al cuadrado.
2. El resultado no está dominado por la distribución del dígito superior o inferior del valor clave original.

Contras:

1. El tamaño de la clave es una de las limitaciones de este método, ya que la clave es de gran tamaño y su cuadrado duplicará el número de dígitos.
2. Otra desventaja es que habrá colisiones, pero podemos intentar reducir las colisiones.

3. Método de plegado de dígitos:

Este método implica dos pasos:

1. Divida el valor-clave k en un número de partes, es decir , k1, k2, k3,….,kn , donde cada parte tiene el mismo número de dígitos excepto la última parte que puede tener menos dígitos que las otras partes.
2. Agregue las partes individuales. El valor hash se obtiene ignorando el último acarreo, si lo hay.

Fórmula:

k = k1, k2, k3, k4, ….., kn
s = k1+ k2 + k3 + k4 +….+ kn
h(K)= s

Aquí,
s se obtiene sumando las partes de la clave k

Ejemplo:

k = 12345
k1 = 12, k2 = 34, k3 = 5
s = k1 + k2 + k3
  = 12 + 34 + 5
  = 51 
h(K) = 51

Nota:
El número de dígitos en cada parte varía según el tamaño de la tabla hash. Supongamos por ejemplo que el tamaño de la tabla hash es 100, entonces cada parte debe tener dos dígitos excepto la última parte que puede tener un número menor de dígitos.

4. Método de multiplicación

Este método implica los siguientes pasos:

1. Elija un valor constante A tal que 0 < A < 1.
2. Multiplique el valor de la clave con A.
3. Extraiga la parte fraccionaria de kA.
4. Multiplique el resultado del paso anterior por el tamaño de la tabla hash, es decir, M.
5. El valor hash resultante se obtiene tomando el piso del resultado obtenido en el paso 4.

Fórmula:

h(K) = suelo (M (kA mod 1))

Aquí,
M es el tamaño de la tabla hash.
k es el valor clave.
A es un valor constante.

Ejemplo:

k = 12345
A = 0,357840
M = 100

h(12345) = piso[ 100 (12345*0.357840 mod 1)]
               = piso[ 100 (4417.5348 mod 1) ]
               = piso[ 100 (0.5348) ]
               = piso[ 53.48 ]
               = 53

Ventajas:

La ventaja del método de la multiplicación es que puede funcionar con cualquier valor entre 0 y 1, aunque hay algunos valores que suelen dar mejores resultados que el resto.

Contras:

El método de multiplicación generalmente es adecuado cuando el tamaño de la tabla es la potencia de dos, entonces todo el proceso de calcular el índice por la clave utilizando el hash de multiplicación es muy rápido.