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

FILE BERKAS LANGSUNGRudi Susanto | [email protected]

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


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)


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.


Konsep File Hash

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


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


Macam – macam Fungsi HASH

a. Fungsi Modulo

b. Metode Pemotongan

c. Metode Pelipatan

d. Metode Pengkuadratan

e. Penambahan Kode ASCII


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


a.Fungsi Modulo

1. N = ukuran tabel/ berkas

N = 12

30 mod N = 6 menghasilkan 2 sisa 6





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


Untuk N = 15 maka P = 17




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


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


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.


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


c. Metode Pelipatan

• Nilai NIP 132312090

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


d.Metode Pengkuadratan

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

• Contoh :

• Carilah pengkuadratan dari 782

Jawab

f (782) =


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


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


Collision (Tabrakan)

• Metode Hashing Korespondensi satu –satu hilang

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


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.


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


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


Contoh : Metode Coalesced Hashing

• Langkah 1 :

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


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 :


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.


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.


Jawab


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


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


Jawaban Linear Probing


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


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

• Linear Probing jarak 3


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.


• Contoh : rekaman-rekaman dengan kunci38,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

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


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


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


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)


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


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)


Terima Kasih


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

Documents