TUGAS
07
SISTEM BERKAS
ORGANISASI
BERKAS
HASHING
DISUSUN OLEH :
Nama :Dista
Putra Wijayanto
NIM :131051067
JURUSAN TEKNIK INFORMATIKA
FAKULTAS TEKNOLOGI INDUSTRI
INSTITUT
SAINS & TEKNOLOGI AKPRIND
YOGYAKARTA
2016
BERIKUT
PROSES PERHITUNGANNYA MENURUT YANG DITENTUKAN PADA SOAL:
Soal
|
#
|
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
|
Pertanyaan :
Selesaikan
soal diatas dengan menggunakan FUNGSI HASH sebagai berikut :
1. K MOD N
2.
K MOD P
3.
Midsquaring
4.
Penjumlahan
Digit
5.
Multiplication
6.
Trunction
7.
Folding
8.
Konversi Radix
Penyelesaian :
- 1 Asumsi yang digunakan pada soal kali ini adalah penempatan kode mata kuliah yang dijadikan kunci dalam penyimpanan dalam memori.
- 2 Kode mata kuliah tersebut memiliki asumsi sebagai berikut :
Terdiri dari 10 karakter, yaitu 4 huruf 1 spasi dan 5 angka.
- 3 Kita misalkan 4 huruf kode matakuliah tersebut merupakan patokan dalam penempatan penyimpanan dalam memori. Misal IPBU = 1 dan TIFS = 2 dan spasi kita anggap tidak ada.
- 4 Sehingga kode mata kuliah menjadi 6 karakter angka, dimana angka pertama merupakan hasil permisalan konversi diatas.
Disimpan:
1.
K MOD N
2.
K MOD P
3.
Midsquaring
4.
Penjumlahan Digit
5.
Multiplication
6.
Trunction
7.
Folding
8.
Konversi Radix
1
K MOD N
Ditanyakan:
Penempatan Nilai-2 kunci
Rata-rata akses
Dik: Nilai-2
kunci :
11101,
11102, 11103, 21202, 21201, 22105
Dit: Penempatan
nila-2 kunci dan Rata-rata akses
Jawab:
Kunci: 11101, 11102, 11103, 21202,
21201, 22105
N=6
P=7
LISCH (Late Insertion Standard Coalesced Hashing)
|
Record
|
Kunci
|
Link
|
|
0
|
||
|
1
|
11101
|
6
|
|
2
|
11102
|
|
|
3
|
11103
|
5
|
|
4
|
21202
|
|
|
5
|
22105
|
|
|
6
|
21201
|
Alamat indeks=0-6
H(11101)=11101 MOD 6=1
H(11102)=11102 MOD 6=2
H(11103)=11103 MOD 6=3
H(21202)=21202 MOD 6=4
H(21201)=21201 MOD 6=3 (collicon)->6
H(22105)=22105 MOD 6=1 (collicon)->5
Rata-rata akses nilai kunci:
(6+2)/6=1.33
Ket:
6->lkh penempatan kunci pd home address
2->lkh penempatan kunci 11101, 11103
(collision)
1
K MOD P
Alamat indeks 2 digit
Kunci: 11101, 11102, 11103, 21202,
21201, 22105
a)
H(K)=K MOD M
M=97
Alamat indeks=0-96
H(11101)= 11101 MOD 97=43
H(11102)= 11102 MOD 97=44
H(11103)= 11103 MOD 97=45
H(21202)= 21202 MOD 97=56
H(21201)= 21201 MOD 97=55
H(22105)= 22105 MOD 97=86
Penempatan nilai-nilai kunci
|
Record
|
Kunci
|
|
0
|
|
|
…
|
|
|
43
|
11101
|
|
44
|
11102
|
|
45
|
11103
|
|
…
|
|
|
55
|
21201
|
|
56
|
21202
|
|
…
|
|
|
86
|
22105
|
|
…
|
|
|
96
|
Rata-rata akses =6/97=0,0618= 0,062
b) H(K) = K MOD M + 1
M = 97
Alamat indeks =
1 – 97
H(11101)= 11101 MOD 97+1=44
H(11102)= 11102 MOD 97+1=45
H(11103)= 11103 MOD 97+1=46
H(21202)= 21202 MOD 97+1=57
H(21201)= 21201 MOD 97+1=56
H(22105)= 22105 MOD 97+1=87
Penempatan nilai-nilai kunci
|
Record
|
Kunci
|
|
1
|
|
|
…
|
|
|
44
|
11101
|
|
45
|
11102
|
|
46
|
11103
|
|
…
|
|
|
56
|
21201
|
|
57
|
21202
|
|
…
|
|
|
87
|
22105
|
|
…
|
|
|
97
|
Rata-rata akses =6/97=0,0618= 0,062
2
Midsquaring
Alamat indeks 2 digit
Kunci: 11101, 11102, 11103, 21202,
21201, 22105
Alamat indeks=0-99
|
K
|
11101
|
11102
|
11103
|
21202
|
21201
|
22105
|
|
K²
|
0123232201
|
0123254404
|
0123276609
|
0449524804
|
0449482401
|
0488631025
|
|
H(K)
|
23
|
25
|
27
|
52
|
48
|
63
|
Penempatan nilai kunci
|
Record
|
Kunci
|
|
0
|
|
|
…
|
|
|
23
|
11101
|
|
…
|
|
|
25
|
11102
|
|
..
|
|
|
27
|
11103
|
|
…
|
|
|
48
|
21201
|
|
…
|
|
|
52
|
21202
|
|
…
|
|
|
63
|
22105
|
|
…
|
|
|
99
|
Rata-rata akses= 6 / 100 = 0,06
3
Penjumlahan Digit
Alamat indeks 2 digit
Kunci:
11101, 11102, 11103, 21202, 21201, 22105
Alamat indeks=0-99
H(11101)= 1+11+01=13
H(11102)= 1+11+02=14
H(11103)= 1+11+03=15
H(21202)= 2+12+02=16
H(21201)= 2+12+01=15 (Collicon)->99
H(22105)= 2+21+05=28
Penempatan nilai kunci
|
Record
|
Kunci
|
Link
|
|
0
|
||
|
…
|
||
|
13
|
11101
|
|
|
14
|
11102
|
|
|
15
|
11103
|
99
|
|
16
|
21202
|
|
|
…
|
||
|
28
|
22105
|
|
|
…
|
||
|
99
|
21201
|
Rata-rata
akses= 6 / 100 = 0,06
4
Multiplication
Alamat indeks 2 digit
Kunci: 11101, 11102, 11103, 21202,
21201, 22105
Alamat indeks=0-99
H(11101)= 1 | 11 | 01 1*01=1
H(11102)= 1 | 10 | 02 1*02=2
H(11103)= 1 | 10 | 03 1*03=3
H(21202)= 2 | 12 | 02 2*02=4
H(21201)= 2 | 12 | 01 2*01=2 (Collicon)->99
H(22105)= 2 | 21 | 05 2*05=10
Penempatan nilai-nilai kunci
|
Record
|
Kunci
|
Link
|
|
0
|
||
|
…
|
||
|
1
|
11101
|
|
|
2
|
11102
|
99
|
|
3
|
11103
|
|
|
4
|
21202
|
|
|
…
|
||
|
10
|
22105
|
|
|
…
|
||
|
99
|
21201
|
Rata-rata
akses= 6 / 100 = 0,06
5
Trunction
Pemotongan dilakukan pada 3 digit
terakhir
Kunci: 11101, 11102, 11103, 21202,
21201, 22105
Alamat indeks=0-99
|
K
|
11101
|
11102
|
11103
|
21202
|
21201
|
22105
|
|
H(K)
|
101
|
102
|
103
|
202
|
201
|
105
|
Penempatan nilai-nilai kunci
|
Record
|
Kunci
|
|
0
|
|
|
…
|
|
|
101
|
11101
|
|
102
|
11102
|
|
103
|
11103
|
|
105
|
22105
|
|
…
|
|
|
201
|
21201
|
|
202
|
21202
|
|
999
|
Rata-rata
akses= 6 / 100 = 0,06
6
Folding
a) Folding by boundary (non
carry)
Alamat
indeks 2 digit
Kunci: 11101, 11102, 11103, 21202,
21201, 22105
Alamat
indeks=0-99
H(11101)= 1 | 11 | 01=10+11+10=31
H(11102)= 1 | 11 | 02=20+11+10=41
H(11103)= 1 | 11 | 03=30+11+10=51
H(21202)= 2 | 12 | 02=20+12+20=52
H(21201)= 2 | 12 | 01=10+12+20=42
H(22105)= 2 | 21 | 05=50+21+20=91
Penempatan
nilai kunci
|
Record
|
Kunci
|
|
0
|
|
|
…
|
|
|
31
|
11101
|
|
…
|
|
|
41
|
11102
|
|
42
|
21201
|
|
…
|
|
|
51
|
11103
|
|
52
|
21202
|
|
…
|
|
|
91
|
22105
|
|
…
|
|
|
99
|
Rata-rata
akses= 6 / 100 = 0,06
b) Folding by boundary (
carry)
Alamat
indeks 2 digit
Kunci: 11101, 11102, 11103, 21202,
21201, 22105
Alamat
indeks=0-99
H(11101)= 1 | 11 | 01=10+11+10=31
H(11102)= 1 | 11 | 02=20+11+10=41
H(11103)= 1 | 11 | 03=30+11+10=51
H(21202)= 2 | 12 | 02=20+12+20=52
H(21201)= 2 | 12 | 01=10+12+20=42
H(22105)= 2 | 21 | 05=50+21+20=91
Penempatan
nilai kunci
|
Record
|
Kunci
|
|
0
|
|
|
…
|
|
|
31
|
11101
|
|
…
|
|
|
41
|
11102
|
|
42
|
21201
|
|
…
|
|
|
51
|
11103
|
|
52
|
21202
|
|
…
|
|
|
91
|
22105
|
|
…
|
|
|
99
|
Rata-rata
akses= 6 / 100 = 0,06
c) Folding by shifting (non
carry)
Alamat indeks 2
digit
Kunci: 11101, 11102, 11103, 21202,
21201, 22105
Alamat
indeks=0-99
H(11101)= 1 | 11 | 01=13
H(11102)= 1 | 11 | 02=14
H(11103)= 1 | 11 | 03=15
H(21202)= 2 | 12 | 02=16
H(21201)= 2 | 12 | 01=15 (Collicon)->99
H(22105)= 2 | 21 | 05=28
Penempatan
nilai kunci
|
Record
|
Kunci
|
Link
|
|
0
|
||
|
…
|
||
|
13
|
11101
|
|
|
14
|
11102
|
|
|
15
|
11103
|
99
|
|
16
|
21202
|
|
|
…
|
||
|
28
|
22105
|
|
|
…
|
||
|
99
|
21201
|
Rata-rata
akses= 6 / 100 = 0,06
d) Folding by shifting (carry)
Alamat indeks 2
digit
Kunci: 11101, 11102, 11103, 21202,
21201, 22105
Alamat
indeks=0-99
H(11101)= 1 | 11 | 01=13
H(11102)= 1 | 11 | 02=14
H(11103)= 1 | 11 | 03=15
H(21202)= 2 | 12 | 02=16
H(21201)= 2 | 12 | 01=15 (Collicon)->99
H(22105)= 2 | 21 | 05=28
Penempatan
nilai kunci
|
Record
|
Kunci
|
Link
|
|
0
|
||
|
…
|
||
|
13
|
11101
|
|
|
14
|
11102
|
|
|
15
|
11103
|
99
|
|
16
|
21202
|
|
|
…
|
||
|
28
|
22105
|
|
|
…
|
||
|
99
|
21201
|
Rata-rata
akses= (6 +1)/ 100 = 0,07
7 Konversi Radix
Alamat indeks 7
digit
Kunci: 11101, 11102, 11103, 21202,
21201, 22105
Alamat
indeks=0-9999999
H(11101)=
1 * 154 + 1 * 15³ + 1 * 15² + 0* 15¹ + 1* 15ยบ
=54225
H(11102)= 1 * 154 + 1 * 153
+ 1 * 152 + 0* 151 + 2* 150
=54225
H(11103)= 1 * 154 + 1 * 153
+ 1 * 152 +0* 151 + 3* 150
=54225
H(21202)= 2 * 154 + 1 * 153
+ 2 * 152 + 0* 151 + 2* 150
=105075
H(21201)= 2 * 154 + 1 * 153
+ 2 * 152 + 0* 151 + 1* 150
=105075
H(22105)= 2 * 154 + 2 * 153
+ 1 * 152 + 0* 151 + 5* 150
=108225
Kunci: 11101, 11102, 11103, 21202,
21201, 22105
N=6
P=15
Alamat indeks=0-6
H(11101)=11101 MOD 15=1
H(11102)=11102 MOD 15=2
H(11103)=11103 MOD 15=3
H(21201)=21201 MOD 15=6
H(21202)=21202 MOD 15=7
H(22105)=22105 MOD 15=10
EISCH (Early Insertion Coalesced Hashing)
Penempatan
nilai kunci
|
Record
|
Kunci
|
|
0
|
|
|
...
|
|
|
54225
|
11101
|
|
54225
|
11102
|
|
54225
|
11103
|
|
…
|
|
|
...
|
|
|
105075
|
21201
|
|
105075
|
21202
|
|
...
|
|
|
108225
|
22105
|
|
9999999
|
Rata-rata akses
:
6
/ 10000000 = 0,0000006
