TUGAS 07
SISTEM BERKAS
SISTEM BERKAS
ORGANISASI BERKAS
HASHING
Disusun Oleh :
Nama: Adib Arwanda Kusuma
Nim: 121051072
JURUSAN TEKNIK INFORMATIKA
FAKULTAS TEKNOLOGI INDUSTRI
INSTITUT SAINS & TEKNOLOGI AKPRIND
YOGYAKARTA
2015
FAKULTAS TEKNOLOGI INDUSTRI
INSTITUT SAINS & TEKNOLOGI AKPRIND
YOGYAKARTA
2015
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
2.
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
|
111101
|
101
|
|
111102
|
111102
|
102
|
|
211103
|
211103
|
103
|
|
221202
|
221202
|
202
|
|
221201
|
221201
|
201
|
|
222105
|
222105
|
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)
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
