PDF de programación - Tema 06 - Tablas

TEMA 6
TABLAS


— Modelo matemático y especificación
— Implementación con acceso basado en búsqueda
— Implementación con acceso casi directo: tablas dispersas

— Tablas dispersas abiertas

— Funciones de localización

— Tablas dispersas cerradas

— Funciones de relocalización

— Eficiencia



i

Tablas



1

6.1 Modelo matemático y especificación
Desde el punto de vista matemático, las tablas son aplicaciones que hacen co-
rresponder a claves, c ∈ C –C conjunto de claves–, valores, v ∈ V –V conjun-
to de valores–. Podemos verlas como una generalización de los árboles de
búsqueda, como colecciones de pares (clave, valor), donde el acceso se realiza
por las claves y donde, a diferencia de los árboles de búsqueda, no se supone
una estructura de árbol –aunque pueden ser implementadas como tales–.
Para dar un modelo matemático de las tablas hay dos posibilidades naturales:

— Funciones totales T : C → V, suponiendo en V un elemento distinguido

NoDef.

— Funciones parciales T : C – → V.


Las operaciones que nos interesan en las tablas son las que permiten: crear una
tabla vacía, insertar una pareja (clave, valor), comprobar si la tabla está vacía,
comprobar si una clave está en la tabla, consultar el valor asociado a una clave,
y borrar un par (clave, valor).


Para ciertas aplicaciones de las tablas resulta conveniente que exista un orden
entre las claves, y que se disponga de una operación que extraiga la informa-
ción almacenada en la tabla en forma de lista (o secuencia) de parejas de tipo
(Clave, Valor), ordenada por claves.

— Las tablas ordenadas se pueden implementar directamente como árboles de

búsqueda.



En ocasiones, también resulta útil que una inserción con clave ya presente en
la tabla combine el nuevo valor con el antiguo, en lugar de limitarse a reempla-
zar el valor antiguo por el nuevo. Sin embargo, esto impone restricciones adi-
cionales sobre el tipo de los valores.



Tablas



2



Especificación de las tablas como funciones parciales
La especificación de las tablas como funciones parciales es muy similar a la
especificación de los árboles de búsqueda (basta con que los elementos tengan
igualdad, no es necesario que tengan orden).


tad TABLA[C :: EQ, V :: ANY]
renombra
C.Elem a Clave
V.Elem a Valor
usa
BOOL
tipo
Tabla[Clave, Valor]
operaciones
Nuevo: → Tabla[Clave, Valor]
/* gen */
Inserta: (Tabla[Clave,Valor], Clave, Valor) → Tabla[Clave,Valor] /* gen */
consulta: (Tabla[Clave, Valor], Clave) – → Valor
/* obs */
borra: (Tabla[Clave, Valor], Clave) → Tabla[Clave, Valor]
/* mod */
está: (Tabla[Clave, Valor], Clave) → Bool
/* obs */
esVacio: Tabla[Clave, Valor] → Bool
/* obs */
ecuaciones
∀ t : Tabla[Clave, Valor] : ∀ i, j : Clave : ∀ x, y : Valor :
Inserta(Inserta(t, i, x), j, y) = Inserta(t, j, y)
si i == j
Inserta(Inserta(t, i, x), j, y) = Inserta(Inserta(t, j, y), i,x) si i /= j
esVacio(Nuevo)
esVacio(Inserta(t, i, x))
está(Nuevo, j)
está(Inserta(t, i, x), j)
def consulta(t, i) si está(t, i)
consulta(Inserta(t, i, x), j) = x
consulta(Inserta(t, i, x), j) =f consulta(t, j)
borra(Nuevo, j)
borra(Inserta(t, i, x), j)
borra(Inserta(t, i, x), j)
errores
consulta(t, i) si NOT está(t, i)
ftad


= cierto
= falso
= falso
= i == j OR está(t, j)

= Nuevo
= borra(t, j)
= Inserta(borra(t, j), i, x)

si i == j
si i /= j

si i == j
si i /= j



Tablas



3

6.2 Implementación con acceso basado en búsqueda


Utilizando las estructuras de datos que ya conocemos, podemos plantear di-
versas implementaciones para el TAD TABLA como colecciones de parejas
(Clave, Valor), donde el acceso por clave se implementa como una búsqueda:

— Vectores de parejas (clave, valor), desordenados u ordenados por clave.


Operación Vector desordenado Vector ordenado
Nuevo
Inserta
esVacio
está
consulta
borra

O(1)
O(n) / O(1) **
O(1)
O(n)
O(n)
O(n)

O(1)
O(n)
O(1)
O(log n)
O(log n)
O(n)



— Secuencias de parejas (clave, valor) implementadas con memoria dinámica,

desordenadas u ordenadas por clave.



Operación
Nuevo
Inserta
esVacio
está
consulta
borra

Secuencia desordenada Secuencia ordenada
O(1)
O(n) / O(1) **
O(1)
O(n)
O(n)
O(n)

O(1)
O(n)
O(1)
O(n)
O(n)
O(n)


** La complejidad de la inserción en un secuencia o vector desordenado es
O(n) si no permitimos claves repetidas y O(1) si las permitimos, con el con-
siguiente desaprovechamiento de espacio y haciendo necesario que las bús-
quedas tengan en cuenta esta circunstancia. En el caso de las secuencias
ordenadas la complejidad de la búsqueda mejora en el caso promedio, aun-
que no así en el caso peor.



Tablas



4

— Arboles de búsqueda. Suponiendo árboles equilibrados (un árbol con n no-

dos se dice equilibrado si su talla es de orden log n) se puede conseguir:



Operación Arbol de búsqueda
Nuevo
Inserta
esVacio
está
consulta
borra

O(1)
O(log n)
O(1)
O(log n)
O(log n)
O(log n)

En este tema vamos a estudiar una nueva estructura de datos, las tablas disper-
sas, que en promedio permiten conseguir un coste constante para todas las
operaciones sobre las tablas.



Tablas



5

6.3 Implementación con acceso casi directo: tablas

dispersas

En este apartado estudiamos técnicas que permiten realizar todas las operacio-
nes en tiempo O(1) en promedio, aunque en el caso peor Inserta, está, consulta y
borra son O(n).


La idea es conseguir que las tablas se comporten como vectores, tratando las
claves como índices. Esta idea no puede aplicarse directamente cuando el con-
junto de todas las claves posibles sea demasiado grande. Por ejemplo, si las
claves son cadenas de caracteres con un máximo de 8 caracteres elegidos de un
conjunto de 52 caracteres, habría un total de


En una aplicación práctica, la cantidad de cadenas que lleguen a usarse como
claves será mucho menor, y es absolutamente impensable reservar un vector
de tamaño L para implementar la tabla.


L = Σ i : 1 ≤ i ≤ 8 : 52 i

Una idea alternativa son las tablas dispersas (en inglés, hash table). La tabla se re-

Array[0..N–1] of Pareja[Clave, Valor]

presenta como un vector de tipo


siendo N suficientemente grande, aunque mucho menor que el número total
de claves posibles, y donde lo que se pretende es que dada una clave sea casi di-
recto determinar en qué posición del vector se debe encontrar.


Una característica interesante de un valor concreto de una tabla dispersa es su
tasa de ocupación, definida como el cociente entre el número n de parejas (Clave,
Valor) almacenadas en la tabla, y el número total N de posiciones del vector:


En algunas implementaciones de las tablas dispersas, la tasa de ocupación pue-
de llegar a ser mayor que 1.

α = n/N



Tablas



6

Función de localización
Para operar con la tabla se necesitará interponer una función que asocie a cada

clave un índice del vector:

h : Clave → [0..N–1]
Dada una clave c, el índice h(c) es la posición del vector en la que en un princi-
pio intentaremos localizar la clave. La función h que usemos para esto se llama-
rá función de localización (en inglés, hashing function).


Al elegir una función de localización se debe buscar

— Eficiencia. El coste de calcular h(c) para una clave c dada debe ser bajo.
— Uniformidad. El reparto de claves entre posiciones debe ser lo más uni-
forme posible. Idealmente, para una clave c elegida al azar la probabilidad
de que h(c) = i debe valer 1/N para cada i ∈ [0..N–1]. Una función de loca-
lización que cumpla esta condición se llama uniforme.

Gráficamente, la situación es:



0
1

N-1

…

Clave

h

[0..N-1]

Por ejemplo, supongamos que N = 16 y que las claves son cadenas de caracte-

h(c) =def ord(ult(c)) mod 16

res. Una posible función de localización es la definida como:


donde ult(c) es el último carácter de c, y ord es la función que devuelve el código
ASCII de un carácter. Usando esta función de localización, obtenemos:


h(“Fred”) = ord(‘d’) mod 16 = 100 mod 16 = 4
h(“Joe”) = ord(‘e’) mod 16 = 101 mod 16 = 5
h(“John”) = ord(‘n’) mod 16 = 110 mod 16 = 14



Tablas



7

c ≠ c’ ∧ h(c) = h(c’)

Colisiones
Como hemos visto, el dominio de una función de localización siempre suele
tener un cardinal mucho mayor que su rango. Por lo tanto, una función de lo-
calización h no puede ser inyectiva.
Cuando se encuentran claves c, c’ tales que:


se dice que se ha producido una colisión. Se dice también que c y c’ son claves si-
nónimas con respecto a h.



las cuatro cadenas colisionan en el índice 4 y son sinónimas con respecto a h.


h(“Fred”) = h(“David”) = h(“Violet”) = h(“Roland”) = 4

Por ejemplo, para la anterior función de colisión:

Tablas dispersas
Se llaman así a las tablas implementadas de manera que:


— La representación concreta de una tabla es un vector t : Array [0..N–1] of

Pareja[Clave, Valor]

Las distintas implementaciones de tablas dispersas se diferencian en dos cosas:

— Se utiliza una función de localización para el paso de claves a índices.


— El método elegido para el tratamiento de colisiones.
— La función de localización elegida.


Vamos a centrarnos primero en estudiar la primera de las características, supo-
niendo fijada una función de localización h, y estudiaremos la segunda caracte-
rística más adelante.
Según la técnica que se utilice para el tratamiento de las colisiones, hablamos
de:

—

tablas dispersas abier