Busqueda por transformacion de claves(hash) y solucionador de colisiones

Busqueda por transformacion de claves(hash)
Este método llamado hash, permite aumentar la velocidad de búsqueda sin necesidad de tener los elementos ordenados, cuenta también con la ventaja de queel tiempo de busqueda es prácticamente independiente del número de componentes del arreglo.

El método trabaja basándose en una función de transformación o función has(h) que convierte una claveen una dirección (índice) dentro del arreglo.
La función hash aplicada a la clave da un índice del arreglo lo que permite acceder directamente a sus elementos.
DirecciónH(clave)
Esta funcionhash debe ser simple de calcular y debe asignar direcciones de la manera más uniformemente posible, es decir debe generar posiciones diferentes dadas dos claves diferentes.
Si esto ocurre :(H(k1) = dirección1, H(h2) = dirección1 y k1!= k2)
Hay una colosion que se define como la asignación de una misma dirección a dos o mas claves diferentes

Para trabajar con este método de búsqueda debeelegirse previamente:
a) Una función hash que sea fácil de calcular y que distribuya uniformemente las claves.
b) Un método para resolver colisiones, si esta se presenta se debe contar con algúnmétodo que genere posiciones alternativamente


Funciones hash
• Función modulo(por división)
• Función cuadrado
• Función plegamiento
• Función truncamiento
Solución de colisiones
• Reasignaciono Prueba lineal
o Prueba cuadrática
o Doble dirección has
• Arreglos anidados
• Encadenamiento
Solucion de colisiones
La elección de un método adecuado para resolver colisiones es tanimportante como la elección de una buena funcion hash
Cuando esta obtiene una misma dirección para dos claves diferentes, se esta ante una colision Algunos de los métodos mas utilizados para resolvercolisiones son los siguientes:
• Reasignacion
• Arreglos anidados
• Truncamiento


Reasignacion
Existen varios métodos que trabajan bajo el principio de comparación y reasignación de elementos:
•...