file berkas langsung - · pdf filemelalui proses pencarian, namun bisa ... (11 adalah...

FILE BERKAS LANGSUNGRudi Susanto | rudist87@gmail.com

Pendahuluan

• Untuk menemukan suatu rekaman tidakmelalui proses pencarian, namun bisalangsung menuju alamat yang ditemptirekaman.

• Solusi awalmenyimpan rekaman padaalamat yang sama dengan nilai kuncirekaman tersebut

2http://rudist.wordpress.com

Pendahuluan

• Contoh : rekaman dengan kunci 100 akandisimpan di alamat 100

• Syarat kunci rekaman = alamat lokasirekaman

• 1 probe untuk setiap rekaman yang dicari

• Kunci rekaman = alamat rekamanhubungan korespondensi satu - satu

3http://rudist.wordpress.com

Kerugian Korespondensi Satu - satu

a. Harus disediakan ruang yang sangat besaruntuk menampung setiap kemungkinannilai kunci yang ada.

Contoh : NIP PNS( 9 digit) satu milyaralamat (kemungkinan 000000000 –999999999)

b. Banyak alamat yang tidak dipergunakan/ kosong.

Contoh : Kode NIP 3 digit awalmenunjukkan kode departemen(000000000 – 000999999 tidak terpakai)

4http://rudist.wordpress.com

Metode HASHING

• Untuk mengurangi banyaknya ruang alamatyang digunakan

• Melakukan pemetaan (melakukankonversi) dari kunci rekaman yang memiliki cakupan nilai yang luas ke nilaialamat yang memiliki cakupan yang telahdipersempit.

5http://rudist.wordpress.com

Konsep File Hash

• Merupakan organisasi file dengan metode akseslangsung (direct acsess), yang menggunakansuatu fungsi untuk memetakan key menjadiaddress

6http://rudist.wordpress.com

Konsep File Hash

• Fungsi yang digunakan disebut fungsi hash/KAT (key toaddress transformation)

• Address yang dihasilkan dari hasil perhitungan fungsihash 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 menjadiaddress

• Transfomasi key akan mudah jika key telah berupa nilaiinteger, untuk key berupa karakter alphanumerik terdapatproses prakondisi untuk mengubahnya menjadi suatunilai integer

7http://rudist.wordpress.com

Macam – macam Fungsi HASH

a. Fungsi Modulo

b. Metode Pemotongan

c. Metode Pelipatan

d. Metode Pengkuadratan

e. Penambahan Kode ASCII

8http://rudist.wordpress.com

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 nilaibanyaknya data, setelah itu banyaknya ruangalamat disesuaikan dengan n

9http://rudist.wordpress.com

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

10http://rudist.wordpress.com

Fungsi Modulo

2. P bilangan prima terkecil yang lebih besaratau 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

11http://rudist.wordpress.com

b.Metode Pemotongan

• Home address dicari dengan memotongnilai kunci ke jumlah digit tertentu yang lebih pendek

• Contoh :

NIP 9 digit dipotong menjadi 3 digit denganmenggambil 3 nomor terakhir. Misal NIP 132312090 memiliki home address 090/ 90

12http://rudist.wordpress.com

c. Metode Pelipatan

• Diandalkan kuci rekaman ditulis di ataskertas dan dilipat ke dalam bagian – bagianyang sama panjang, lalu setiap bagiandijumlahkan. Folding (Metoda Pelipatan), dapat dilakukan dengan cara:

1. Folding by boundary

2. Folding by shifting

13http://rudist.wordpress.com

c. Metode Pelipatan

1. Folding by boundary

• contoh jika key = 123456789, maka transformasike 3 digit address dengan teknik folding by boundary dapat dilakukan dengan membagidigit key tsb dengan cara seolah-olah melipatbatas pembagian digit seperti berikut :

*apabila kode – kode itu ditambahkan (tanpa carry) , makadiperoleh 654.

14http://rudist.wordpress.com

c. Metode Pelipatan

2. Folding by shiftingcontoh jika key = 123456789, maka transformasike 3 digit address dengan teknik folding by shifting dapat dilakukan dengan membagi digit key tsb dengan cara seolah-olah menggeser bataspembagian digit seperti berikut :

*apabila kode – kode itu ditambahkan (tanpa carry) ,maka diperoleh 258

15http://rudist.wordpress.com

c. Metode Pelipatan

• Nilai NIP 132312090

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

16http://rudist.wordpress.com

d.Metode Pengkuadratan

• Home address dicari denganmengkuadratkan setiap digit pembentukkunci, lalu semua hasilnya dijumlahkan

• Contoh :

• Carilah pengkuadratan dari 782

Jawab

f (782) =

17http://rudist.wordpress.com

e.Penambahan Kode ASCII

• Jika kunci bukan berupa kode numerik.

• Home address dicari dengan menjumlahkankode ASCII setiap huruf pembentuk kunci.

• Contoh : Rekaman dengan kunci ADE

memiliki home address 65+68+69 = 192

18http://rudist.wordpress.com

Soal1. Berapakah home-address dari rekaman rekaman

dengan kunci 3 digit NIM terakhir anda bila diketahuiberkas memiliki 11 rekaman (N=11)

2. Carilah home-address anda masing masing denganketentuan

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)

http://rudist.wordpress.com 19

Kriteria Fungsi Hash yang Baik

• Dapat mendistribusikan setiap rekamansecara merata, sehingga dapatmeminimalkan terjadinya collision

• Dapat dieksekusi dengan efisien, sehinggawaktu tidak habis hanya untuk menghitunghome address saja

20http://rudist.wordpress.com

Collision (Tabrakan)

• Metode Hashing Korespondensi satu –satu hilang

• Peristiwa dimana terdapat 2 buah rekamandengan kunci yang berbeda namunmemiliki home address yang samaCollision/ Tabrakan/ Tumbukan

21http://rudist.wordpress.com

RESOLUSI KOLISI

• Yang menjadi tujuan utama metode resolusikolisi adalah menempatkan rekamansinonim pada suatu lokasi yang membutuhkan probes tambahan yang minimum dari home-address rekamantersebut.

• Synonim adalah dua atau lebih nilai keyyang berbeda pada hash ke home address yang sama.

• Penyelesaianmemberikan petunjuk padalokasi rekaman sinonim.

22http://rudist.wordpress.com

RESOLUSI KOLISI

• Karena collision dapat dipastikan akan selaluterjadi, maka dikatakan bahwa output dari fungsihash (home address) bukanlah merupakan alamatunik yang pasti ditempati oleh rekaman yang diproses, namun hanya berupa kemungkinanalamat yang bisa ditempati.

• Jika home address dari suatu rekaman ternyatasudah ditempati rekaman lain, maka harusdicarikan alamat lain untuk ditempati rekamantersebut

• Proses pencarian alamat lain Resolusi Kolisi23http://rudist.wordpress.com

Metode Collision Resolution

• Metode Open Addressing

• Metode Chaining

• Metode Coalesced Hashing

• Metode Chained Progressive Overflow(Linier Probing)

• Metode Bucket

http://rudist.wordpress.com 24

Metode Coalesced Hashing

• Bila terjadi tumbukan dalampemasukan kunci rekaman maka dicarialamat yang paling besar/paling akhir

• Contoh : misalkan akan dilakukanpenyisipan rekaman-rekaman dengan kunci38,51,40,61,83,24, dan 60

http://rudist.wordpress.com 25

Contoh : Metode Coalesced Hashing

• Langkah 1 :

• Hash semua kunci dengan kunci modulus 11 (11 adalah kapasitas berkas), maka akandihasilkan :

http://rudist.wordpress.com 26

Kunci Key mod 11

38 5

51 7

40 7

61 6

83 6

24 2

60 5

Contoh : Metode Coalesced Hashing

• Langkah 2. Masukkan ke alamat :

http://rudist.wordpress.com 27

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

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.

http://rudist.wordpress.com 28

Kunci Kunci mod 11 probe

38 5 1

51 7 1

40 7 2

61 6 1

83 6 2

24 2 1

60 5 2

Rumus Probe rata-rata

=probe total/jumlah rekaman

Dari gambar disamping probe total = 10 dan jumlah rekaman7

Jadi intuk membaca masing-masingrekaman 1 kali diperlukan rata-rata probe 1.4

Soal

• Misalkan akan dilakukan penyisipanrekaman-rekaman dengan dengan key : 24, 18, 30, 28, 39, 13 dan 14

• Hash (key) = key mod 11, dimana 11 adalahukuran table.

http://rudist.wordpress.com 29

Jawab

http://rudist.wordpress.com 30

alamat Rekaman Medan Penghubung

0

1

2 24 9

3 14

4

5

6 28 10

7 18

8 30

9 13

10 39

Kunci Key mod 11

24 2

18 7

30 8

28 6

39 6

13 2

14 3

Probe rata2 =9/7

Metode Open Addressing

• Alamat alternatif dicari pada alamat-alamatselanjutnya yang masih kosong

• Cara mencari alamat alternatif ada 2 macam, yaitu :

– Linear Probingpencarian dilakukan dengan jarak pencarianyang fix (tetap), biasanya satu satu

– Quadratic Probingpencarian dilakukan dengan jarak pencarianberubah dengan perubahan yang tetap

http://rudist.wordpress.com 31

Contoh Soal Linear Probing

Sesuai namanya, bila lokasi yang akan ditempatitelah terisi, maka dilihat lokasi selanjutnyaapakah msh belum terisi.

• Fungsi hash yang dipakai adalah :f(key) = key mod 10

• Ruang alamat yang tersedia : 10 alamat

• Metode Collision Resolution yang dipakaiadalah Open Addressing dengan Linear Probingjarak 3

• Urutan kunci yang masuk adalah : 20, 31, 33, 40, 10, 12, 30, dan 15

http://rudist.wordpress.com 32

Jawaban Linear Probing

http://rudist.wordpress.com 33

0 20

1 31

2 12

3 33

4

5 30

6 40

7

8 15

9 10

20 0 0 0

31 1 1 1

33 3 3 3

40 0 0, 3, 6 6

10 0 0, 3, 6, 9 9

12 2 2 2

30 0 0, 3, 6, 9, 2, 5 5

15 5 5, 8 8

Key f Proses Addr

Probe total = 19

Probe rata-rata = 19/8

Soal

• Misalkan akan dilakukan penyisipanrekaman-rekaman dengan dengan key : 24, 18, 30, 28, 39, 13 dan 14

• Hash (key) = key mod 11, dimana 11 adalahukuran table

• Linear Probing jarak 3

http://rudist.wordpress.com 34

Metode Bucket

• Jmlh pengaksesan dapat direduksi denganmeletakkan lebih dari satu rekaman padasatu alamat penyimpan. Kemungkinantersebut dpt direalisir bila digunakan sistembuckets disebut juga blok atau halaman.

• Disediakan 2 alamat kunci yaitu kunci 1 dankunci 2

• Sama seperti linier probing,bila terjadikolisi(tubrukan) jika lokasi yangditempati telah terisi,maka dilihatlokasi selanjutnya apakah belum terisi.

http://rudist.wordpress.com 35

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

http://rudist.wordpress.com 36

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

Kunci Home-Addres

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

• Membaca rekaman dalam buckets

http://rudist.wordpress.com 37

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

Soal

• Misalkan akan dilakukan penyisipanrekaman-rekaman dengan dengan key : 24, 18, 30, 28, 39, 13 dan 14

• Hash (key) = key mod 11, dimana 11 adalahukuran table

http://rudist.wordpress.com 38

Metode Chaining

• Dengan metode ini, harus disediakan ruangekstra untuk menyimpan rekaman-rekamanyang mengalami tabrakan (terpisah daritabel hash)

• Pada setiap ruang alamat yang ada, tidakhanya menyimpan data rekaman namunjuga menyimpan suatu nilai yang menunjukkan alamat rekaman selanjutnyayang harusnya menempati ruang tersebut

• Setiap sinonim (nilai-nilai yang memilikihome address sama) akan membentukrantai (chain)

http://rudist.wordpress.com 39

Metode Progressive Overflow

• Metode Open Addressing dengan Linear Probingdisebut juga sebagai Metode Progressive Overflow

• Metode ini jika didesain dengan salah bisamenimbulkan infinite loop, dimana alamatalternatif tidak dapat ditemukan karena pencarianhanya memutar-mutar di tempat yang sama

• Kelemahan ini dapat diatasi dengan cara :

– Jarak pencarian diambil suatu nilai yang bukanmerupakan faktor dari jumlah ruang alamat (n)

– Banyaknya ruang alamat diambil suatu bilanganprima, misalkan ada 10 data, maka disediakan ruangalamat sebanyak 11

http://rudist.wordpress.com 40

Tugas

1. Dilakukan penyisipan rekaman-rekamandengan 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 pilihsalah satu)

2. Dilakukan penyisipan rekaman-rekamandengan 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 danprobe rata-rata! (Metode silahkan pilihsalah satu)

http://rudist.wordpress.com 41

Terima Kasih

http://rudist.wordpress.com 42