BÚSQUEDA DE VECTORES
| 2.1 | Introducción |
| 2.2 | Búsqueda Lineal |
| 2.3 | Búsqueda Binaria |
| 2.4 | Búsqueda de Hash |
Siendo optimistas, una secretaria podría perder tan sólo uno o dos minutos para encontrar el archivo de uno de los clientes de la compañía para la cual trabaja, esto, asumiendo que los archivos estén perfectamente ordenados y catalogados. Ahora, con una computadora en su oficina, la búsqueda completa puede hacerse en tan sólo unos segundos y la secretaria no tiene que encargarse de volver a buscar el lugar correcto para almacenar el archivo, de eso se encargan los programadores que desarrollan la aplicación de la cual la secretaria toma ventaja. Este es tan sólo un ejemplo de la importancia de las operaciones de búsqueda en un computador, las cuales se realizan a todos los niveles y con infinidad de implementaciones distintas, de la cuales, a continuación presentamos algunas que son útiles en el caso de que la búsqueda se haga en una estructura de datos lineal.
La búsqueda de un elemento dentro de un array es una de las operaciones más importantes en el procesamiento de la información, y permite la recuperación de datos previamente almacenados. El tipo de búsqueda se puede clasificar como interna o externa, según el lugar en el que esté almacenada la información (en memoria o en dispositivos externos). Todos los algoritmos de búsqueda tienen dos finalidades:
2.2 Búsqueda lineal (secuencial)
Consiste en recorrer y examinar cada uno de los elementos del array hasta encontrar el o los elementos buscados, o hasta que se han mirado todos los elementos del array.
Este es el método de búsqueda más lento,
pero si nuestra información se encuentra completamente desordenada es
el único que nos podrá ayudar a encontrar el dato que buscamos.
El siguiente algoritmo ilustra un esquema de implementación del algoritmo
de búsqueda secuencial:
for(i=j=0;i<N;i++)
if(array[i]==elemento)
{
solucion[j]=i;
j++;
}
Este algoritmo se puede optimizar cuando el array está
ordenado, en cuyo caso la condición de salida cambiaría a:
for(i=j=0;array[i]<=elemento;i++)
o cuando sólo interesa conocer la primera ocurrencia del elemento en
el array:
for(i=0;i<N;i++)
if(array[i]==elemento)
break;
En este último caso, cuando sólo interesa la
primera posición, se puede utilizar un centinela, esto es, dar a la posición
siguiente al último elemento de array el valor del elemento, para estar
seguro de que se encuentra el elemento, y no tener que comprobar a cada paso
si seguimos buscando dentro de los límites del array:
array[N]=elemento;
for(i=0;;i++)
if(array[i]==elemento)
break;
Si al acabar el bucle, i vale N esto indica que no se encontró el elemento. El número medio de comparaciones que hay que hacer antes de encontrar el elemento buscado es de (N+1)/2.
2.2.1. Complejidad de la Búsqueda Lineal.
(A) MEJOR CASO: El algoritmo de búsqueda lineal termina tan pronto como encuentra el elemento buscado en el array. Si tenemos suerte, puede ser que la primera posición examinada contenga el elemento que buscamos, en cuyo caso el algoritmo informará que tuvo éxito después de una sola comparación. Por tanto, la complejidad en este caso será O(1).
(B) PEOR CASO: Sucede cuando encontramos X en la última posición del array. Como se requieren n ejecuciones del bucle mientras, la cantidad de tiempo es proporcional a la longitud del array n, más un cierto tiempo para realizar las instrucciones del bucle mientras y para la llamada al método. Por lo tanto, la cantidad de tiempo es de la forma an + b (instrucciones del mientras * tamaño del arreglo + llamada al método) para ciertas constantes a y b, que representan el coste del bucle mientras y el costo de llamar el método respectivamente. Representando esto en notación O, O(an+b) = O(n).
(C) CASO MEDIO: Supongamos que cada elemento almacenado en el array es igualmente probable de ser buscado. La media puede calcularse tomando el tiempo total de encontrar todos los elementos y dividiéndolo por n:
Total = a (1 + 2 + ...+n) + bn = a (n(n+1) / 2) + bn, a representa
el costo constante asociado a la ejecución del ciclo y b el costo constante
asociado a la evaluación de la condición. 1, 2 , ..n, representan
el costo de encontrar el elemento en la primera, segunda, ..., enesima posición
dentro del arreglo.
Media = (Total / n) = a((n+1) / 2) + b que es O(n).
Este es el algoritmo de más simple implementación pero no el
más efectivo. En el peor de los casos se recorre el array completo y
el valor no se encuentra o se recorre el array completo si el valor buscado
está en la última posición del array. La ventaja es su
implementación sencilla y rápida, la desventaja, su ineficiencia.
2.3 Búsqueda binaria (dicotómica)
Si los elementos sobre los que se realiza la búsqueda están ordenados, entonces podemos utilizar un algoritmo de búsqueda mucho más rápido que el secuencial, la búsqueda binaria. El algoritmo consiste en reducir paulatinamente el ámbito de búsqueda a la mitad de los elementos, basándose en comparar el elemento a buscar con el elemento que se encuentra en la mitad del intervalo y en base a esta comparación:
Se puede aplicar tanto a datos en listas lineales (Vectores, Matrices, etc.) como en árboles binarios de búsqueda. Los prerrequisitos principales para la búsqueda binaria son:
La búsqueda binaria consiste en dividir el array por su elemento medio en dos subarrays más pequeños, y comparar el elemento con el del centro. Si coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (si está) en el primer subarray, y si es mayor está en el segundo. Por ejemplo, para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarían los siguientes pasos:
Se toma el elemento central y se divide el array en dos:
{1,2,3,4}-5-{6,7,8,9}
Como el elemento buscado (3) es menor que el central (5), debe estar en el primer
subarray: {1,2,3,4}
Se vuelve a dividir el array en dos:
{1}-2-{3,4}
Como el elemento buscado es mayor que el central, debe estar en el segundo subarray:
{3,4}
Se vuelve a dividir en dos:
{}-3-{4}
Como el elemento buscado coincide con el central, lo hemos encontrado.
Si al final de la búsqueda todavía no lo hemos encontrado, y el
subarray a dividir está vacio {}, el elemento no se encuentra en el array.
La implementación sería:
int desde,hasta,medio,elemento,posicion; // desde y hasta
indican los límites del array que se está mirando.
int array[N];
// Dar valor a elemento.
for(desde=0,hasta=N-1;desde<=hasta;)
{
if(desde==hasta) // si el array sólo tiene un elemento:
{
if(array[desde]==elemento) // si es la solución:
posicion=desde; // darle el valor.
else // si no es el valor:
posicion=-1; // no está en
el array.
break; // Salir del bucle.
}
medio=(desde+hasta)/2; // Divide el array en dos.
if(array[medio]==elemento) // Si coincide con el central:
{
posicion=medio; // ese es la solución
break; // y sale del bucle.
}
else
if(array[medio]>elemento) // si es menor:
hasta=medio-1; // elige el array de
la izquierda.
else // y si es mayor:
desde=medio+1; // elige el array de la derecha.
}
2.3.2. Versión recursiva de la Búsqueda Binaria.
Su única novedad es que después de comparar el elemento de búsqueda con el elemento de la mitad de la tabla, se invoca recursivamente a realizar la búsqueda en uno de los dos posibles intervalos, el inferior o el superior, finalizando en el momento en el que se encuentre el elemento o ya se tenga un único elemento y no coincida con el buscado.
int binariaRecursiva(int A[], int X, int inicio, int
fin)
{
int medio;
if (inicio > fin) return -1;
else
{
medio = inicio+(inicio+fin)/2;
if (A[medio] < X) return binariaRecursiva(A,X,medio+1,fin);
else if (A[medio] > X) return binariaRecursiva(A,X,inicio,medio
-1);
else return medio;
}
}
2.3.3. Complejidad de la Búsqueda Binaria.
Para poder medir la velocidad de cálculo del algoritmo de búsqueda binaria, se deberán obtener el número de comparaciones que realiza el algoritmo, es decir, el número de vueltas del ciclo o el número de recursiones. Aunque en principio puede parecer que ambas versiones invierten el mismo tiempo, la recursiva es más lenta a medida que se incrementa considerablemente el número de elementos a considerar, ya que existirán más llamadas a la función por resolver, con el consiguiente gasto de tiempo y memoria en guardar y restaurar parámetros.
En el mejor caso, la búsqueda binaria podría toparse con el elemento buscado en el primer punto medio, requiriéndose sólo una comparación de elementos. Esto equivale al caso óptimo durante una búsqueda secuencial, pero en el peor de los casos la búsqueda binaria es mucho más rápida cuando N es grande.
El algoritmo de búsqueda binaria progresivamente va
disminuyendo el número de elementos sobre el que realizar la búsqueda
a la mitad: n, n/2, n/4, ... Así, tras log (n) divisiones se habrá
localizado el elemento o se tendrá la seguridad de que no estaba. Log
(n) divisiones es el numero máximo de veces que se puede reducir a la
mitad la cantidad de registros a considerar, hasta que solo se tenga un elemento.
2.4 Búsqueda mediante transformación de claves (hash)
Hasta ahora las técnicas de localización de registros vistas, emplean un proceso de búsqueda que implica cierto tiempo y esfuerzo. El método de transformación de claves nos permite encontrar directamente el registro buscado en tablas o archivos que no se encuentran necesariamente ordenados, en un tiempo independiente de la cantidad de datos.
En los párrafos siguientes se hará referencia a tablas, en lugar de arreglos, como las estructuras de almacenamiento de la información, pues en general el método de Hashing se aplica en situaciones que implican el manejo de una considerable cantidad de información, organizada .
A diferencia de una búsqueda indexada por claves ordinaria, donde usamos el valor de las claves como índices de un arreglo y necesitamos indispensablemente que los mismos sean enteros distintos dentro de un rango equivalente al rango de la tabla, utilizar el método de Hashing nos permite manejar aplicaciones de búsqueda donde no tenemos claves con características tan limitadas. El resultado es un método de búsqueda completamente diferente a los métodos basados en comparaciones, ahora en vez de navegar por las estructuras comparando palabras clave con las claves en los items, tratamos de referenciar items en una tabla directamente haciendo operaciones aritméticas para transformar claves en direcciones de la tabla. Esto último se logra implementando una Función Hash, que se va a encargar de dicha transformación.
Idealmente, todas las claves deberían corresponder con direcciones diferentes, pero es muy frecuente que dos o mas claves diferentes sean transformadas a la misma dirección, cuando esto pasa, se dice que se presenta una Colisión. Es por eso que también se debe implementar algún proceso de resolución de Colisiones, que se va a encargar de tratar tales situaciones. Uno de los métodos de resolución de colisiones que existen usa Listas enlazadas y se lo denomina “encadenamiento directo” o “Hashing abierto” el cual es muy útil en situaciones dinámicas, donde el numero de elementos es difícil de predecir por adelantado.
El Hashing es un buen ejemplo de balance entre tiempo y espacio. Si no hubiera limitaciones de memoria, entonces podríamos hacer cualquier búsqueda en un solo acceso simplemente utilizando la clave como una dirección de memoria. Este ideal no puede ser llevado a cabo, porque la cantidad de memoria requerida es prohibitiva cuando la cantidad de registros es considerable. De la misma manera, si no hubiese limitación de tiempo, podríamos usar un menor espacio en memoria usando un método secuencial. Hashing provee una manera de usar una razonable cantidad de memoria y tiempo y lograr un balance entre los dos extremos mencionados. En particular, podemos lograr el balance deseado simplemente ajustando el tamaño de la tabla, sin necesidad de re-escribir código o cambiar algoritmos.
En líneas generales podemos decir, que es razonable esperar búsquedas (Search), borrados (Delete) e inserciones (Insert) en tiempo constante , independientemente del tamaño de la tabla. O sea que es ideal para aplicaciones que realicen mayoritariamente este tipo de operaciones, por el otro lado, Hashing no provee implementaciones eficientes para otras operaciones como por ejemplo Ordenamiento (Sort) o Selección (Select).
2.4.1 Funciones Hash:
La función hash es la que se va a encargar de transformar las claves en direcciones de la tabla. Se puede definir la “función ideal” como aquella que distribuya a todos los elementos lo mas uniformemente posible sobre la gama de valores índice, es decir, si tenemos una tabla que puede almacenar N items, entonces requerimos de una función que transforme claves a enteros en el rango [0, N-1], que la salida de la función tenga aproximadamente la misma probabilidad para cada entero, y que la distribución de las claves no esté ligada a patrón alguno. La función de Hash que se seleccione debe ser calculable de modo eficiente, es decir, estar compuesta de un numero reducido de operaciones aritméticas básicas.
No hay reglas que permitan determinar cual será la función mas apropiada para un conjunto de claves, de tal forma que se pueda asegurar una uniformidad máxima. Hacer un análisis de las características de las claves, puede sin embargo ayudar en la elección de la función.
La implementación de la función hash depende del tipo de clave. No va a ser la misma si la clave es un entero, un real o una cadena.
Dentro de las funciones más comunes para la implementación de hashing se encuentran:
Aunque alguna otra técnica pueda desempeñarse mejor en situaciones particulares, la técnica del residuo de la división proporciona generalmente la mejor distribución. Ninguna función hash se desempeña siempre mejor que las otras. El método del medio del cuadrado puede aplicarse en archivos con factores de cargas bastantes bajas para dar generalmente un buen desempeño. El método de pliegues puede ser la técnica mas fácil de calcular pero produce resultados bastante erráticos, a menos que la longitud de la llave sea aproximadamente igual a la longitud de la dirección. Si la distribución de los valores de llaves no es conocida, entonces el método del residuo de la división es preferible. Note que el hashing puede ser aplicado a llaves no numéricas. Las posiciones de ordenamiento de secuencia de los caracteres en un valor de llave pueden ser utilizadas como sus equivalentes "numéricos". Alternativamente, el algoritmo hash actúa sobre las representaciones binarias de los caracteres.
Todas las funciones hash presentadas tienen destinado un espacio
de tamaño fijo. Aumentar el tamaño del archivo relativo creado
al usar una de estas funciones, implica cambiar la función hash, para
que se refiera a un espacio mayor y volver a cargar y reorganizar de nuevo los
datos.
Ejemplo 2.1. Función Hashing - Metodo del residuo
El código que se le asigna a un estudiante de una universidad esta formado por la inicial del nombre, la inicial del apellido y el número del carnet, cuyos dígitos corresponden al año de entrada año de entrada, el semestre y un consecutivo de 4 dígitos. El espacio de llaves en este caso tiene un tamaño de 1.458'000.000 códigos potenciales diferentes, calculado de la siguiente manera:
27*27*100*2*10.000=>inicial_nombre*inicial_apellido*año*semestre*consecutivo.
En la Facultad de Ingenieria hay aproximadamente 3.000 estudiantes, cuyos códigos están distribuidos de manera no uniforme sobre dicho espacio de llaves. La función de hashing debería ser tal que, que al código de un estudiante le asociara una dirección en el espacio físico de representación de la información (área primaria de la tabla).
Una posible función de hashing, para este caso, sería sumar todos los dígitos del carnet y multiplicar dicho resultado por el código ASCII de las iniciales. Luego, a este valor se le aplicaría la función módulo N. Esta función siempre retorna un valor entre 0 y 2.999 (N=3.000).
Aplicando esta función se tiene:
h("VD9113984")= 86*68*35 = 204.680 % 3.000 = 680
h("CM9113578")= 67*77*34 = 175.406 % 3.000 = 1406
El desempeño de una tabla de hash empieza a disminuir a medida que aumenta el factor de carga (tamaño de la tabla / capacidad), dado que aumenta el número de colisiones y se debe recurrir a estructuras de datos auxiliares, sobre las cuales se hacen búsquedas más lentas. Por esta razón es recomendable definir desde el comienzo una capacidad extra de aproximadamente el 20%, para asegurar un buen desempeño de la función de hashing, a medida que el factor de carga aumenta.
2.4.2 Resolución de Colisiones:
Hay varios métodos de manejar la presencia de colisiones. Dentro de estos métodos se encuentran: Hashing Abierto y Hashing Cerrado.
- Hashing Abierto: (encadenamiento directo)
La forma mas sencilla de resolver las colisiones es simplemente crear para cada dirección de la tabla, una lista encadenada de todos los elementos cuyas llaves mapean al mismo índice.
Cuando se busque una clave se tendrá que recorrer la lista que le corresponda hasta encontrar el elemento buscado. El factor de carga será l = N/M , que va a ser el largo promedio de cada lista.
(N = numero de elementos insertados, M = cantidad de listas)
Las listas pueden dejarse desordenadas o bien mantenerlas ordenadas. Lo mas frecuente es usar listas desordenadas porque es mas fácil de implementar , y es mas eficiente, vamos a tener una Inserción de orden constante y una búsqueda proporcional a l .
En el caso que utilicemos la tabla en su mayor parte haciendo búsquedas va a ser útil mantener las listas ordenadas, con esto lograremos acelerar las búsquedas por un factor de 2 a cambio de una Inserción mas lenta.
Como elegir el tamaño M de la tabla?
Se debería elegir una M que sea suficientemente pequeña de manera que no se este derrochando una gran cantidad de memoria contigua con espacios vacíos, pero lo suficientemente grande de modo que las búsquedas secuenciales sean eficientes. La práctica indica que debemos elegir un M que sea aproximadamente entre 1/5 y 1/10 de las cantidad de claves que se espera que ingresen en la tabla.
Una de las mayores virtudes del encadenamiento directo es que esta decisión no es crítica: si se ingresan mas claves de las esperadas, simplemente las búsquedas van a ser un poco mas lentas que con un M mas grande. Mientras que si se ingresan menos claves de las esperadas, tendremos una búsqueda bastante rápida con tal vez cierto derroche de espacio.
- Hashing Cerrado: (direccionamiento abierto)
Si se puede predecir, con suficiente precisión, la posibilidad de la cantidad de elementos que van a ser ingresados en la tabla hash, y se tiene suficiente memoria contigua disponible para guardar todas las claves, entonces ya no vale la pena usar una estructura de datos secundaria (las listas) como en Hashing Abierto.
Indefectiblemente se necesita una tabla mas grande, tal que el tamaño M sea mayor que la cantidad N de items, valiéndose de los espacios vacíos en la tabla para resolver las colisiones. Estos métodos son los que conocemos como métodos de “Hashing Cerrado”.
Generalmente , el factor de carga debería estar por debajo de l = 0.5 para una buen desempeño. A continuación se describen las tres estrategias mas comunes para la resolución de colisiones.
* Búsqueda Lineal: (Linear Probing)
Es el más simple de los métodos de Hashing Cerrado. Cuando se presenta una colisión, simplemente se busca, avanzando de a un lugar por vez, el próximo lugar vacío en la tabla, y se guarda ahí la clave si no está repetida.
La inspección comienza en la posición a la cual lleva la función hash, ahí se tienen tres posibles situaciones: si la posición actual de la tabla contiene un ítem cuya clave es igual a la que buscamos, entonces tenemos un hit, si la posición de la tabla está vacía, tenemos una pérdida, de otra manera seguimos con la próxima posición en el siguiente índice, continuando (volviendo al principio de la tabla si llegamos al final) hasta que encontremos o una pérdida o un hit.
Al igual que en Hashing abierto, el desempeño del método de linear probing depende del factor l. Aunque la forma de calcular l = N/M ,es la misma, lo interpretamos de manera diferente. En Hashing Abierto l es “el porcentaje de posiciones ocupadas en la tabla” y por supuesto debe ser menor que 1.
Para con un l pequeño, se espera que la mayoría de las búsquedas encuentren una posición vacía en unos pocas inspecciones en la tabla. Mientras que si el factor es muy cercano a 1 (tabla casi llena) una búsqueda puede llevar un gran numero de inspecciones e incluso puede caer en un ciclo infinito, por eso no se debe cargar la tabla hasta valores muy cercanos al llenado total.
El costo promedio de la búsqueda lineal depende fuertemente de la independencia de las inspecciones respecto de la inspección anterior . Desafortunadamente estas no son totalmente independientes, lo cual provoca que se generen en ciertas zonas de la tabla, grupos contiguos de datos (clusters) mientras que otras zonas permanecen vacías. Si este efecto es muy pronunciado, la búsqueda se tornará principalmente secuencial, perdiendo así las ventajas del método hash.
* Búsqueda Cuadrática: (Quadratic Probing)
La Búsqueda cuadrática es un método de resolución de colisiones mejora el problema del agrupamiento primario (Clustering) de la Búsqueda Lineal. El proceso es similar al anterior, pero mientras que la función de inspección de Búsqueda Lineal es f(i) = i ; ahora vamos a usar una función cuadrática f(i) = i^2, entonces , en una inserción cuando encontremos un lugar ocupado avanzara primero 1, luego 2^2 ,luego 3^2 ,etc. hasta encontrar un lugar vacío.
Si bien la Búsqueda cuadrática mejora sustancialmente el problema de Clustering Primario, tiene la desventaja de que pueden quedar celdas sin visitar (Clustering Secundario), en particular, si la tabla esta llena en mas de un 50% (l>0.5) , no hay garantías de encontrar una celda vacía si el tamaño de la tabla no es PRIMO. Sin embargo, si el tamaño de la tabla es un número primo esta garantizado que podremos insertar un nuevo elemento.
Como borrar una clave de una tabla con Búsqueda lineal o cuadrática? No podemos simplemente borrarla, porque los items que fueron insertados después no van a ser encontrados ya que la búsqueda va a ser interrumpida por el “agujero” que dejo el borrado. Una solución es aplicar “rehashing” para los items insertados posteriormente, otra mas sencilla sería poner un centinela que ocupe el espacio de la clave borrada.
* Hashing Doble
La Solución definitiva para eliminar casi completamente el Clustering tanto primario como secundario de los métodos citados anteriormente, es el Hashing Doble. En el cual una segunda función es usada para manejar la resolución de colisiones. La segunda función debe ser elegida con cuidado, de otra manera el programa puede no funcionar. No puede haber ningún caso en que la segunda función se evalué a cero, ya que esto generaría un ciclo infinito, también es importante que el valor de la segunda función sea relativamente primo al tamaño de la tabla, de otra manera las secuencias serían muy cortas.
Una segunda función simple y efectiva podría ser la siguiente: Hash2 (clave c) { return (c%97)+1; }
En Hashing doble, la única forma de borrar items es reemplazándolos por centinelas, de otra manera se perderían algunas claves.
* Re-Hashing
Cuando las tablas se llenan demasiado, el tiempo de ejecución de algunas operaciones va a empezar a ser muy largo. Sobre todo cuando se combinan muchas inserciones con borrados. Una solución es crear otra tabla que sea el doble de grande (con una nueva función hash asociada) y procesar la tabla hash original entera, computando el nuevo valor hash para cada elemento (no-centinela) e insertarlo en la nueva tabla.
Esta operación completa es lo que denominamos Re-Hashing. Obviamente es una operación muy costosa (orden N), pero dado que no va a pasar muy frecuentemente, no esta nada mal y su efecto va a pasar prácticamente desapercibido. Solo el desafortunado usuario cuya inserción provoque un Re-Hash va a sentir el efecto.
En que momento aplicar el Re-Hash queda a criterio del programador, algunas posibilidades son:
El método de Re-Hashing es apropiado para usar en implementaciones de tabla de símbolos donde los patrones de uso son impredecibles, ya que puede manejar tablas de todos los tamaños de una forma razonable.
* Hashing Extensible
Cuando la cantidad de información se debe manejar es muy grande para trabajarla en la memoria, la principal preocupación pasa a ser la cantidad de accesos a disco requeridos para obtener datos.
Sea Hashing abierto o cerrado el que se use, el gran problema es que las colisiones podrían causar que varios bloques sean examinados durante una búsqueda, inclusive en una tabla hash bien distribuida.
El Hashing Extensible permite que una búsqueda sea ejecutada en 2 accesos a disco y también las inserciones en unos pocos accesos.
El método es muy parecido a la estructura de árboles B, pero fijamos el tamaño de las hojas o “buckets” a M, tal que sea igual a la cantidad de items que entren en un bloque del disco, D va a ser la cantidad de Bits y el tamaño de la raíz o “Directorio” va a ser entonces 2D. Cuando el “bucket” se llena, lo dividimos en 2 nuevos “buckets”, mientras que cuando el Directorio se llena, agregamos un dígito al mismo, duplicando su tamaño. La función Hash van a ser los últimos dígitos de la clave (lo que definimos como D) y va a ir creciendo con el tiempo.
Ventajas de la búsqueda por hashing
1. Se pueden usar los valores naturales de la llave, puesto
que se traducen internamente a direcciones fáciles de localizar.
2. Se logra independencia lógica y física, debido a que los valores
de las llaves son independientes del espacio de direcciones.
3. No se requiere almacenamiento adicional para los índices.
Desventajas de la búsqueda por hashing
1. No pueden usarse registros de longitud variable
2. El archivo no esta clasificado
3. No permite llaves repetidas
4. Solo permite acceso por una sola llave
Costos de la búsqueda por hashing
· Tiempo de procesamiento requerido para la aplicación de la función
hash
· Tiempo de procesamiento y los accesos E/S requeridos para solucionar
las colisiones.
La eficiencia de una función hash depende de:
1. La distribución de los valores de llave que realmente se usan
2. El numero de valores de llave que realmente están en uso con respecto
al tamaño del espacio de direcciones
3. El numero de registros que pueden almacenarse en una dirección dada
sin causar una colisión
4. La técnica usada para resolver el problema de las colisiones
El contenido de esta página esta basado en el material disponible en: