Tecnicas hash y colisiones

¿ QUÉ ES UNA COLISIÓN ?
Es una situación que se produce cuando dos entradas distintas a una función producen la misma salida.//Es el resultado de la transmisión simultánea de dos nodos en un medio compartido. Las tramas se dañan//Redes:

Una función de dispersión o de hash tiene como finalidad transformar, a partir de operaciones numéricas, los caracteres que componen la llave delregistro, de forma que indiquen en qué dirección se va a almacenar o recuperar el registro.
Estas direcciones idealmente deben ser únicas para cada valor de llave e irrepetibles. Pro esto, también se conocen como funciones de mapeo de uno a uno (el valor de la llave para una dirección única dentro del archivo). El problema es que no siempre se puede dar esa relación de uno a uno.
Cuando se tienemás de una llave diferente y se transforman a través de la función de dispersión y de la misma dirección para almacenar estos registros se conoce como colisión. Ya que sólo se puede almacenar un registro en cada dirección.
TÉCNICAS DE COLISIONES
Hay varias técnicas de resolución de colisiones, pero las más populares son encadenamiento y direccionamiento abierto.
Encadenamiento
En latécnica más simple de encadenamiento, cada casilla en el array referencia una lista de los registros insertados que colisionan en la misma casilla. La inserción consiste en encontrar la casilla correcta y agregar al final de la lista correspondiente. El borrado consiste en buscar y quitar de la lista.
[pic]
Ejemplo de encadenamiento.
La técnica de encadenamiento tiene ventajas sobredireccionamiento abierto. Primero el borrado es simple y segundo el crecimiento de la tabla puede ser pospuesto durante mucho más tiempo dado que el rendimiento disminuye mucho más lentamente incluso cuando todas las casillas ya están ocupadas. De hecho, muchas tablas hash encadenadas pueden no requerir crecimiento nunca, dado que la degradación de rendimiento es lineal en la medida que se va llenandola tabla. Por ejemplo, una tabla hash encadenada con dos veces el número de elementos recomendados, será dos veces más lenta en promedio que la misma tabla a su capacidad recomendada.
Las tablas hash encadenadas heredan las desventajas de las listas ligadas. Cuando se almacenan cantidades de información pequeñas, el gasto extra de las listas ligadas puede ser significativo. También losviajes a través de las listas tienen un rendimiento de caché muy pobre.
Otras estructuras de datos pueden ser utilizadas para el encadenamiento en lugar de las listas ligadas. Al usar árboles auto-balanceables, por ejemplo, el tiempo teórico del peor de los casos disminuye de O(n) a O(log n). Sin embargo, dado que se supone que cada lista debe ser pequeña, esta estrategia es normalmenteineficiente a menos que la tabla hash sea diseñada para correr a máxima capacidad o existan índices de colisión particularmente grandes. También se pueden utilizar arreglos dinámicos para disminuir el espacio extra requerido y mejorar el rendimiento del caché cuando los registros son pequeños.
Direccionamiento abierto
Las tablas hash de direccionamiento abierto pueden almacenar los registrosdirectamente en el array. Las colisiones se resuelven mediante un sondeo del array, en el que se buscan diferentes localidades del array (secuencia de sondeo) hasta que el registro es encontrado o se llega a una casilla vacía, indicando que no existe esa llave en la tabla.
[pic]
Ejemplo de direccionamiento abierto.

Las secuencias de sondeo más socorridas incluyen:

*sondeo lineal: en el que elintervalo entre cada intento es constante--frecuentemente 1.
*sondeo cuadrático: en el que el intervalo entre los intentos aumenta linealmente (por lo que los índices son descritos por una función cuadrática),
*doble hasheo: en el que el intervalo entre intentos es constante para cada registro pero es calculado por otra función hash.
El sondeo lineal ofrece el mejor rendimiento del caché,...