Tablas de dispersion

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 hashing (tabla de dispersión.) Planteamiento inicial La estructura de datos ideal para la tabla de dispersión es un arreglo detamaño fijo que contiene las claves (elementos de la tabla). Una clave 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 clave 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 llamafunció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 3 4 5 6 7 8 9 Función Hash (o de Dispersión) Es la correspondencia entre la clave y un índice del arreglo. Por lo general, cuando las claves son números enteros la función de dispersión toma la forma: h(x) = clave MOD MAX_T Felipe Juan Eva Ana

1

El tamañode la tabla debe ser primo. De esta forma, y si las claves son números aleatorios, esta función suele distribuir las claves uniformemente. Si tuviéramos la tabla de la figura anterior (MAX_T =10), y todas las claves terminaran en cero, la dispersión con esta función no nos valdría. Cuando las claves son cadenas de caracteres lo usual es sumar los valores ASCII de los caracteres de la cadena. Acontinuació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 claves. Pongamos un ejemplo: tenemos una tabla con un tamaño MAX_T= 10007 (primo) y las claves 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á valoresentre 0 y 1016 (127*8). Luego la distribución no es equitativa A continuaciòn vamos a tratar el tema de las colisiones. Esto ocurre cuando dos elementos distintos toman el mismo valor. Para solucionar las colisiones veremos dos métodos: la dispersión abierta y la dispersión cerrada. Dispersión abierta La dispersión abierta, también llamada encadenamiento separado, consiste en tener una lista delos 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:

2

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 clave y se devuelve un puntero a la posición de la celda que contiene la clave.

3

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...