Estructura de datos

ARCHIVOS RELATIVOS
Los archivos relativos proveen acceso directo a un record de acuerdo a su dirección relativa.  Para poder lograr esto, los records están enumerados desde el 1 hasta la cantidad que se haya estimado.  El problema con esto es que no podemos utilizar ese número como campo clave, porque habría que separar los espacios de los records comenzando en uno.  Para poder almacenarlos,entonces recurrimos a utilizar una fórmula la cual convierte el record, a una dirección relativa en ese archivo.  Dicha fórmula se llama "hash functions" ó "key-to-address transforms". La figura 1 muestra como los records se almacenan en el "prime data area" de acuerdo a un "hash function" y si existe una colisión, el record se almacena en un area de "overflow".
(figura 1)
 
Para que el "Hashfunction" trabaje adecuadamente, debe tener los siguientes atributos:
1. Consistencia - Siempre debe dar el mismo valor relativo.
2. Fácil de codificar y eficiente para ejecutar -  Para poder aligerar el Input-Output del archivo.
3. Habilidad para ubicar un key a una dirección relativa -
4. Aplicabilidad Universal -
5. De muchos a uno cuando convierte el valor del key a una dirección relativa -6. Habilidad de minimizar las colisiones -
 
HASH FUNCTIONS
   Aqui procederemos a mencionar por lo menos 5 algoritmos de "Hashing" para poder conceptualizar el formato.
 
I. DIVISION-REMAINDER HASH FUNCTION
  Esta es la función que vamos a utilizar para el proyecto.  Sea K un key numérico entero y M el numero de localizaciones (buckets) en el prime data area.
   1. Escoja un entero divisorllamado Q.  Ese número debe ser lo mas cercano a la cantidad de buckets que tiene el archivo. (M)  Debe ser o un número primo ó un entero sin factores pequeños.  Un entero que sea divisible por pequeños números primos como lo son el 2, 3, 5, 7, 11 y 13 tienden a tener muchas colisiones.
   2. Hay que dividir K por Q.  El sobrante debe dar un entero entre 0 a Q - 1.  Ese sobrante puede usarsecomo "Relative Address".
Ejemplo:
SECUENCIA DE ENTRADA DEL KEY | KEY (K) | DIVISOR(Q) | RESIDUO |
1 | 4023 | 11 | 8 |
2 | 4031 | 11 | 5 |
3 | 4011 | 11 | 7 |
4 | 3971 | 11 | 0 |
5 | 3812 | 11 | 6 |
6 | 4214 | 11 | 1 |
7 | 4241 | 11 | 6 |
8 | 4146 | 11 | 10 |
II. MIDSQUARE HASH FUNCTION
  De nuevo, K es un KEY entero y M es el número de buckets que hay en el archivo.
  1. Seeleva el Key a la 2.  K2
  2. Se extraen del medio del resultado una cantidad de dígitos que tenga la misma magnitud del largo del archivo (digitos).
  3. Se comprime el resultado multiplicandolo por un factor de compresión.  En este caso es cantidad de  digitos sin usar/100 * cantidad de dígitos seleccionados.  En otras palabras 6 / 100 * 2.
  4. Se le suma el desplazamiento (si aplica).
Ejemplo:SECUENCIA DE ENTRADA DEL KEY | KEY (K) | KEY2 | PORCION DEL MEDIO | FACTOR DE COMPRESION(0.12) |
1 | 4023 | 16184529 | 84 | 10 |
2 | 4031 | 16248961 | 48 | 5 |
3 | 4011 | 16088121 | 88 | 10 |
4 | 3971 | 15768841 | 68 | 8 |
5 | 3812 | 14531344 | 31 | 3 |
6 | 4214 | 17757796 | 57 | 6 |
7 | 4241 | 17986081 | 86 | 10 |
8 | 4146 | 17189316 | 89 | 10 |
III. SHIFT-FOLDING HASHFUNCTION
  1. Divide el Key en tres partes.  Le incluye ceros a la derecha e izquierda de ser necesario.
  2. Suma esos tres dígitos y trunca si la cantidad de dígitios sobrepasa la del archivo.
  3. Multiplica por el factor de compresión (el mismo del anterior).
  4. Se le suma el desplazamiento (si aplica).
Ejemplo:
SECUENCIA DE ENTRADA DEL KEY | KEY (K) | KEYCOMPUESTO | SUMATORIA | FACTOR DECOMPRESION(0.12) |
1 | 4023 | 04 02 30 | 36 | 4 |
2 | 4031 | 04 03 10 | 17 | 2 |
3 | 4011 | 04 01 10 | 15 | 1 |
4 | 3971 | 03 97 10 | 110 | 1 |
5 | 3812 | 03 81 20 | 104 | 0 |
6 | 4214 | 04 21 40 | 65 | 7 |
7 | 4241 | 04 24 10 | 38 | 4 |
8 | 4146 | 04 14 60 | 78 | 9 |
IV. BOUNDARY-FOLDING HASH FUNCTION
  Es una variación de la anterior. 
  1. Divide el Key en tres partes.  Le...