Puntos Extra- 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 (

Planteamiento inicial

La estructura de datos ideal para la tabla de dispersión es un arreglo de tamañ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 llama función de dispersión.

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

El tamaño de 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.

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 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á valores entre 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.

 tabla de dispersión.)

Tablas de Dispersión

(Hashing Tables)