TUGAS 7
SISTEM BERKAS
“ORGANISASI BERKAS HASHING”
Oleh :
Disusun Oleh :
Nama : LILIK
NUGROHO
Nim : 121051118
JURUSAN TEKNIK INFORMATIKA
FAKULTAS TEKNOLOGI INDUSTRI
YAYASAN PEMBINA POTENSI PEMBANGUNAN
INSTITUT SAINS DAN TEKNOLOGI AKPRIND
YOGYAKARTA
2014 / 2015
Mata makalah ini akan menjelaskan teknik organisasi berkas menggunakan teknik hashing untuk soalnya seperti berikut :
SOAL
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 :
- K MOD N
- K MOD P
- Midsquaring
- Penjumlahan Digit
- Multiplication
- Trunction
- Folding
- Konversi Radix
Ditanya
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
|
- 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
Record
|
Kunci
|
Link
|
0
|
…
| |
…
|
…
| |
11
|
111101
|
98
|
…
|
…
| |
22
|
111102
|
99
|
…
|
…
| |
44
|
221202
| |
…
|
…
| |
63
|
211103
| |
…
|
…
| |
98
|
222105
| |
99
|
221201
|
Penempatan nilai-nilai kunci :
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
Record
|
Kunci
|
0
|
…
|
…
|
…
|
32
|
111101
|
…
|
…
|
42
|
111102
|
…
|
…
|
44
|
221201
|
…
|
…
|
53
|
211103
|
54
|
221202
|
…
|
…
|
93
|
222105
|
…
|
…
|
99
|
…
|
H(221201) => 22 | 12 | 01
=> 22 + 12 + 10
=> 44
H(222105) => 22 | 21 | 05
=> 22 + 21 + 50
=> 93
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
Indobd.com - Raja Bonus Judi Online Terpercaya
BalasHapusIndoBD.com Agen Bola Online-Dengan tampilan yang sederhana namun elegan, BDIndo.com Agen Bola Online Ternama dan Terpercaya hadir sebagai Agen Bola online profesional yang menjanjikan kepada membernya permainan aman dengan kualitas server yang nyaris tanpa gangguan. Bahkan fitur robot yang kerap kali ditemukan di situs bola online lain, bisa dipastikan tidak akan terdapat di situs ini. Hal ini dapat anda buktikan sendiri jika sudah menjadi member dan bermain disana. Jadi tingkat kecerdasan berpikir dan ketelian serta taktik bermain yang handal bisa menjadi daya dukung buat kamu yang memiliki keberuntungan. Beruntung belum tentu pintar, pintar belum tentu cerdas, namun orang cerdas adalah orang yang teliti dan taktis dalam setiap mengambil keputusan. Sedangkan untuk fitur bonus, BDIndo.com adalah rajanya bonus permainan online.
Hot Promo Spesial Indobd Hingga akhir Tahun :
-Bonus Rollingan casino hingga 0.8%
-Bonus Deposit New member Casino 10%
-Bonus Deposit Casino setiap kali deposit 5%
-Bonus Deposit 20% untuk Akun Bola
-Bonus Deposit 5% setiap kali Deposit untuk Akun Bola
-Bonus CAshback 7% untuk Akun Bola
-Bonus Referal 10%
-Bonus Cashback Casino 5%
Website Kami : http://www.indobd.com
Pin bbm : 557F872F
BANK SUPPORT : BCA | MANDIRI | BNI