M.I.A Daniel Alejandro García López
TABLAS HASH
TABLAS HASH
Primer componente: Arreglo de cubetas.- Es una
arreglo A de tamaño N, en el que se puede
considerar que cada celda de A es una cubeta.
 Segundo componente: Función Hash.- mapea
cada clave k con un entero del intervalo [0, N-1].

Una función hash es “buena” si mapea las claves en tal
forma que minimiza las colisiones hasta donde es
posible.
 Fácil y rápida de calcular.

PROCESO DE OBTENCIÓN DE TABLA HASH
Objetos arbitrarios
Valor o código Hash
…-3 -2 -1 0 1 2 3 …
Mapeo de compresión
0 1 2 3 4 5 6 …N-1
CODIGO HASH

Toma una clave arbitraria k, y le asigna un valor
entero. El entero asignado a una clave k se
llama código hash o valor hash. Este valor no
necesita encontrarse en el intervalo [0 N-1], y
hasta puede ser negativo, pero es preferible
que el conjunto de códigos hash eviten las
colisiones lo más que se pueda.
MAPAS DE COMPRESION

El código hash para una clave k no será
adecuado, en el caso normal, para usarse de
inmediato en un arreglo de cubetas, porque el
intervalo de códigos hash posible para claves
será mayor. Por lo tanto se requiere mapear, o
relacionar los valores con los indices en el
intervalo [0, N-1].
MÉTODO DE DIVISIÓN O ARITMÉTICA MODULAR
Elegir el número de elementos que deseamos
almacenar en nuestra tabla Hash
 Elegir el número primo(N) mayor a nuestro
numero de elementos a almacenar
 H(k)=|k| mod N

ESQUEMAS DE MANEJO DE COLISIÓN

Encadenamiento separado: Forma sencilla y
eficiente para manejar colisiones es hacer que
cada cubeta guarde una referencia a una lista.
 Demo

Direccionamiento abierto
 Prueba
lineal(Complicacion de eliminación)A[i+1]
 Prueba cuadrática(A[i+f(j) mod N]: j=0,1,2,, j^2)
 Doble hash(A[i+f(j) mod N]: j=1,2,3, j*h’(k); h’(k)=qk-(k mod q))
Descargar

Tablas hash