hash

TABLA HASH

Es un conjunto formado por un número arbitrario de elementos distintos (del mismo tipo), identificado cada uno por una palabra clave diferente, junto con un conjunto de procedimientos de acceso.

FUNCIÓN HASH

Es la que se va a encargar de transformar las claves en direcciones de la tabla.Podríamos definir a la “función ideal” como aquella que distribuya a todos nuestros objetos lo mas uniformemente posible sobre la gama de valores índice, en un tamaño M, en donde M es la cantidad de elementos que tiene la tabla

Metodología para el diseño de funciones hash

Residual (división): el índice de un número es resto de la división de ese número entre un número N prefijado, preferentemente primo. Los números se guardarán en las direcciones de memoria de 0 a N-1. Este método tiene el problema de que al menos un índice es señalado por dos elementos. A este fenómeno se le llama colisión.Representación:H(llave)=llave MOD N donde: 0<= H(llave)<=N-1 Ejemplo.Si el número N es el 13, los números siguientes quedan transformados 13000000 --> 012345678 --> 713602499 --> 171140205 --> 673062138 --> 6


Cuadrática(multiplicación): consiste en elevar al cuadrado la clave y coger las cifras centrales. Este método también presenta problemas de colisión:Representación: H(llave)=digitos_centrales(llave^2) Ejemplo:123*123=15129 --> 51136*136=18496 --> 84730*730=532900 --> 29301*301=90601 --> 06


Folding(plegamiento): consiste en agrupar algunos de los dígitos que conforman la llave y aplicar algunas operaciones (normalmente con suma o multiplicación) que permita generar un índice para el espacio de almacenamiento. También se produce colisión.Ejemplo.Si dividimos los número de 8 cifras en 3, 3 y 2 cifras y se suman, dará otro número de tres cifras (y si no, se cogen las tres últimas cifras):13000000 --> 130=130+000+0012345678 --> 657=123+456+7871140205 --> 118 --> 1118=711+402+0513602499 --> 259=136+024+9925000009 --> 259=250+000+09

Resolver colisionesUna colisión se presenta cuando la función que convierte la llave en una posición dentro de la tabla, generan la misma dirección para dos valores de llave diferenteDependiendo de la forma en que se busca una posición nueva para el elemento cisionado a partir de la dirección base, estas metodologías o pruebas se dividen en 2 grupos:• Direccionamiento abierto• Encadenamiento

Resolver colisiones

• Para almacenar los elementos esta función utiliza solo el espacio definido en la tabla.

• El espacio en la tabla es considerado circular, es decir cuando un elemento provoca una colisión se almacena en otra posición del mismo espacio definido para la tabla, hacia arriba o hacia debajo de la dirección base original

• Cuando se busca, examinamos varias entradas hasta encontrarlo o es claro que no está.

• No hay una lista ni elementos almacenados fuera de la “tabla”.

Dentro de las pruebas mas comunes tenemos las siguientes:

Direccionamiento abierto

Resolver colisiones

Prueba lineal: hi(x) = (h(x) + i)%M, donde i es un contador del número de ocasiones en las que se a registrado una colisión.

Prueba cuadrática: hi(x) = (h(x) + i^2)%M.

Hashing doble: hi(x) = (h(x) + i h (x))%M, donde h’(x) es otra función hash, ′llamada función hash secundaria, cuyo requisito es que nunca pueda tomar el valor 0.


Resolver colisiones

Direccionamiento abiertoEjemplo de la prueba cuadrática

Resolver colisiones

• Las búsquedas de una clave en la tabla hash se realizan en el mismo orden que se siguió para la inserción.

• Los borrados marcan las posiciones de la tabla con un valor distinto de libre u ocupado, para facilitar las nuevas inserciones y la búsqueda de elementos.


Resolver colisiones

Direccionamiento abiertoEjemplo de la prueba cuadrática

hash

Documents