Tugas 7 sistem berkas (Hashing)

TUGAS 07
SISTEM BERKAS

ORGANISASI BERKAS
HASHING

Disusun Oleh :

Nama:             Indra Kurniawan

Nim:                131051015

JURUSAN TEKNIK INFORMATIKA
FAKULTAS TEKNOLOGI INDUSTRI
INSTITUT SAINS & TEKNOLOGI AKPRIND
YOGYAKARTA
2016

1.Soal

·         Gunakanlah asumsi yang tepat untuk menjawab pertanyaan-pertanyaan berikut :

#	Kode	Nama	Status	Sks	Smt
1	IPBU 11101	Pancasila	W	2	1
2	IPBU 11102	Agama	W	2	1
3	TIFS 11103	Database	W	2	1
4	TIFS 21202	Delphi	W	2	2
5	TIFS 21201	Foxpro	W	2	2
6	TIFS 22105	Pascal	w	2	2

·         Disimpan dengan metode

1.      K MOD N

2.      K MOD P

3.      Midsquaring

4.      Penjumlahan Digit

5.      Multiplication

6.      Trunction

7.      Folding

8.      Konversi Radix

·         Dengan soal yaitu :

a.       Penempatan nilai-nilai kunci

b.      Rata-rata akses

     Jawab

·         Asumsi yang saya gunakan pada kasus kode mata kuliah yang dijadikan kunci untuk penempatan penyimpanan didalam memori yaitu :

1.      Kode mata kuliah berjumlah 9 buah dengan 4 buah berbentuk huruf dan 5 buah berbentuk angka

2.      4 buah yang berbentuk huruf menandakan jenis mata kuliah yang dikategorikan kedalam kategori tertentu

3.      Maka dari itu saya mengasumsikan bahwa 4 buah huruf tersebut dikonversikan kedalam suatu angka tertentu dimana itu sebagai patokan dalam penghitungan untuk penempatan penyimpanan didalam memori

4.      Yaitu “IPBU” dalam asumsi saya, diganti dengan angka “1” dan “TIFS” diganti dengan angka “2” dan jika ada kode lain maka menyesuaikan urutannya

5.      Sehingga dalam perhitungan nanti menjadi 6 digit dengan asumsi digit pertama yang paling kiri adalah pengganti kode mata kuliah yang berbentuk huruf, yang digunakan untuk memudahkan dalam proses penghitungan.

6.      Sehingga kuncinya menjadi :

#	Kode	Nama	Status	Sks	Smt
1	1 11101	Pancasila	W	2	1
2	1 11102	Agama	W	2	1
3	2 11103	Database	W	2	1
4	2 21202	Delphi	W	2	2
5	2 21201	Foxpro	W	2	2
6	2 22105	Pascal	W	2	2

     a.      K MOD N

Kunci : 111101, 111102, 211103, 221202, 221201, 222105

N : 6

P : 7

Alamat indeks : 0-6

H(111101) è 111101 MOD 6 = 5 

H(111102) è 111102 MOD 6 = 0

H(211103) è 211103 MOD 6 = 5

·         Collision, ditempatkan pada indeks terbesar yang masih kosong

·         6 masih kosong, sehingga H(211103) è 6

·         Home addres 5 diberi link ke 6

H(221202) è 221202 MOD 6 = 0

·         Collision, ditempatkan pada indeks terbesar yang masih kosong

·         4 masih kosong, sehingga H(221202) è 4

·         Home address 0 diberi link ke 4

H(221201) è 221201 MOD 6 = 5

·         Collision, ditempatkan pada indeks terbesar yang masih kosong

·         3 masih kosong, sehingga H(221201) è 3

·         Home address terahir 6 diberi link ke 3

H(222105) è 222105 MOD 6 = 3

·         Coliision, ditempatkan pada indeks terbesar yang masih kosong

·         2 masih kosong, sehingga H(222105) è 2

·         Home address 3 diberi link ke 2

Pada K MOD N terdapat alamat kunci yang sama, sehingga diselesaikan dengan Collision agar tidak terjadi alamat kunci indeks yang sama, sehingga :

Record	Kunci	Link
0	111102	4
1
2	222105
3	221201	2
4	221202
5	111101	6
6	211103	3

Rata-rata akses = (6+2+3+4)/6 = 2.5

Ket :

·         6 langkah penempatan kunci pada home address

·         2 langkah penempatan kunci 211103, 221202 (collision)

·         3 langkah penempatan kunci 221201 (collision)

·         4 langkah penempatan kunci 222105 (collision)

      b.      K MOD P

·         H(K) = K MOD M

·         Alamat indeks = 0 s/d M-1

Jawab :

Kunci = 111101, 111102, 211103, 221202, 221201, 222105

Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit, sehingga M=97

Alamat indeks= 0 – 96

H(111101) è 111101 MOD 97 = 36

H(111102) è 111102 MOD 97 = 37

H(211103) è 211103 MOD 97 = 31

H(221202) è 221202 MOD 97 = 42

H(221201) è 221201 MOD 97 = 41

H(222105) è 222105 MOD 97 = 72

Penempatan nilai-nilai kunci :

Record	Kunci
0	…
…	…
31	211103
…	…
36	111101
37	111102
…	…
41	221201
42	221202
…	…
72	222105
…	…
…	…
96

Rata –rata akses = 6/97 = 0.61

·         H(K) = K MOD M+1

M=97

Alamat indeks = 1 – 97

H(111101) è 111101 MOD 97 + 1 = 37

H(111102) è 111102 MOD 97 + 1 = 38

H(211103) è 211103 MOD 97 + 1 = 32

H(221202) è 221202 MOD 97 + 1 = 43

H(221201) è 221201 MOD 97 + 1 = 42

H(222105) è 222105 MOD 97 + 1 = 73

Penempatan nilai-nilai kunci :

Record	Kunci
1	…
…	…
32	211103
…	…
37	111101
38	111102
…	…
42	221201
43	221202
…	…
73	222105
…	…
…	…
97

Rata –rata akses = 6/97 = 0.61

      c.       Midsquaring

Kunci = 111101, 111102, 211103, 221202, 221201, 222105

Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit

K	K^2	H(K)
111101	12343432201	34
111102	12343654404	36
211103	44564476609	44
221202	48930324804	03
221201	48929882401	98
222105	49330631025	06

Penempatan kunci

Record	Kunci
0	…
…	…
03	221202
…	…
06	222105
…	…
34	111101
	…
36	111102
…	…
44	211103
…	…
98	221201
99	…

Rata rata akses = 6/100 = 0.06

    d.      Penjumlahan Digit

Kunci = 111101, 111102, 211103, 221202, 221201, 222105

Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit sehingga alamat indeks dari 0-99

H(111101) è 11 + 11 + 01 = 23

H(111102) è 11 + 11 + 02 = 24

H(211103) è 21 + 11 + 03 = 35

H(221202) è 22 + 12 + 02 = 36

H(221201) è 22 + 12 + 01 = 35

·         Collision, ditempatkan pada indeks terbesar yang masih kosong

·         99 masih kosong, sehingga H(221201) è 99

·         Home address 35 diberi link ke 99

H(222105) è 22 + 21 + 05 = 48

Record	Kunci	Link
0	…
…	…
23	111101
24	111102
…	…
35	211103	99
36	221202
…	…
…	…
48	222105
…	…
…	…
…	…
99	221201

Rata-rata akses = (6+1)/100=0.07

Ket=

6 è langkah penempatan setiap kunci pada home address

1 è langkah penempatan kunci 221201 (collision)

    e.       Multiplication

Kunci = 111101, 111102, 211103, 221202, 221201, 222105

Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit sehingga alamat indeks dari 0-99

H(111101)       è 11 | 11 | 01

                        è 11 * 01

                        è 11

H(111102)       è 11 | 11 | 02

                        è 11 * 02

                        è 22

H(211103)       è 21 | 11 | 03

                        è 21 * 03

                        è 63

H(221202)       è 22 | 12 | 02

                        è 22 * 02

                        è 44

H(221201)       è 22 | 12 | 01

                        è 22 * 01

                        è 22

·         Collision, ditempatkan pada indeks terbesar yang masih kosong

·         99 masih kosong, sehingga H(221201) è 99

·         Home address 22 diberi link ke 99

H(222105)       è 22 | 21 | 05

                        è 22 * 05

                        è 110

                        è 11

·         Collision, ditempatkan pada indeks terbesar yang masih kosong

·         99 masih kosong, sehingga H(222105) è 98

·         Home address 11 diberi link ke 98

Record	Kunci	Link
0	…
…	…
11	111101	98
…	…
22	111102	99
…	…
…	…
44	221202
…	…
…	…
63	211103
…	…
98	222105
99	221201

Rata-rata akses = (6+2)/100=0.08

Ket=

6 è langkah penempatan setiap kunci pada home address

2 è langkah penempatan kunci 221201, 222105 (collision)

    f.       Trunction

Kunci = 111101, 111102, 211103, 221202, 221201, 222105

Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 3 digit sehingga alamat indeks dari 0-999

Pemotongan pada 3 digit terahir

K	Pemotongan	H(K)
111101	111 101	101
111102	111 102	102
211103	211 103	103
221202	221 202	202
221201	221 201	201
222105	222 105	105

Record	Kunci
0	…
…	…
101	111101
102	111102
103	211103
…	…
105	222105
…	…
201	221201
202	221202
…	…
…	…
…	…
999	…

Rata-rata akses = 6/1000=0.006 

    g.      Folding

·           Folding by boundary (non carry)

Kunci = 111101, 111102, 211103, 221202, 221201, 222105

Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit sehingga alamat indeks dari 0-99

H(111101)       è 11 | 11 | 01

                        è 11 + 11 + 10

                        è 32

H(111102)       è 11 | 11 | 02

                        è 11 + 11 + 20

                        è 42

H(211103)       è 21 | 11 | 03

                        è 12 + 11 + 30

                        è 53

H(221202)       è 22 | 12 | 02

                        è 22 + 12 + 20

                        è 54

H(221201)       è 22 | 12 | 01

                        è 22 + 12 + 10

                        è 44

H(222105) è 22 | 21 | 05

                        è 22 + 21 + 50

                        è 93

 

Record	Kunci
0	…
…	…
32	111101
…	…
42	111102
…	…
44	221201
…	…
53	211103
54	221202
…	…
93	222105
…	…
99	…

Rata-rata akses = 6/100=0.06

·         Folding by boundary (carry)

Kunci = 111101, 111102, 211103, 221202, 221201, 222105

Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit sehingga alamat indeks dari 0-99

H(111101)       è 11 | 11 | 01

                        è 11 + 11 + 10

                        è 32

H(111102)       è 11 | 11 | 02

                        è 11 + 11 + 20

                        è 42

H(211103)       è 21 | 11 | 03

                        è 12 + 11 + 30

                        è 53

H(221202)       è 22 | 12 | 02

                        è 22 + 12 + 20

                        è 54

H(221201)       è 22 | 12 | 01

                        è 22 + 12 + 10

                        è 44

H(222105) è 22 | 21 | 05

                        è 22 + 21 + 50

                        è 93

 

Record	Kunci
0	…
…	…
32	111101
…	…
42	111102
…	…
44	221201
…	…
53	211103
54	221202
…	…
93	222105
…	…
99	…

Rata-rata akses = 6/100=0.06

·         Folding by shifting (non-carry)

Kunci = 111101, 111102, 211103, 221202, 221201, 222105

Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit sehingga alamat indeks dari 0-99

H(111101)       è 11 | 11 | 01

                        è 11 + 11 + 01

                        è 23

H(111102)       è 11 | 11 | 02

                        è 11 + 11 + 02

                        è 24

H(211103)       è 21 | 11 | 03

                        è 21 + 11 + 03

                        è 35

H(221202)       è 22 | 12 | 02

                        è 22 + 12 + 02

                        è 36

H(221201)       è 22 | 12 | 01

                        è 22 + 12 + 01

                        è 35

ð  Collision, ditempatkan pada indeks terbesar yang masih kosong

ð  99 masih kosong, sehingga H(221201) è 99

ð  Home address 35 diberi link ke 99

H(222105) è 22 | 21 | 05

                        è 22 + 21 + 05

                        è 48

Record	Kunci	Link
0	…
…	…
23	111101
24	111102
…	…
…	…
35	211103	99
36	221202
…	…
48	222105
…	…
…	…
…	…
99	221201

Rata-rata akses = (6+1)/100=0.07

Ket=

6 è langkah penempatan setiap kunci pada home address

1 è langkah penempatan kunci 221201 (collision)

·         Folding by shifting (carry)

Kunci = 111101, 111102, 211103, 221202, 221201, 222105

Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit sehingga alamat indeks dari 0-99

H(111101)       è 11 | 11 | 01

                        è 11 + 11 + 01

                        è 23

H(111102)       è 11 | 11 | 02

                        è 11 + 11 + 02

                        è 24

H(211103)       è 21 | 11 | 03

                        è 21 + 11 + 03

                        è 35

H(221202)       è 22 | 12 | 02

                        è 22 + 12 + 02

                        è 36

H(221201)       è 22 | 12 | 01

                        è 22 + 12 + 01

                        è 35

ð  Collision, ditempatkan pada indeks terbesar yang masih kosong

ð  99 masih kosong, sehingga H(221201) è 99

ð  Home address 35 diberi link ke 99

H(222105) è 22 | 21 | 05

                        è 22 + 21 + 05

                        è 48

Record	Kunci	Link
0	…
…	…
23	111101
24	111102
…	…
…	…
35	211103	99
36	221202
…	…
48	222105
…	…
…	…
…	…
99	221201

Rata-rata akses = (6+1)/100=0.07

Ket=

6 è langkah penempatan setiap kunci pada home address

1        è langkah penempatan kunci 221201 (collision) 

     h.      Konversi Radix

Kunci = 111101, 111102, 211103, 221202, 221201, 222105

Pada kasus ini, saya hanya menyediakan lebar alamat indeksnya 7 digit sehingga alamat indeks dari 0-9999999

H(111101)       è 1 * 15⁵ + 1 * 15⁴ + 1 * 15³ + 1 * 15² + 0* 15¹ + 1* 15⁰

                                    è 813601

H(111102)       è 1 * 15⁵ + 1 * 15⁴ + 1 * 15³ + 1 * 15² + 0* 15¹ + 2* 15⁰

                                    è 813602

H(211103)       è 2 * 15⁵ + 1 * 15⁴ + 1 * 15³ + 1 * 15² + 0* 15¹ + 3* 15⁰

                                    è 1572978

H(221202)       è 2 * 15⁵ + 2 * 15⁴ + 1 * 15³ + 2 * 15² + 0* 15¹ + 2* 15⁰

                                    è 1623827

H(221201)       è 2 * 15⁵ + 2 * 15⁴ + 1 * 15³ + 2 * 15² + 0* 15¹ + 1* 15⁰

                                    è 1623826

H(222105) è 2 * 15⁵ + 2 * 15⁴ + 2 * 15³ + 1 * 15² + 0* 15¹ + 5* 15⁰

                                    è 1626980

Record	Kunci
0	…
…	…
813601	111101
813602	111102
…	…
1572978	211103
…	…
1623826	221201
1623827	221202
…	…
1626980	222105
…	…
…	…
9999999

Rata –rata akses = 6/10000000=0.0000006