Sabtu, 13 Juni 2015
TUGAS 07
SISTEM BERKAS
ORGANISASI
BERKAS HASHING
Disusun oleh :
Ardiansyah
(121051020)
JURUSAN TEKNIK INFORMATIKA
FAKULTAS TEKNOLOGI INDUSTRI
INSTITUT SAINS & TEKNOLOGI AKPRIND
YOGYAKARTA
2015
SOAL :
Diketahui:
Gunakanlah asumsi-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 menggunakan metode :
1. K MOD N
2. K MOD P
3. Midsquaring
4. Penjumlahan Digit
5. Multiplication
6. Trunction
7. Folding
8. Konversi Radix
Ditanyakan :
1. Penempatan nilai-nilai kunci
2. 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 :
#
|
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
|
1. K MOD N
Kunci : 111101, 111102, 111103, 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) , H(211103) => 6
H(221202) => 221202 MOD 6 = 0 (collision) , H(221202) => 4
H(221201) => 221201 MOD 6 = 5 (collision) , H(221201) => 3
H(222105) => 222105 MOD 6 = 3 (collision) , H(222105) => 2
· Kunci – kunci yang sama di collision-kan ke indeks terbesar yang masih kosong agar tidak terjadi penempatan kunci yang sama di dalam satu indeks yang sama.
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
Kunci : 111101, 111102, 111103, 221202, 221201, 222105
Alamat indeks 2 digit
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
|
K^2
|
H(K)
|
111101
|
12343432201
|
34
|
111102
|
12343654404
|
36
|
211103
|
44564476609
|
44
|
221202
|
48930324804
|
03
|
221201
|
48929882401
|
98
|
222105
|
49330631025
|
06
|
Penempatan nilai-nilai kunci :
Record
|
Kunci
|
0
|
…
|
…
|
…
|
03
|
221202
|
…
|
…
|
06
|
222105
|
…
|
…
|
34
|
111101
|
…
| |
36
|
111102
|
…
|
…
|
44
|
211103
|
…
|
…
|
98
|
221201
|
99
|
…
|
Rata-rata akses :
6 / 100 = 0,06
4. Penjumlahan Digit
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Alamat indeks 2 digit
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 (collision) , H(221201) => 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
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Alamat indeks 2 digit
Alamat indeks = 0 – 99
H(11101) = 11 | 11 | 01 11 * 01 = 11
H(11102) = 11 | 11 | 02 11 * 02 = 22
H(11103) = 22 | 11 | 03 22 * 03 = 63
H(21202) = 22 | 12 | 02 22 * 02 = 44
H(21201) = 22 | 12 | 01 22 * 01 = 22 (collision) => 99
H(22105) = 22 | 21 | 05 22 * 05 = 110 => 11 (collision) => 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
|
Pemotongan
|
H(K)
|
111101
|
111101
|
101
|
111102
|
111102
|
102
|
211103
|
211103
|
103
|
221202
|
221202
|
202
|
221201
|
221201
|
201
|
222105
|
222105
|
105
|
Penempatan nilai-nilai kunci :
Record
|
Kunci
|
0
|
…
|
…
|
…
|
101
|
111101
|
102
|
111102
|
103
|
211103
|
…
|
…
|
105
|
222105
|
…
|
…
|
201
|
221201
|
202
|
221202
|
…
|
…
|
999
|
…
|
Rata-rata akses :
6 /100 = 0,06
7. Folding
· Folding by boundary (non carry)
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Alamat indeksnya 2 digit.
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
Alamat indeksnya 2 digit
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
Alamat indeksnya 2 digit
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) , H(221201) => 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
Alamat indeksnya 2 digit
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) , H(221201) => 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
8. Konversi Radix
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Alamat indeksnya 7 digit
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
Penempatan Kunci :
Record
|
Kunci
|
0
|
…
|
…
|
…
|
813601
|
111101
|
813602
|
111102
|
…
|
…
|
1572978
|
211103
|
…
|
…
|
1623826
|
221201
|
1623827
|
221202
|
…
|
…
|
1626980
|
222105
|
…
|
…
|
9999999
|
Rata –rata akses = 6/10000000=0.0000006
