Tablas de Dispersión

Primero empecemos por ver qué son las funciones de dispersión. Las funciones de dispersión consisten en la elección de una clave para el buen funcionamiento de la estructura, es la relación entre la llave y la posición en la tabla. Estas tienen las siguientes características:

• Ser una función sencilla y por tanto rápida.
• Distribuir uniformemente los elementos en el espacio de almacenamiento
• Evitar en lo posible la aparición de sinónimos
• Para dos claves muy similares, generar posiciones distantes.

Ahora, las tablas de dispersión se pueden definir como 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 numero entero positivo perteneciente a un rango de valores, relativamente pequeños. En estas organizaciones, cada uno de los elementos ha de tener una clave que identifica de manera univoca el elemento.

Son estructuras de datos que tienen como finalidad realizar las operaciones fundamentales de búsqueda y eliminación de un registro.
La organización ideal de una tabla es de tal forma que el campo clave de los elementos se corresponda directamente con el índice de la tabla.

En esta imagen se puede ver lo que se le llama una tabla de dispersión ideal, que significa que cada llave está en una celda distinta.

 

****************************************************************************************************

Tablas Hash

Las tablas hash se usan para conseguir una búsqueda e inserción muy rápidas. Para eso usamos un array, con lo que volvemos a la estructura básica
de almacenamiento, aunque hay una diferencia importante que es lo que
hace que sea mejor que el array en cuanto a rapidez: a cada dato se le asigna,
mediante una fórmula matemática llamada función hash, una posición única
en la tabla, con lo que la búsqueda, la inserción y el borrado son inmediatos: O(1).

Los inconvenientes de una tabla hash son:

• Al tratarse de un array, el tamaño de la tabla está limitado y debe fijarse
  desde el principio.
• Como las posiciones ocupadas no tienen por qué ser consecutivas, no se
  puede recorrer el contenido de una tabla hash.
• Como la posición de una palabra se calcula de forma matemática, los datos no pueden almacenarse ordenados.
• Si permitimos datos duplicados se produce lo que se denomina “colisión”,
  que consiste en que a dos palabras se les asigna la misma posición en el
  array.

Aquí hice un ejemplo para explicar una tabla hash, y también una función hash.

En ésta tabla, la función hash genera un índice basado en el dígito colocado en el extremo derecho del valor ASCII de la segunda letra del nombre de la persona.

Por ejemplo, en el nombre “Jessica”, la segunda letra es una “e”. El valos ASCII de “e” es 101. El dígito colocado en el extremo derecho de 101 es 1, por lo tanto el registro para “Jessica” es almacenado en el índice 1 de la tabla hash.

La tabla hash en la figura anterior muestra cada nombre en su posición asignada.

Las implantaciones de tablas hash con complicadas por que deben manejar colisiones potenciales. Básicamente, las colisiones disminuyen el desempeño de las operaciones de la tabla hash. La mejor manera de reducir el número de colisiones e incrementar la eficiencia de la tabla hash, es usar una buena función hash, la cual distribuye equitativamente la asignación de claves a través de las posiciones de la tabla hash.

Referencias:

• http://www.ganimides.ucm.cl/haraya/doc/Tablas_de_Dispersion.pdf
• http://www.ie.uia.mx/acad/atortole/progra2/hash.html
• http://www.creationexus.tk/component/kunena/50-Programaci%C3%B3n/400-Tablas-de-Dispersion-o-Funciones-Hash.html
• http://www.iuma.ulpgc.es/users/jmiranda/docencia/programacion/Tema8_ne.pdf
• http://www.slideshare.net/lcahuich/15-tablas-hash