• Author / Uploaded
• ANDREA CAROLINA GOMEZ CAMELO

Citation preview

Equipo 3 Luis Miguel Castellanos

(Cód. 20162020084)

Iván Rodríguez Pineda

(Cód.20161020514)

Andrea Carolina Gómez Camelo

(Cód. 20171020038)

Taller funciones Hash 1. Descripción: Dada las siguientes claves: a = 48353 b = 63785 c = 95632 d = 47581 e = 19357 Crear un arreglo para 100 registros y utilizando las funciones hash: módulo, cuadrado, plegamiento, y truncamiento, guardarlos o insertarlos. NOTA: para la función que sea necesario ubicar la posición de los dígitos de la clave, manejar las posiciones pares, realizar todos los pasos para cada función. 2. Función hash módulo Para el uso de esta función, el número que discrimina el índice será el tamaño del arreglo, es decir, se aplica la función módulo a la clave según el tamaño del arreglo, al inicializar el arreglo se tomará que cada posición está vacía, aplicando dicha función a cada clave se obtiene: Clave a

Índice=48353 % 100=53 Clave b

Índice=63785 % 100=85 Clave c

Índice=95632 % 100=32

Clave d

Índice=47581 % 100=81 Clave e

Índice=19357 % 100=57 Ahora, después de obtener el índice en el cual irá cada clave y verificando que no haya colisiones entre las claves se procede a guardar o almacenar las claves en el arreglo, como resultado las parejas (índice, clave) del arreglo, tomando solo las que tienen una clave definida, quedaría así ordenadas según el valor del índice:

(32 , 95632) ,(53 , 48353),(57 , 19357),(81, 47581),(85 , 63785) 3. Función hash cuadrado Para esta función, en primer lugar se calcula el cuadrado de cada clave Clave a

cuadrado=483532=2338012609 Clave b

cuadrado=637852 =4068526225 Clave c

cuadrado=956322=9145479424 Clave d

cuadrado=475812=2263951561 Clave e

cuadrado=193572 =374693449 A partir de esto, el siguiente procedimiento será obtener el índice donde irá la clave, retirando un número de dos dígitos, de la mitad del cuadrado de cada clave, teniendo en cuenta que para cifras pares se toma el valor de la mitad de la longitud del cuadrado y su siguiente dígito, en caso de ser impar la longitud, se retira el dígito de la mitad y el elemento anterior, quedando así: Clave a

Índice=mitad (2338012609) Índice=2338 012609=01 Clave b

Índice=mitad (4068523225) Índice=4068 526225=52

Clave c

Índice=mitad (9145479424) Índice=9145 47 9424=47 Clave d

Índice=mitad (2263951561) Índice=2263 951561=95 Clave e

Índice=mitad (374693449) Índice=374 69 3449=69 Para finalizar se debe verificar que no haya colisiones entre las claves y luego almacenar en el arreglo, el resultado luego de ingresar las claves sería

( 1,48353 ) , ( 47,95632 ) , ( 52,63785 ) , ( 69,19357 ) ,(95,47581) 4. Función hash plegamiento Para la implementación de esta función procede a dividir cada clave en un grupos de a dos parejas comenzando de izquierda a derecha, en el caso de que las claves tengan una longitud impar el último grupo de dígitos será de 3; el resultado de este proceso en cada clave es el siguiente: Clave a

Agrupar (48353)=(48)(353) Clave b

Agrupar (63785)=(63)(785) Clave c

Agrupar (95632)=( 95)(632) Clave d

Agrupar (47581)=(47)(581) Clave e

Agrupar (19357)=(19)(357) Luego se procede a sumar los grupos de cada clave y ya que el resultado es mayor la cantidad de registros disponibles, se aplica el módulo para obtener un índice dentro de las dimensiones del arreglo: Clave a

Suma(48353)=( 48)+(353)=401 Índice=401 % 100=01 Clave b

Suma(63785)=(63)+(785)=848 Índice=848 % 100=48 Clave c

Suma(95632)=(95)+( 632)=727 Índice=727 % 100=27 Clave d

Suma(47581)=(47)+(581)=628 Índice=628 % 100=28 Clave e

Suma(19357)=(19)+(357)=376 Índice=376 % 100=76 Ahora se insertan los números dentro del arreglo, verificando previamente que no haya ningún tipo de colisión, entre los índices generados, resultando así:

( 1,48353 ) , ( 27,95632) , ( 28,47581 ) , ( 48,63785 ) ,(76,19357) 5. Función hash truncamiento Para esta última función, el procedimiento comienza con la selección de ciertos dígitos de la cada clave, según las especificaciones para este taller serán las posiciones pares de los

dígitos de la clave, se inicia el conteo de izquierda a derecha y se comienza desde 1 el conteo, por lo que para cada clave se obtiene lo siguiente: Clave a

Selección(48353)=4 8 3 5 3 Índice=85

Clave b

Selección(63785)=6 3 7 8 5 Índice=38 Clave c

Selección(95632)=9 5 6 3 2 Índice=53 Clave d

Selección(47581)=4 7 5 8 1 Índice=78 Clave e

Selección(19357)=1 9 3 57 Índice=95 Como con las anteriores funciones se verifica que no se presenten colisiones entre los índices generados y se pasa a insertar las claves en el arreglo, quedando así:

6. Comparación de resultados Ya con cada función aplicada se muestra a continuación el resultado de cada función para ver las diferencias de los índices generados en cada caso: ●

Función módulo

(32 , 95632) ,(53 , 48353),(57 , 19357),(81, 47581),(85 , 63785) ●

Función mitad cuadrado

( 1,48353 ) , ( 47,95632 ) , ( 52,63785 ) , ( 69,19357 ) ,(95,47581) ●

Función plegamiento

( 1,48353 ) , ( 27,95632) , ( 28,47581 ) , ( 48,63785 ) ,(76,19357) ●

Función truncamiento

( 38,63785 ) , (53,95632 ) , ( 78,47581 ) , ( 85,48353 ) ,(95,19357)