Selasa, 07 Juli 2015

Tugas 07 Sistem Berkas

TUGAS 7
SISTEM BERKAS
“ORGANISASI BERKAS HASHING”

akprind-hitam

Oleh :

Disusun Oleh :
                         Nama     :              LILIK NUGROHO
                                                             Nim        :               121051118


JURUSAN TEKNIK INFORMATIKA
FAKULTAS TEKNOLOGI INDUSTRI
YAYASAN PEMBINA POTENSI PEMBANGUNAN
INSTITUT SAINS DAN TEKNOLOGI AKPRIND
YOGYAKARTA
2014 / 2015



Mata makalah ini akan menjelaskan teknik organisasi berkas menggunakan teknik hashing untuk soalnya seperti berikut :

SOAL
Gunakanlah asumsi-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 menggunakan metode :
  1. K MOD N
  2. K MOD P
  3. Midsquaring
  4. Penjumlahan Digit
  5. Multiplication
  6. Trunction
  7. Folding
  8. Konversi Radix

Ditanya
1.        Penempatan nilai-nilai kunci
2.        Rata-rata akses







Penyelesaian
Asumsi yang digunakan pada soal kali ini adalah penempatan kode mata kuliah yang dijadikan kunci dalam penyimpanan dalam memori. Kode mata kuliah tersebut memeliki asumsi sebagai berikut :
  • Terdiri dari 10 karakter, yaitu 4 huruf 1 spasi dan 5 angka.
  • 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.
  • Sehingga kode mata kuliah menjadi 6 karakter angka, dimana angka pertama merupakan hasil permisalan konversi diatas.
  • Kemudian kunci pada table akan berubah seperti berikut :

#
Kode
Nama
Status
SKS
Smt
1
111101
Pancasila
W
2
1
2
111102
Agama
W
2
1
3
211103
Database
W
2
1
4
221202
Delphi
W
2
2
5
221201
Foxpro
W
2
2
6
222105
Pascal
W
2
2

  1. K MOD N
Kunci : 111101, 111102, 111103, 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) , H(211103) => 6
H(221202) => 221202 MOD 6 = 0 (collision) , H(221202) => 4
H(221201) => 221201 MOD 6 = 5 (collision) , H(221201) => 3
H(222105) => 222105 MOD 6 = 3 (collision) , H(222105) => 2

  • Kunci – kunci yang sama di collision-kan ke indeks terbesar yang masih kosong agar tidak terjadi penempatan kunci yang sama di dalam satu indeks yang sama.

Penempatan nilai-nilai kunci :
Record
Kunci
Link
0
111102
4
1


2
222105

3
221201
2
4
221202

5
111101
6
6
211103
3

Rata-rata akses :
6 / 7 = 0,86

2.      K MOD P
Kunci :                        111101, 111102, 111103, 221202, 221201, 222105
Alamat indeks 2 digit
a)      H(K) = K MOD M
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,0618 = 0,062
b)     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,0618 = 0,062

3.      Midsquaring
Alamat indeks 2 digit
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Alamat indeks = 0 - 99
K
K^2
H(K)
111101
12343432201
34
111102
12343654404
36
211103
44564476609
44
221202
48930324804
03
221201
48929882401
98
222105
49330631025
06

Penempatan nilai-nilai kunci :
Record
Kunci
0
…
…
…
03
221202
…
…
06
222105
…
…
34
111101

…
36
111102
…
…
44
211103
…
…
98
221201
99
…

Rata-rata akses :
6 / 100 = 0,06

4.      Penjumlahan Digit
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Alamat indeks 2 digit
Alamat indeks = 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) , H(221201) => 99
H(222105) => 22 + 21 + 05 = 48
Penempatan nilai-nilai kunci :

Record
Kunci
Link
0
…

…
…

23
111101

24
111102

…
…

35
211103
99
36
221202

…
…

…
…

48
222105

…
…

…
…

…
…

99
221201



Rata-rata akses :
6 / 100 = 0,06

5.      Multiplication
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Alamat indeks 2 digit
Alamat indeks = 0 – 99
H(11101) = 11 | 11 | 01                       11 * 01 = 11
H(11102) = 11 | 11 | 02                       11 * 02 = 22
H(11103) = 22 | 11 | 03                       22 * 03 = 63
H(21202) = 22 | 12 | 02                       22 * 02 = 44
H(21201) = 22 | 12 | 01                       22 * 01 = 22 (collision) => 99
H(22105) = 22 | 21 | 05                       22 * 05 = 110 => 11 (collision) => 98
Record
Kunci
Link
0
…

…
…

11
111101
98
…
…

22
111102
99
…
…

44
221202

…
…

63
211103

…
…

98
222105

99
221201


Penempatan nilai-nilai kunci :
Rata-rata akses :
6 / 100 = 0,06











6.      Trunction
Pemotongan dilakukan pada 3 digit terakhir
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Alamat indeks = 0 – 999
K
Pemotongan
H(K)
111101
111101
101
111102
111102
102
211103
211103
103
221202
221202
202
221201
221201
201
222105
222105
105


Penempatan nilai-nilai kunci :
Record
Kunci
0
…
…
…
101
111101
102
111102
103
211103
…
…
105
222105
…
…
201
221201
202
221202
…
…
999
…
Rata-rata akses :
6 /100 = 0,06


7.      Folding
  • Folding by boundary (non carry)
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Alamat indeksnya 2 digit.
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
Alamat indeksnya 2 digit
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

Record
Kunci
0
…
…
…
32
111101
…
…
42
111102
…
…
44
221201
…
…
53
211103
54
221202
…
…
93
222105
…
…
99
…
H(221201) => 22 | 12 | 01
                  => 22 + 12 + 10
                  => 44
H(222105)            => 22 | 21 | 05
                        => 22 + 21 + 50
                        => 93
Rata-rata akses = 6/100=0.06

         Folding by shifting (non-carry)
Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Alamat indeksnya 2 digit
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) , H(221201) => 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
Alamat indeksnya 2 digit
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) , H(221201) => 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

8.      Konversi Radix

Kunci = 111101, 111102, 211103, 221202, 221201, 222105
Alamat indeksnya 7 digit
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

Penempatan Kunci :
Record
Kunci
0
…
…
…
813601
111101
813602
111102
…
…
1572978
211103
…
…
1623826
221201
1623827
221202
…
…
1626980
222105
…
…
9999999

Rata –rata akses = 6/10000000=0.0000006
Read More
Diposting oleh di 1 komentar:
Langganan: Postingan (Atom)