Tablas de Dispersión

(Hashing)

Dispersión cerrada

La dispersión cerrada o direccionamiento abierto, soluciona las colisiones buscando celdas alternativas hasta encontrar una vacía (dentro de la misma tabla).
Se va buscando en las celdas: d₀(x), d₁(x), d₂(x), ..., donde d_i(x) = (hashing(x) + f(i)) MOD MAX_T.
La función f( ) es la estrategia de resolución de las colisiones, y se debe cumplir que:

Al estar todos los datos en la misma tabla, se necesita que la ésta sea más grande; el factor de carga tiene que ser menor o igual a 0.5.
Dentro de la dispersión cerrada hay tres estrategias distintas: la exploración lineal, la exploración cuadrática y la dispersión doble.
 

Exploración lineal

En este tipo de estrategia la función f() es una función lineal de i, por ejemplo:  f(i) = i. Esto significa que las celdas se recorren en secuencia buscando una celda vacía; es decir, si hay una colisión se prueba en la celda siguiente y así sucesivamente hasta encontrar una vacía.
Lo veremos en un ejemplo: tenemos una tabla con MAX_T = 10 y la función de dispersión h(x)= x MOD 10.
(Se recuerda que MAX_T debe ser primo, aquí se ultiliza 10 por sencillez de cálculo, pero sería un grave error encontrarlo en un código real.)
En este ejemplo, que es el de la figura de abajo, la primera colisión ocurre cuando queremos insertar el 49. Como la celda 9 está ocupada se pone en la siguienta celda desocupada. Cuando el 58 entra en colisión con el 18 va a la siguiente celda y entra en colisión con el 89, y después con el 49 antes de encontrar su posición. Con el 69 pasa algo parecido.

	Tabla vacía	Después de 89	Después de 18	Después de 49	Después de 58	Después de 69
0				49	49	49
1					58	58
2						69
3
4
5
6
7
8			18	18	18	18
9		89	89	89	89	89

Las desventajas que tiene este método son: el tiempo que se tarda en encontrar una celda vacía y la formación de bloques de celdas ocupadas, llamada efecto agrupamiento primario. A causa de este efecto, cualquier llave que se disperse en un agrupamiento realizará varios intentos para resolver la colisión, y agrandará el agrupamiento.
Para inserciones y búsquedas no exitosas el número de intentos aproximado sería: 1/2(1 + 1/(1 - l)²). Para búsquedas exitosas sería: 1/2(1 + 1/(1 - l)), un número menor que el anterior.

Exploración cuadrática

	Tabla vacía	Después de 89	Después de 18	Después de 49	Después de 58	Después de 69
0				49	49	49
1
2					58	58
3						69
4
5
6
7
8			18	18	18	18
9		89	89	89	89	89

En este caso, cuando el 49 entra en colisión con el 89, la siguiente posición es la celda siguiente (f(1) = 1² = 1). Después, cuando el 58 entra en colisión también intenta la celda siguiente, pero está ocupada. En su segunda colisión, el 58 intenta la celda que está 4 posiciones más allá ( 2² = 4), y como está libre se coloca en ella (en la celda 2). Con el 69 ocurre lo  mismo.
En este tipo de exploración no hay garantía de encontrar una celda vacía si la tabla se llena a más de la mitad, o antes si el tamaño de la tabla no es primo. Existe un Teorema que dice:

        Si se usa la exploración cuadrática, y el tamaño de la tabla es primo, entonces siempre se puede insertar un elemento nuevo si la tabla está, al menos, medio vacía.

Aunque la exploración cuadrática elimina el agrupamiento primario, se produce otro fenómeno llamado agrupamiento secundario, ya que las llaves que se dispersan a la misma posición intenterán las mismas celdas.

Dispersión doble

	Tabla vacía	Después de 89	Después de 18	Después de 49	Después de 58	Después de 69
0						69
1
2
3					58	58
4
5
6				49	49	49
7
8			18	18	18	18
9		89	89	89	89	89

La primera colisión ocurre al insertar el 49; calculando la función de dispersión nos quedaría: h₂(49) = 7 - (49 MOD7), que es igual a: h₂(49) = 7 - 0 = 7; luego el 49 se insertará en la posición 6. En la segunda colisión, al insertar el 58, la función será: h₂(58) = 7 - 2 = 5, por lo tanto el 58 se colocará en la posición 3. Finalmente intentamos insertar el 69, que con la función de dispersión iría en la posición: h₂(69) = 7 - 6 = 1, por lo que la celda resultante es la cero.
Aunque en el ejemplo el tamaño de la tabla no es  primo, por hacer más fáciles los cálculos, sería conveniente que fuera primo siempre. De esta manera hay más posiciones alternativas que cuando no es primo.
La conclusión es que con la dispersión doble se consiguen buenos resultados, aunque es más compleja y, por lo tanto, más lenta que otras soluciones (como la exploración cuadrática).

Declaraciones de tipos

  TYPE
    ClaseEntrada = (legal, vacia, eliminada);
    Entrada_disp = RECORD
                     elem : TipoElemento;
                     info : ClaseEntrada;
                   END;
    posicion = INDICE;
    TablaDisp = ARRAY [INDICE] OF Entrada_disp;

Inicialización de la tabla

  PROCEDURE IniciarTabla (VAR D: TablaDisp);
  VAR
    i: integer;
  BEGIN
    FOR i:=0 TO MAX_T-1 DO
      D[i].info := vacia;
  END;

Búsqueda para dispersión cerrada con exploración cuadrática

  FUNCTION Buscar (llave: TipoElemento; D:TablaDisp): INDICE;
  VAR
    i, pos : posicion;
  BEGIN
    i := 0;
    pos := hashing (llave);
    WHILE D[pos].info <> vacia DO BEGIN
      IF D[pos].elem = llave THEN (* encontrado *)
	BREAK;
      END;
      INC (i);
      pos := (pos + 2 * i - 1);
      IF pos > MAX_T THEN
	pos := pos - MAX_T;
    END;
    Buscar:= pos;
  END;

  FUNCTION BuscarMejor (llave: TipoElemento; D:TablaDisp): INDICE;
  VAR
    i, pos, hueco : posicion;
  BEGIN
    i := 0;
    hueco := -1; (* todavia no hay hueco *)
    pos := hashing (llave);
    WHILE D[pos].info <> vacia DO BEGIN
      IF D[pos].info = eliminada THEN BEGIN (* hay hueco *)
	hueco := pos; (* no acabamos porque quizá "llave" este más adelante *)
      END;
      IF D[pos].elem = llave THEN (* encontrado *)
	BREAK;
      END;
      INC (i);
      pos := (pos + 2 * i - 1);
      IF pos > MAX_T THEN
	pos := pos - MAX_T;
    END;
    Buscar:= pos;
  END;

Inserción en tablas de dispersión cerrada

  PROCEDURE Insertar (llave: TipoElemento; VAR D: TablaDisp);
  VAR
    p; pos: INDICE;
  BEGIN
    pos := Buscar (llave, D);
    IF D[pos].info <> legal THEN BEGIN (* celda apropiada para insertar *)
      D[pos].elem := llave;
      D[pos].info := legal;
    END;
  END;

Tema anterior

Tema siguiente