La función módulo o por
división toma el residuo de
la división entre la clave y el total de elementos de la estructura,
generando la siguiente fórmula:
dirección = (clave % total elementos)
Para lograr una
mayor uniformidad en la distribución de los elementos, se debe buscar que el
valor que se usa en el total de
elementos sea un número primo más cercano al tamaño de la estructura.
Ejemplo. Si
tenemos un total de 100 elementos y dos claves que sean 7259 y 9359, las
direcciones generadas son las siguientes:
dirección = (7259%100) = 59
dirección = (9359%100) = 59
Estos dos casos
generan una colisión, ya que los dos números no se pueden asignar dentro de
la misma dirección en la estructura, para evitar la colisión, se cambia el
valor de 100 por el numero primo más cercano a él, en este caso seria un 97,
lo que generaría las siguientes direcciones:
dirección = (7259%97) = 81
dirección = (9359%97) = 47
La función cuadrada como su nombre lo indica eleva al
cuadrado la clave y del resultado, se toman los dígitos centrales como la
dirección. El número de dígitos a tomar se determina del por el rango del
índice de toda la estructura. La fórmula hash es la siguiente:
dirección = dígitos centrales (clave2)
Ejemplo. Si
tenemos un total de 100 elementos y dos claves que sean 7259 y 9359, las
direcciones generadas son las siguientes:
dirección = dígitos centrales (72592)
= 52693081 = 93
dirección = dígitos centrales (93592)
= 87590881 = 90
Como el rango de
claves es de 1 a 100 se toman dos dígitos centrales.
La función plegamiento divide la clave en partes de igual número
de dígitos (la última puede tener menos dígitos), tomando como dirección los
dígitos menos significativos, después de realizar una operación entre las
partes, ya sea una serie de sumas o de multiplicaciones. La fórmula seria la
siguiente:
dirección = dígitos menos
significativos (suma de partes)
dirección =
dígitos menos significativos (multiplicación de partes)
Ejemplo. Si
tenemos un total de 100 elementos y dos claves que sean 7259 y 9359, las
direcciones generadas son las siguientes:
dirección = dígitos
menos significativos (72 + 59) =
dígitos
menos significativos (131) = 31
dirección = dígitos
menos significativos (93 + 59) =
dígitos
menos significativos (152) = 52
Como el rango de
claves es de 1 a 100 se toman dos dígitos para las particiones y para la
dirección.
La función truncamiento toma algunos de los dígitos de las claves
y forma con ellos una dirección. La elección de los dígitos es arbitraria,
podrían tomarse los de las posiciones pares o impares para con ellos generar
la dirección donde se almacenara la clave, uniendo los dígitos de izquierda
a derecha o de derecha a izquierda, su fórmula es la siguiente:
dirección =
elegir dígitos (unión dígitos)
Ejemplo. Si
tenemos un total de 100 elementos y dos claves que sean 7259 y 9359, las
direcciones generadas son las siguientes:
dirección =
elegir dígitos (7, 5) = 75
dirección =
elegir dígitos (9, 5) = 95
Para este caso
se tomaron los dígitos impares y se unieron de izquierda a derecha.
Un método para
la solución de colisiones es tan importante como la función hash,
este método debe entrar en operación cuando la función hash asigna la misma
dirección a dos o mas claves diferentes.
Algunos de los
métodos para la solución de colisiones más utilizados son:
- Reasignación.
- Arreglos anidados.
- Encadenamiento.
El método de reasignación como su nombre lo indica consiste en
reasignar otra dirección de forma alternativa en caso de encontrar una
colisión, con alguno de los siguientes métodos:
- Prueba lineal.
- Prueba cuadrática.
- Doble dirección hash.
La prueba lineal consiste en recorrer la estructura
secuencialmente a partir del punto de colisión, hasta encontrar un lugar
vació, la estructura se debe controlar como una estructura circular, donde
el siguiente elemento después del último es el primero.
La prueba cuadrática es similar a la anterior, con la
diferencia de que la búsqueda de un lugar vació no se hace de forma
consecutiva, se genera a partir de la elevación de un valor al cuadrado,
donde ese valor inicia con el número 1 y lo suma a la dirección que se
encuentra en colisión (d+i2), si se genera nuevamente una
colisión el valor del número se incrementa, se eleva al cuadrado y se suma a
la dirección inicial (d+1, d+4, d+9, d+16, …, d+i2), este proceso
se repite hasta que se encuentre una dirección vacía. Está generación de
direcciones puede llegar a exceder el tamaño de la estructura, si es así, la
dirección inicia en uno y el valor inicial a elevar es el cero.
La doble dirección hash consiste en generar otra dirección hash,
una vez que se detecta la colisión, la generación de la nueva dirección se
hace a partir de la dirección previamente obtenida más uno. La función hash
que se aplique para generar la nueva dirección puede no ser la misma a la
utilizada en el proceso anterior, para esto no existe una regla establecida,
lo que permite utilizar cualquiera de las funciones hash conocidas hasta
ahora.
El método de arreglos anidados consiste en que cada elemento de la
estructura contenga otra estructura, en la cual se almacenen los elementos
colisionados. Generando con esto una estructura con dos dimensiones,
controlando en la primera dimensión los elementos iniciales y en la segunda
dimensión los colisionados. Esta alternativa genera otro problema mayor,
¿cuál debe ser el tamaño de la segunda estructura que controla la segunda
dimensión?
Ejemplo. Crear
una estructura que almacena 10 elementos que son: 15, 20, 24, 51, 71, 13,
16, 22, 46 y 69, y utiliza la función truncamiento tomando los dígitos
pares, ordenados de izquierda a derecha, la solución seria la siguiente:
Búsqueda
externa.
La búsqueda
externa es aquella en la que todos los elementos se encuentran almacenados
en un archivo, el cual se encuentra en un dispositivo de almacenamiento
secundario como un disco duro, una cinta o una memoria usb.
Los métodos de
búsqueda externa más importantes son:
- Secuencial.
- Binaria.
- Hash (transformación de claves)
Secuencial.
El método de búsqueda secuencial externa consiste en revisar el archivo
elemento por elemento hasta encontrar el dato que se esta buscando, o hasta
llegar al final del archivo. Este método de búsqueda se puede aplicar a
archivos ordenadas o desordenadas.
Si la búsqueda
se aplica a un archivo desordenado y el elemento que se está buscando existe
más de una vez, el proceso de búsqueda debe continuar hasta que se llegue al fin del archivo.
Ejercicios. Crear
un programa que genera N números aleatorios, los guarde en un archivo y
posteriormente aplique la búsqueda secuencial.
Si la búsqueda
se aplica a un archivo ordenado y el elemento que se está buscando existe
más de una vez, el proceso de búsqueda termina cunado el elemento del
archivo que se esta comparando es mayor que el que se esta buscando.
Ejercicios. Crear
un programa que genera N números aleatorios, los guarde en un archivo, los
ordene de forma ascendente y posteriormente aplique la búsqueda secuencial.
Binaria.
El método de búsqueda binaria externa utiliza el mismo principio que la
búsqueda binaria interna. Divide el total de elementos del archivo en dos,
comparando el elemento buscado con el central, en caso de no ser iguales se
determina si el elemento buscado es menor o mayor al central, para
determinar si la búsqueda continua del lado izquierdo (menor) o derecho
(mayor) del central, repitiendo el mismo proceso de división y comparación,
hasta encontrar el elemento buscado o que la división ya no sea posible.
El archivo debe
estar ordenado y se debe conocer el número de elementos del mismo para
aplicar este método.
Ejercicios. Crear
un programa que genera N números aleatorios, los guarde en un archivo y
posteriormente aplique la búsqueda binaria.
