Tablas de Dispersión

(Hashing Tables)

Dispersión abierta

La dispersión abierta, también llamada encadenamiento separado, consiste en tener una lista de los elementos que se dispersan en el mismo valor de la tabla. Suponiendo una tabla de tamaño 10 de números enteros y con la función de dispersión: dispersión(x) = x MOD 10, nos quedaría una tabla de dispersión abierta como la de la figura:

Las declaraciones de los tipos necesarios para la dispersión abierta son:

  TYPE
    posicion =POINTER TO nodo;
    nodo = RECORD
            elem : TipoElemento;
            sig : posicion;
           END;
    TablaDisp = ARRAY INDICE OF posicion;

Inicialización de la tabla

Primero debemos inicializar la tabla, asignando a cada celda el valor NIL:

  PROCEDURE IniciaTabla (VAR D: TablaDisp);
  VAR
    i : integer;
  BEGIN
    FOR i:=0 TO MAX_T-1 DO
      D[i]:= NIL;
  END;

Búsqueda en la tabla

Para efectuar una búsqueda en una tabla, primero usamos la función de dispersión para determinar la lista a recorrer. Seguidamente, se recorre la lista hasta encontrar la llave y se devuelve un puntero a la posición de la celda que contiene la llave.

  FUNCTION Buscar (llave: TipoElemento; D: TablaDisp): posicion;
  VAR
    res, p: posicion;
  BEGIN
    p := D[hashing(llave)];
    res:= NIL;
    WHILE p <> NIL DO
      IF p^.elemento = llave THEN BEGIN
        res:= p; BREAK;
      END;
      p := p^.sig;
    END;
    Buscar:= res;
  END;

Inserción en la tabla

Para insertar un elemento en una tabla, primero buscamos en la lista que le corresponde para ver si ya está insertado; si es nuevo, se inserta al principio de la lista:

  PROCEDURE Insertar (llave:TipoElemento; VAR D: TablaDisp);
  VAR
    h: INTEGER;
    pos, lista : posicion;
    nuevo : posicion;
  BEGIN
    pos := Buscar (llave, D);
    IF pos = NIL THEN BEGIN (* no encontrado *)
      h:= hashing(llave);
      NEW (nuevo);
      nuevo^.elem := llave;
      nuevo^.sig := D[h];
      D[h]:= nuevo;
    END;
  END;

Factor de carga

Llamamos factor de carga de una tabla de dispersión , l, al cociente entre el número de elementos en la tabla y el tamaño de la misma:

La longitud media de una lista es l. El tiempo que se tarda en realizar una búsqueda será el tiempo en que se calcula la función de dispersión más el tiempo necesario para recorrer la lista. Si la búsqueda es infructuosa, el número medio de enlaces por recorrer es l. Si la búsqueda tiene éxito los enlaces por recorrer son, por término medio, 1 + l /2.
De esto se deduce que el factor de carga es importante a la hora de diseñar una tabla. En el caso de la dispersión abierta la regla general es que l tienda a 1 (es decir, el tamaño de la tabla igual a los elementos esperados).
Tampoco debemos olvidar que el tamaño de la tabla debe ser primo.

Tema anterior

Tema Siguiente