Tecnicas De Hasing

.peiper.com.ar

White paper Autor: Ramix (Ramiro A. Gómez) Sitio web: Fecha: 6 FEB 2008

Hashing

Indice

Introducción 1

¿Qué es el hashing? 1

Funciones hash 2

Colisiones 3

Usos del hashing 4

Tablas hash 5

Hashing dinámico 5

Conclusiones 6

Introducción

En esta edición de Peiper decidimos armar un white paper con una de la técnicas más interesantes que tiene la informática, no decimos la más interesante, pero sí una de ellas. Esto es así porque el hashing tiene varios usos, que van desde búsqueda rápida de datos hasta encriptación, pasando por códigos de verificación.

¿Qué es el hashing?

El hashing es una técnica que consta de datos de entrada, una función hash y una salida. Esta función calcula un código específico para un dato de entrada (como puede ser un nombre, por ejemplo). El valor calculado puede parecer aleatorio, pero no lo es, ya que las operaciones para computar la salida son siempre las mismas. La función hash asocia siempre la misma salida para una entrada determinada. Por ejemplo:

hash(“María”) = 1082358727484

luego, a los 3 días calculamos hash(María) nuevamente

hash(“María”) = 1082358727484

y el valor computado es el mismo.

La salida de la función hash es siempre un número, pero se puede convertir a caracteres u otro tipo de dato. Además, este número depende exclusivamente de la entrada porque las operaciones se realizan sobre estos. Pero la pregunta que nos hacemos es ¿para qué quisieramos asignarle un código a un dato de entrada (como ser un nombre)? La respuesta es que este número lo podemos usar para almacenar ese dato en la posición indicada.

Ejemplo: hash(“Pepe”) = 130

Entonces vamos a almacenar en la posición 130 la cadena “Pepe”, además de sus datos personales, por ej. Cuando querramos buscar “Pepe” no hace falta recorrer todo el arreglo. Calculamos la función hash a este nombre y accedemos a la posición del arreglo que nos indica la salida de la función.

Si no existiría el hashing, por ejemplo, para buscar un dato en un arreglo tendríamos que buscar en cada posición, una por una. Y esto se vuelve un problema para conjuntos grandes de datos.

Imaginen tener una lista de clientes de una tarjeta de crédito a nivel mundial, con un tamaño de 500 millones. Solo para encontrar uno de ellos habría que recorrer una media de 250 millones de posiciones!! Agreguen a esto si tenemos 1.000.000 de ellos queriendo acceder al mismo tiempo. Esta sí es una situación crítica!

Funciones hash

Aunque la filosofía de nuestro sitio es explicar cosas complejas de la manera más sencilla posible (algo que denominámos “algoritmia a la criolla”... y no es un plato de comida,je), vamos a introducir un poco de formalidad, de manera de verlo resumido en símbolos.

Una función hash es una función

h(x): N->N/ h(x) = y

(generalmente la entrada son números naturales y la

salida también).

Muchas veces es imposible encontrar una función inversa

hi(y) = x

ya que dos entradas x totalemente distintas pueden llegar a producir una misma salida y. Si es posible encontrarla, es un proceso muy complejo que consume mucho tiempo si se realiza por fuerza bruta.

Una función hash debe ser:

• r ápida de calcula r: porque es posible que se necesite calcular muchas en poco tiempo

• d istribuir los elementos de manera uniforme e n todo el rango de la salida: para evitar los aglomeramientos que degradarían el rendimiento.

• S iempre devolver el mismo código hash para un a misma entrada: por ej. tener cuidado de usar valores aleatorios calculados dentro de la función.

• P rovocar pocas colisione s (en lo posible ninguna): cuando una función hash no tiene colisiones se dice que es “perfecta”.

La técnica de hashing aplicada sobre tablas permite operaciones de búsqueda, inserción y borrado muy eficientes, de orden O(k), k:constante. En la práctica la eficiencia media de estas operaciones es O(1,5) u O(2). Para comparar, en búsqueda lineal es O(n/2), n:cantidad de elementos.

Ya podemos ver la gran ventaja de las tablas hash: la búsqueda es “casi” independiente de la cantidad de elementos.

Una vez que tiene los números de entrada les aplica sumas, restas, multiplicaciones, divisiones, operaciones lógicas AND, OR, NOT y XOR (entre otras). También rota

Una función hash traduce los datos de entrada a números. Por ej., a cada carácter le asigna un número.

los bits de un número a izquierda o derecha. Es decir, puede aplicar todas las operaciones que se realizan sobre números.

Una buena función de éstas, produce un número totalmente diferente aunque los cambios en los datos de entrada sean mínimos. Se relaciona de buena manera con un comportamiento caótico (donde influyen sobremanera las condiciones iniciales, la entrada). Ej:

hash(“Peiper”) = 5875775475550

Ahora reemplazamos la P por D,

hash(“Deiper”) = 8416409012872

Colisiones

Si tenemos W cantidad de entradas posibles, y la cantidad de bits de la salida es Z; si 2Z < W quiere decir que tenemos más entradas que posibles salidas. Por ejemplo: tenemos 1000 nombres y nuestra salida es de 9 bits. Con 9 bits podemos formar 29 combinaciones distintas de los bits, o sea 512.

000000000, 000000001, 000000010, 000000011, etc... Tenemos que mapear 1000 claves a 512 posiciones, y

...