Institut Sains Dan Teknologi Akprind Yogyakarta

Yogyakarta Indonesia

Sumatera Selatan Indonesia

Tarian Sumatera Selatan

BackTrack Linuk

Programing

Senin, 13 Juni 2016

Tugas 07 Sistem Berkas

11.13    No comments



TUGAS 07
SISTEM BERKAS

MAKALAH ORGANISASI BERKAS
HASHING


Disusun Oleh:

Nama   :Indah Permata Sari
Nim     :131051064


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






KATA PENGANTAR
Assalamu'allaikum Wr.Wb.

Segala puji bagi Allah SWT yang telah memberikan nikmat serta hidayah-Nya terutama nikmat kesempatan dan kesehatan sehingga penulis dapat menyelesaikan makalah tugas 7 mata kuliah Sistem Berkas dengan judul “Organisasi Berkas Hashing”.
Makalah ini merupakan salah satu tugas mata kuliah Sistem Berkas di program studi Teknik Informatika Fakultas Teknologi Industri pada IST AKPRIND Yogyakarta Selanjutnya penulis mengucapkan terima kasih yang sebesar-besarnya kepada semua pihak yang telah membantu penulisan laporan ini.
Penulis menyadari bahwa terdapat kekurangan dalam penulisan laporan ini, maka dari itu penulis mengharapkan kritik dan saran yang membangun dari para pembaca demi kesempurnaan makalah ini.
Penulis berharap, semoga laporan ini dapat memberikan manfaat bagi yang membaca.

Yogyakarta, 30 April 2016

Indah Permata Sari






DAFTAR ISI
LEMBAR JUDUL
KATA PENGANTAR


A.    Perhitungan Fungsi Hash
1)      K MOD N
2)      K MOD P
3)      Midsquaring
4)      Penjumlahan Digit
5)      Multiplication
6)      Trunction
7)      Folding
8)      Konversi Radix

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)


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

Read More
Langganan: Postingan (Atom)