Metodo Hashing

METODO DE BUSQUEDA HASHING



JOSE DAVID GOMEZ CRUZ

ESTRUCTUTRA DE DATOS
UNIVERSIDAD MANUELA BELTRAN
SEPTIEMBRE 6 DE 2011
CAJICA
METODO DE BUSQUEDA HASHING

PROFESOR:
JOSE MORENO

JOSE DAVID GOMEZ CRUZ





ESTRUCTURA DE DATOS
UNIVERSIDAD MANUELA BELTRAN
SEPTIEMBRE 6 DE 2011
CAJICA
INTRODUCCION

Hash se refiere a una función o método para generar claveso llaves que representen de manera casi unívoca a un documento, registro, archivo, etc, resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo.
A la función que transforma una clave en un índice de una tabla se le llama función de hasheo (hash function). Si h es una función de hasheo y clave esuna clave entonces h(clave) es el hasheo de la clave. Si r es el registro cuya clave hashea en hr, entonces hr es la clave de hasheo de r.
Cabe decir que una buena función de hasheo es aquella que minimizan las colisiones y distribuye de forma uniforme los registros. Dejar espacios en blanco en un arreglo es ineficiente en término de espacio, pero reduce sensiblemente la necesidad de resolver loshash clashes y, por lo tanto, gana en velocidad.








METODO DE BUSQUEDA HASHING
Resolviendo colisiones de hasheo por direccionamiento abierto
Un método simple para resolver colisiones de hasheo es el de poner el registro en la siguiente posición disponible en el arreglo. Esta técnica es llamada comprobación lineal(lineal probing) y es un ejemplo de un método general pararesolver colisiones de hasheo llamado rehasheo (rehashing) o direccionamiento abierto (open addresing). En general una función de rehasheo, rh, acepta un índice del arreglo para calcular otro. Si la posición h(clave) del arreglo ya se encuentra ocupada por un registro con una clave diferente, rh es aplicada al valor de h(clave)para encontrar otra posición donde el registro pueda ser guardado. Siesta ´ultima posición se encuentra también ocupada puede ser aplicada la función, nuevamente, para saber sí rh(rh(h(clave))) está disponible.

Notemos que puede ocurrir que en el rehasheo nunca se encuentre una posición disponible por lo que se seguiría intentando calcular sin ningún resultado innatamente. Esto puede pasar por dos motivos. Primero que la tabla este completa, lo cual esfácilmente salvable contando las veces que se aplica la función y comparando contra el total de elementos de la tabla. Segundo existen posiciones libres en la tabla pero la función de rehasheo nunca las toca. Consideremos la situación donde las los impares están llenos, los pares vacíos, y la función de rehasheo solo toca los impares.
Una de las propiedades de la una buena función de rehasheo es aquellaque para cualquier ´índice i, los sucesivos rehasheos rh(i),rh(rh(i)),etc., cubre enteros desde 0 hasta el tamaño de la tamtabla - 1.
Existe otra forma de medir la eficiencia de la función de rehasheo. Consideremos el caso de un rehasheo lineal. Considerando que la función de hasheo produce índices de que son uniformemente distribuidos sobre intervalos de 0 y tamtabla -
1. Cuando el arregloestá vacío veremos que cualquier registro será ingresado en la tabla. Luego, que se hayan realizado varias entradas y algunas colisiones hayan sido resueltas, lo anterior ya no será cierto. El efecto en el cual dos claves que hashean en diferentes valores compiten entre ellas en sucesivos rehasheos se llama agrupamiento primario (primary clustering).
De hecho las funciones que dependenexclusivamente de los ´índices ha ser rehasheados causan agrupamiento primario.


Una forma de resolver este problema es permitir que la función de rehasheo dependa del número de veces que la función fue aplicada a un valor particular de hasheo. De esta forma rh es una función de dos argumentos. rh(i,j) depende del entero de rehasheo i y de la clave que está siendo rehasheada por j -esima ves.
Otro...