Tugas 07 Sistem Berkas - Organisasi Berkas Hashing
TUGAS 07
SISTEM BERKAS
“ORGANISASI BERKAS HASHING”
SISTEM BERKAS
“ORGANISASI BERKAS HASHING”
Disusun Oleh :
Jeck Anderson (182052001)
Dosen Pengampu :
Edhy Sutanta, S.T., M.Kom.
JURUSAN TEKNIK INFORMATIKA
FAKULTAS TEKNOLOGI INDUSTRI
INSTITUT SAINS & TEKNOLOGI AKPRIND
YOGYAKARTA
2020
FAKULTAS TEKNOLOGI INDUSTRI
INSTITUT SAINS & TEKNOLOGI AKPRIND
YOGYAKARTA
2020
Soal
:
Gunakan asumsi-asumsi yang tepat untuk
menjawab pertanyaan pertanyaan berikut ini
Mata Kuliah.dbf
#
|
Kode
|
Nama
|
Status
|
SKS
|
1
|
TFT
11101
|
Pancasila
|
W
|
2
|
2
|
TFT
11102
|
Agama
|
W
|
2
|
3
|
TFT
11103
|
KBD
|
W
|
3
|
4
|
TFP
21202
|
C++
|
W
|
3
|
5
|
TFP
21021
|
Java
|
W
|
3
|
6
|
TFP
22105
|
Skripsi
|
W
|
6
|
Disimpan:
- K MOD N
- K MOD
- Midsquaring
- Penjumlahan Digit
- Multiplication
- Trunction
- Folding By Boundary Non Carry
- Konversi Radix
Ditanyakan
:
Penempatan nilai-nilai kunci dan Rata-rata
aksess
Penyelesaian
:
Pada kasus pertanyaan yang di atas
maka asumis untuk menyelesaikan kasus tersebut sebagain berikut :
Kode mata kuliah berjumlah 8 buah dengan 3 buah berbentuk huruf dan 5 buah berbentuk angka
Tiga buah berbentuk huruf menandakan jenis mata kuliah yang dikategorikan kedalam kategori tertentu
Maka dari itu disimpulkan 3 buah huruf tersebut dikonversikan kedalam suatu angka tertentu dimana sebagai patokan dalam penghitung untuk menempatkan penyimpanan didalam memori. IPBU diganti dengan angka 1 dan TIFS diganti dengan angka 2 dan jika ada kode lain maka menyesuaikan urutanya. Sehingga dalam perhitungan nanti menjadi 5 digit dengan asumsi digit pertama yang paling kiri adalah pengganti kode mata kuliah yang berbentuk huruf, yang digunakan untuk memudahkan dalam proses perhitungan.
Kode mata kuliah berjumlah 8 buah dengan 3 buah berbentuk huruf dan 5 buah berbentuk angka
Tiga buah berbentuk huruf menandakan jenis mata kuliah yang dikategorikan kedalam kategori tertentu
Maka dari itu disimpulkan 3 buah huruf tersebut dikonversikan kedalam suatu angka tertentu dimana sebagai patokan dalam penghitung untuk menempatkan penyimpanan didalam memori. IPBU diganti dengan angka 1 dan TIFS diganti dengan angka 2 dan jika ada kode lain maka menyesuaikan urutanya. Sehingga dalam perhitungan nanti menjadi 5 digit dengan asumsi digit pertama yang paling kiri adalah pengganti kode mata kuliah yang berbentuk huruf, yang digunakan untuk memudahkan dalam proses perhitungan.
Kuncinya menjadi
seperti ini
#
|
Kode
|
Nama
|
Status
|
SKS
|
1
|
1
11101
|
Pancasila
|
W
|
2
|
2
|
1
11102
|
Agama
|
W
|
2
|
3
|
2
11103
|
KBD
|
W
|
3
|
4
|
2
21202
|
C++
|
W
|
3
|
5
|
2
21021
|
Java
|
W
|
3
|
6
|
2
22105
|
Skripsi
|
W
|
6
|
1.
K MOD N
Kunci : 111101, 111102, 211103, 221202,
221021, 222105
N : 6 P: 6
Alamat Index: 0-6
H(111101)
=> 111101 MOD 6 = 5
H(111102) => 111102 MOD 6 = 0
H(211103) => 211103 MOD 6 = 5
H(221202) => 221202 MOD 6 = 0
H(221021) => 221021 MOD 6 = 5
H(222105) => 222105 MOD 6 = 3
H(111102) => 111102 MOD 6 = 0
H(211103) => 211103 MOD 6 = 5
H(221202) => 221202 MOD 6 = 0
H(221021) => 221021 MOD 6 = 5
H(222105) => 222105 MOD 6 = 3
Penempatan
nilai-nilai Kunci :
Record
|
Kunci
|
0
|
|
1
|
111101
|
2
|
111102
|
3
|
211103
|
4
|
221202
|
5
|
221021
|
6
|
222105
|
Rata-rata akses = 6 / 7 = 0,86
2.
K MOD P
H(K) = K MOD M
Alamat indeks = 0 s/d M-1
Jawab:
Kunci = 111101, 111102, 211103, 221202, 221021, 222105
Alamat index = 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(221021) => 221021 MOD 97 = 41
H(222105) => 222105 MOD 97 = 72
H(111102) => 111102 MOD 97 = 37
H(211103) => 211103 MOD 97 = 31
H(221202) => 221202 MOD 97 = 42
H(221021) => 221021 MOD 97 = 41
H(222105) => 222105 MOD 97 = 72
Penempatan
nilai-nilai kunci:
Record
|
Kunci
|
0
|
|
31
|
211103
|
36
|
111101
|
37
|
111102
|
41
|
111101
|
42
|
111102
|
72
|
222105
|
96
|
Rata –rata akses = 6/97 = 0.61
3.
Midsquaring
Kunci
= 111101,
111102, 211103, 221202, 221021, 222105
Penempatan
Kunci
Record
|
Kunci
|
0
|
|
03
|
111102
|
06
|
222105
|
34
|
111101
|
36
|
111102
|
44
|
211103
|
98
|
111101
|
96
|
Rata
rata akses = 6/100 = 0.06
4.
Penjumlahan Digit
Kunci = 111101, 111102, 211103, 221202, 221021, 222105
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
H(222105) è 22
+ 21 + 05 = 48
Record
|
Kunci
|
0
|
|
23
|
111101
|
24
|
111102
|
35
|
211103
|
36
|
221202
|
48
|
222105
|
99
|
111102
|
Rata-rata akses = (6+1)/100=0.07
5.
Multiplication
Kunci = 111101, 111102, 211103, 221202, 221021, 222105
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(221021) =>
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
98è99 masih kosong, sehingga H(222105)
Home address 11 diberi link ke 98
Record
|
Kunci
|
Link
|
0
|
||
11
|
111101
|
98
|
22
|
111102
|
99
|
44
|
221202
|
|
63
|
211103
|
|
98
|
222105
|
|
99
|
221202
|
Rata-rata akses = (6+2)/100=0.08
Keterangan :
6 => langkah
penempatan setiap kunci pada home address
2 => langkah penempatan
kunci 221202, 222105 (collision)
6.
Trunction
Kunci = 111101, 111102, 211103, 221202, 221021, 222105
Pemotongan pada 3 digit terakhir
K
|
Pemotongan
|
H(K)
|
111101
|
111101
|
101
|
111102
|
111102
|
102
|
211103
|
211103
|
103
|
221202
|
221202
|
202
|
221021
|
221021
|
021
|
222105
|
222105
|
105
|
Penempatan Kunci
Record
|
Kunci
|
0
|
|
101
|
111101
|
102
|
111102
|
103
|
211103
|
105
|
222105
|
201
|
111102
|
202
|
221202
|
999
|
Rata-rata akses = 6/1000=0.006
7.
Folding By
Boundary Non Carry
Kunci = 111101, 111102,
211103, 221202, 221021, 222105
2 digit sehingga alamat indeks = 0 – 99
H(011101) = 01 | 11 | 01 = 10 + 11 + 10 = 31
H(011102) = 01 | 11 | 02 = 10 + 11 + 20 = 41
H(111103) = 11 | 11 | 03 = 11 + 11 + 30 = 52
H(121202) = 12 | 12 | 02 = 21 + 12 + 20 = 53
H(121201) = 12 | 12 | 01 = 21 + 12 + 10 = 43
H(122105) = 12 | 21 | 05 = 12 + 21 + 50 = 83
2 digit sehingga alamat indeks = 0 – 99
H(011101) = 01 | 11 | 01 = 10 + 11 + 10 = 31
H(011102) = 01 | 11 | 02 = 10 + 11 + 20 = 41
H(111103) = 11 | 11 | 03 = 11 + 11 + 30 = 52
H(121202) = 12 | 12 | 02 = 21 + 12 + 20 = 53
H(121201) = 12 | 12 | 01 = 21 + 12 + 10 = 43
H(122105) = 12 | 21 | 05 = 12 + 21 + 50 = 83
Penempatan Kunci
Record
|
Kunci
|
0
|
|
31
|
011101
|
41
|
011102
|
43
|
221202
|
52
|
211103
|
53
|
221202
|
83
|
221202
|
99
|
Rata-rata akses: 6/100=0,06 detik
8.
Konversi Radix
Kunci = 111101, 111102, 211103, 221202, 221021, 222105
H(111101)
= 1 * 2^4 + 1 * 2^3 + 1 * 2^2 + 1 * 2^0 = 16+8+4+1 = 29
H(111102) = 1 * 2^4 + 1 * 2^3 + 1 *
2^2 + 2 * 2^0 = 16+8+4+2 = 30
H(211103) = 1 * 2^5 + 1 * 2^4 + 1
* 2^3 + 1 * 2^2 + 3* 2^0 = 32+16+8+4+3 = 63
H(221202) = 1 * 2^5 + 2 *
2^4 + 1 * 2^3 + 2 * 2^2 + 2 * 2^0 = 32+32+8+8+2 = 82
H(221021) = 1 * 2^5 + 2 *
2^4 + 1 * 2^3 + 2 * 2^2 + 1 * 2^0 = 32+32+8+8+1 = 81
H(222105) = 1 * 2^5 + 2 * 2^4 + 2 * 2^3 + 1 * 2^2 + 5 * 2^0 = 32+32+16+4+5 = 89
H(222105) = 1 * 2^5 + 2 * 2^4 + 2 * 2^3 + 1 * 2^2 + 5 * 2^0 = 32+32+16+4+5 = 89
Penempatan Kunci
Record
|
Kunci
|
0
|
|
813601
|
111101
|
813602
|
111102
|
1572978
|
211103
|
1623826
|
221021
|
1623827
|
221202
|
1626980
|
222105
|
9999999
|
Rata –rata akses = 6/10000000=0.0000006
0 Response to "Tugas 07 Sistem Berkas - Organisasi Berkas Hashing"
Post a Comment