sadfasdfasdfadsf

White paper – Hashing

Autor: Ramix (Ramiro A. Gómez)
Sitio web: www.peiper.com.ar
Fecha: 6 FEB 2008
Indice

Introducción..................... 1
¿Qué es el hashing?.............. 1
Funciones hash................... 2
Colisiones....................... 3
Usos del hashing................. 4
Tablas hash...................... 5
Hashing dinámico................. 5Conclusiones..................... 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 unaté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 noshacemos 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 elarreglo. 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 nivelmundial, 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 “algoritmiaa 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 produciruna 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 calcular: porque es posible que se
necesite calcular muchas en poco tiempo
● distribuir los elementos de manera uniforme en
todo el rango de la salida: para evitar los
aglomeramientos que degradarían el rendimiento.
●Siempre devolver el mismo código hash para una
misma entrada: por ej. tener cuidado de usar
valores aleatorios calculados dentro de la
función.
● Provocar pocas colisiones (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...