Metodos de Busqueda

Índice
Tema: Métodos de Búsqueda 3
Búsqueda Secuencial 3
Algoritmo Para Búsqueda Secuencial 3
Mejoras en la eficiencia de la búsqueda secuencial 3
Búsqueda Hashing 4
FUNCION HASH 4
VENTAJAS 4
DESVENTAJAS 4
ALGORITMO HASHING 4
ALGORITMOS DE HASH MÁS COMUNES 5
FUNCIONES DE HASH 5
COMPARACIÓN ENTRE LAS FUNCIONES HASH 6
Tablas hash 6
OPERACIONES BÁSICAS 6
INSERSION 7
BUSQUEDA 7
HASHING ABIERTO 7HASHING CERRADO 7
Bibliografía 7



Tema: Métodos de Búsqueda

Búsqueda Secuencial

El método de búsqueda secuencial consiste en revisar elemento tras elemento hasta encontrar el dato buscado. La búsqueda secuencial se puede aplicar en arreglos o en listas enlazadas.

Consiste básicamente en recorrer el arreglo de izquierda a derecha hasta que se encuentre el elemento buscado o se termine elarreglo, lo que ocurra primero. Normalmente cuando una función de búsqueda concluye con éxito, interesa conocer en qué posición fue hallado el elemento que se estaba buscando.
Algoritmo Para Búsqueda Secuencial

El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la llave indicada (k), o hasta al final de la lista.

Lasituación óptima es que el registro buscado sea el primero en ser examinado. El peor caso es cuando las llaves de todos los n registros son comparados con k (lo que se busca). El caso promedio es n/2 comparaciones. Este método de búsqueda es muy lento, pero si los datos no están en orden es el único método que puede emplearse para hacer las búsquedas. Si los valores de la llave no son únicos, paraencontrar todos los registros con una llave particular, se requiere buscar en toda la lista.

Mejoras en la eficiencia de la búsqueda secuencial

1)Muestreo de acceso
Este método consiste en observar que tan frecuentemente se solicita cada registro y ordenarlos de acuerdo a las probabilidades de acceso detectadas.

2)Movimiento hacia el frente
Este esquema consiste en que la lista de registros sereorganice dinámicamente. Con este método, cada vez que búsqueda de una llave sea exitosa, el registro correspondiente se mueve a la primera posición de la lista y se recorren una posición hacia abajo los que estaban antes que él.

3)Transposición
Este es otro esquema de reorganización dinámica que consiste en que, cada vez que se lleve a cabo una búsqueda exitosa, el registro correspondiente seintercambia con el anterior. Con este procedimiento, entre más accesos tenga el registro, más rápidamente avanzara hacia la primera posición. Comparado con el método de movimiento al frente, el método requiere más tiempo de actividad para reorganizar al conjunto de registros. Una ventaja de método de transposición es que no permite que el requerimiento aislado de un registro, cambie de posicióntodo el conjunto de registros. De hecho, un registro debe ganar poco a poco su derecho a alcanzar el inicio de la lista.

4)Ordenamiento
Una forma de reducir el número de comparaciones esperadas cuando hay una significativa frecuencia de búsqueda sin éxito es la de ordenar los registros en base al valor de la llave. Esta técnica es útil cuando la lista es una lista de excepciones, tales como unalista de decisiones, en cuyo caso la mayoría de las búsquedas no tendrán éxito. Con este método una búsqueda sin éxito termina cuando se encuentra el primer valor de la llave mayor que el buscado, en lugar de la final de la lista
Búsqueda Hashing

Hash: se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc.,resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo.
FUNCION HASH

Es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor. Varían en los conjuntos de partida y de llegada y en cómo afectan a...