TUGAS 07
MAKALAH SISTEM BERKAS
ORGANISASI BERKAS HASHING
DISUSUN OLEH
Nama :
ALFIANDRI
NIM : 121051128
Mata Kuliah :
Sistem Berkas
Jurusan
Teknik Informatika
Fakultas Teknologi
Industri
Institut Sains dan
Teknologi AKPRIND
Yogyakarta
2015
SOAL :
Mata_Kuliah.dbf
|
#
|
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 :
1.
K MOD N
2.
K MOD P
3.
Midsquaring
4.
Penjumlahan Digit
5.
Multiplication
6.
Trunction
7.
Folding
8.
Konversi Radix
Ditanyakan :
Penempatan nilai-nilai kunci
Rata-rata akses
Penyelesaian :
Asumsi yang digunakan pada soal kali ini adalah penempatan kode mata kuliah
yang dijadikan kunci dalam penyimpanan dalam memori.
Kode mata kuliah tersebut memeliki asumsi sebagai berikut :
ü Terdiri dari 10
karakter, yaitu 4 huruf 1 spasi dan 5 angka.
ü Kita misalkan 4
huruf kode matakuliah tersebut merupakan patokan dalam penempatan penyimpanan
dalam memori. Misal IPBU = 1 dan TIFS = 2 dan spasi kita anggap tidak ada.
ü Sehingga kode
mata kuliah menjadi 6 karakter angka, dimana angka pertama merupakan hasil
permisalan konversi diatas.
Kemudian kunci pada table akan berubah seperti berikut :
Mata_Kuliah.dbf
|
#
|
Kode
|
Nama
|
Status
|
SKS
|
Smt
|
|
1
|
111101
|
Pancasila
|
W
|
2
|
1
|
|
2
|
111102
|
Agama
|
W
|
2
|
1
|
|
3
|
211103
|
Database
|
W
|
2
|
1
|
|
4
|
221202
|
Delphi
|
W
|
2
|
2
|
|
5
|
221201
|
Foxpro
|
W
|
2
|
2
|
|
6
|
222105
|
Pascal
|
W
|
2
|
2
|
JAWABAN
:
1.
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(collison)è 6
H(221202) = 221202 MOD 6 = 0(collison) è 4
H(221201) = 221201 MOD 6 = 5(collison) è 3
H(222105) = 222105 MOD 6 = 3(collicon) è 2
Penempatan
nilai-nilai kunci :
|
Record
|
Kunci
|
Link
|
|
0
|
111102
|
4
|
|
1
|
|
|
|
2
|
222105
|
|
|
3
|
221201
|
2
|
|
4
|
221202
|
|
|
5
|
111101
|
6
|
|
6
|
211103
|
3
|
Rata-rata akses :
6 / 7 = 0,86
2.
K MOD P
Alamat indeks 2
digit
Kunci : 111101 111102
211103 221202 221201
222105
a)
H(K) = K MOD M
M = 97
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,0618 =
0,062
b)
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,0618 =
0,062
3.
Midsquaring
Alamat indeks 2
digit
Kunci : 111101 111102
211103 221202 221201
222105
Alamat indeks = 0 - 99
|
K
|
111101
|
111102
|
211103
|
221202
|
221201
|
222105
|
|
K²
|
12343432201
|
12343654404
|
44564476609
|
48930324804
|
48929882401
|
49330631025
|
|
|
34
|
36
|
44
|
03
|
98
|
06
|
Penempatan nilai-nilai kunci :
|
Record
|
Kunci
|
|
0
|
|
|
...
|
|
|
3
|
221202
|
|
...
|
|
|
6
|
222105
|
|
...
|
|
|
34
|
111101
|
|
...
|
|
|
36
|
111102
|
|
...
|
|
|
44
|
211103
|
|
...
|
|
|
98
|
221201
|
|
99
|
|
Rata-rata akses :
6 / 100 = 0,06
4.
Penjumlahan Digit
Alamat indeks 2
digit
Kunci : 111101 111102
211103 221202 221201
222105
Alamat indeks = 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(collison) è 99
H(222105) = 22+21+05 =
48
Penempatan nilai-nilai kunci :
|
Record
|
Kunci
|
Link
|
|
0
|
|
|
|
...
|
|
|
|
23
|
111101
|
|
|
24
|
111102
|
|
|
...
|
|
|
|
35
|
211103
|
99
|
|
36
|
221202
|
|
|
...
|
|
|
|
48
|
222105
|
|
|
...
|
|
|
|
99
|
221201
|
|
Rata-rata akses :
6 / 100 = 0,06
5.
Multiplication
Alamat indeks 2
digit
Kunci : 111101 111102
211103 221202 221201
222105
Alamat indeks = 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(collison) è 99
H(222105) =22 | 21 | 05 22 * 05 = 110 è 11(collison) è 98
Penempatan nilai-nilai kunci :
|
Record
|
Kunci
|
Link
|
|
0
|
|
|
|
...
|
|
|
|
11
|
111101
|
98
|
|
...
|
|
|
|
22
|
111102
|
99
|
|
...
|
|
|
|
44
|
221202
|
|
|
...
|
|
|
|
63
|
211103
|
|
|
...
|
|
|
|
98
|
222105
|
|
|
99
|
221201
|
|
Rata-rata akses :
6 / 100 = 0,06
6.
Trunction
Pemotongan dilakukan
pada 3 digit terakhir
Kunci : 111101 111102
211103 221202 221201
222105
Alamat indeks = 0 – 999
|
K
|
111101
|
111102
|
211103
|
221202
|
221201
|
222105
|
|
H(K)
|
101
|
102
|
103
|
202
|
201
|
105
|
Penempatan nilai-nilai kunci :
|
Record
|
Kunci
|
|
0
|
|
|
...
|
|
|
101
|
11101
|
|
102
|
11102
|
|
103
|
11103
|
|
...
|
|
|
105
|
22105
|
|
...
|
|
|
201
|
21201
|
|
202
|
21202
|
|
...
|
|
|
999
|
|
Rata-rata akses :
6 /100 = 0,06
7.
Folding
Folding by boundary (non carry)
Alamat indeks 2 digit
Kunci : 111101 111102
211103 221202 221201
222105
Alamat indeks = 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
Penempatan nilai-nilai kunci :
|
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)
Alamat indeks 2 digit
Kunci : 111101 111102
211103 221202 221201
222105
Alamat indeks = 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
Penempatan nilai-nilai kunci :
|
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)
Alamat indeks 2 digit
Kunci : 111101 111102
211103 221202 221201
222105
Alamat indeks = 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(collison) è 99
H(222105) = 22 | 21 | 05
= 22 + 21 + 05 = 48
Penempatan nilai-nilai kunci :
|
Record
|
Kunci
|
Link
|
|
0
|
|
|
|
...
|
|
|
|
23
|
111101
|
|
|
24
|
111102
|
|
|
...
|
|
|
|
35
|
211103
|
99
|
|
36
|
221202
|
|
|
...
|
|
|
|
48
|
222105
|
|
|
...
|
|
|
|
99
|
221201
|
|
Rata-rata akses :
6 / 100 = 0,06
Folding by shifting (carry)
Alamat indeks 2 digit
Kunci : 111101 111102
211103 221202 221201
222105
Alamat indeks = 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(collison) è 99
H(222105) = 22 | 21 | 05
= 22 + 21 + 05 = 48
Penempatan nilai-nilai kunci :
|
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
8.
Konversi Radix
Alamat indeks 7 digit
Kunci : 111101 111102
211103 221202 221201
222105
Alamat indeks = 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
Penempatan nilai-nilai kunci :
|
Record
|
Kunci
|
|
0
|
|
|
...
|
|
|
813601
|
111101
|
|
813602
|
111102
|
|
...
|
|
|
1572978
|
211103
|
|
...
|
|
|
1623826
|
221201
|
|
1623827
|
221202
|
|
...
|
|
|
1626980
|
222105
|
|
...
|
|
|
9999999
|
|
Rata-rata akses :
6 / 10000000 = 0,0000006
0 komentar:
Posting Komentar