hashing

1

Capítulo 7

Tablas de hash.
7.1. Operaciones.
La tabla de hash pertenece a la categoría de diccionarios que son aquellas estructuras de datos y
algoritmos que permiten buscar, insertar y descartar elementos.
Si las operaciones se reducen solamente a buscar e insertar se llaman tablas de símbolos.
En diccionarios puros sólo se implementa buscar.
Los diccionarios y tablas pertenecentambién a la categoría de conjuntos dinámicos.

7.2. Clave.
La información que se desea buscar suele ser una estructura que organiza la información. Uno
de los campos de esa estructura se denomina clave, y debe ser única. Sólo una de las estructuras
puede tener un determinado valor de la clave.
Si la clave es un string, deben definirse operadores de comparación, los cuales generalmentecomparan en forma alfabética.

7.3. Tabla de acceso directo.
Un arreglo es una estructura de datos que permite implementar tablas de acceso directo. Es este
caso la clave es el índice del arreglo, y existe una posición del arreglo para cada posible clave.
Si el contenido de una celda del arreglo es un puntero a la estructura con los datos asociados a la
clave, se puede implementar las operacionesen forma sencilla. Si el elemento asociado a una
clave no está presente se lo indica con un puntero de valor NULL.

Índice

Tabla
Estructura 0

0
1
2
3
4

Estructura 2
Estructura 4
Figura 7.1 Tabla de acceso directo.

Profesor Leopoldo Silva Bijit

11-06-2008

2

Estructuras de Datos y Algoritmos

pnodo buscar(int clave)
{
return (Tabla[clave]);
}
int insertar(intclave, pnodo pestructura)
{
if (Tabla[clave] == NULL ) Tabla[clave]=pestructura; return 0;
else return (1); // error: ya estaba.
}
int descartar(int clave)
{
if (Tabla[clave]!= NULL ) {free(Tabla[clave]); Tabla[clave]= NULL ; return 0;}
else return (1); //error: no estaba.
}
Todas las operaciones son O(1).
Para emplear esta solución el tamaño del arreglo, debe ser igual al número declaves posibles y
éstas deben estar entre 0 y N-1.

7.4. Tablas de Hash.
Si el número de claves almacenadas en la tabla es pequeño en comparación con el número total
de claves posibles, la estructura tabla de hash resulta una forma eficiente de implementación.
Ejemplos:
Claves alfanuméricas: Con las letras del abecedario se pueden escribir un gran número de
palabras, pero el número de palabrasempleadas como identificadores por un programador es
muchísimo menor; y se desea almacenar los identificadores del programador solamente.
Claves enteras: el número de RUTs posibles asciende a varios millones, pero el número de
RUTs de los alumnos de una carrera no sobrepasa los mil; y se desea almacenar solamente los
alumnos de una carrera.
Las tablas de hash se implementan basadas en unarreglo cuyo tamaño debe ser proporcional al
número de claves almacenadas en la tabla.

7.5. Función de hash.
Lo fundamental del método es encontrar una función que a partir de la clave (proveniente de un
universo de N claves posibles), sea ésta numérica o alfanumérica, encuentre un entero sin signo
entre 0 y B-1, si la tabla de hash está formada por B elementos. Con N>> B.
La función de hashmuele o desmenuza o hace un picadillo con la clave, de allí el nombre; que
es el significado de la palabra inglesa hash (no es un apellido).

Profesor Leopoldo Silva Bijit

11-06-2008

Tablas de hash

3

Para toda clave x, perteneciente al Universo, debe estar definida la función de hash, h(x), con
valores enteros entre 0 y (B-1).
La función h(x) debe distribuir las claves, lo másequitativamente posible, entre los B valores.
Si h( xi )

h( x j ) se dice que hay colisión, y debe disponerse de un método para resolverla.

Si la función de hash es “buena”, habrán pocas colisiones; si hay c colisiones en promedio, las
operaciones resultarán de complejidad O(c), constante; prácticamente independiente de B. Si
todas las claves que se buscan en la tabla, producen colisiones,...