Tablas y Archivos De Acceso Directo

En los manejos de estos archivos comúnmente es menester conformar listas que tengan algún atributo en común o caracteristica, asi que para
llegar a un elemento que se encuentra en una posición determindada , es menester encontrar la cabeza de la lista, acceder al registro y asegurar que es el que deseamos. ahora si dicho elemento lamentablemente no es , tendremos que usar la direccion del siguiente elemento para traerlo a memoria principal y continuar asi hasta entcontrarlo o llegar elemento n-1 de la lista.

Podemos decir que la conformación de lista en archivos de acceso directo para buscar estos elementos no sera por supuesto la única razon, porque es necesario encadenar registros debido a las condicones de almacenamiento, sin necesidad que exista para ello una relación entre los campos de los registros.

Otro asunto a considerar es el empleo y uso de encadenamiento en tablas, que es similiar al manejo de ficheros; claro con la diferencia que si se encuentrar en memoria principal la lectura se pasa por alto.

Tambien como todos sabemos debemos recordar a los apuntadores o llanamente punteros , porque en los sistemas utlilizados anteriormente, las direcciones (ojo con eso), son absolutas, mientras que en las tablas y archivos son relativas y se expresan de forma diferente, por ejemplo
en el caso de las tablas se emplean los subindice y mediante estos se determina la ubicacion de cualquier campo.

Ahora bien una de las tecnicas mas reconocidas y usadas para archivos y tablas son los que se conocen como aleatorización o simplemente
Hash. Basicamente apartir de un campo de información , que actúa como clave de un registro, nos genera un número seudo-aletorio y mediante éste, se determina la posición del elemento en el medio de almacenamiento, si se dan cuenta actúa como un puntero ( índice) .

Permitiendo con ello establecer una relación clave-->posicion , por supuesto la posicion de almacenamiento. más adelante vamos hablar
de las Tecnicas de Aleatorizacion

TECNICAS DE ALEATORIZACION

Las tecnicas de aleatorizacion tienen por fin obtener un numero seudo-aletorio en un conjunto determinado de elemento con base en una clave. Ya que trabajamos con numeros es menester transformar dichos string en numeros. Se acuerdan del codigo ascii, una opcion puede
ser esa o bien asignar un número a cada letra .

Veamos un ejemplo:

XCOM

X = 58
C = 43
O = 4F
M = 4D

es decir hemos tomado el codigo ASCII del alias xcom ( me cambiare este alias..por cierto) y lo hemos pasado a una conversión hexadecimal. finalmente la clave XCOM tiene su correspondiente clave 58434F4D si! , ahora bien quitemos las letras 584344 o a base 10
88677977 o bien a binario(se las dejo a ustedes). En fin lo importante aqui que hemos convertido la palabra clave XCOM en un clave numerica en base al codigo ascii en representacion hexadecimal.

Ahora bien, el numero es grande comparada con el numero de posiciones que estan disponible en una tabla, y por cierto el caso mas obvio
es que nunca tengamos una relación uno a uno , debido a esto se debe reducir mediante las tecnicas de Hash.

Ejemplo :

La clave para los alumnos de la universidad es rut y el numero de alumnos es de alrededor de unos 900. Se hace menester convertir el numero de rut en un numero seudo -aletorio de 1 a 900 tal que :

J=ALETORIO(RUT)

Lo que indica que a partir de su rut se genera un numero seudo-aletorio J tal que

1<= J<=800

Podemos observar que dentro del conjunto algun J se repita, y eso como dijo el agente a neo es inevitalbe. Pues bien, no seremos neo
que nos meteremos a la matriz a volar y patear traseros para buscar alguna solución , para ello hay tecnicas que se muestran a continuación.

Metodo del Residuo

Para este metodo se toma la clave y se divide por el tamaño de la tabla o archivo y el residuo determina la posición relativia en la tabla o archivo. Normalmente para bajar el numero de sinonimos se escoge un numero primo que sea ligeramente menor que el tamaño de la tabla

Entonces
K=Mod(Clave/(M+1))

M tamaño de la tabla
K posicion dentro de la tabla , elementos que estan entre 0 y M-1

la funcion mod es conocida por todos y por supuesto java la ofrece.

Metodo de los cuadrados

Elevamos la clave al cuadrado, tomamos los del medio y se multiplican por un factor de conversión, con el objectivo siempre de ajustar la el tamaño de clave

Dada la clave 8253 encontrar su posicion en una tabla de tamaño 400

8253*8253=68112009
120*0.4= 48
48=Aleatorio(8253)

Metodo de defazamiento

Aqui vamos a desplazar los números externos de la clave sobre los centrales, se suman y se multiplican por un factor de conversión. Esta se puede utilizar cuando la clave es baste grande con respecto al tamanño de la tabla.

veamos un ejemplo:

483259782
4832
9782
= 7211 y este número obtenido lo multiplican por el factor de conversión

Metodo de cambio de base de los números

Esta tecnica es como conversión binaria , pero en vez de binaria vamos a tomar la base 11

ejemplo:

la clave 59582 generar el número seudo aletorio

5*11^4 + 9*11^3+5*11^2+8*11^1+2*11^0
finalmente el numero obtenido lo reducen por cualquiera de los metodos anteriores.

Método de la división de polinomios

En este caso:

P(x) Polinomio generado
Q(x) Polinomio previamente establecido
R(x) Polinomio residuo

asi que :

El polinomio P(x) se divide por un el Q(x), y nos genera el R(x) y apartir de los coeficinetes de R(x) multiplicamos por un factor de conversión
para generar la posición

A la izquierda situamos el dividendo. Si el polinomio no es completo dejamos huecos en los lugares que correspondan.

A la derecha situamos el divisor dentro de una caja.

Dividimos el primer monomio del dividendo entre el primer monomio del divisor.

Multiplicamos cada término del polinomio divisor por el resultado anterior y lo restamos del polinomio dividendo:

Volvemos a dividir el primer monomio del dividendo entre el primer monomio del divisor. Y el resultado lo multiplicamos por el divisor y lo restamos al dividendo.

Repetimos el proceso anterior hasta que el grado del resto sea menor que el grado del divisor, y por tanto no se puede continuar dividiendo.

Para comprobar si la operación es correcta, utilizaríamos la prueba de la división:

D = d · c + r

Ejemplo:

P(x)= 3x^5+5x^4+9x^3+8x^2+4x^1+9x^0
Q(x)=3x^3+2x^2+1x^1+2x^0
aplicando lo anterior

R(x)=x^2+5x^0

Ahora bien en el factor de conversion sera (0.7) la posicion de almacenamiento sera 73.

Pues bien si analizamos todos los métodos detenidamente ustedes van notar que la distribución del para almacenamiento de la tabla no será
de las mejores porque se va concentrar en algunos sitios de ella. Lo mejor en este caso , y con el objectivo de obtener una mejor aleatorización de los datos es que pueden combinar los métodos. eso nos dará una mejor distribución de los datos.

Por mucho que tengamos métodos especializados en aleatorización de los datos es inevitable encontrarse con repeticiones en las posiciones de las tablas y como dijo el agente a neo es inevitable. esto debido al cambio de intervalos. Asi como es inevitable hay
que buscar formas adecuadas para tratar dichos sinónimos.

Para ello podremos tratarlos en la misma area en que se trabajan los registros principales o se tenga una área especializada para éstos.
Cuando se posee una sola área para tratar el manejo de estas repeticiones, se usan funciones que determinen la posicion o mediantes métodos encadenados.

Metodos No Encadenamientos

Antes de hablar de los métodos encadenados, primeramente debemos hablar de los métodos no encadenados, vamos a suponer que tenemos una sola área (única) de almacenamiento. Entonces a partir del registro principal o sea la posición generada por el algoritmo de aleatorización se busca un espacio disponible para almacenar las repeticiones, para este caso se da un punto de inicio a partir del cual se pueden encontrar . Para mejorar el método, cuando se usa disco, se puede dejar espacios adicionales en la pista para el almacenamientos de estas repeticiones.

Otra alternativa es aplicar una función para que a partir de la posción generada por el algoritmo de aleatorización calcule las posiciones de los repeticiones (sinonimos). Existe difirentes funciones pero una de las que se puede aplicar es la siguiente

Ki+1=ki+ N/2-i

para i=0,1,2,3...N/2