TUGAS7
SISTEM
BERKAS
ORGANISASI BERKAS HASHING
Disusun
oleh :
NAMA :
WIRTO
NIM :
141051003
JURUSAN TEKNIK INFORMATIKA
FAKULTAS
TEKNOLOGI INDUSTRI
INSTITUT
SAINS & TEKNOLOGI AKPRIND
YOGYAKARTA
2016/2017
1.
Soal
·
Gunakanlah
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 metode
1. K MOD N
2. K MOD P
3. Midsquaring
4. Penjumlahan Digit
5. Multiplication
6. Trunction
7. Folding
8. Konversi Radix
·
Dengan
soal yaitu :
a. Penempatan
nilai-nilai kunci
b. 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 9 buah dengan 4 buah berbentuk huruf dan 5 buah berbentuk
angka
2. 4
buah yang berbentuk huruf menandakan jenis mata kuliah yang dikategorikan
kedalam kategori tertentu
3. Maka
dari itu saya mengasumsikan bahwa 4 buah huruf tersebut dikonversikan kedalam
suatu angka tertentu dimana itu sebagai patokan dalam penghitungan untuk
penempatan penyimpanan didalam memori
4. Yaitu
“IPBU” dalam asumsi saya, diganti dengan angka “1” dan “TIFS” diganti dengan
angka “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 penghitungan.
6. Sehingga
kuncinya menjadi :
#
|
Kode
|
Nama
|
Status
|
Sks
|
Smt
|
1
|
1 11101
|
Pancasila
|
W
|
2
|
1
|
2
|
1 11102
|
Agama
|
W
|
2
|
1
|
3
|
2 11103
|
Database
|
W
|
2
|
1
|
4
|
2 21202
|
Delphi
|
W
|
2
|
2
|
5
|
2 21201
|
Foxpro
|
W
|
2
|
2
|
6
|
2 22105
|
Pascal
|
W
|
2
|
2
|
a. 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
· Collision, ditempatkan pada indeks terbesar
yang masih kosong
→ 6 masih kosong, sehingga H(211103) → 6
· Home addres 5 diberi link ke 6
H(221202) →
221202 MOD 6 = 0
· Collision, ditempatkan 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, ditempatkan pada indeks terbesar
yang masih kosong
→ 3 masih kosong, sehingga H(221201) → 3
· Home address terahir 6 diberi link ke 3
H(222105) 222105
MOD 6 = 3
· Coliision, ditempatkan 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 = (6+2+3+4)/6 = 2.5
Ket
:
·
6
langkah penempatan kunci pada home address
·
2
langkah penempatan kunci 211103, 221202 (collision)
·
3 langkah
penempatan kunci 221201 (collision)
·
4
langkah penempatan kunci 222105 (collision)
b. K
MOD P
· H(K) = K MOD M
· Alamat indeks = 0 s/d M-1
Jawab :
Kunci = 111101, 111102, 211103, 221202,
221201, 222105
Pada kasus ini, saya hanya menyediakan lebar
alamat indeksnya 2 digit, sehingga 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
c. Midsquaring
Kunci = 111101, 111102, 211103, 221202,
221201, 222105
Pada kasus ini, saya hanya menyediakan lebar
alamat indeksnya 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
|
Penempatan kunci
Record
|
Kunci
|
0
|
…
|
…
|
…
|
03
|
221202
|
…
|
…
|
06
|
222105
|
…
|
…
|
34
|
111101
|
…
|
|
36
|
111102
|
…
|
…
|
44
|
211103
|
…
|
…
|
98
|
221201
|
99
|
…
|
Rata rata akses = 6/100 = 0.06
d. Penjumlahan
Digit
Kunci
= 111101, 111102, 211103, 221202, 221201, 222105
Pada
kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit sehingga
alamat indeks 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 diberi 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
Ket=
6 → langkah
penempatan setiap kunci pada home address
1 →
langkah penempatan kunci 221201 (collision)
e. Multiplication
Kunci
= 111101, 111102, 211103, 221202, 221201, 222105
Pada
kasus ini, saya hanya menyediakan lebar alamat indeksnya 2 digit sehingga alamat
indeks 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
Ket=
6 → langkah
penempatan setiap kunci pada home address
2 →
langkah penempatan kunci 221201, 222105 (collision)
f. Trunction
Kunci
= 111101, 111102, 211103, 221202, 221201, 222105
Pada
kasus ini, saya hanya menyediakan lebar alamat indeksnya 3 digit sehingga
alamat indeks dari 0-999
Pemotongan
pada 3 digit terahir
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
|
102
|
111102
|
103
|
211103
|
…
|
…
|
105
|
222105
|
…
|
…
|
201
|
221201
|
202
|
221202
|
…
|
…
|
…
|
…
|
…
|
…
|
999
|
…
|
Rata-rata
akses = 6/1000=0.006
g. Folding
· Folding by boundary (non carry)
Kunci = 111101, 111102, 211103, 221202,
221201, 222105
Pada kasus ini, saya hanya menyediakan lebar
alamat indeksnya 2 digit sehingga 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
Pada kasus ini, saya hanya menyediakan lebar
alamat indeksnya 2 digit sehingga 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
Pada kasus ini, saya hanya menyediakan lebar
alamat indeksnya 2 digit sehingga 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,
ditempatkan pada indeks terbesar yang masih kosong
·
99 masih
kosong, sehingga H(221201) 99
·
Home
address 35 diberi link ke 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
Pada kasus ini, saya hanya menyediakan lebar
alamat indeksnya 2 digit sehingga 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,
ditempatkan pada indeks terbesar yang masih kosong
·
99
masih kosong, sehingga H(221201) → 99
·
Home
address 35 diberi link ke 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)
h. Konversi
Radix
Kunci = 111101, 111102, 211103, 221202,
221201, 222105
Pada kasus ini, saya hanya menyediakan lebar
alamat indeksnya 7 digit sehingga 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
Record
|
Kunci
|
0
|
…
|
…
|
…
|
813601
|
111101
|
813602
|
111102
|
…
|
…
|
1572978
|
211103
|
…
|
…
|
1623826
|
221201
|
1623827
|
221202
|
…
|
…
|
1626980
|
222105
|
…
|
…
|
…
|
…
|
9999999
|
Rata
–rata akses = 6/10000000=0.0000006
0 Response to "Tugas 7 Sistem Berkas ORGANISASI BERKAS HASHING"
Post a Comment