Métodos de búsqueda

Secuencial

Este método de búsqueda, también conocido como lineal, es el más sencillo y consiste en buscar desde el principio de un arreglo desordenado, el elemento deseado y continuar con cada uno de los elementos del arreglo hasta hallarlo o hasta que ha llegado al final del arreglo y terminar.

Binaria o dicotómica

Para este tipo de búsqueda es necesario que el arreglo este ordenado. El método consiste en dividir el arreglo por su elemento medio en dos sub-arreglos más pequeños, y comparar el elemento con el del centro. Si coinciden, la búsqueda termina. Si el elemento es menor, se busca en el primer sub-arreglo, y si es mayor se busca en el segundo.

Tablas Hash

Una tabla hash es una estructura de datos que asocia claves con valores; su uso más frecuente se centra en las operaciones de búsqueda ya que permite el acceso a los elementos almacenados en la tabla a partir de una clave generada.

Las tablas hash se implementan sobre arreglos que almacenan grandes cantidades de información, sin embargo como utilizan posiciones pseudo-aleatorias, el acceso a su contenido es bastante lento.

Función hash

La función hash realiza la transformación de claves (enteros o cadenas de caracteres) a números conocidos como hash, que contengan enteros en un rango [0..Q-1], donde Q es el número de registros que podemos manejar en memoria, los cuales se almacenan en la tabla hash.

Hashing Multiplicativo

Esta técnica trabaja multiplicando la clave k por sí misma o por una constante, usando después alguna porción de los bits del producto como una localización de la tabla hash.

Tiene como inconvenientes el que las claves con muchos ceros se reflejarán en valores hash también con ceros, y el que el tamaño de la tabla está restringido a ser una potencia de 2.

Para evitar las restricciones anteriores se debe de calcular

h(k) = entero [Q * Frac(C*k)]

donde Q es el tamaño de la tabla y

0 <= C <= 1. Hashing por División

En este caso la función se calcula simplemente como h(k) = modulo (k,Q) usando el 0 como el primer índice de la tabla hash de tamaño Q. Es importante elegir el valor de Q con cuidado. Por ejemplo si Q fuera par, todas las claves pares serían aplicadas a localizaciones pares, lo que constituiría un sesgo muy fuerte. Una regla simple para elegir Q es tomarlo como un número primo.

Fuente: Apunte Análisis, diseño e implantación de algoritmos de la facultad de contaduría y administración, UNAM