Tablas de dispersion (puntos extras)

¿Que son las tablas de dispersion?

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).


¿Cual es su funcion?

 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  referencia : http://www.ie.uia.mx/acad/atortole/progra2/hash.html