El método llamado por transformación de claves (hash), permite aumentar la velocidad de búsqueda sin necesidad de tener los elementos ordenados. Cuenta también con la ventaja de que el tiempo de búsqueda es prácticamente independiente del número de componentes del arreglo.

Trabaja basándose en una función de transformación o función hash (H) que convierte una clave en una dirección (índice) dentro del arreglo dirección H(clave).

Cuando se tienen claves que no se corresponden con índices (p. ejem. por ser alfanuméricas), o bien cuando las claves son valores numéricos muy grandes, debe utilizarse una función hash que permita transformar la clave para obtener una dirección apropiada. Esta función hash debe de ser simple de calcular y debe de asignar direcciones de la manera mas uniforme posible. 

Es decir, dadas dos claves diferentes debe generar posiciones diferentes. Si esto no ocurre (H(K1)=d,H(K2)=d y K1K2), hay una colisión. Se define, entonces, una colisión como la asignación de una misma dirección a dos o más claves distintas.

Por todo lo mencionado, para trabajar con este método de búsqueda debe elegirse previamente:

· Una función hash que sea fácil de calcular y que distribuya uniformemente las claves.

· Un método para resolver colisiones. Si estas se presentan se debe contar con algún método que genere posiciones alternativas.

1. Sea cual sea la longitud del texto base A, la longitud de su hash resultante B siempre va a ser la misma. Por ejemplo, si la longitud de la salida B esta defiinida en 128 bits, si aplicamos una función hash a un A de 5 bits nos dará un B de 128 bits, y si se la aplicamos a un A de 380 millones de bits, nos dará un B de 128 bits igualmente.

2- Para cada entrada A, la función generará una salida B única.  O lo que es lo mismo, es imposible que dos textos bases A y A' tengan un mismo hash.

Según estas dos primeras propiedades, nos damos cuenta enseguida de la utilidad de las funciones de hash.

La más inmediata es usarla para generar un resumen de algo. De hecho, estas funciones se conocen también como funciones resumen. Un ejemplo real puede ser el del típico repositorio de documentos. Si alguien quiere almacenar digamos "Las_Aventuras_Del_Ingenioso.doc" cuyo contenido es El Quijote enterito, el sistema lo primero que tiene que hacer es revisar que no está previamente ya almacenado con el mismo o con otro nombre, por ejemplo "ElQuijote.doc". El sistema puede comparar letra a letras el documento de entrada con todos los docs de su BBDD para comprobar que no está, o puede comparar el resumen del documento de entrada con los resúmenes de los documentos de la BBDD, opción mucho más manejable y rápida.

Además, como la salida B es única para cada A, se puede usar también para verificar la integridad de A. Podemos ver que muchos programas incluyen su hash junto con su descarga, de esta forma, podemos verificar que el programa no ha sido modificado ni le han introducido un virus o ha sido troyanizado. Si a los bytes de una aplicación A les calculo el hash B y lo adjunto, cuando alguien modifique la aplicación A, al calcular de nuevo su hash su valor habrá cambiado y será distinto de B.

Podeis probar a calcular el md5 de un documento, luego modificais una simple coma del documento y calculais de nuevo el MD5. Vereis como ha cambiado completamente, aunque solo hemos modificado una simple coma.

3- Dado un texto base, es fácil y rápido (para un ordenador) calcular su número resumen

4- Es imposible reconstruir el texto base a partir del número resumen. 

Esto es lo que se conoce como One-Way hash functions. A partir del hash es imposible reconstruir el texto base.
Atención aquí !!!, no quiero que os lieis. Este es un punto que muchos no teneis claro. Solo hay que leer bien, a partir del hash B es imposible sacar el texto A, quiere decir no existe forma o es computacionalmente imposible, que mediante operaciones matemáticas inversas o no a las del algoritmo de hash, se llegue desde B al texto base. 

Si os dais cuenta, esto es muy distinto que usar fuerza bruta. No tiene nada que ver. Con fuerza bruta le aplicamos la función de hash a diferentes textos hasta que obtenemos un hash similar al hash del texto que buscamos, con lo que por consecuencia tendremos el texto buscado.

5. - No puede presentar Colisiones.

Que son las colisiones

Según la primera caracteristica que hemos visto de las funciones hash, que nos dice que el tamaño del hash B resultante de A es siempre el mismo, deducimos que no puede cumplirse la segunda caracterisitca, que dice que el hash B tiene que ser único para cada A. 

Por ejemplo, la función MD5 nos devuelve un hash de 128 bits. Para que cada hash equivalga a un unico texto base, tendría que existir solamente un texto por cada combinación del hash devuelto, o sea, tendría que haber solamente 2^128 textos distintos, lo cual no es cierto. Como textos distintos hay infinitos, podemos decir que hay infinitas posibilidades de que dos textos tengan el mismo hash.

Esto es lo que se conoce como colisiones.

Seguramente las hemos visto muchas veces sin darnos cuenta de que pasaba. Hay muchos sistemas que requieren contraseñas de uso, como pueden ser los sistemas de foros y demás, donde lo que se almacena no es la contraseña, sino el hash de esa contraseña. Esto no se hace con el propósito de resumir la contraseña, seguramente será mas corta que el hash generado, se hace con el propósito de que si alguien tiene acceso al almacén de contraseñas, o si alguien desensambla la aplicación proteguida, etc, no pueda ver la contraseña en plano y siga sin acceso (a no ser que la crackee por fuerza bruta si conoce el algoritmo de la función).

Os habeis encontrado alguna vez con algún programa que te pide una contraseña para acceder a algo, le metes el crackeador, y te da acceso pero sin darte la clave? Creo recordar que en el Excel95 o 97, el programa que desprotejía las hojas o las celdas, funcionaba así, te desproteguía la hoja pero no te daba la clave.

Eso es porque el algoritmo de la función hash que usan para las contraseñas es tan simple como el que hemos puesto de ejemplo, y tiene multiples colisiones muy fáciles de encontrar. Así que en vez de buscar la contraseña se buscaban colisiones a ese hash, contraseñas alternativas que tenían el mismo hash que la contraseña verdadera.

La fortaleza de una función hash requiere que estas colisiones sean las mínimas posibles y que encontrarlas sea lo más dificil posible.