Hora: Jueves V1
Hola a todos, aquí les dejo mi entrada sobre Tablas de Dispersión :)
Las tablas de dispersión o también llamadas hashing tables son una técnica que se utiliza para realizar inserciones, eliminaciones y búsquedas en un tiempo constante.
La estructura de datos ideal para la tabla de dispersión es un arreglo de tamaño fijo que contiene una clave que son los elementos de tabla, una clave es una cadena de caracteres con un valor asociado. Por ejemplo: 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 asignará un número entre 0 y MAX_T-1 y se colocará en la celda que le corresponde.
La relación entre la llave y la posición en la tabla es lo que se llama función de dispersión.
La función de las tablas de dispersión es la correspondencia entre la clave y un índice del arreglo.
Cuando las claves son números enteros la función de dispersión toma la forma:
h(x) = clave MOD MAX_T
Existen 2 tipos de dispersiones, la dispersión abierta y cerrada, las cuales se utilizan para solucionar colisiones, que es cuando dos elementos distintos toman el mismo valor.
*Dispersión abierta
Es también llamada encadenamiento separado y consiste en tener una lista de los elementos que se dispersan en el mismo valor de la tabla. Por ejemplo si tenemos 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 de la siguiente manera:
Por ejemplo las declaraciones para esta dispersión abierta quedarian de la siguiente manera:
TYPEPROCEDURE IniciaTabla (VAR D: TablaDisp);
posicion =POINTER TO nodo;
nodo = RECORD
elem : TipoElemento;
sig : posicion;
END;
TablaDisp = ARRAY INDICE OF posicion;
Primero debemos iniciar la tabla asignando a cada celda el valor NILL:
VAR
i : integer;
BEGIN
FOR i:=0 TO MAX_T-1 DO
D[i]:= NIL;
END;
Para realizar una búsqueda en una tabla, primero se utiliza la función de dispersión para determinar la lista a recorrer. Y ya cuando se recorre la lista hasta encontrar la clave y se devuelve un puntero a la posición de la celda que contiene la clave.
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;
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;
Se le llama factor de carga de una tabla de dispersión, λ, a la razón entre el número de elementos en la tabla y el tamaño de la misma:
La longitud media de una lista es λ. El tiempo que se tarda en realizar una búsqueda será el tiempo en que se cálcula 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 λ, pero si la búsqueda tiene éxito los enlaces por recorrer son, por término medio, 1 + λ /2.
No debemos olvidar que el tamaño de la tabla debe ser
*Dispersión cerrada
La dispersión cerrada o direccionamiento abierto, soluciona las colisiones buscando celdas alternativas hasta encontrar una vacía.
Se va buscando en las celdas: d0(x), d1(x), d2(x), ..., donde
di(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:
f(i)= { 0 si i=0
< >0 si i<>0
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. En este ejemplo, la primera colisión ocurre cuando queremos insertar el 49. Como la celda 9 está ocupada se pone en la siguiente 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.
Algunas de 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. Para inserciones y búsquedas no exitosas el número de intentos aproximado sería: 1/2(1 + 1/(1 - λ)2). Mientras que para búsquedas exitosas sería: 1/2(1 + 1/(1 - λ)), un número menor que el anterior.
Exploración cuadrática
Este método elimina el problema del agrupamiento primario, la función de colisiones cuadrática:
f(i) = i2.
En este caso, cuando el 49 entra en colisión con el 89, la siguiente posición es la celda siguiente
(f(1) = 12 = 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á ( 22 = 4), y como está libre se coloca en ella (en la celda 2). Con el 69 ocurre lo mismo.
Con este tipo de método no hay garantía de encontrar una celda vacía si la tabla se llena a más de la mitad, o si el tamaño de la tabla no es primo.
Aunque la exploración cuadrática elimina el agrupamiento primario, se produce otro fenómeno llamado agrupamiento secundario, ya que las claves que se dispersan a la misma posición intentarán las mismas celdas.
_
*Dispersión doble
La función para la dispersión doble es: f (i) = i * h2 (x). Lo que se hace es aplicar una segunda función de dispersión a x, y luego se prueba a distancias h2(x), 2h2(x), ...
Es muy importante la buena elección de h2(x) y, además, nunca debe ser cero. Si elegimos la función:
h2(x) = R - (x MOD R) con R un número primo menor que MAX_T, funcionará bien.
La siguiente tabla aparece como quedaría la dispersión cerrada con dispersión doble y cuando insertamos las mismas claves que en los ejemplos anteriores y para R = 7.
En este caso la primera colisión ocurre al insertar el 49; calculando la función de dispersión nos quedaría: h2(49) = 7 - (49 MOD7), que es igual a: h2(49) = 7 - 0 = 7; luego el 49 se insertará en la posición 6. La segunda colisión ocurrirá al insertar el 58, la función será: h2(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: h2(69) = 7 - 6 = 1, por lo que la celda resultante es la cero.
Las declaraciones de los tipos para implantar la dispersión cerrada son las siguientes:
TYPE
ClaseEntrada = (legal, vacia, eliminada);
Entrada_disp = RECORD
elem : TipoElemento;
info : ClaseEntrada;
END;
posicion = INDICE;
TablaDisp = ARRAY [INDICE] OF Entrada_disp;
La puesta a valores iniciales de la tabla se realiza poniendo el campo info a vacío.
PROCEDURE IniciarTabla (VAR D: TablaDisp);
VAR
i: integer;
BEGIN
FOR i:=0 TO MAX_T-1 DO
D[i].info := vacia;
END;
La búsqueda para dispersión cerrada con exploración cuadrática devolverá la posición de la llave en la tabla de dispersión. Si no se encuentra, devuelve la celda donde estaría insertada la llave, que estará marcada como vacía. Y quedaría algo asi :
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;
Aquí se utiliza la forma rápida de hacer la resolución cuadrática. Siendo la definición de la función cuadrática: f(i) = f(i-1) + 2i - 1, se deduce que se puede implementar con una multiplicación por dos y un decremento. Si la posición resultante se sale del array, se le resta el tamaño de la tabla.
Por otro lado, es trivial modificar esta función para que reaproveche huecos eliminados en caso de no encontrar el elemento:
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;
En el caso de la inserción de tablas en la dispersión cerrada, cuando la clave está ya en la tabla no se hace nada; si no, se coloca en la posición que resulte de la rutina buscar:
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;
Bueno está fue mi entrada sobre Tablas de Dispersión, espero les sea útil cualquier comentario hagánmelo saber. Saludos :) primo.
Muy bien. Ocho puntos para el lab.
ResponderEliminar