FILE BERKAS LANGSUNG. Rudi Susanto

FILE BERKAS LANGSUNG Rudi Susanto | [email protected]

Pendahuluan • Untuk menemukan suatu rekaman tidak melalui proses pencarian, namun bisa langsung menuju alamat yang ditempti rekaman. • Solusi awal  menyimpan rekaman pada alamat yang sama dengan nilai kunci rekaman tersebut

http://rudist.wordpress.com

2

Pendahuluan • Contoh : rekaman dengan kunci 100 akan disimpan di alamat 100 • Syarat  kunci rekaman = alamat lokasi rekaman • 1 probe untuk setiap rekaman yang dicari • Kunci rekaman = alamat rekaman  hubungan korespondensi satu - satu


3

Kerugian Korespondensi Satu - satu a. Harus disediakan ruang yang sangat besar untuk menampung setiap kemungkinan nilai kunci yang ada. Contoh : NIP PNS( 9 digit)  satu milyar alamat (kemungkinan 000000000 – 999999999) b. Banyak alamat yang tidak dipergunakan/ kosong. Contoh : Kode NIP 3 digit awal menunjukkan kode departemen (000000000 – 000999999  tidak terpakai) http://rudist.wordpress.com

4

Metode HASHING • Untuk mengurangi banyaknya ruang alamat yang digunakan • Melakukan pemetaan (melakukan konversi) dari kunci rekaman yang memiliki cakupan nilai yang luas ke nilai alamat yang memiliki cakupan yang telah dipersempit.


5

Konsep File Hash • Merupakan organisasi file dengan metode akses langsung (direct acsess), yang menggunakan suatu fungsi untuk memetakan key menjadi address


6

Konsep File Hash • Fungsi yang digunakan disebut fungsi hash/KAT (key to address transformation) • Address yang dihasilkan dari hasil perhitungan fungsi hash disebut dengan istilah home address • Jadi, terdapat dua komponen dalam file hash : - Ruang rekord, yang terdiri atas m slot address - Fungsi hash, yang mentransformasi key menjadi address • Transfomasi key akan mudah jika key telah berupa nilai integer, untuk key berupa karakter alphanumerik terdapat proses prakondisi untuk mengubahnya menjadi suatu nilai integer http://rudist.wordpress.com

7

Macam – macam Fungsi HASH a. Fungsi Modulo

b. Metode Pemotongan c. Metode Pelipatan d. Metode Pengkuadratan e. Penambahan Kode ASCII


8

a.Fungsi Modulo • Home address dicari dengan cara mencari sisa hasil bagi nilai kunci dengan suatu nilai tertentu f(key)  key mod n Dengan nilai n dapat berupa 2 kemungkinan, yaitu : 1. Banyaknya ruang alamat yang tersedia

2. Bilangan prima terdekat yang berada di atas nilai banyaknya data, setelah itu banyaknya ruang alamat disesuaikan dengan n http://rudist.wordpress.com

9

a.Fungsi Modulo 1. N = ukuran tabel/ berkas N = 12

30 mod N = 6 menghasilkan 2 sisa 6 40 mod N = 4 menghasilkan 3 sisa 4 50 mod N = 2 menghasilkan 4 sisa 2 60 mod N = 0 menghasilkan 5 sisa 0 http://rudist.wordpress.com

10

Fungsi Modulo 2. P  bilangan prima terkecil yang lebih besar atau sama dengan N Untuk N = 12 maka P = 13 30 mod P = 4 menghasilkan 2 sisa 4

40 mod P = 1 menghasilkan 3 sisa 1 Untuk N = 15 maka P = 17

50 mod P = 16 menghasilkan 2 sisa 16 70 mod P = 2 menghasilkan 4 sisa 2 http://rudist.wordpress.com

11

b.Metode Pemotongan • Home address dicari dengan memotong nilai kunci ke jumlah digit tertentu yang lebih pendek • Contoh : NIP 9 digit dipotong menjadi 3 digit dengan menggambil 3 nomor terakhir. Misal NIP 132312090 memiliki home address 090/ 90


12

c. Metode Pelipatan • Diandalkan kuci rekaman ditulis di atas kertas dan dilipat ke dalam bagian – bagian yang sama panjang, lalu setiap bagian dijumlahkan. Folding (Metoda Pelipatan), dapat dilakukan dengan cara:

1. Folding by boundary 2. Folding by shifting


13

c. Metode Pelipatan 1. Folding by boundary

• contoh jika key = 123456789, maka transformasi ke 3 digit address dengan teknik folding by boundary dapat dilakukan dengan membagi digit key tsb dengan cara seolah-olah melipat batas pembagian digit seperti berikut :

*apabila kode – kode itu ditambahkan (tanpa carry) , maka diperoleh 654. http://rudist.wordpress.com

14

c. Metode Pelipatan 2. Folding by shifting contoh jika key = 123456789, maka transformasi ke 3 digit address dengan teknik folding by shifting dapat dilakukan dengan membagi digit key tsb dengan cara seolah-olah menggeser batas pembagian digit seperti berikut :

*apabila kode – kode itu ditambahkan (tanpa carry) , maka diperoleh 258 http://rudist.wordpress.com

15

c. Metode Pelipatan • Nilai NIP  132312090

• Tentukan hasil penjumlahan dengan Folding by boundary dan Folding by shifting!


16

d.Metode Pengkuadratan • Home address dicari dengan mengkuadratkan setiap digit pembentuk kunci, lalu semua hasilnya dijumlahkan • Contoh : • Carilah pengkuadratan dari 782 Jawab f (782) =


17

e.Penambahan Kode ASCII • Jika kunci bukan berupa kode numerik.

• Home address dicari dengan menjumlahkan kode ASCII setiap huruf pembentuk kunci. • Contoh : Rekaman dengan kunci ADE memiliki home address 65+68+69 = 192


18

Soal 1.

Berapakah home-address dari rekaman rekaman dengan kunci 3 digit NIM terakhir anda bila diketahui berkas memiliki 11 rekaman (N=11)

2.

Carilah home-address anda masing masing dengan ketentuan a. Hashing dengan pemotongan (ambil 3 digit terakhir dari NIM anda) b. Hashing dengan lipatan dari NIM anda (Folding by boundary dan Folding by shifting!) c. Hashing dengan penguadratan NIM anda

3. Hashing dengan penambahan nilai ACII (Kunci =Nama depan Anda)


19

Kriteria Fungsi Hash yang Baik • Dapat mendistribusikan setiap rekaman secara merata, sehingga dapat meminimalkan terjadinya collision • Dapat dieksekusi dengan efisien, sehingga waktu tidak habis hanya untuk menghitung home address saja


20

Collision (Tabrakan) • Metode Hashing  Korespondensi satu – satu hilang • Peristiwa dimana terdapat 2 buah rekaman dengan kunci yang berbeda namun memiliki home address yang sama  Collision/ Tabrakan/ Tumbukan


21

RESOLUSI KOLISI • Yang menjadi tujuan utama metode resolusi kolisi adalah menempatkan rekaman sinonim pada suatu lokasi yang membutuhkan probes tambahan yang minimum dari home-address rekaman tersebut.

• Synonim adalah dua atau lebih nilai key yang berbeda pada hash ke home address yang sama. • Penyelesaian  memberikan petunjuk pada lokasi rekaman sinonim. http://rudist.wordpress.com

22

RESOLUSI KOLISI • Karena collision dapat dipastikan akan selalu terjadi, maka dikatakan bahwa output dari fungsi hash (home address) bukanlah merupakan alamat unik yang pasti ditempati oleh rekaman yang diproses, namun hanya berupa kemungkinan alamat yang bisa ditempati. • Jika home address dari suatu rekaman ternyata sudah ditempati rekaman lain, maka harus dicarikan alamat lain untuk ditempati rekaman tersebut • Proses pencarian alamat lain  Resolusi Kolisi http://rudist.wordpress.com

23

Metode Collision Resolution • Metode Open Addressing

• Metode Chaining • Metode Coalesced Hashing • Metode Chained Progressive Overflow(Linier Probing) • Metode Bucket


24

Metode Coalesced Hashing • Bila terjadi tumbukan dalam pemasukan kunci rekaman maka dicari alamat yang paling besar/paling akhir • Contoh : misalkan akan dilakukan penyisipan rekaman-rekaman dengan kunci 38,51,40,61,83,24, dan 60


25

Contoh : Metode Coalesced Hashing • Langkah 1 :

• Hash semua kunci dengan kunci modulus 11 (11 adalah kapasitas berkas), maka akan dihasilkan : Kunci Key mod 11


38

5

51

7

40

7

61

6

83

6

24

2

60

5 26

Contoh : Metode Coalesced Hashing • Langkah 2. Masukkan ke alamat : alamat

Rekaman

Medan Penghubung

0 1 2

24

3 4 5

38

8

6

61

9

7

51

10

8

60

9

83

10

40


27

Rumus Probe rata-rata • Untuk membaca masing-masing rekaman 1 kali diperlukan rata-rata probe 1.4 diperoleh dari total jumlah probe dibagi jumlah rekaman. Kunci

Kunci mod 11

probe

38

5

1

51

7

1

Dari gambar disamping probe total = 10 dan jumlah rekaman 7

40

7

2

61

6

1

Jadi intuk membaca masing-masing rekaman 1 kali diperlukan ratarata probe 1.4

83

6

2

24

2

1

60

5

2

Rumus Probe rata-rata =probe total/jumlah rekaman


28

Soal • Misalkan akan dilakukan penyisipan rekaman-rekaman dengan dengan key : 24, 18, 30, 28, 39, 13 dan 14 • Hash (key) = key mod 11, dimana 11 adalah ukuran table.


29

Jawab

alamat

Rekaman

Medan Penghubung

0 Kunci

Key mod 11

1

24

2

2

18

7

3

30

8

4

28

6

39

6

13

2

14

3

6 7

9


9

28 18

10

5

8 Probe rata2 =9/7

24 14

10

30 13 39 30

Metode Open Addressing • Alamat alternatif dicari pada alamat-alamat selanjutnya yang masih kosong • Cara mencari alamat alternatif ada 2 macam, yaitu : – Linear Probing pencarian dilakukan dengan jarak pencarian yang fix (tetap), biasanya satu satu – Quadratic Probing pencarian dilakukan dengan jarak pencarian berubah dengan perubahan yang tetap


31

Contoh Soal Linear Probing Sesuai namanya, bila lokasi yang akan ditempati telah terisi, maka dilihat lokasi selanjutnya apakah msh belum terisi. • Fungsi hash yang dipakai adalah : f(key) = key mod 10

• Ruang alamat yang tersedia : 10 alamat • Metode Collision Resolution yang dipakai adalah Open Addressing dengan Linear Probing jarak 3

• Urutan kunci yang masuk adalah : 20, 31, 33, 40, 10, 12, 30, dan 15 http://rudist.wordpress.com

32

Jawaban Linear Probing Key 20 31 33 40 10 12 30 15

f Proses Addr 0 0 0 1 1 1 3 3 3 0 0, 3, 6 6 0 0, 3, 6, 9 9 2 2 2 0 0, 3, 6, 9, 2, 5 5 5 5, 8 8

Probe total = 19

0 1 2 3 4 5 6 7 8 9

20 31 12 33 30 40 15 10

Probe rata-rata = 19/8 http://rudist.wordpress.com

33

Soal • Misalkan akan dilakukan penyisipan rekaman-rekaman dengan dengan key : 24, 18, 30, 28, 39, 13 dan 14 • Hash (key) = key mod 11, dimana 11 adalah ukuran table • Linear Probing jarak 3


34

Metode Bucket • Jmlh pengaksesan dapat direduksi dengan meletakkan lebih dari satu rekaman pada satu alamat penyimpan. Kemungkinan tersebut dpt direalisir bila digunakan sistem buckets disebut juga blok atau halaman. • Disediakan 2 alamat kunci yaitu kunci 1 dan kunci 2 • Sama seperti linier probing,bila terjadi kolisi(tubrukan) jika lokasi yang ditempati telah terisi,maka dilihat lokasi selanjutnya apakah belum terisi. http://rudist.wordpress.com

35

• Contoh : rekaman-rekaman dengan kunci 38,51,40,61,83,24,60,20 dan 94 Alamat

Kunci 1

Kunci 2

0 1 2

24

3 4 5

38

60

6

61

83

7

51

40

8

94

9

20

10 http://rudist.wordpress.com

Kunci

HomeAddres

Probe

38

5

1

51

7

1

40

7

1

61

6

1

83

6

1

24

2

1

60

5

1

20

9

1

94

6

3

Probe total

11 36

• Membaca rekaman dalam buckets Kunci

Home Address

Proses

Probe

38

5

5

1

51

7

7

1

40

7

7

1

61

6

6

1

83

6

6

1

24

2

2

1

60

5

5

1

20

9

9

1

94

6

6,7,8

3

Probe total

11

Jadi probe rata-rata = 11/9 =1,2 http://rudist.wordpress.com

37

Soal • Misalkan akan dilakukan penyisipan rekaman-rekaman dengan dengan key : 24, 18, 30, 28, 39, 13 dan 14 • Hash (key) = key mod 11, dimana 11 adalah ukuran table


38

Metode Chaining • Dengan metode ini, harus disediakan ruang ekstra untuk menyimpan rekaman-rekaman yang mengalami tabrakan (terpisah dari tabel hash) • Pada setiap ruang alamat yang ada, tidak hanya menyimpan data rekaman namun juga menyimpan suatu nilai yang menunjukkan alamat rekaman selanjutnya yang harusnya menempati ruang tersebut • Setiap sinonim (nilai-nilai yang memiliki home address sama) akan membentuk rantai (chain) http://rudist.wordpress.com

39

Metode Progressive Overflow • Metode Open Addressing dengan Linear Probing disebut juga sebagai Metode Progressive Overflow • Metode ini jika didesain dengan salah bisa menimbulkan infinite loop, dimana alamat alternatif tidak dapat ditemukan karena pencarian hanya memutar-mutar di tempat yang sama

• Kelemahan ini dapat diatasi dengan cara : – Jarak pencarian diambil suatu nilai yang bukan merupakan faktor dari jumlah ruang alamat (n) – Banyaknya ruang alamat diambil suatu bilangan prima, misalkan ada 10 data, maka disediakan ruang alamat sebanyak 11


40

Tugas 1. Dilakukan penyisipan rekaman-rekaman dengan kunci : 15, 25, 38,49,59,69,79,100,126, 150 Ke dalam berkas dengan kapasitas 12, Fungsi hash yang dipakai adalah : f(key) = key mod 10 dan carilah probe total dan probe rata-rata! (Metode silahkan pilih salah satu)

2. Dilakukan penyisipan rekaman-rekaman dengan kunci :45 ,43,82,75,25,17,37,55,100 120 ke dalam berkas dengan kapasitas 15, Fungsi hash yang dipakai adalah : f(key) = key mod 10 carilah probe total dan probe rata-rata! (Metode silahkan pilih salah satu) http://rudist.wordpress.com

41

Terima Kasih


42

FILE BERKAS LANGSUNG. Rudi Susanto

Recommend Documents