Busqueda Por Transformacion De Claves

BUSQUEDA POR TRANSFORMACION DE CLAVES
En los métodos de búsqueda lineal y binaria el tiempo de búsqueda es proporcional al número de componentes del mismo, a un mayor número de elementos se debe realizar un mayor número de comparaciones.
El método de búsqueda binaria es más eficiente que el secuencial, pero tiene la restricción de que el arreglo debe estar ordenado.
El método de búsquedallamado por transformación de claves (hash), permite aumentar la velocidad de búsqueda sin tener la necesidad de tener los elementos ordenados. Tiene la ventaja también que el tiempo de búsqueda es prácticamente independiente del número de componentes del arreglo.
Si se tiene una colección de datos cada uno de ellos identificado por una clave. Resulta conveniente poder tener acceso a ellos de maneradirecta (sin tener que recorrer algunos datos antes de llegar al buscado).
El método por transformación de claves trabaja basándose en una función de transformación o función hash (H) que convierte una clave dada en una dirección (índice) dentro del arreglo.
Dirección H(clave)
La función hash aplicada a la clave da un índice del arreglo, lo que permite accesar directamente sus elementos. El casomás trivial se presenta cuando las claves son números enteros consecutivos.
Ejm. Si se desea almacenar la información relacionada a 100 alumnos cuyas matriculas son números del 1 al 100. En este caso debe definirse un arreglo de 100 elementos con índices numéricos comprendidos entre los valores 1 al 100. Los datos de cada alumno ocuparan la posición del arreglo que se corresponda con el numerode la matricula, de esta manera se podrá accesar directamente la información de cada alumno.
Ejm2. Si se desea almacenar la información de 100 empleados. La clave de cada empleado será su número de seguro social. Si la clave está formada por 11 dígitos, resulta por completo ineficiente definir un arreglo con 99 999 999 999 elementos para almacenar solamente los datos de 100 empleados. Utilizar unarreglo tan grande asegura
la posibilidad de accesar directamente sus elementos, sin embargo el costo en memoria es excesivo.
Siempre debe equilibrarse el costo por espacio de memoria con el costo por tiempo de búsqueda.
Cuando se tienen claves que no se corresponden con índices (por ejemplo por ser alfanuméricas), o bien cuando las claves son valores numéricos muy grandes, debe utilizarse unafunción hash que permita transformar la clave para obtener una dirección apropiada. Esta función hash debe ser simple de calcular y debe asignar direcciones de la manera más uniforme posible. Es decir dadas dos claves diferentes debe generar posiciones diferentes. Si esto no ocurre (H(K1) = d y H(K2) = d y K1 ¡= K2) hay una colisión. Se define entonces una colisión como la asignación de una mismadirección a dos o más claves distintas.
Para trabajar con este método de búsqueda debe elegirse previamente: Una función hash que sea fácil de calcular y que distribuya uniformemente las claves. Un método para resolver colisiones. Si estas se presentan se debe contar con algún método que genere posiciones alternativas.
Funciones hash
Seleccionar una buena función hash es importante pero tambiénes difícil. No hay reglas que permitan determinar cuál será la función más apropiada para un conjunto de claves, de tal manera que asegure la máxima uniformidad en la distribución de las mismas. Hacer un análisis de las principales características de las claves puede ayudar en la elección de la función hash.
Función modulo (por división)
Consiste en tomar el residuo de la división de la clavepor el número de componentes del arreglo. Si se tiene un arreglo de N elementos y sea K la clave del dato a buscar. La función hash queda definida por la siguiente fórmula:
H(K) = K mod N + 1
Al residuo de la división se le suma 1, esto es para obtener un valor entre 1 y N.
Para lograr una mayor uniformidad en la distribución, N debe ser un número primo o divisible por muy pocos números. Por...