Trabajo estructura de datos

ANDRES FELIPE HIGUERA MARTINEZ
LORENA VELANDIA MATEUS
INGENIERIA INDUSTRIAL
ESTRUCTURA DE DATOS

EJERCICIOS HASHING

1. Se desea almacenar información de los libros de una biblioteca:
Hay aproximadamente 20.000 libros. Con un tamaño máximo para 70.000 libros. Las búsquedas se hacen por código ISBN-10: + {99921-58-10-7, 9971-5-0210-0, 960-425-059-0, 80-902734-1-6, 85-359-0277-5,1-84356-028-3, 0-684-84328-5, 0-85131-041-9, 0-943396-04-2}
Resolver:
¿Cuál es el tamaño del espacio de llaves?
RTA: El tamaño es de 10 de los códigos de los libros es de ISBN-10 el tamaño de los dígitos es de 10.000.000.000

¿Cuál debería ser la capacidad del área primaria?
RTA: Son 20.000 libros con un tamaño máximo de 70.000
20.000 + / - (20%) = +24.000 / -16.000

Posible función dehashing : + h(ISBN) = (ISBN%20.000) + 1
RTA: Se toma el valor ISBN-10 y este a su vez se divide en 20.000 que es el número de libros, y el residuo de esto es el numero de la función hashing mas uno, se realiza la formulación en Excel para saber este residuo. Esa es la función hashing
ISBN
(ISBN %20000 + 1
9992158107
18108
9971502100
2101
9604250590
10591
8090273416
13417
85359027752776
1843560283
284
684843285
3286
851310419
10420
943396042
16043

¿Cuál es el factor de carga?
RTA: El factor de carga se obtiene de la división entre el tamaño y la capacidad del ejercicio dando un porcentaje el tamaño es de 10.000.000.000 y la capacidad del área primaria es de 24.000.
= 3*10-4 = 0.037%

Identificar las colisiones.
RTA:
Valor
N. colisión si-no
Dato %9992158107

8107
9971502100

2100
9604250590
1-si
40590
8090273416

23416
8535902775

32775
1843560283
1-si
40283
684843285

33285
851310419
1-si
40419
943396042

6042


2. Dado un arreglo de tamaño 17; inserta en una tabla hash los siguientes datos:
79, 24, 25, 38, 37, 26, 52, 27, 40, 50,33,11,25,17,66,43,84

¿Indicando qué datos tienen colisión?
RTA: El residuoente el dato y el tamaño del arreglo dan es dato de comparación para la colisión lineal






La inserción lineal de las colisiones
Valor
N.Colision si-no
=dato%17
79

11
24

7
25

8
38

4
37

3
26

9
52

1
27

10
40

6
50

16
33
si
16
33
1
0
11
si
11
11
1
12
25
=
8
17
si
0
17
1-si
1
17
2
2
66

15
43
si
9
43
1-si
10
43
2-si11
43
3-si
12
43
4
13
84
Si
16
84
1-si
0
84
2-si
1
84
3-si
2
84
4-si
3
84
5-si
4
84
6
5





La inserción exploración cuadrática de las colisiones
Valor
N.Colision
=dato%17
79

11
24

7
25

8
38

4
37

3
26

9
52

1
27

10
40

6
50

16
33
Si
16
33
1
0
11
Si
11
11
1
12
25
=
8
17
Si
0
17
1-si
1
17
2-si
417
3-si
9
17
4-si
16
17
5-si
8
17
6
2
66

15
43
Si
9
43
1-si
10
43
2-si
13
84
si
16
84
1-si
0
84
2-si
3
84
3-si
8
84
4-si
15
84
5-si
7
84
6-si
1
84
7
14





Resultado de la tabla hash
Posición
Lineal
Cuadrática
0
33
33
1
52
52
2
17
17
3
37
37
4
38
38
5
84

6
40
40
7
24
24
8
25
25
9
26
26
10
27
27
11
79
7912
11
11
13
43
43
14

84
15
66
66
16
50
50

3. Teniendo un arreglo de N=10 elementos, para facilidad del cálculo, pero recuerden que preferentemente N debe ser primo.
Insertar en una tabla Hash cuya función H(k)= clave% N los elementos 7,9,27,33,50,28,14,12,13,21
RTA: La función has es el numero por el tamaño
7 *%10= 7
9*%10= 9
27*%10= 7
33*%10= 3
50*%10= 0
28*%10=8
14*%10= 4
12*%10= 2
13*%10= 3
21*%10=1

Manejar las colisiones por:
Exploración lineal.

Valor
N.Colision si-no
=dato%10
7

7
9

9
27
Si
7
27
1
8
33

3
50

0
28
Si
8
28
1-si
9
28
2-si
0
28
3
1
14

4
12

2
13
Si
3
13
1-si
4
13
2
5
21
Si
1
21
1-si
2
21
2-si
3
21
3-si
4
21
4-si
5
21
5
6


Exploración cuadrática
Valor...