Tablas Hash

TABLAS DE DISPERSION Y FUNCIONES HASH.
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 detener una clave que identifica de manera unívoca al elemento.
Las tablas de dispersión son estructuras de datos que tienen como finalidad realizar las operaciones fundamentales de búsqueda y eliminación de un registro en un tiempo de ejecución constante (complejidad constante 0(1)).
La organización ideal de una tabla es de tal forma que el campo clave de los elementos se correspondadirectamente con el índice de la tabla. Por ejemplo, una compañía tiene 300 empleados, cada uno identificado con un número de nómina de 0 a 999. La forma de organizar la tabla es con un arreglo de 1000 registros, sin embargo, muchas posiciones de la tabla están vacías, se corresponden con números de nómina que no existen. Se puede concluir que el primer problema que platea esta organización: ¿Cómo evitarque el arreglo o vector utilizado este en una proporción adecuado al número de registros? Las funciones de transformación de claves, funciones hash, permiten que el rango posible de índices esté en proporción al número de registros. Las funciones que transforman números grandes en otros más pequeños se conocen como funciones de dispersión o funciones hash.
OPERACIONES DE TABLAS DE DISPERSION.
Laoperación de insertar añade un elemento en la posición que le corresponde según la clave del elemento.
La operación eliminar extrae un elemento de la tabla que se encuentra en la posición que le corresponde según su clave.
En las tablas dispersas no se utiliza directamente la clave para indexar, el índice se calcula con una función matemática, función hash h(x), que tiene como argumento laclave del elemento y devuelve una dirección o índice en el rango de la tabla. Según esto, considerando h(x) la función hash, se puede especificar las operaciones del tipo tabla dispersa:
Buscar (Tabla T, Clave x)
Devuelve el elemento de la tabla T [h(x)].
Insertar (Tabla T, elemento k)
Añade el elemento k, T [h (Clave (k)] k.
Eliminar (Tabla T, Clave x)
Retira de la tabla el elemento conclave x, T [h (x)] LIBRE.
La ventaja de utilizar tablas de dispersión radica en la eficiencia de estas operaciones. Si la función hash es de complejidad constante, la complejidad de cada una de las 3 operaciones también es constante, 0 (1). Un problema potencial de la función de dispersión es el de las colisiones, esto es dadas 2 claves distintas xi, xj se obtenga la misma dirección o índice: h(xi)=h (xj). La operación de insertar tiene que incorporar el proceso de resolución de colisiones, no pueden estar 2 elementos en la misma posición. De igual forma los procesos de búsqueda y eliminación también quedan afectados por la resolución de colisiones. Las tablas dispersa se diseñan considerando el problema de las colisiones. Siempre se reservan mas posiciones de memoria, m, que elementosprovistos a almacenar, n. Cuantas más posiciones haya, menor es el riesgo de colisiones, pero más huecos libres quedan (memoria desaprovechada). El parámetro que mide la proporción entre el número de elementos almacenados, n, en una tabla dispersa y el tamaño de la tabla, m, se denomina factor de carga, £ =n/m. Se recomienda elegir m de tal manera que el factor de carga sea £ ≤ 0.8
FUNCIONES DEDISPERSION.
Una función de dispersión convierte el dato considerado campo clave (tipo entero o cadena de caracteres) en un índice dentro del rango de definición del arreglo o vector que almacena los elementos de tal forma que sea adecuado para indexar el arreglo. La idea que subyace es utilizar la clave de un elemento para determinar su dirección o posición en un almacenamiento secuencial, pero...