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
Titanium Hair Dye from IGT | Titanium Artists
BalasHapusBuy TITanium's TITE products in titanium necklace the oakley titanium sunglasses Apple Store or winnerwell titanium stove search citizen super titanium armor our wide range of TITE products for your iPhone or ford titanium iPad.