TABLAS HASH
Definiciones
Tabla
Una tabla es un diccionario serial o indexado.
Si, para acceder a las distintas posiciones de la tabla se define una función de cálculo de índices,
entonces aquella se denomina tabla hash.
Hash
Cuando el proceso de búsqueda de una llave en una tabla se reduce a un único acceso, entonces la
posición del registro al interior de la tabla depende sólo de la llave.
Luego, para insertar un elemento en la tabla se debe disponer de una función de transformación de
la llave.
Formalmente, hash significa particionar un conjunto U en un número m de clases de modo que, cada
clase se almacene en una tabla indexada desde 0 a m-1.
Para determinar la clase de un elemento, se define una función hash
h : U {0, 1, …, m-1}
x h(x)
donde h(x) se usa para referenciar la tabla, es decir, si T es una tabla hash, entonces un elemento x
se debe insertar en T[h(x)].
Si card(U) m, entonces siempre es posible encontrar una función h tal que h(x1) h(x2), x1 x2.
En cambio, si card(U) m, entonces x1 x2 tal que h(x1) = h(x2). Este fenómeno se denomina colisión
y x1, x2 reciben el nombre de sinónimos.
El tratamiento de las colisiones da origen a dos tipos de hash.
Hash Abierto
Este método consiste en representar una tabla T mediante un arreglo de punteros a listas de enlace
simple de modo que, cada lista contenga todos los sinónimos.
Cada clase, es decir, T[h(x)] se denomina bucket.
Si h(x) se aproxima a una distribución uniforme entonces, para un total de n elementos, existirá un
promedio de n/m en cada bucket.
La más simple e ilustrativa función hash es una función modular de la forma
h(x) = x mod m
donde se recomienda que m sea un número primo.
Tabla
Hash
Abierto
U 0
2
4 8 0 2
3
Función
6 4
hash
1 5
Llaves en 3
la Tabla 6
5 7
7
8
9
9
1
Representación en Pascal
const M = 100;
Vacio = Nil;
type Base = integer;
Clave = integer;
Elemento = record
key : Clave;
info : Base;
end;
Lista = ^Nodo;
Nodo = record
key : Clave;
info : Base;
link : Lista;
end;
Tabla = array[0..M-1 of Lista;
Implementación en Pascal
function h(k : Clave) : integer;
begin
h := k mod M;
end;
procedure Crear(var T : Tabla);
var i : integer;
begin
for i := 0 to M-1 do
T[i := Vacio;
end;
function Buscar(T : Tabla; k : Clave) : Lista;
begin
Buscar := LBuscar(T[h(k),k);
end;
function Existe(T : Tabla; k : Clave) : boolean;
begin
Existe := Buscar(T,k) <> Vacio;
end;
function LBuscar(L : Lista; k : Clave) : Lista;
begin
if L = Vacio then
LBuscar := Vacio
else
if k = L^.key then
LBuscar := L
else
LBuscar := LBuscar(L^.link,k);
end;
procedure Insertar(var T : Tabla; e : Elemento);
begin
LInsertar(T[h(e.key),e);
end;
procedure LInsertar(var L : Lista; e : Elemento);
2
begin
if L = Vacio then
begin
new(L);
L^.key := e.key;
L^.info := e.info;
L^.link := Vacio;
end
else
if e.key <> L^.key then
LInsertar(L^.link,e);
end;
procedure Eliminar(var T : Tabla; k : Clave);
begin
LEliminar(T[h(k),k);
end;
procedure LEliminar(var L : Lista; k : Clave);
var p : Lista;
begin
if L <> Vacio then
if k = L^.key then
begin
p := L;
L := L^.link;
dispose(p);
end
else
LEliminar(L^.link,k);
end;
Hash Cerrado
Este método consiste en almacenar los registros en la misma tabla y utilizar la estrategia conocida
como "rehash" para resolver el problema de las colisiones. Si, al tratar de insertar un registro en la
posición h(x) se produce una colisión, entonces mediante rehash es posible generar una secuencia
de posiciones alternativas h1(x), h2(x), …, hasta encontrar una libre en la tabla.
Existen variadas funciones rehash, sin embargo, la más común es la cocida como rehash lineal, cuya
expresión es
hi(x) = (h(x) + i) mod m
O bien, en forma recurrente
hi+1(x) = (hi(x) + 1) mod m
h0(x) = h(x)
3
Tabla
Hash
Cerrado
U 0
K5 K0
2
K4 K8
K2 3
Función
K6 hash 4
K1
5
Llaves en
la Tabla 6
K3 7
8
K9
9
Representación en Pascal
const M = 100;
Vacio = <valor1>;
Libre = <valor2>;
type Base = integer;
Clave = integer;
Elemento = record
key : Clave;
info : Base;
end;
Tabla = array[0..M-1 of Elemento;
"Libre" significa ubicación disponible para insertar pero no en calidad de "Vacio", pues pertenece a
una secuencia de elementos en colisión.
Implementación en Pascal
function h(k : Clave) : integer;
begin
h := k mod M;
end;
procedure Crear(var T : Tabla);
var i : integer;
begin
for i := 0 to M-1 do
T[i.key := Vacio;
end;
function Buscar(T : Tabla; k : Clave) : integer;
var i, j : integer;
distinto, ocupada, revisando : boolean;
begin
i := h(k);
j := i;
distinto := k <> T[j.key;
4
ocupada := T[j.key <> Vacio;
revisando := true;
while distinto and ocupada and revisando do
begin
j := (j+1) mod M;
distinto := k <> T[j.key;
ocupada := T[j.key <> Vacio;
revisando := j <> i;
end;
if not distinto then
Buscar := j
else
Buscar := M;
end;
function Existe(T : Tabla; k : Clave) : boolean;
begin
Existe := Buscar(T,k) <> M;
end;
procedure Insertar(var T : Tabla; e : Elemento);
var i, j : integer;
distinto, ocupada, revisando : boolean;
begin
i := h(k);
j := i;
distinto := k <> T[j.key;
ocupada := (T[j.key <> Vacio) and (T[j.key <> Libre);
revisando := true;
while distinto and ocupada and revisando do
begin
j := (j+1) mod M;
distinto := k <> T[j.key;
ocupada := (T[j.key <> Vacio) and (T[j.key <> Libre);
revisando := j <> i;
end;
if distinto and not ocupada then
T[j := e;
end;
procedure Eliminar(var T : Tabla; k : Clave);
var j : integer;
begin
j := Buscar(T,k);
if j <> M then
T[j.key := Libre;
end;
