Social Icons

twitter facebook google plusemail

Pages

Senin, 22 Juni 2015

Tugas VII Hashing



TUGAS 07
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

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

                               



               
                               






 
 
Blogger Templates