Sunday, June 19, 2016

Tugas 7 Sistem Berkas

10:40 AM    No comments

TUGAS 07
SISTEM BERKAS

ORGANISASI BERKAS HASHING



Disusun Oleh :
                         NAMA      : Elfrid Ticker Th
                         NIM          : 131051075

JURUSAN TEKNIK INFORMATIKA
FALKULTAS TEKNOLOGI INDUSTRI
INSTITUT SAINS & TEKNOLOGI AKPRIND
YOGYAKARTA
2016

KATA PENGANTAR
Puji dan syukur kami panjatkan kehadirat Tuhan Yang Maha Esa yang telah memberikan rahmatnya dan hidayah-Nya, sehingga kami dapat menyelesaikan tulisan ini dengan judul “Organisasi Berkas Hashing” dengan tepat waktu. Tulisan ini disusun untuk memenuhi syarat ketuntasan tugas Sistem Berkas di Institut Sains & Teknologi Akprind dan menambah wawasan kami tentang ini.
Kami ucapkan terima kasih untuk kepada pihak yang telah membantu kami agar tulisan ini dapat selesai, antara lain:
Bapak Edhy Sutanta, S.T., M.Kom., selaku dosen mata kuliah Sistem Berkas.
Berbagai pihak yang telah membantu.
Kami menyadari tulisan ini masih banyak kesalahan. Untuk itu kami mohon maaf dengan rendah hati. Kami bersedia menerima kritik saran yang bersifat membangun untuk memperbaiki kesalahan itu.
Yogyakarta 31 maret 2016


                                                                                                                   Elfrid Ticker Th








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

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)

       2.   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

       3.       Midsquaring
            Alamat indeks 2 digit
Kunci: 11101, 11102, 11103, 21202, 21201, 22105
            Alamat indeks=0-99
           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
      4.       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
           5.       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
           6.       Trunction
            Pemotongan dilakukan pada 3 digit terakhir
Kunci: 11101, 11102, 11103, 21202, 21201, 22105
            Alamat indeks=0-99
             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
     7.      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

            8.       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


Read More
Subscribe to: Posts (Atom)