Tablas de Dispersión

(Hashing Tables)

Las tablas de dispersión o hashing tables (en inglés) es una técnica que se utiliza para implementar inserciones, eliminaciones y búsquedas en un tiempo medio constante.
La estructura de datos central de esta técnica es la tabla de dispersión.

Planteamiento inicial

La estructura de datos ideal para la tabla de dispersión es un array de tamaño fijo que contiene las llaves (elementos de la tabla). Una llave suele ser una cadena de caracteres (o de números) con un valor asociado Si el tamaño de la tabla es MAX_T, la tabla se declara entre 0 y MAX_T-1. A cada llave se le hará corresponder un número entre 0 y MAX_T-1 y se colocará en la celda correspondiente.
La relación entre la llave y la posición en la tabla es lo que se llama función de dispersión.
En la figura siguiente se muestra cómo sería una tabla de dispersión ideal (cada llave cae en una celda distinta).

0
1
2	Ana
3
4	Juan
5	Eva
6
7	Felipe
8
9

Función de Dispersión

Es la correspondencia entre la llave y un índice del array. Por lo general, cuando las llaves son números enteros la función de dispersión toma la forma:

h(x) = llave MOD MAX_T

El tamaño de la tabla debe ser primo. De esta forma, y si las llaves son números aleatorios, esta función suele distribuir las llaves uniformemente. Si tuviéramos la tabla de la figura anterior (MAX_T =10), y todas las llaves terminaran en cero, la dispersión con esta función no nos valdría.
Cuando las llaves son cadenas de caracteres lo usual es sumar los valores ASCII de los caracteres de la cadena.

A continuación se declaran los tipos apropiados para la tabla de dispersión y el índice, que es el que devuelve la función de dispersión.

  TYPE
    INDICE = 0 .. MAX_T - 1;
    TablaDisp= ARRAY INDICE OF ...

Una implementación sencilla de la función de dispersión sería la siguiente:

  FUNCTION hashing (llave: TipoCadena): INDICE;
  VAR
    aux, j: integer;
  BEGIN
    aux := ord (llave[1]);
    FOR j:=2 TO Length (llave) DO
      aux := aux + ord (llave[j]);
    hashing := aux MOD MAX_T;
  END;

El problema de esta función es que, si la tabla es grande, no hace una distribución uniforme de las llaves. Pongamos un ejemplo: tenemos una tabla con un tamaño MAX_T= 10007 (primo) y las llaves tienen una longitud máxima de ocho caracteres; como ord devuelve un número entero de valor máximo 127, la función de dispersión sólo tendrá valores entre 0 y 1016 (127*8). Luego la distribución no es equitativa.

Otra función de dispersión que da mejores resultados es la Regla de Horner:

  FUNCTION hashing (llave: TipoCadena): INDICE;
  VAR
    aux, j: integer;
  BEGIN
    aux := ord (llave[1]);
    FOR j:=2 TO Length (llave) DO
      aux := (aux*32 + ord (llave[j])) MOD MAX_T;
    hashing := aux;
  END;

La Regla de Horner calcula una función polinómica de la forma:

(En este caso se escoge 32 porque así se realiza un desplazamiento de 5 bits).
De esta fución se puede esperar una mejor distribución que la anterior, pues cadenas con las misma letras pero en diferente orden dar&aacuta;n diferente resultado. Un factor negativo es la operación MOD que se hace en cada iteración, para evitar el desbordamiento, y que hace el cálculo más costoso.

Seguidamente vamos a tratar el tema de las colisiones. Esto ocurre cuando dos elementos distintos se dispersan en el mismo valor. Para solucionar las colisiones veremos dos métodos: la dispersión abierta y la dispersión cerrada.

Siguiente tema