Colissiones(hash)

Manejo de Colisiones
Colisión (hash)
En informática, una colisión de hash es una situación que se produce cuando dos entradas distintas a una función de hash producen la misma salida.
Es matemáticamente imposible que una función de hash carezca de colisiones, ya que el número potencial de posibles entradas es mayor que el número de salidas que puede producir un hash. Sin embargo, lascolisiones se producen más frecuentemente en los malos algoritmos. En ciertas aplicaciones especializadas con un relativamente pequeño número de entradas que son conocidas de antemano es posible construir una función de hash perfecta, que se asegura que todas las entradas tengan una salida diferente. Pero en una función en la cual se puede introducir datos de longitud arbitraria y que devuelve un hash detamaño fijo (como MD5), siempre habrá colisiones, dado que un hash dado puede pertenecer a un infinito número de entradas.

En búsquedas
Un método eficiente de búsqueda puede ser mediante el procesamiento de una clave de búsqueda usando una función de hash, tomar a continuación el valor de hash resultante y usarlo finalmente como índice en un vector o arreglo de datos. La estructura de datosresultante de este esquema se llama tabla hash. Mientras claves de búsqueda distinta mapeen índices distintos, la búsqueda puede realizarse en tiempo constante. Por el otro lado, cuando varias claves de búsqueda mapean al mismo índice, se produce una colisión. Las formas convencionales de tratar esta situación son el encadenado (construcción de listas ligadas de valores para cada índice del arreglo)y direccionamiento abierto (búsqueda de otros índices cercanos del arreglo que tengan posiciones no ocupadas). Sin embargo, ambas soluciones degradan la complejidad de la búsqueda de peor caso a tiempo lineal de número de elementos.

Resistencia fuerte y débil a colisiones
Para un dado, si resulta fácil encontrar un tal que , se habla de una resistencia débil a colisiones. Si resulta difícilencontrar un par tal que, se habla de una resistencia fuerte a colisiones.

En criptografía
Una de las propiedades deseables de las funciones de hash criptográficas es que sea computacionalmente imposible que se produzca una colisión. El valor de una función hash puede ser usado para certificar que un texto dado (o cualquier otro dato) no ha sido modificado, publicando el valor firmado de lafunción de hash si no es factible que se produzca una colisión. En este contexto, factible se refiere a cualquier método capaz de producirla más rápido que un ataque de cumpleaños de fuerza bruta.
El proceso de encontrar dos valores arbitrarios cuyos hashes collisionan se llama ataque de colisiones. El proceso de encontrar un valor arbitrario cuyo hash colisione con otro hash dado se llama ataque preimagen. Un ataque pre imagen exitoso es mucho más serio que un ataque de colisiones exitoso.
Colisión (hash) 2

Clasificación
• Hashing Perfecto: Existe una Función de Enumeración que asigna a cada valor del dominio una única posición de memoria. No posee colisiones.
• Hashing Puro: La función de Hash puede asignar a dos valores distintos el mismo lugar en memoria. Y Estos dos valoresreciben el nombre de sinónimos. Las estructuras de hashing puros poseen colisiones y en consecuencia se deberán establecer mecanismos para tratar los mismos.

Podemos clasificarlos enestructuras cerradas y abiertas y dentro de las abiertas en estáticas y dinámicas:
• Cerradas: No utilizan un nuevo espacio en memoria.
• Abiertas: Utilizan espacio adicional.
• Estática: La estructura principal nocrece.
• Dinámica: La estructura principal se expande a medida que aumenta la cantidad de elementos.

Resolución de colisiones
Si dos llaves generan un hash apuntando al mismo índice, los registros correspondientes no pueden ser almacenados en la misma posición. En estos casos, cuando una casilla ya está ocupada, debemos encontrar otra ubicación donde almacenar el nuevo registro, y hacerlo de...