Tablas de Dispersión
(Hashing)
Redispersión
Cuando la tabla está muy llena, el tiempo en que se
ejecutan las operaciones aumenta bastante; además el intento de insertar
elementos puede fallar en la dispersión cerrada con resolución cuadrática.
Una solución es la redispersión, que consiste en construir otra tabla
de aproximadamente el doble del tamaño de la anterior, con una función de
dispersión asociada, y recorrer la tabla de dispersión original, calculando la
nueva posición de cada elemento e insertándolo en la nueva tabla. Lo veremos con
un ejemplo:
Tenemos una tabla de dispersión cerrada de tamaño 7, con
una función de dispersión: h(x) = x MOD 7, y usamos la exploración lineal
para las colisiones. Si insertamos los elementos: 13, 15, 24, 6 y 23, la tabla
resultante será:
Como la
tabla está tan llena, creamos una nueva. El tamaño de ésta será el nömero primo
más cercano al doble del tamaño de la tabla original, en este caso 17. Luego la
nueva función de dispersión será: h(x) = x MOD 17.
Recorremos la
tabla anterior y vamos insertando los elementos 6, 15, 23, 24 y 13 en la tabla
nueva. La nueva tabla de dispersión cerrada después de la redispersión es la
siguiente:
| 0 |
| 1 |
| 2 |
| 3 |
| 4 |
| 5 |
| 6 |
| 7 |
| 8 |
| 9 |
| 10 |
| 11 |
| 12 |
| 13 |
| 14 |
| 15 |
| 16 | |
|
El mayor inconveniente de este método es que es muy costoso y, a veces,
lento. Existen varias estrategias a la hora de implantar la redispersión:
redisperar cuando la tabla se llene a la mitad (l=0.5);
redispersar cuando falla una inserción o redispersar cuando la tabla llega a un
factor de carga determinado. La tercera estrategia es la más conveniente (si se
elige un buen umbral de corte), ya que el rendimiento disminuye al aumentar el
factor de carga.
La ventaja es que libera al programador de ocuparse del
tamaño de la tabla.
La redispersión se puede hacer en lenguajes como Ada y
C, pero no en lengujes como PASCAL, MODULA,...
Tema
anterior 