1.3.3 Búsqueda indexada
La búsqueda indexada es un algoritmo que no requiere que los registros estén ordenados previamente. En este método, cada registro se asocia con un valor único conocido como llave, que a menudo es el mismo que el valor del registro. Esta llave se procesa mediante una función hash, que realiza una operación aritmética para generar un valor entero. Luego, este valor se aplica a una operación módulo con el tamaño del arreglo, resultando en un índice que indica dónde debe almacenarse el registro.
El uso de la función hash permite asignar un lugar específico para cada registro, facilitando su recuperación rápida. Sin embargo, puede haber casos en que diferentes llaves generen el mismo índice, lo que se conoce como colisión. Una buena función hash dispersa uniformemente los valores en el arreglo y minimiza las colisiones, aunque siempre existe la posibilidad de que ocurran.
Si el valor en el índice calculado por la función hash no coincide con el valor buscado, se concluye que el registro no existe en el arreglo.
Función Hash
La función hash dispersa los valores de los registros en el arreglo y reduce las colisiones. A continuación, se presentan dos estrategias para implementarla:
- Método de la división: Si k es la llave, m es el tamaño del arreglo y h(k) es la función hash, se realiza la operación h(k) = k mod m para obtener el índice de almacenamiento del registro. Este método puede llevar a una mala dispersión si m es par, asignando llaves pares a índices pares y llaves impares a índices impares. Para mitigar esto, se sugiere utilizar un número primo como tamaño del arreglo.
- Método de la multiplicación: En este caso, la llave k se multiplica por una constante A (con un valor entre 0 y 1), siendo recomendado el valor A ≈ 0.6180339887 para evitar colisiones. La operación se define como h(k) = floor(kA) mod 1, donde kA mod 1 representa la parte fraccional de la multiplicación. Este método es flexible respecto al tamaño del arreglo, pero se recomienda que sea una potencia de 2.