tablas hash

'

$

An´lisis y Dise˜ o de Algoritmos
a
n
Tablas de Hash
Guillermo Morales-Luna
Arturo D´ P´rez
ıaz e
CONTENIDO
1. Dispersi´n
o
2. Funciones de dispersi´n
o
(a) M´todo de divisi´n
e
o
(b) M´todo de multiplicaci´n
e
o
3. Direccionamiento abierto
&

%
1

$

'

Dispersi´n
o
• Un diccionario es una estructura de datos abstracta para
conjuntos din´micos en loscuales se aplican las operaciones
a
INSERCION, SUPRESION y BUSQUEDA.
• El uso de arreglos para almacenar estructuras de datos
din´micas es simple, sin embargo,
a
– Los arreglos son de tama˜o fijo
n
– Normalmente se desperdicia espacio de memoria
• Dispersi´n (Hash)
o
– Ubica registros en funci´n de ´
o
ındices, o llaves,
eficientemente.
&

%
2

'

$

Direccionamiento Directo
•Supongamos que se tiene un universo de llaves U
razonablemente peque˜o.
n
– U = 0, 1, . . . , n − 1, donde n no es muy grande
– No existen llaves duplicadas
• En el arreglo T [1 . . . n − 1] cada posici´n se utiliza para
o
representar una llave en el universo. Si el diccionario, S ⊂ U
– si i ∈ S, entonces, T [i] = nil
– si i ∈ S, entonces, T [i] proporciona un apuntador al registro.
•Espacio requerido: Θ(card(T ))
• Inserciones, supresiones y b´squedas toman tiempo O(1).
u
&

%
3

'

$

Implementaci´n de un conjunto din´mico mediante una tabla de
o
a
dispersi´n T .
o
&

%

4

'

$

Tablas de Dispersi´n
o
• La cardinalidad de U debe ser suficientemente peque˜a para
n
que el direccionamiento directo sea pr´ctico
a
• Sean U : conjunto de llaves
• T= [[0, m − 1]]: direcciona elementos de U , m 1 se puede sesgar un aumento de
o
colisiones.
&

%

11

'

$

M´todo de la multiplicaci´n
e
o
Sea · mod 1 : x → x − x : parte fraccionaria de enteros. Sea w el
tama˜o de la palabra de una computador. Ej. 23 2, el enter A es la
n
fracci´n A/w. El m´todo es elegir una constante enter A prima
o
e
relativa a w, y
A
h : k → m(( k)mod 1)
w

(2)

Si m es una potencia de 2, se elige A tal que h(k) consiste de los
bits m´s significativos de la mitad menos significativa del producto
a
Ak.
El m´todo multiplicativo convierte una progresi´n aritm´tica,
e
o
e
k, k + d, k + 2d, . . ., en una progresi´n aritm´tica aproximada,
o
e
h(k), h(k + d), h(k + 2d), . . . de valores de hash distintos.
&
12

%

'

$M´todo de la multiplicaci´n
e
o

&

%
13

'

$

√
Sea A/w la raz´n ´urea φ−1 = 1 ( 5 − 1). h(0), h(1), h(2), . . ., se
o a
2
mapean a {0}, {φ−1 }, {2φ−1 }, . . .
t

t

t

t

t

t

t

t

t

t

t

t

t

.

0

1

2

3

4

5

6

&

7

8

9

10

11

12

13

%
14

'

$

Dispersi´n universal
o
Elegir una funci´n dedispersi´n particular para cada llave.
o
o
H ⊂ [[0, m − 1]]U : colecci´n (finita) de funciones.
o
H es universal si ∀u1 , u2 ∈ U :
u1 = u2 ⇒ card{h ∈ H|h(u1 ) = h(u2 )} =

card(H)
m

(3)

h : x → hx (x), hx ∈ H elegida aleatoriamente.

&

%
15

'

$

Dispersi´n universal
o
Observaci´n 2 Si H es universal, n: n´mero de llaves, m:
o
u
tama˜o tabla, entonces ∀u, esperanza deln´mero de colisiones
n
u
n−1
donde u aparezca es m .
∀u, v ∈ U , u = v, sean cuv =
Se tiene, E(cuv ) =

1
,
m

1

si h(u) = h(v),

0

en otro caso.

y E(Cu ) =

v=u

&

E(cuv ) =

y Cu =

cuv .
v=u

n−1
.
m

%
16

'

$

Construcci´n colecci´n universal H
o
o
• Supongamos que m: n´mero primo. Sea r > 0. A cada x le
u
asociamos r+1 secuencias de s´ımbolos x = (xr , . . . , x1 , x0 ).
• Por ejemplo, si x se representa en binario con k bits, entonces
xi : i-´simo bloque de k/r bits.
e
• Ahora, sea a ∈ [[0, m − 1]]r+1 =< a0 , a1 , . . . , ar > un conjunto
de r + 1 n´meros elegidos aleatoriamente del conjunto
u
0, 1, . . . , m − 1
• La funci´n
o
ha : x → (x · a) mod m = (

r
i=0

xi ai ) mod m.

• Sea H = {ha |a ∈ [[0, m −...