Jawaban dan Soal Ujian Akhir Semester - Sistem Berkas:
<<SEMOGA BERMANFAAT>>
Monday, July 27, 2020
Sunday, July 26, 2020
TUGAS 7 SISTEM BERKAS
ORGANISASI BERKAS HASHING
Dibuat Oleh:
Nama : Cahiman
Nim : 171051004
*Soal:
Gunakan
asumsi-asumsi yang tepat untuk menjawab pertanyaan-pertanyaan berikut.
Mata_Kuliah.dbf
|
# |
Kode |
Nama |
Status |
SKS |
|
1 |
TFT 11101 |
Pancasila |
W |
2 |
|
2 |
TFT 11102 |
Agama |
W |
2 |
|
3 |
TFP 11103 |
KBD |
W |
3 |
|
4 |
TFP 21202 |
C++ |
W |
3 |
|
5 |
TFP 21201 |
Java |
W |
3 |
|
6 |
TFP 22105 |
Skripsi |
W |
6 |
*Disimpan :
1. K
MOD N
2. K
MOD P
3. Midsquaring
4. Penjumlahan
Digit
5. Multiplication
6. Trunction
7. Floding
by boundary non carry
8. Konversi
Radix
*Ditanyakan :
Penempatan
nilai-2 kunci
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 8 buah dengan 3 buah berbentuk huruf dan 5 buah berbentuk angka.
2. 3
buah yang berbentuk huruf menandakan jenis mata kuliah yang dikategorikan
kedalam kategori tertentu.
3. Maka
dari itu mengasumsikan bahwa 3 buah huruf tersebut dikonversikan kedalam suatu
angka tertentu dimana itu sebagai patokan dalam perhitungan untuk penempatan
penyimpanan didalam memori.
4. “TFT”
dalam ibaratkan angkat “1” dan “TFP” ibaratkan angkat “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 perhitungan.
6. Sehingga
hasilnya menjadi seperti berikut :
|
# |
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 21201 |
Java |
W |
3 |
|
6 |
2 22105 |
Skripsi |
W |
6 |
*Disimpan:
1.
K
MOD N
Kunci
: 111101, 111102, 211103, 221202, 221201,
222015
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, di tempatkan
pada indeks terbesar yang masih kosong
6 masih kosong, sehingga H (2111103) → 6
ü Home address 5
diberi link ke 6
H
(221202) → 221202 mod 6 = 0
ü Collision, di
tempatkan 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, di
tempatkan pada indeks terbesar yang masih kosong
3 masih kosong, sehingga H (221202) → 3
ü Home address
terakhir 6 diberi link ke 3
H
(222105) → 222105 MOD 6 = 3
ü Collision, di
tempatkan 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 = ( 2 + 3 + 4 + 6 ) / 6 = 2.5
Keterangan
: - 2 : langkah penempatan kunci 211103, 221202 ( collision )
- 3
: langkah penempatan kunci 221201 ( collision )
- 4 : langkah penempatan kunci
222105 ( collision )
- 6 :
langkah penempatan kunci pada home address
2.
K
MOD P
H
( K ) = K MOD M
Alamat
indeks = 0 s/d M-1
Jawab
:
Kunci
= 111101, 111102, 211103, 221202, 221201, 222105
Lebar
alamat indeks 2 digit, 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
3.
Midsquaring
Kunci
= 111101, 111102, 211103, 221202, 221201, 222105
Lebar
alamat indeks 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 |
|
Record |
Kunci |
|
0 |
... |
|
... |
... |
|
03 |
221202 |
|
... |
... |
|
06 |
222105 |
|
... |
... |
|
34 |
111101 |
|
|
... |
|
36 |
111102 |
|
... |
... |
|
44 |
211103 |
|
... |
... |
|
98 |
|
|
99 |
|
Rata-rata
akses = 6 / 100 = 0/06
4.
Penjumlahan
Digit
Kunci
= 111101, 111102, 211103, 221202, 221201, 222105
Alamat
indeks 2 digit 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 di beri 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
Keterangan
: - 6 : langkah penempatan setiap kunci
pada home address
- 1 : langkah penempatan kunci 221201 ( collision
)
5.
Multiplication
Kunci
= 111101, 111102, 211103, 221202, 221201, 222105
Lebar
alamat indeks 2 digit 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
Keterangan
: - 6 : langkah penempatan setiap
kunci pada home address
- 2 : langkah penempatan kunci 221201, 222105
(collision)
6.
Trunction
Kunci
= 111101, 111102, 211103, 221202, 221201, 222105
Lebar
alamat indeks 3 digit dari 0 – 999
Pemotongan pada 3 digit terakhir :
|
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 |
|
101 |
111102 |
|
103 |
211103 |
|
... |
... |
|
105 |
211105 |
|
... |
… |
|
201 |
221201 |
|
202 |
221202 |
|
... |
... |
|
... |
... |
|
... |
... |
|
999 |
… |
Rata-rata
akses = 6 / 1000 = 0.006
7.
Folding
by boundary non carry
Kunci
= 111101, 111102, 211103, 221202, 221201, 222105
Lebar
alamat indeks 2 digit 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
8. Konversi Radix
Kunci
= 111101, 111102, 211103, 221202, 221201, 222105
Lebar
alamat indeks 7 digit 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
<<SEMOGA BERMANFAAT>>
Subscribe to:
Posts (Atom)