Jorge Niedbalski R : Another boring unix programmer.

Cada desarrollador debe conocer al menos una manera de identificar un elemento desde un vector utilizando un indice. Un indice es un puntero que “apunta” un objeto ya sea de un tipo de dato básico o algun elemento compuesto ( struct, map, otro vector).

Para un valor dado t se utiliza una funcion m tal que m genere una llave k que represente un indice en un vector o un slot de un array asociativo.

Dadas las limitaciones como espacio de direcciones disponibles en una computadora digital , es teoricamente imposible que para cada valor t de un conjunto potencialmente infinito , no existan colisiones para el mismo indice en el mismo slot.

Debido a este axioma la gran mayoria de los algoritmos que implementan tabla hash asumen la paradoja del cumpleaños implicando que a medida que aumentan los indices en la tabla. independiente de la uniformidad de la función de dispersión , la probabilidad de colisión aumenta linealmente.

Es por lo antes expuesto que es un requerimiento escencial para la funcion de dispersion proveer una distribución uniforme que garantice una baja cantidad de colisiones y un costo cercano a lineal para la resolución. Mas adelante iré describiendo algunas tecnicas para la resolución de colisiones en una tabla hash ( algunas estudiadas durante mi tesis de pregrado ).

Lo importante es que conozcamos al menos una función que distribuya valores no conocidos de tamaño-no acordado ( variable ) . Para el caso de valores conocidos es posible crear una tabla hash perfecta ( todos sus valores se distribuyen sin colisiones ) matematicamente es definida como injectiva.

Si cada elemento de entrada puede ocurrir con una probabilidad uniforme , como por ejemplo suponiendo que cada elemento del conjunto de entrada es un integro en el rango de 0 hasta N -1 , una buena funcion hash puede ser h = integro % n.

Para el caso de strings de tamaño variable , existen diferentes funciones para generar llaves que distribuyen relativamente bien en arquitecturas de 32 o 64 bits. La que utilizo con mayor frecuencia es la popular DJBX33X , propuesta por Daniel J. Bernstein . Tambien pueden guiarse por otras funciones de acuerdo a esta comparativa.

La funcion DJBX33X tiene algunas caracterizticas que la hacen única, en primer lugar por que se calcula muy rapido en procesadores i386 y en segundo lugar por que distribuye muy cercano a perfecto.

hash(i) = hash(i-1) * 33 + string[i]

Las razones de por que se escoge el numero 33 como constante son explicadas por Ralf S. Engelschall , sabiendo que este fue escogido como la función hash de PHP ( No es menor , comprendiendo que PHP basa sus GST y otras funcionalidades del lenguaje en tablas de dispersion).

Si experimentalmente se prueban todos los multiplos entre 1 y 256 se detectan que no todos los numeros pares funcionan bien, a diferencia los numeros impares funcionan igual o mejor. En particular el numero 33 no tiene nada de especial por sobre otros buenos numeros con excepcion de que su operacion de multiplicacón puede ser reemplazada por un solo desplazamiento más una operacion de suma o resta.

Ejemplo de implementación utilizando un desplazamiento y suma , con una variante para performance ( repitiendo 8 veces ) :

djbx33a(
    register act_uint8_t *key,
    register act_size_t len)
{
    register act_uint32_t hash = 5381;

#ifdef ACT_NON_OPTIMIZE
    while (len-- > 0)
        hash = ((hash << 5) + hash) + *key++;
#else
    /* variant with the hash unrolled eight times */
    for (; len >= 8; len -= 8 ) {
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
    }
    switch (len) {
        case 7: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        case 6: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        case 5: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        case 4: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        case 3: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        case 2: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        case 1: hash = ((hash << 5) + hash) + *key++; break;
        default: /* case 0: */ break;
    }
#endif
    return hash;
}

Tambien puede utilizarse una variante usando un XOR

 hash = ((hash << 5) + hash) ^ *key++;

Tambien es posible utilizar algoritmos de checksum o criptograficos como funciones de dispersión, generalmente producen valores con una distribucion lo suficientemente uniformes , en particular SHA-1 garantiza una uniformidad fuerte , para aplicaciones comunes la desventaja de utilizarlo es el costo del tiempo de calculo.

A modo de conclusión existen multiples funciones de generacion de llaves de dispersión, lo importante es que cumplan con proveer una distribucion uniforme para un set de datos dado. Es importante , además, que sean eficientes en funcion de tiempo, esperando un tiempo lineal. Es posible utilizar funciones criptograficas o de checksum ( no use CRC32 ).

Una formula para calcular la probabilidad de una colisión, puede ser :

Hash collision formula

Por ejemplo 80M de llaves @ 16 KB ( 12.2 TB) tiene una probabilidad de 2.18e-31 de una colisión.

Recordarles que cuando se implementa un algoritmo de tabla hash es importante proveer un buen mecanismo de solución a colisiones, tema que abordare en otro articulo.