PDF de programación - Estructuras de datos: Tablas de dispersión

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Estructuras de datos: Tablas de dispersión

Algoritmos

Facultad de Informática
Universidad de A Coruña

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Tablas de dispersión

Objetivo: realizar inserciones, eliminaciones y búsquedas
en tiempo promedio constante.
Estructura de datos ideal: un vector con tamaño fijo N.

Una función de dispersión establece la correspondencia
de cada clave con algún número en el intervalo [0 . . . N − 1].
Esta función tiene que ser fácil de calcular, y asegurar que
dos claves distintas se correspondan con celdas diferentes.

Como esto último es imposible, buscamos una función
que distribuya homogéneamente las claves entre las celdas.

Resta escoger una función y decidir el tamaño de la tabla
y qué hacer cuando dos claves caen en la misma celda.

Si al insertar un elemento, éste se dispersa en el mismo valor
que un elemento ya insertado tenemos una colisión
y hay que resolverla.

Las tablas de dispersión se usan para representar diccionarios
en los que se busca una clave y se devuelve su definición.

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Índice

1 Funciones de dispersión

2 Dispersión abierta

3 Dispersión cerrada

Exploración lineal
Exploración cuadrática
Exploración doble

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Funciones de dispersión (i)

Toda función de dispersión debe:
calcularse de forma sencilla, y
distribuir uniformemente las claves.

Por ejemplo, si las claves son números enteros, clave mod N
es una función buena, salvo que haya propiedades indeseables:

Si N fuese 100 y todas las claves terminasen en cero,
esta función de dispersión sería una mala opción.

Es buena idea asegurarse de que el tamaño de la tabla
sea un número primo.

Si las claves fuesen enteros aleatorios, esta función sería
muy simple y distribuiría las claves con uniformidad.
Por lo regular, las claves son cadenas de caracteres.

La longitud y las propiedades de las claves influirán en la elección
de una buena función de dispersión.

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Funciones de dispersión (ii)

Una opción es sumar los valores ASCII de los caracteres.
función Dispersión1 (Clave, TamañoClave): Índice

valor := ascii(Clave[1]);
para i := 2 hasta TamañoClave hacer

valor := valor + acii(Clave[i])

fin para
devolver valor mod N

fin función

Es una función fácil de implementar, y se ejecuta con rapidez.
Pero si el tamaño de la tabla es grande, esta función
no distribuye bien las claves.

Por ejemplo, si N = 10007 y las claves tienen 8 caracteres,
la función sólo toma valores entre 0 y 1016 = 127· 8.

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Funciones de dispersión (iii)

función Dispersión2 (Clave, TamañoClave): Índice
devolver (ascii(Clave[1]) + 27*ascii(Clave[2])

+ 729*ascii(Clave[3])) mod N

fin función

En esta función de dispersión se supone que la clave tiene
al menos tres caracteres.
Si los primeros caracteres son aleatorios y el tamaño de la tabla
es 10007, esperaríamos una distribución bastante homogénea.
Desafortunadamente, los lenguajes naturales no son aleatorios.

Aunque hay 273 = 17576 combinaciones posibles,
en un diccionario el número de combinaciones diferentes
que nos encontramos es menor que 3000.
Sólo un porcentaje bajo de la tabla puede ser aprovechada
por la dispersión.

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Funciones de dispersión (iv)

En la función de dispersión que sigue intervienen todos los
caracteres en la clave y se puede esperar una buena distribución.
función Dispersión3 (Clave, TamañoClave): Índice

valor := ascii(Clave[1]);
para i := 2 hasta TamañoClave hacer

valor := (32*valor + acii(Clave[i])) mod N

fin para
devolver valor

fin función

El código calcula una función polinómica con base en la regla:
LongitudClave−1
i=0

32i · ascii(clave[LongitudClave− i])

Para “abcd” p. ej.
(323 · ascii(a) + 322 · ascii(b) + 32· ascii(c) + ascii(d)) mod N

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Funciones de dispersión (v)

La multiplicación por 32 es el desplazamiento de cinco bits.
Con lenguajes que permitan el desbordamiento se aplicaría mod
una sola vez justo antes de volver.
Si las claves son muy grandes, no se usan todos los caracteres.

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Índice

1 Funciones de dispersión

2 Dispersión abierta

3 Dispersión cerrada

Exploración lineal
Exploración cuadrática
Exploración doble

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Resolución de colisiones: dispersión abierta (i)

La solución consiste en tener una lista de todos los elementos
que se dispersan en un mismo valor.
Al buscar, usamos la función de dispersión
para determinar qué lista recorrer.
Al insertar, recorremos la lista adecuada.

Si el elemento resulta ser nuevo, se inserta al frente
o al final de la lista.

Además de listas, se podría usar cualquier otra estructura
para resolver las colisiones, como un árbol binario de búsqueda.

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Resolución de colisiones: dispersión abierta (ii)

El factor de carga, l
entre el número de elementos en la tabla y su tamaño.

, de una tabla de dispersión es la relación

l = N úmero de claves en la tabla

N

La longitud media de una lista es l

.

En dispersión abierta, la regla es igualar el tamaño
de la tabla al número de elementos esperados, (l = 1).

El esfuerzo al realizar una búsqueda es:

1 el tiempo constante necesario para evaluar la función

de dispersión, O(1), más

2 el tiempo necesario para recorrer la lista, O(l ).

En una búsqueda infructuosa el promedio
de nodos recorridos es O(l )
En una búsqueda con éxito, O(l /2)

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Ejemplo de dispersión abierta (i)

Valores de la función de dispersión:

hash(Ana,11) =7
hash(Olga,11)=7

hash(Luis,11)=6
hash(Rosa,11)=6

Tabla después de insertar Ana:

hash(José,11)=7
hash(Iván,11)=6

1

6

7

2

3

0
10
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [Ana] [ ] [ ] [ ]

8

9

4

5

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Ejemplo de dispersión abierta (i)

Valores de la función de dispersión:

hash(Ana,11) =7
hash(Olga,11)=7

hash(Luis,11)=6
hash(Rosa,11)=6

Tabla después de insertar Ana:

hash(José,11)=7
hash(Iván,11)=6

6

7

4

5

1

2

3

0
10
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [Ana] [ ] [ ] [ ]
Tabla después de insertar Luis:

9

8

2

1

3

0
10
[ ] [ ] [ ] [ ] [ ] [ ] [Luis] [Ana] [ ] [ ] [ ]

4

5

8

9

6

7

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Ejemplo de dispersión abierta (i)

Valores de la función de dispersión:

hash(Ana,11) =7
hash(Olga,11)=7

hash(Luis,11)=6
hash(Rosa,11)=6

Tabla después de insertar Ana:

hash(José,11)=7
hash(Iván,11)=6

7

6

1

4

2

3

5

0
10
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [Ana] [ ] [ ] [ ]
Tabla después de insertar Luis:

8

9

6

5

2

4

1

3

0
10
[ ] [ ] [ ] [ ] [ ] [ ] [Luis] [Ana] [ ] [ ] [ ]
Tabla después de insertar José:

7

8

9

1

3

2

0
10
[ ] [ ] [ ] [ ] [ ] [ ] [Luis] [Ana; José] [ ] [ ] [ ]

4

5

9

7

8

6

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Ejemplo de dispersión abierta (ii)

Tabla después de insertar Olga:

3

4

2

1

0
10
[ ] [ ] [ ] [ ] [ ] [ ] [Luis] [Ana; José; Olga] [ ] [ ] [ ]

5

6

7

8

9

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Ejemplo de dispersión abierta (ii)

Tabla después de insertar Olga:

6

2

1

3

5

4

0
10
[ ] [ ] [ ] [ ] [ ] [ ] [Luis] [Ana; José; Olga] [ ] [ ] [ ]
Tabla después de insertar Rosa:

8

9

7

2

1

3

0
10
[ ] [ ] [ ] [ ] [ ] [ ] [Luis; Rosa] [Ana; José; Olga] [ ] [ ] [ ]

9

8

5

4

6

7

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Ejemplo de dispersión abierta (ii)

Tabla después de insertar Olga:

6

4

3

5

2

1

0
10
[ ] [ ] [ ] [ ] [ ] [ ] [Luis] [Ana; José; Olga] [ ] [ ] [ ]
Tabla después de insertar Rosa:

8

7

9

6

7

1

2

5

4

3

0
10
[ ] [ ] [ ] [ ] [ ] [ ] [Luis; Rosa] [Ana; José; Olga] [ ] [ ] [ ]
Tabla después de insertar Iván:

9

8

3

1

2

0
[ ] [ ] [ ] [ ] [ ] [ ] [Luis; Rosa; Iván]

5

4

6

7
10
[Ana; José; Olga] [ ] [ ] [ ]

8

9

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Tablas de dispersión abiertas: pseudocódigo (i)

tipo

Índice = 0..N-1
Posición = ˆNodo
Lista = Posición
Nodo = registro

Elemento : TipoElemento
Siguiente : Posición

fin registro
TablaDispersión = vector [Índice] de Lista

procedimiento InicializarTabla (T)

para i := 0 hasta N-1 hacer

CrearLista(T[i])

fin para

fin procedimiento

Algoritmos

Tablas de dispersi ón

Funciones de dispersi ón
Dispersi ón abierta
Dispersi ón cerrada

Tablas de dispersión abiertas: pseudocódigo (i)

función Buscar (Elem, Tabla): Posición

i := Dispersión(Elem);
devolver BuscarLista(Elem, Tabla[i])

fin función

procedimiento Insertar (Elem, Tabla)

pos := Buscar(Elem, Tabla); {No inserta repetidos}
si pos = nil entonces
i := Dis