TUGAS 07
SISTEM BERKAS
SISTEM BERKAS
ORGANISASI BERKAS
HASHING
Disusun Oleh :
Nama : Seprindo Adi Putra
Nim : 121051025
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)
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