TablasHash

Tablas de Hash
Roberto Abreu

1 de Noviembre de 2010
Santiago de los Caballeros

Roberto Abreu

Tablas de Hash

¿Diccionarios?

O(1) en promedio. Combinaciones llaves/valores. Ejemplo: Tablas
de S´ımbolos de compiladores,
Roberto Abreu

Tablas de Hash

Tablas de Acceso Directo

Roberto Abreu

Tablas de Hash

Tablas de Acceso Directo

Universo de llaves U 0, 1, ..., m − 1
Cada elemento delarreglo (Tabla de Acceso Directo) se
empareja con una llave del universo U
Funcionan bien cuando m es razonablemente peque˜
no
Operaciones BUSCAR, INSERTAR y ELIMINAR toman O(1)

Roberto Abreu

Tablas de Hash

Tablas de Acceso Directo

Inconvenientes con las Tablas de Acceso Directo
Si U es grande, almacenar una tabla T de tama˜
no |U| es
impr´actico o imposible
El conjunto K de llaves realmentealmacenadas puede ser muy
peque˜
no: ¡espacio muerto!

Roberto Abreu

Tablas de Hash

Tablas de Hash

Roberto Abreu

Tablas de Hash

Tablas de Hash

Elemento con llave k almacenado en la posici´on h(k)
> h es una funci´
on hash que computa la posici´on en la tabla.
Empareja al universo U con las posiciones de la tabla hash
T [0, 1, . . . , m − 1]:
h : U → {0, 1, . . . , m − 1}

m es t´ıpicamentemucho m´as peque˜
no que |U|
O(1) en promedio

Roberto Abreu

Tablas de Hash

Colisiones

Debido a que |U| > m, h(ki ) == h(kj ) para i = j
Esto se conoce como una colisi´
on y es imposible impedirla
Pero si podemos minimizar las ocurrencias de colisiones con
una apropiada funci´
on de hash
Roberto Abreu

Tablas de Hash

Encadenamiento

Inserci´on toma O(1) en el peor de los casos: se asume que noest´a
B´
usqueda toma tiempo en relaci´
on a la longitud de la lista
Eliminar: O(1) si las listas son doblemente enlazadas. ¿?
Roberto Abreu

Tablas de Hash

An´alisis de Hashing con Encadenamiento
Dada una tabla de hash T con m posiciones y almacenando n
elementos:
el factor de carga α para T es
posici´on)

n
m

(promedio elementos /

α puede ser menor que, igual a o mayor que 1
Peor de loscasos: Θ(n): b´
usqueda lineal.
Pero NO utilizamos tablas de Hash por su rendimiento en el
peor de los casos
El caso promedio depende entonces de qu´e tan bien h
distribuye el conjunto de llaves entre las m posiciones.
Asunci´on Del Hashing Uniforme Simple
Cada elemento tiene igual chance de estar en cualquiera de las m
posiciones
Roberto Abreu

Tablas de Hash

An´alisis de Hashing conEncadenamiento

Valor Esperado
Para j = 0, 1, . . . , m − 1, definimos la longitud de la listaT [j] en
t´erminos de nj tanto que n = n0 + n1 + . . . + nm−1
El valor esperado de nj es E [nj ] = α = n/m

Roberto Abreu

Tablas de Hash

An´alisis de Hashing con Encadenamiento
Teorema
En una tabla de hash con el mecanismo de encadenamiento para
manejar colisiones, una b´
usqueda fallida toma Θ(1 + α) en
promedio,asumiendo Hashing Uniforme Simple
Demostraci´on
Si k ∈
/ K , k tiene igual probabilidad de hacer hash en
cualquiera de las m posiciones
Tiempo esperado de una b´
usqueda fallida = E [nh(k) ] = α.
Tiempo total esperado: Tiempo esperado de b´
usqueda fallida
+ tiempo de computaci´
on de hash
Tiempo promedio esperado: Θ(1 + α)

Roberto Abreu

Tablas de Hash

An´alisis de Hashing con EncadenamientoTeorema
En una tabla de hash con el mecanismo de encadenamiento para
manejar colisiones, una b´
usqueda exitosa toma Θ(1 + α) en
promedio, asumiendo Hashing Uniforme Simple
Puntos
Asumimos que el elemento buscado puede ser cualquiera de
los n elementos de la tabla
N´
umero de elementos examinados: 1 + que los elementos que
aparecen antes de x en su lista
Esos elementos son insertados luego de xTomamos el promedio, sobre los n elementos de la tabla, de 1
m´as el n´
umero esperado de elementos en la lista de x luego de
ser x insertado.
Definimos una variable indicadora Xij = I h(ki ) = h(kj )
Pr h(ki ) = h(kj ) =

1
m

Roberto Abreu

Tablas de Hash

An´alisis de Hashing con Encadenamiento


E

1
n

n



n

1 +
i=1


Xij 

j=i+1

1
=
n
1
=
n

n
i=1
n



n

1 +

E [Xij ]
j=i+1

...