Los más antiguos archivos de disco de acceso directo fueron utilizados por las maquinas electrónicas de contabilidad que utilizaban un número perforado en una tarjeta,para determinar en dónde debería archivarse el resto del contenido de la tarjeta. Los métodos modernos de acceso directo transforman la llave mediante un algoritmo de computación antes de utilizarla como dirección. El método de acceso directo es rápido, ya que se evitan las operaciones intermedias de archivo, pero obliga a que los datos se localicen dé acuerdo con un solo atributo llave. Puede compararse el acceso directo con un archivo secuencial indexado en el que el acceso se proporciona de acuerdo con un solo atributo; sin embargo, los registros dentro de los archivos directos no están eslabonados con sus registros predecesores o sucesores. Los métodos de archivo directo utilizan un cálculo para proporcionar la dirección de registro para una llave, mientras que las organizaciones de archivo indexado buscan en índices para determinar cuál es el registro correspondiente a una llave. ESTRUCTURA DE LOS ARCHIVOS DIRECTOS.
Un archivo relativo (directo) consiste en una colección de registros de longitud fija almacenados uno al lado del otro en un dispositivo de almacenamiento de acceso directo (direct - access storage device, DASD). El almacenamiento de este tipo de archivos se restringe a los DASD, tales como discos y tambores, por que el acceso a registros se hace generalmente en orden aleatorio.
Cada registro en un archivo de organización relativa se puede referir por mediode un número -entero- de dirección, el cual indica su distancia o desplazamiento desde el origen del archivo. Al primer registro en un archivo relativo se le asigna el valor 1, 2 al siguiente y así sucesivamente. De este modo, la dirección relativa de un valor entero que refleja su posición respecto al primer registro del archivo. El acceso aleatorio de un registro en un archivo de organización relativa se hace vía su número relativo de registro.
Un archivo de organización relativa puede crearse con un programa en un lenguaje de alto nivel si es que el método de acceso del sistema operativo central es capaz de manejar esta organización, y si el compilador del lenguaje de interface con tal método de acceso.
import java.io.*;
import javax.swing.*;
public class CrearArchivoAleatorio {
private static final int NUMERO_REGISTROS = 100;
// permitir al usuario seleccionar el archivo a abrir
private void crearArchivo()
{
// mostrar cuadro de diálogo para que el usuario pueda seleccionar el archivo
JFileChooser selectorArchivo = new JFileChooser();
selectorArchivo.setFileSelectionMode( JFileChooser.FILES_ONLY );
int resultado = selectorArchivo.showSaveDialog( null );
// si el usuario hizo clic en el botón Cancelar del cuadro de diálogo, regresar
if ( resultado == JFileChooser.CANCEL_OPTION )
return;
// obtener el archivo seleccionado
File nombreArchivo = selectorArchivo.getSelectedFile();
// mostrar error si el nombre del archivo es inválido
if ( nombreArchivo == null || nombreArchivo.getName().equals( "" ) )
JOptionPane.showMessageDialog( null, "Nombre de archivo incorrecto",
"Nombre de archivo incorrecto", JOptionPane.ERROR_MESSAGE );
else {
// abrir el archivo
try {
RandomAccessFile archivo =
new RandomAccessFile( nombreArchivo, "rw" );
RegistroCuentasAccesoAleatorio registroEnBlanco =
new RegistroCuentasAccesoAleatorio();
// escribir 100 registros en blanco
for ( int cuenta = 0; cuenta < NUMERO_REGISTROS; cuenta++ )
registroEnBlanco.escribir( archivo );
archivo.close(); // cerrar el archivo
// mostrar mensaje indicando que el archivo se creó
JOptionPane.showMessageDialog( null, "Se creó el archivo " +
nombreArchivo, "Estado", JOptionPane.INFORMATION_MESSAGE );
System.exit( 0 ); // terminar el programa
} // fin del bloque try
// procesar excepciones durante operaciones de apertura, escritura o cierre del archivo
catch ( IOException excepcionES ) {
JOptionPane.showMessageDialog( null, "Error al procesar el archivo",
"Error al procesar el archivo", JOptionPane.ERROR_MESSAGE );
System.exit( 1 );
}
} // fin de instrucción else
} // fin del método crearArchivo
public static void main( String args[] )
{
JDialog.setDefaultLookAndFeelDecorated(true);
CrearArchivoAleatorio aplicacion = new CrearArchivoAleatorio();
aplicacion.crearArchivo();
}
} // fin de la clase CrearArchivoAleatorio
convierte una clave en una dirección (índice) dentro del arreglo.
como la asignación de una misma dirección a dos o más claves distintas.
H(K) = elegirdigitos (d1,d2...dn) + 1
Función de hashing resistente a seudocolisiones: Una función de hashing es resistente a
y algún IV, tal que h(x) = z.
y algún IV, tal que h(x) = z.
import java.util.*;
import java.io.*;
/** CloseWords: Saca probecho de la tendencia a la aglomeración que * posee el método hashCode() de la clase String para buscar palabras "cercanas" * al argumento. */
public class CloseWords
{
Hashtable ht;
String currString;
/** En el código siguiente creamos una instancia de la clase Hashtable en la cual almacenaremos * nuestra lista de todas las palabras en el dicionario del sistema (si, es muy ineficiente * almacenar en memoria palabras mediante este indexado). * * @param args */
public static void main(String[] args)
{
ht = new Hashtable();
try
{
DataInputStream in = new DataInputStream(
new BufferedInputStream(
new FileInputStream("/usr/dict/words")));
while((currString = in.readLine())!=null)
ht.put(new Integer(currString.hashCode()), currString);
int i = args[0].hashCode();
int found=0;
while(found < 5)
{
i--;
if(ht.get(new Integer(i))!=null)
{
System.out.println(ht.get(new Integer(i)));
found++;
}
}
i = args[0].hashCode();
found=0;
while(found < 5)
{
i++;
if(ht.get(new Integer(i))!=null)
{
System.out.println(ht.get(new Integer(i)));
found++;
}
}
}
catch(IOException ioe)
{
System.out.println("IO Exception");
}
}
}
/** CloseWords: Saca probecho de la tendencia a la aglomeración que * posee el método hashCode() de la clase String para buscar palabras "cercanas" * al argumento. */
public class CloseWords
{
Hashtable ht;
String currString;
/** En el código siguiente creamos una instancia de la clase Hashtable en la cual almacenaremos * nuestra lista de todas las palabras en el dicionario del sistema (si, es muy ineficiente * almacenar en memoria palabras mediante este indexado). * * @param args */
public static void main(String[] args)
{
ht = new Hashtable();
try
{
DataInputStream in = new DataInputStream(
new BufferedInputStream(
new FileInputStream("/usr/dict/words")));
while((currString = in.readLine())!=null)
ht.put(new Integer(currString.hashCode()), currString);
int i = args[0].hashCode();
int found=0;
while(found < 5)
{
i--;
if(ht.get(new Integer(i))!=null)
{
System.out.println(ht.get(new Integer(i)));
found++;
}
}
i = args[0].hashCode();
found=0;
while(found < 5)
{
i++;
if(ht.get(new Integer(i))!=null)
{
System.out.println(ht.get(new Integer(i)));
found++;
}
}
}
catch(IOException ioe)
{
System.out.println("IO Exception");
}
}
}
/** En el código siguiente creamos una instancia de la clase Hashtable en la cual almacenaremos * nuestra lista de todas las palabras en el dicionario del sistema (si, es muy ineficiente * almacenar en memoria palabras mediante este indexado). * * @param args */
public static void main(String[] args)
{
ht = new Hashtable();
try
{
DataInputStream in = new DataInputStream(
new BufferedInputStream(
new FileInputStream("/usr/dict/words")));
while((currString = in.readLine())!=null)
ht.put(new Integer(currString.hashCode()), currString);
int i = args[0].hashCode();
int found=0;
while(found < 5)
{
i--;
if(ht.get(new Integer(i))!=null)
{
System.out.println(ht.get(new Integer(i)));
found++;
}
}
i = args[0].hashCode();
found=0;
while(found < 5)
{
i++;
if(ht.get(new Integer(i))!=null)
{
System.out.println(ht.get(new Integer(i)));
found++;
}
}
}
catch(IOException ioe)
{
System.out.println("IO Exception");
}
}
}
int i = args[0].hashCode();
int found=0;
while(found < 5)
{
i--;
if(ht.get(new Integer(i))!=null)
{
System.out.println(ht.get(new Integer(i)));
found++;
}
}
i = args[0].hashCode();
found=0;
while(found < 5)
{
i++;
if(ht.get(new Integer(i))!=null)
{
System.out.println(ht.get(new Integer(i)));
found++;
}
}
}
catch(IOException ioe)
{
System.out.println("IO Exception");
}
}
}
while(found < 5)
{
i--;
if(ht.get(new Integer(i))!=null)
{
System.out.println(ht.get(new Integer(i)));
found++;
}
}
i = args[0].hashCode();
found=0;
while(found < 5)
{
i++;
if(ht.get(new Integer(i))!=null)
{
System.out.println(ht.get(new Integer(i)));
found++;
}
}
}
catch(IOException ioe)
{
System.out.println("IO Exception");
}
}
}
while(found < 5)
{
i++;
if(ht.get(new Integer(i))!=null)
{
System.out.println(ht.get(new Integer(i)));
found++;
}
}
}
catch(IOException ioe)
{
System.out.println("IO Exception");
}
}
}
La clase
CrearArchivoAleatorio.java, que posee el método main, muestra un cuadro de dialogo que permite al usuario crear el archivo:FUNCIONES HASH Ó HASHING
El método llamado por transformación de claves (hash), permite aumentar la
velocidad de búsqueda sin necesidad de tener los elementos ordenados. Cuenta
también con la ventaja de que el tiempo de búsqueda es prácticamente
independiente del número de componentes del arreglo.
Trabaja basándose en una función de transformación o función hash (H) que
Cuando se tienen claves que no se corresponden con índices (p. ejem. por ser
alfanuméricas), o bien cuando las claves son valores numéricos muy grandes,
debe utilizarse una función hash que permita transformar la clave para obtener
una dirección apropiada. Esta función hash debe de ser simple de calcular y debe
de asignar direcciones de la manera mas uniforme posible. Es decir, dadas dos
claves diferentes debe generar posiciones diferentes. Si esto no ocurre
(H(K1)=d,H(K2)=d y K1K2), hay una colisión. Se define, entonces, una colisión
Función Módulo (por división)
Consiste en tomar el residuo de la división de la clave entre el numero de
componentes del arreglo.
La función hash queda definida por la siguiente formula:
H(K) = (K mod N) + 1
Se recomienda que N sea el numero primo inmediato inferior al numero total de
elementos.
Función Centro de Cuadrados
Consiste en elevar al cuadrado la clave y tomar los dígitos centrales como
dirección. El numero de dígitos a tomar queda determinado por el rango del índice.
La función hash que definida por la sig. formula:
Administración de Archivos Ing. Bruno López Takeyas
H(K) = digitos_centrales (K²) + 1
Función Plegamiento
Consiste en dividir la clave en partes de igual numero de dígitos (la ultima puede
tener menos dígitos) y operar con ellas, tomando como dirección los dígitos menos
significativos. La operación entre las partes puede hacerse por medio de sumas o
multiplicaciones. La función hash queda definida por la sig. formula:
H(K) = digmensig ((d1...di) + (di + 1...dj) + ... + (d1...dn)) + 1
Función Truncamiento
Consiste en tomar algunos dígitos de la clave y formar con ellos una dirección. La
función hash queda definida por la sig. fórmula:
Función de hashing resistente a colisiones: Una función de hashing es resistente a colisiones
si es computacionalmente no factible hallar un par de mensajes distintos x, x’ tal que h(x) =
h(x’). Hay dos variantes: con IV’s (initialization vectors) fijos (la habitual) o de IV aleatorio en
la cual uno de esos vectores puede variar libremente. Salvo que se indique lo contrario, nos
referiremos sólo a la variante con IV’s fijos. La complejidad de este ataque (IV fijo) contra un
hashing de n-bits es O(2n/2).
seudocolisiones si es computacionalmente no factible hallar un par de mensajes distintos x, x’
tal que h(x) = h(x’) en las cuales se puedan usar distintos IV’s para ambos mensajes x, x’.
Función de hashing resistente a seudopreimágenes: Una función de hashing es resistente a
seudopreimágenes si dado el digesto z es computacionalmente no factible hallar algún mensaje x
import java.lang.*;
