Tablas de Dispersión y Funciones Hash

Introducción

Las tablas de datos permiten el acceso directo a un elemento de una secuencia, indicando la posición que ocupan. Un diccionario es también una secuencia de elementos, pero éstos son realmente pares formados, por ejemplo, por un identificador y un número entero. Las tablas de dispersión se suelen utilizar para implementar cualquier tipo de diccionario. El potencial de las tablas hash o dispersas radica en la búsqueda de elementos; conociendo el campo clave se puede obtener directamente la posición que ocupa, y por consiguiente, la información asociada a dicha clave. Sin embargo, no permiten algoritmos eficientes para acceder a todos los elementos de la tabla, en su recorrido. El estudio de las tablas hash acarrea el estudio de funciones hash o dispersión, que mediante expresiones matemáticas permiten obtener direcciones según una clave que es el argumento de la función.

Tablas de Dispersión

Las tablas de dispersión, o simplemente tablas hash, son estructuras de datos que se usan en aplicaciones que manejan una secuencia de elementos, de tal forma que cada elemento tiene asociado un valor clave, que es un número entero positivo perteneciente a un rango de valores, relativamente pequeño. En estas organizaciones, cada uno de los elementos ha de tener una clave que identifica de manera única al elemento. Por ejemplo, el campo número de cuenta del conjunto de alumnos de la Universidad Iberoamericana puede considerarse un campo clave para organizar la información relativa al alumnado de la universidad ya que el número de cuenta es único. Hay una relación única (uno a uno) entre el campo y el registro alumno. Podemos suponer que no existen, simultáneamente, dos registros con el mismo número de cuenta.

Definición de una tabla de dispersión

Las tablas de dispersión son estructuras de datos que tienen como finalidad realizar la búsqueda o eliminación de un registro con una complejidad constante. La organización ideal de una tabla es aquella en la cual el campo clave de los elementos se corresponde directamente con el índice de la tabla. Si por ejemplo, una compañía tiene 300 empleados, cada uno identificado con un número de empleado de 0 a 999, la forma de organizar la tabla es con un arreglo de 1000 registros.

struct Empleado Tabla[1000];

El elemento Tabla[i] almacena al empleado cuyo número de empleado es i. Con esta organización la búsqueda de un empleado se ha realizado directamente, con un único acceso, debido a que el número de empleado es la posición en la tabla. La eficiencia se puede expresar como tiempo constante, 0(1).

Sin embargo, muchas posiciones de la tabla están vacías ya que se corresponden con números de empleado que no existen. En este ejemplo, el rango del campo clave es relativamente pequeño; pero imaginemos que los números de empleado fueran de 5 dígitos, las posiciones no existentes estarían en clara desproporción y la memoria ocupada por la tabla estaría desaprovechada. Pero enseguida se puede plantear la solución. Tomar los tres primeros dígitos del número de nómina como índice del arreglo o tabla de registros, entonces se hemos hecho una transformación del campo clave en un entero de 3 dígitos:

h(número de nómina) -> índice

Se puede concluir que el primer problema que plantea esta organización es: øcómo evitar que el arreglo utilizado esté en una proporción adecuada al número de registros? Las funciones de transformación de claves, funciones hash, permiten que el rango posible de índices estén en proporción al número real de registros.

Una función que transforma números grandes en otros más pequeños se conoce como o función hash.

Funciones de Dispersión

Una función de dispersión convierte el dato del campo clave, un entero o una cadena, en un valor entero en el rango de definición del arreglo o vector que va a almacenar los elementos, de tal forma que sea adecuado para indexar el arreglo.

La idea básica es utilizar la calve de un registro para determinar su dirección, pero sin desperdiciar mucho espacio, para lo que hay que realizar una transformación mediante una función hash, del conjunto de K claves sobre el conjunto L de direcciones de memoria:

h(x) : K -> L

Ésta es la función de direccionamiento hash o función de dispersión. Si x es una clave, entonces h(x) se denomina direccionamiento hash de la clave x, además es el índice de la tabla donde se debe guardar el registro con esa clave. Así, si la tabla tiene un tamaño tamTabla = 199, la función hash elegida tiene que generar índices en el rango 0 .. tamTabla - 1. Si la clave es un entero, por ejemplo el número de serie de un artículo (por ejemplo, hasta 6 dígitos), y se dispone de una tabla de tamTabla elementos, la función de direccionamiento tiene que ser capaz de transformar valores pertenecientes a un conjunto de 999999 elementos en un conjunto de tamTabla. La clave también puede ser una cadena de caracteres, en este caso se hace una transformación previa a valor entero.

Hay que contemplar el hecho de que la función hash, h(x), no dé valores distintos: es posible (según la función elegida) que dos claves diferentes c1 y c2 den la misma dirección h(c1) = h(c2). Entonces se produce el fenómeno de la colisión, y se debe usar algún método para resolverla. Por lo tanto, en el estudio del direccionamiento hash hay que dividirlo en dos partes: búsqueda de funciones hash y resolución de colisiones.

Aritmética Modular

Una función de dispersión que utiliza la aritmética modular genera valores dispersos calculando el residuo de la división entera entre la clave x y el tamaño de la tabla m.

h(x) = x mod m

Plegamiento

La técnica del plegamiento se utiliza cuando el valor entero del campo clave elegido sea demasiado grande, pudiendo ocurrir que no pueda ser almacenado en memoria. Consiste en partir la clave x en varias partes x1, x2, x3, Ö, xn, y la combinación de las partes de un modo conveniente (a menudo sumando las partes) da como resultado la dirección del registro.

Cada parte xi, con la excepción a lo sumo de la última, tiene el mismo número de dígitos que la dirección especificada.

h(x) = x1 + x2 + x3 + Ö + xr

En la operación que se realiza para el cálculo de la función hash, se desprecian los dígitos más significativos que se obtienen del acarreo. Generalmente se utiliza esta técnica para transformar una clave muy grande en otra más pequeña, y a continuación se aplica la función hash de aritmética modular.

Mitad del Cuadrado

Esta técnica de obtener direcciones dispersas consiste, en primer lugar, en calcular el cuadrado de la clave x, y a continuación extraer de x^2, los dígitos que se encuentran en ciertas posiciones. El número de dígitos a extraer depende del rango de dispersión que se desea obtener. Así, si el rango es de 0 a 999, se extraen tres dígitos, siempre, aquellos que están en las mismas posiciones.

Un problema potencial, al calcular x^2, es que sea demasiado grande y exceda el máximo rango del valor que se está utilizando. Es importante, al aplicar este método de dispersión, utilizar siempre las mismas posiciones para todas las claves.

Método de la Multiplicación

La dispersión de una clave utilizando el método de la multiplicación genera direcciones en tres pasos. Primero, multiplica la clave x por una constante real R , comprendida entre 0 y 1 ( 0 < R < 1.0 ). En segundo lugar, determina la parte decimal, d, del número obtenido, Rx, y por último se multiplica el tamaño de la tabla, m, por d y al truncarse el resultado se obtiene un número entero en el rango 0 Ö m - 1.

  1. R * x
  2. d = R * x - ParteEntera(R * x)
  3. h(x) = ParteEntera(m * d)
    4. h(x) = x1 + x2 + x3 + Ö + xr

Una elección de la constante R es la inversa de la razón áurea R = 0.6180334.

Colisiones y Resolución de Colisiones

La dirección de dos registros, según la clave elegida, puede que sea la misma posición de la tabla, entonces se producirá una colisión que hay que resolver. Una función hash ideal h(x), debe generar direcciones distintas para dos claves distintas. No siempre es así, no siempre proporciona direcciones distintas: puede ocurrir que para dos claves diferentes existan direcciones diferentes:

x1, x2 -> h(x1) = h(x2)


Este hecho es conocido como colisión; es evidente que al diseñar una tabla de dispersión se debe proporcionar métodos de resolución de colisiones.

Exploración de Direcciones

Los diversos métodos de exploración se utilizan cuando todos los elementos, colisionados o no, se almacenan en la misma tabla. Las colisiones se resuelven explorando sucesivamente en una secuencia de direcciones, hasta que se encuentra una posición libre, o un hueco, en el caso del proceso de insertar, o se encuentra el elemento buscado en las operaciones buscar y eliminar.

Exploración Lineal

Es la forma más primaria y simple de resolver una colisión entre claves al aplicar una función de dispersión. Supongamos que tenemos un elemento de clave x, la dirección que devuelve la función es h(x) = p, si esta posición ya está ocupada por otro elemento se ha producido una colisión. La forma de resolver esta colisión con exploración lineal, consiste en buscar la primera posición disponible que siga a p. La secuencia de exploración que se genera es lineal: p, p+1, p+2, Ö m-1 y así sucesivamente hasta encontrar una posición vacía. La tabla se ha de considerar circular, es decir, si m-1 es la última posición, la que sigue será la posición 0.