CONFERENCIA

TÉCNICAS DE ALMACENAMIENTO, RECUPERACIÓN Y MANTENIMIENTO DE INFORMACION EN ARCHIVOS DE ACCESO ALEATORIO POR MEDIO DE TRANSFORMACIONES ARITMÉTICAS(HASHING).

CONFERENCISTA

José Arturo Barreto Gutiérrez

Matemático. Universidad del Valle. Cali. Colombia

Master of Arts. Universidad de Texas. U. S. A.

DIRIGIDA A:

Estudiantes de cursos básicos y avanzados de programación, Técnicos superiores e Ingenieros de Sistemas.

MOTIVACIÓN

Todo estudiante de programación en las carreras de Ingeniería se familiariza con la producción de programas en lenguajes de bajo nivel, altamente portátiles, que se caracterizan porque corren en plataformas económicas, ya sea bajo Windows, UNIX o LINUX, en sistemas micro o mainframe. Estos lenguajes se caracterizan por que constan de un conjunto muy básico de instrucciones y funciones nativas. Un ejemplo de ello es el lenguaje C (ahora C++). Algunos más afortunados tienen acceso a Visual C o Visual Basic.

El alto costo de las licencias de los ambientes avanzados que corren bajo Windows, que además no garantizan portabilidad, invita a la producción de programas de aplicación en lenguajes de bajo nivel, disponibles en el ambiente universitario. Los programadores en C++ (C con clases) que no tienen acceso a un compilador pueden bajar gratuitamente una versión de C++ Builder, la cual suministra vía internet su propietario BORLAND. Otros compiladores de C++ se pueden bajar (Dev C, por ejemplo), buscando compiladores gratuitos de C vía ALTAVISTA.

Una confirmación del punto de vista sostenido en el párrafo anterior es el éxito obtenido en toda Latinoamérica por los sistemas SAINT, desarrollados originalmente en Maracaibo utilizando versiones compiladas del lenguaje PASCAL. Por ello SAINT corre en casi cualquier computador desde el MICRO hasta el MAINFRAME. Al no requerir recursos avanzados de software, sus versiones de bajo costo alejan a la piratería.

Tanta simplicidad tiene sus costos. Generalmente es necesario programar desde cero muchos procedimientos. Para ello en los cursos generales de programación se estudian las ESTRUCTURAS DE DATOS y su implementación.

La conferencia presenta un modelo que permite la creación y mantenimiento eficiente de BASES DE DATOS con dichos lenguajes, utilizando dos técnicas: HASHING o DESMENUZAMIENTO y LISTAS ENLAZADAS.

Se presentarán las ideas principales sin caer en la codificación, lo cual presupondría conocimientos del lenguaje, de tal manera que el participante que tenga mínima experiencia se motive a participar en cursos de especialización.

RESUMEN

La representación más común de un archivo es una lista, arreglo o tabla unidimensional. A continuación representamos una lista secuencial bidimensional en la cual la clave de acceso a los datos de cada persona es su cédula de identidad.

CLAVE DATO(S)

15625350	Hernández, Juan ...
5323482	Martínez, Pedro ...
...	...

Estas listas, pese a su simplicidad, presentan serios problemas a medida que crecen ya que para buscar, eliminar o modificar un dato, es necesaria una búsqueda secuencial de la clave que consume tiempo cuando la lista es muy grande, especialmente cuando se trata de almacenamiento en dispositivos físicos como los discos, cuya lectura es más lenta.

En estas listas existe una posición “física” (el sitio en memoria o disco donde comienza) y una posición lógica (el siguiente), que prácticamente es física ya que los elementos de la lista deben ser físicamente consecutivos,

LISTAS ENLAZADAS

En una lista enlazada, los elementos (no necesariamente físicamente consecutivos), se enlazan por medio de apuntadores (Ptr). Es así como los sistemas operativos manejan el espacio libre, el direccionamiento y hasta las eliminaciones en los dispositivos de disco.

Para aquellos que están familiarizados con las listas enlazadas presentamos los siguientes diagramas alusivos al tema:

Lista enlazada original:

Principio 1ro. 2do. Ultimo Fin

Eliminación de registro intermedio

Principio 1ro. 2do. Fin

Inserción de registro utilizando elemento libre

Principio 1ro.

Clave   Dato       Ptr

Clave   Dato       Ptr

Clave   Dato        Ptr

1ro.

2do. Ultimo Fin

Se presentarán de manera didáctica y por medio de un lenguaje gráfico semejante al anterior, algoritmos de inserción, búsqueda y eliminación de “registros” en una lista enlazada, sin aludir a un lenguaje de programación específico

Siguiendo un modelo similar se ejemplificará el manejo de espacios libres, complicándose ligeramente los diagramas, siguiendo el principio LIFO (Last In First Out). Nótese además que nuestros registros siempre se adicionan al comienzo de la lista, para evitar búsquedas innecesarias.

HASHING

Para terminar se ilustrará el método de HASHING o DEZMENUZAMIENTO por el cual a cada clave se le asigna una posición física a partir de una ARITMÉTICA EN MODULO o de RESIDUOS.

Generalmente las claves aparecen dispersas por provenir de datos externos, como sucedería si se quisiera almacenar información de los estudiantes de la Universidad Central (UCV), teniendo como clave el número de la cédula de identidad. Los números de cédula en este caso difieren notablemente entre diferentes personas, ya sea por la fecha en que obtuvieron su cédula (edad) o por el estado donde se emitió. Nuestro archivo no requeriría mas de 80000 registros pese a la dispersión de los números millonarios de las cédulas.

No tendría sentido tener una lista enlazada de miles o peor millones de registros. Nuestro método desmenuzará la información produciendo COLISIONES, que es el fenómeno por el cual nuestra función matemática asigna la misma dirección a ciertas claves diferentes. Cada colisión se resolverá en la misma lista enlazada. Nuestro archivo de datos consistirá entonces de un sinnúmero de listas enlazadas de longitud (número de registros) razonable.

Tanto al ingresar al archivo como al buscar un registro (estudiante) para consultar, modificar o eliminar, nuestro algoritmo consultará la función de desmenuzamiento (Hash) para saber en cual dirección comienza la lista enlazada correspondiente. Se utilizarán diagramas como el siguiente:

Lista enlazada 1

Cédula1

C.I.

C.I.

C.I.

Dirección- 1