COLISIÓN HASH

Las funciones Hash son muy efectivas al momento de producir números enteros, sin embargo, existe un problema ya que se pueden producir los mismos enteros para dos objetos diferentes. A este problema se le llama Colisión.

Cuando sucede una Colisión, no es posible una organización adecuada de la tabla Hash. Y para tratar este problema existen diferentes algoritmos para resolver por diferentes métodos todas las colisiones posibles:

Linear Probing: En el momento en el que se genera el mismo entero mientras que el primero en salir ya ocupa una posición designada, se procede a buscar a partir de la posición cero de la tabla un lugar vacío avanzando en unidades para poner el entero en esa posición.

Rehashing:Consiste en realizar una segunda función Hash diferente a la primera, con el objetivo de que si hay una entero repetido, se aplique a su llave correspondiente la segunda función, para que tenga diferente localización dentro de la tabla.

Quadratic Probing: Cuando sucede una colición, se procede a tomar H(i)+i² como próxima posición en el caso de que se produzca el mismo entero, y también i representa el intervalo de avance para la función y su resultado.

protected final int findPos( Hashable x )

{

    int collisionNum = 0;

    int currentPos = x.hash( array.length );

    while( array[ currentPos ] != null &&

           !array[ currentPos ].element.equals( x ) )

    {

        currentPos += 2 * ++collisionNum - 1;

            if( currentPos >= array.length )  // Implementar mod

                currentPos -= array.length;

        }

        return currentPos;

    }

}

Encadenamiento: Una vez que se repiten dos llaves, se le agrega un link a la primera llave marcando a la segunda, es decir, a el nodo de la tabla Hash se le agrega otro con un marcador.

ENCADENAMIENTO VS RE-HASHING: 

Organización	Ventajas	Desventajas
Encadenamiento	Número ilimitado de elementos Número ilimitado de colisiones	Repetición excesiva de listas ligadas
Re-hashing	Rehashing rápido. Acceso rápido	El número maximo de elementos debe ser conocido. Hay más probabilidad de que haya colisiones.

En el siguiente link encontramos una animación donde  se explica de manera visual lo que sucede cuando hay una colisión...

Ejemplo de Applet de Colisión

Existe una función Hash llamda Hash Perfecta, la cual no produce enteros repetidos, pero tiene la desventaja de que solamente es efectiva para un número de datos menor de 50.