Sunday 5 July 2015
Posted by Unknown |
TUGAS 07 SISTEM BERKAS
ORGANISASI BERKAS
HASHING
Disusun Oleh :
Nama : Muh. Dimas Eko P
Nim : 121051115
JURUSAN TEKNIK INFORMATIKA
FAKULTAS TEKNOLOGI INDUSTRI
INSTITUT SAINS & TEKNOLOGI AKPRIND
YOGYAKARTA
2015
FAKULTAS TEKNOLOGI INDUSTRI
INSTITUT SAINS & TEKNOLOGI AKPRIND
YOGYAKARTA
2015
· 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 * 155 + 1 * 154 + 1 * 153 + 1 * 152 + 0* 151 + 1* 150
è 813601
H(111102) è 1 * 155 + 1 * 154 + 1 * 153 + 1 * 152 + 0* 151 + 2* 150
è 813602
H(211103) è 2 * 155 + 1 * 154 + 1 * 153 + 1 * 152 + 0* 151 + 3* 150
è 1572978
H(221202) è 2 * 155 + 2 * 154 + 1 * 153 + 2 * 152 + 0* 151 + 2* 150
è 1623827
H(221201) è 2 * 155 + 2 * 154 + 1 * 153 + 2 * 152 + 0* 151 + 1* 150
è 1623826
H(222105) è 2 * 155 + 2 * 154 + 2 * 153 + 1 * 152 + 0* 151 + 5* 150
è 1626980
Record
|
Kunci
|
0
|
…
|
…
|
…
|
813601
|
111101
|
813602
|
111102
|
…
|
…
|
1572978
|
211103
|
…
|
…
|
1623826
|
221201
|
1623827
|
221202
|
…
|
…
|
1626980
|
222105
|
…
|
…
|
…
|
…
|
9999999
|
Rata –rata akses = 6/10000000=0.0000006
Subscribe to:
Posts (Atom)
