GD - PRACTICO 0 - MODULO 0 - ARCHIVOS - Rev 2021

Vista previa del material en texto

JTP: Ing. Carlos Lemir – JTP: Ing. Daniel E. Ibarra – Comisiones: 3K1,3K2,3K3,3K4. Página de 
 
FFaaccuullttaadd RReeggiioonnaall 
TTuuccuummáánn 
UUnniivveerrssiiddaadd 
TTeeccnnoollóóggiiccaa NNaacciioonnaall 
 
AARRCCHHIIVVOOSS 
 
 
MMOODDUULLOO 00:: AArrcchhiivvooss HHaasshh.. 
 
GGeessttiióónn ddee DDaattooss -- DDeeppaarrttaammeennttoo SSiisstteemmaass 
 
 
 
1.- Defina que es un Archivo de Datos. ¿Para qué se usan los archivos de Datos? 
2.- Defina que es un Registro. ¿Cuál es la estructura de un registro? 
3.- Que es una Clave o Llave dentro de un Registro? ¿Cuál es su uso? 
4.- De un ejemplo de registros con al menos 4 atributos para los siguientes casos: Proveedores, Clientes de un 
banco, Artículos de Librería. Identifique claramente la Clave en cada caso 
5.- Origen de la palabra HASH. 
6.- Defina brevemente Tabla de datos. 
7.- Que operaciones se pueden realizar en un archivo? ¿En qué consiste la función buscar? 
8.- Archivos de acceso Directo: HASH. Defina que es un archivo HASH y su estructura. 
9.- Que es Hash y Hashing? 
10.- Que son las colisiones? 
11.- Para que se usan los archivos HASH? De ejemplos. 
12.- Ejercicios con Archivos HASH. 
12.1.- Se tiene la siguiente lista de diferentes calles de la ciudad de San Miguel de Tucumán: CANADÁ, 
COLOMBIA, PERÚ, CHILE, PARAGUAY, BRASIL, HAITÍ, PANAMÁ, SANTIAGO, MONTEAGUDO, MUÑECAS, 
MAIPÚ, SARMIENTO. Se desea organizar a la misma como un archivo con una estructura Hash con cuatro 
entradas, con la función hash “largo de la palabra MOD 4”. 
Se pide lo siguiente: 
12.1.1.- Se debe determinar la capacidad del bucket, sabiendo que el buffer de entrada/salida 
tiene una capacidad de 1024 bytes y el registro de cada calle ocupa 330 bytes. El puntero ocupa 
15 bytes. 
12.1.2.- Determinar el número de registros o slots por bucket. 
12.1.3.- Ingresar los datos en la estructura con técnica de desborde encadenada. Graficar la es-
tructura resultante. 
12.1.4.- Efectuar las siguientes operaciones, y graficar la estructura final resultante: 
12.1.4.1.- Eliminar el registro con clave MUÑECAS. 
12.1.4.2.- Añadir el registro con clave VENEZUELA. 
12.1.4.3.- Modificar la clave CHILE por CUBA. 
12.1.4.4.- Eliminar el registro con clave PANAMÁ. 
12.1.4.5.- Modificar la clave PERÚ por NICARAGUA. 
12.2.- Se tiene la siguiente lista de nombres de mujeres: Diana, Alicia, Claudia, Silvia, Patricia, Paola, 
Magda, Rocío, Martina, Helena, Elvira, Teresa, Ana, Gina, Silvana, Mariela, Malena. Cada nombre será 
considerado un registro de la tabla. Se desea organizar a la misma como un archivo con una estructura 
de tabla Hash con “NroReg” entradas, con la función hash “(Σ del valor de cada carácter del nom-
bre) Mod NroReg”. (NroReg = Tamaño de la tabla). 
 La siguiente tabla debe ser usada para la asignación de valores numéricos a caracteres alfabéticos: 
 
 
 
 
 
 
 
 
 
JTP: Ing. Carlos Lemir – JTP: Ing. Daniel E. Ibarra – Comisiones: 3K1,3K2,3K3,3K4. Página de 
 
 
FFaaccuullttaadd RReeggiioonnaall 
TTuuccuummáánn 
UUnniivveerrssiiddaadd 
TTeeccnnoollóóggiiccaa NNaacciioonnaall 
 
AARRCCHHIIVVOOSS 
 
 
PPrrááccttiiccoo:: AArrcchhiivvooss HHaasshh.. 
 
GGeessttiióónn ddee DDaattooss -- DDeeppaarrttaammeennttoo SSiisstteemmaass 
 
A b c D e F g h i j k l m n o p q r s t u v w x y z 
1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 
 
Se pide lo siguiente: 
12.2.1.- Ingresar los datos en la estructura con técnica de desborde encadenada. 
12.2.2.- Graficar la estructura resultante. 
 
Resolución : 
1,2,3 y 4: A desarrollar por el alumno consultado la teoría y bibliografía recomendada. 
5: El término hash proviene, aparentemente, de la analogía con el significado estándar en inglés de dicha pala-
bra en el mundo real: picar y mezclar. Donald Knuth indica que, aunque Hans Peter Luhn de IBM parece ser el 
primero que utilizó este concepto en 1953, el término sólo habría aparecido en la literatura a finales de los 60 del 
siglo XX. La aparición de la primera función hash data del año 1961. En ese entonces, Wesley Peterson creó la 
función Cyclic Redundancy Check (Comprobación de Redundancia Cíclica). Fue creada para comprobar cómo de 
correctos eran los datos transmitidos en redes (como Internet) y en el sistema de almacenamiento digital. Con la 
evolución de la informática y los computadores, estos sistemas se fueron especializando cada vez más. Esto per-
mitió crear nuevas y mejores funciones hash entre las que se pueden destacar: 
 MD2: es una de las primeras funciones hash criptográficas. Creada por Ronald Rivest, en el año de 1989. 
Con un alto nivel de eficiencia y seguridad para el momento, era fundamental en la seguridad de Inter-
net. Su consecuente evolución llevó a la creación de la función hash MD5. La cual es aún usada en am-
bientes donde la seguridad no es una alta prioridad. 
 RIPEMD: es una función hash criptográfica creada por el proyecto europeo RIPE en el año de 1992. Su 
principal función era la de sustituir al estándar del momento, la función hash MD4. En la actualidad aún 
se considera muy seguro, especialmente en sus versiones RIPEMD-160, RIPEMD-256 y RIPEMD-320. 
 SHA: el estándar actual de hashes criptográficos. Creada por la NSA en 1993, como parte de su proyecto 
interno para autentificar documentos electrónicos. SHA y sus derivadas son consideradas las funciones 
hash más seguras hasta el momento. Es de especial interés, SHA-256 por ser fundamental en la tecno-
logía que hizo posible el Bitcoin. 
6: Las tablas son agregados de componentes individuales llamados registros. Los registros son una entidad con 
una colección de datos asociados con nombres para establecer el tipo de información. Los registros en una tabla 
generalmente tienen asociada una clave y cada registro contiene información asociada con su clave. Así, puede 
decirse que los registros serían (k 1 ,I 1 ),(k 2 ,I 2 ),(k 3 ,I 3 ), ...(k j ,I j ), donde I i es la información asociada 
con la clave k i , para i = 1,2,...j 
7: Operaciones tales como: búsqueda, actualización, inserción, borrado y reportes se pueden realizar a una tabla. 
El proceso de buscar en una tabla consiste en un método sistemático para localizar la clave deseada, ki, de la 
cual deseamos conocer su información asociada. Es muy común que una tabla sea creada en memoria con límites 
definidos. 
 
 
 
 
 
 
 
 
JTP: Ing. Carlos Lemir – JTP: Ing. Daniel E. Ibarra – Comisiones: 3K1,3K2,3K3,3K4. Página de 
 
 
FFaaccuullttaadd RReeggiioonnaall 
TTuuccuummáánn 
UUnniivveerrssiiddaadd 
TTeeccnnoollóóggiiccaa NNaacciioonnaall 
 
AARRCCHHIIVVOOSS 
 
 
PPrrááccttiiccoo:: AArrcchhiivvooss HHaasshh.. 
 
GGeessttiióónn ddee DDaattooss -- DDeeppaarrttaammeennttoo SSiisstteemmaass 
 
 
 
8: Los ARCHIVOS HASH, también conocidos como ARCHIVOS DE ACCESO 
DIRECTO, consiste en particionar los registros mediante una función hash –
h(x)-que toma como argumento el valor de la clave y nos devuelve una direc-
ción de memoria denominada bucket o cubeta, donde esperamos encontrar a 
nuestro registro. 
Por razones técnicas (por ejemplo para hacer al archivo reubicable) normal-
mente a cada valor de la función hash h(x) se la asocia a una tabla hash, en 
donde cada una de sus entradas tiene asociado un puntero por el cual se accede al bucket o cubeta. 
 
9: Dada una tabla de tamaño N, y un conjunto S (S<=N) de claves con un rango M (N << M); la posición de una 
clave particular se determina transformando la clave en un entero que se halle entre 1 y N. El proceso de trans-
formación se llama Hashing y una transformación particular se llama hash. El hash de una clave es la posiciónque dicha clave va a ocupar en la tabla. 
La organización de datos en tablas busca una correspondencia entre la clave del registro y la dirección fí-
sica donde este se almacena. En este caso, la función hashing de la clave, define la posición del registro en la ta-
bla. La función hashing es una transformación que sirve como base para obtener una dirección. Las funciones 
más comunes son: Modulo, Digitos centrales, Doblaje, otras. 
 
10: En algunos casos, en un conjunto de claves, se puede llegar a dar que para por lo menos dos claves se tenga 
el mismo hash, entonces ocurre una colisión, el proceso de insertar la segunda (tercera, cuarta,.....) clave con el 
mismo hash, requiere la búsqueda de una nueva posición en la tabla, a este proceso se le llama rehashing. 
 
11: Las funciones hash se usan por ejemplo para proteger contraseñas, para garantizar la integridad de una des-
carga de datos, o para producir firmas digitales. No son propiamente métodos de encriptación, sino algoritmos. 
Por Ej.: Una de las utilidades podría ser la de proteger la confidencialidad de una contraseña, ya que podría estar 
en texto plano y ser accesible por cualquiera y aun así no poder ser capaces de deducirla. En este caso, para sa-
ber si una contraseña que está guardada, por ejemplo, en una base de datos es igual a la que hemos introducido, 
no se descifra el hash (ya que debería de ser imposible hacerlo) para hacer la comparación, sino que se aplicará 
la misma función de resumen a la contraseña que se introdujo por teclado, y se comparará el resultado con el 
que tenemos guardado. 
Pongamos un ejemplo, la función hash MD5 es una de estas funciones de resumen y la usaremos para 
resumir el siguiente texto: “Genbeta Dev” ingresado por teclado, y aplicaremos la “función” con el comando es-
pecifico que tienen la mayoría de sistemas basados en Linux (md5sum): 
 
 
 
 
 
 
 
 
 
 
JTP: Ing. Carlos Lemir – JTP: Ing. Daniel E. Ibarra – Comisiones: 3K1,3K2,3K3,3K4. Página de 
 
 
FFaaccuullttaadd RReeggiioonnaall 
TTuuccuummáánn 
UUnniivveerrssiiddaadd 
TTeeccnnoollóóggiiccaa NNaacciioonnaall 
 
AARRCCHHIIVVOOSS 
 
 
PPrrááccttiiccoo:: AArrcchhiivvooss HHaasshh.. 
 
GGeessttiióónn ddee DDaattooss -- DDeeppaarrttaammeennttoo SSiisstteemmaass 
 
 
Gdatos2020@ubuntu:~$ md5sum Genbeta Dev (enter) 
Resultado: 
b71dada304875838f0263e3ae50c2c49 
(Este es el valor que deberíamos comparar con el guardado en la base de datos.) 
12.1: 
12.1.1 y 12.1.2: Se divide la capacidad del buffer (1024 bytes) por el tamaño del registro (330 bytes), 
lo que nos da un resultado de 3 registros o slots por bucket, con un resto de 234 bytes. Se necesita 1 by-
tes para los 3 bits de lleno/vacio y 15 bytes para el puntero, lo que totaliza 16 bytes adicionales que ca-
ben perfectamente en los 34 bytes sobrantes. 
12.1.3: Aplicamos la función H(x) = “largo de la palabra MOD 4” a la lista de 13 elementos dada: CANA-
DÁ, COLOMBIA, PERÚ, CHILE, PARAGUAY, BRASIL, HAITÍ, PANAMÁ, SANTIAGO, MONTEAGUDO, MUÑE-
CAS, MAIPÚ, SARMIENTO, y damos ingreso a la tabla Con técnica de desborde encadenada. 
 
H(Canadá) 2 H(Brasil) 2 H(Muñecas) 3
H(Colombia) 0 H(Haití) 1 H(Maipú) 1
H(Perú) 0 H(Panamá) 2 H(Sarmiento) 1
H(Chile) 1 H(Santiago) 0
H(Paraguay) 0 H(Monteagudo) 2
 
 
0 1 1 1 COLOMBIA PERU PARAGUAY
1 1 0 0 SANTIAGO *
2 1 1 1 CHILE HAITI MAIPU
3 1 0 0 SARMIENTO *
1 1 1 CANADÁ BRASIL PANAMA
1 0 0 MONTEAGUDO *
1 0 0 MUÑECAS * 
 
12.1.4: Aplicar las siguientes operaciones: 
12.1.4.1.- Eliminar el registro con clave MUÑECAS. 
12.1.4.2.- Añadir el registro con clave VENEZUELA. 
12.1.4.3.- Modificar la clave CHILE por CUBA. 
0 1 1 1 COLOMBIA PERU PARAGUAY
1 1 1 0 SANTIAGO CUBA *
2 0 1 1 CHILE HAITI MAIPU
3 1 1 0 SARMIENTO VENEZUELA *
1 1 1 CANADÁ BRASIL PANAMA
1 0 0 MONTEAGUDO *
0 0 0 MUÑECAS * 
 
H(CUBA) 0
H(VENEZUELA) 1
 
 
 
 
 
 
 
JTP: Ing. Carlos Lemir – JTP: Ing. Daniel E. Ibarra – Comisiones: 3K1,3K2,3K3,3K4. Página de 
 
 
FFaaccuullttaadd RReeggiioonnaall 
TTuuccuummáánn 
UUnniivveerrssiiddaadd 
TTeeccnnoollóóggiiccaa NNaacciioonnaall 
 
AARRCCHHIIVVOOSS 
 
 
PPrrááccttiiccoo:: AArrcchhiivvooss HHaasshh.. 
 
GGeessttiióónn ddee DDaattooss -- DDeeppaarrttaammeennttoo SSiisstteemmaass 
 
 
12.1.4.4.- Eliminar el registro con clave PANAMÁ. 
12.1.4.5.- Modificar la clave PERÚ por NICARAGUA. 
0 1 0 1 COLOMBIA PERU PARAGUAY
1 1 1 0 SANTIAGO CUBA *
2 0 1 1 CHILE HAITI MAIPU
3 1 1 1 SARMIENTO VENEZUELA NICARAGUA *
1 1 0 CANADÁ BRASIL PANAMA
1 0 0 MONTEAGUDO *
0 0 0 MUÑECAS * 
 
12.2: A desarrollar por el alumno. Ejemplo de cálculo hash: 
Clave Método Hash 
Diana (4+9+1+5+1) Mod 17 3 
Alicia (1+7+9+3+9+1) Mod 17 13 
 
H(NICARAGUA) 1