TABLA DE DISPERSIÓN

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.

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.

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.


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.

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.


www.lcc.uma.es/~lopez/modular/tads/dispersion.pdf


http://www.angelfire.com/wy2/est_info/secciona.html

http://www.ie.uia.mx/acad/atortole/progra2/hash.html


www.ublug.org.ar/index.php?...top%2FSPHINX3%2FTablas...Dispersion...