Embed Size (px)
Citation preview
SEDE CONCEPCIÓN TALCAHUANO
Análisis de algoritmos
José Rivera
José Martínez
Docente: Pilar Pardo
Concepción, 16 Abril de 2014
2
Contenido Introducción ........................................................................................................................................ 3
Algoritmos Binarios ............................................................................................................................. 4
Técnica de Búsqueda Binaria. ............................................................................................................. 5
Descripción de la técnica. ................................................................................................................ 5
Algoritmo:........................................................................................................................................ 5
Ejemplo............................................................................................................................................ 6
Ventajas de la técnica. .................................................................................................................... 7
Desventajas de la técnica. ............................................................................................................... 7
Principales Aplicaciones. ..................................................................................................................... 8
Ejemplo: Árbol Binario de Búsqueda: ............................................................................................. 8
Solución: .............................................................................................................................................. 8
Complejidad de la Búsqueda Binaria................................................................................................. 10
Búsqueda mediante transformación de claves (hash) ...................................................................... 11
Funciones Hash: ................................................................................................................................ 12
Función Hashing - Método del residuo ............................................................................................. 13
Aplicando esta función se tiene: ................................................................................................... 14
Resolución de Colisiones: .............................................................................................................. 14
Hashing Abierto: (encadenamiento directo) ..................................................................................... 14
¿Cómo elegir el tamaño M de la tabla? ........................................................................................ 15
Hashing Cerrado: (direccionamiento abierto) .................................................................................. 15
Búsqueda Lineal: (Linear Probing)..................................................................................................... 16
Búsqueda Cuadrática: (Quadratic Probing) ....................................................................................... 17
Hashing Doble ................................................................................................................................... 17
Re-Hashing ........................................................................................................................................ 18
Hashing Extensible ............................................................................................................................ 18
Ventajas de la búsqueda por hashing ........................................................................................... 19
Desventajas de la búsqueda por hashing ...................................................................................... 19
Costos de la búsqueda por hashing .............................................................................................. 19
La eficiencia de una función hash depende de: ............................................................................ 20
Conclusión ............................................................................................. Error! Bookmark not defined.
3
Introducción
Una tabla o un archivo es un grupo de elementos, cada uno de los cuales se llama registro.
Hay una llave asociada a cada registro, que se usa para diferenciar unos de otros. La asociación
entre un registro y su llave puede ser simple o compleja. En la forma más simple, la llave está
contenida dentro del registro en un tramo a una distancia específica del principio del mismo. Una
llave de ese tipo es la llave interna o incluida.
En este trabajo, se verán las técnicas de búsqueda secuencial ordenada/desordenada, secuencial
indexada, binaria e interpolación. En cada una se mencionan su descripción, sus
ventajas/desventajas, y algunas aplicaciones, por supuesto también se eran sus respectivos
algoritmos, ¿pero que es un algoritmo de búsqueda?.
Un algoritmo de búsqueda es un algoritmo que acepta un argumento a y trata de encontrar un
registro cuya llave sea A. El algoritmo puede dar como resultado el registro entero O, lo que es
mas común, un apuntador a dicho registro.
Si la búsqueda es infructuosa, con mucha frecuencia, es deseable agregar un nuevo registro con
dicho argumento como llave. Un algoritmo que haga esto se le llama tabla búsqueda o
diccionario.
La búsqueda en la cual toda la tabla esta de manera frecuente en la memoria principal se le llama
búsqueda interna, mientras que la búsqueda en la que la mayor parte de la tabla está en la
memoria auxiliar se llama búsqueda externa.
4
Algoritmos Binarios
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:
Determinar si el elemento buscado se encuentra en el conjunto en el que se busca. Si el elemento
está en el conjunto, hallar la posición en la que se encuentra.
5
Técnica de Búsqueda Binaria.
Descripción de la técnica. Si los datos que se buscan están clasificados en un determinado orden, el método citado
anteriormente se denomina búsqueda binaria.
La búsqueda binaria utiliza un método de ‘divide y vencerás 'para localizar el valor deseado. Con
este método se examina primero el elemento central de la lista; si éste es el elemento buscado,
entonces la búsqueda ha terminado.
En caso contrario, se determinar si el elemento buscado será en la primera o la segunda mitad de
la lista y a continuación se repite este proceso, utilizando el elemento central de esa sub lista.
Se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda. Los
prerrequisitos principales para la búsqueda binaria son:
• La lista debe estar ordenada en un orden específico de acuerdo al valor de la llave.
• Debe conocerse el número de registros.
Algoritmo: 1. Se compara la llave buscada con la llave localizada al centro del arreglo.
2. Si la llave analizada corresponde a la buscada fin de búsqueda.
3. Si la llave buscada es menor que la analizada repetir proceso en mitad superior, sino en la
mitad inferior.
4. El proceso de partir por la mitad el arreglo se repite hasta encontrar el registro o hasta que
el tamaño de la lista restante sea cero , lo cual implica que el valor de la llave buscada no
está en la lista.
El esfuerzo máximo para este algoritmo es de log2n. El mínimo de 1 y en promedio ½ log2 n.
6
Ejemplo
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.
7
Ventajas de la técnica.
La búsqueda binaria es un método eficiente siempre que el vector esté ordenado. En la práctica,
esto suele suceder, pero no siempre. Por esta razón la búsqueda binaria exige una ordenación
previa del archivo
La búsqueda binaria proporciona un medio para reducir el tiempo requerido para buscar en una
lista. Este método, sin embargo, exige que los datos estén ordenados.
Es mas rápido por su recursividad, su mayor ventaja es con los archivos extensos.
El código del procedimiento de esta búsqueda es corto en comparación con las demás técnicas de
búsqueda.
En esencia, con una sola comparación eliminamos la mitad de la tabla; este es el método mas
eficiente de buscar en una lista ordenada sin emplear tablas o índices adicionales.
Desventajas de la técnica.
La búsqueda binaria tiene, sin embargo, inconvenientes a resaltar:
El archivo debe estar ordenado y el almacenamiento de un archivo ordenado suele plantear
problemas en las inserciones y eliminaciones de elementos.
No revisa todos los elementos del archivo, requiere que todos los elementos estén ordenados
Esta búsqueda mas de uno o dos accesos si el archivo es enorme; y mantener ese archivo
ordenado es muy costoso.
8
Principales Aplicaciones.
Ejemplo: Árbol Binario de Búsqueda: Se distinguen 2 casos triviales con solución directa: árbol vacío (elemento no encontrado) o raíz
del árbol.
Solución: Cuando el elemento no se encuentra en la raíz, dividimos el árbol en 2 subarboles (izquierda y
derecha) y aplicamos ABB, sobre aquel que nos interese (al estar ordenado solo debemos ir por
una de las ramas).
La combinación de resultados es trivial: la solución del subproblema es también la del problema
global.
Supongamos la lista:
1231
1473
1545
1834
1892
1898 elemento central
1983
2005
2446
2685
3200
9
Si está buscando el elemento 1983, se examina el número central 1898 en la sexta posición. Ya
que 1983 es mayor que 1898, se desprecia la primera sub lista y nos centramos en la segunda
1983
2005
2446 elemento central
2685
3200
El número central de esta sub lista es 2446 y el elemento buscado es 1983 menos que 2446;
eliminamos la segunda sub lista y nos queda
1983
2005
Como no hay término central elegimos el término inmediatamente anterior al término central,
1983, que es el buscado.
Se han necesitado tres comparaciones, mientras que la búsqueda secuencial hubiese necesitado
siete.
10
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 número
máximo de veces que se puede reducir a la mitad la cantidad de registros a considerar, hasta que
solo se tenga un elemento
11
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 más 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 número 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.
12
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).
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 número
reducido de operaciones aritméticas básicas.
No hay reglas que permitan determinar cuál será la función más 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:
Función Modulo: Se toma el resto de la división entre la clave y el numero de N de items.
Estadísticamente se puede verificar que para una mayor uniformidad en la distribución, N debe ser
un número primo, o al menos que sea divisible por pocos números. H(k) = (K mod N).Función
Cuadrado: Se eleva al cuadrado la clave y se toman los dígitos centrales como dirección. El número
de dígitos a tomar es determinado por el rango del índice (por ejemplo si tengo 100 índices, tomo
solo 2 dígitos). H(k) = dig_centrales(k^2).Sumatoria de valores ASCII: Se toma el resto entre la
sumatoria de los valores ASCII de la cadena de caracteres y el número N (tamaño de la tabla).
Como char es un valor entero que es como mucho 127, para valores de N grandes, se necesita que
las claves sean de una longitud considerable, de otra manera la distribución no va a ser uniforme.
Plegamiento: consiste en dividir el número en diferentes partes, y operar con ellas (normalmente
con suma o multiplicación). También se produce colisión. Por ejemplo, si se dividen los números
13
de 8 cifras en 3, 3 y 2 cifras y se suman, dará otro número de tres cifras (y si no, se cogen las tres
últimas cifras): 13000000 --> 130=130+000+00.
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 más 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.
Función Hashing - Método del residuo
El código que se le asigna a un estudiante de una universidad está 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 Ingeniería 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).
14
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.
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 más 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 = número 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
15
¿Cómo 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 más comunes para la resolución de colisiones.
16
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 número 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.
17
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 está llena en más 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 más 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.
18
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 está 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 qué momento aplicar el Re-Hash queda a criterio del programador, algunas posibilidades son:
Aplicar Re-hash cada vez que la tabla este llena en más de un 50%- Aplicar Re-hash solo cuando
una inserción falla- Aplicar Re-hash cuando el factor de carga l supera un valor estipulado.
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.
19
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 está 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.
20
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.
