2006 edhy sutanta makalah maret 2006 wahana ilmiah hal 37-57 beberapa metode penyelesaian collision...

8/19/2019 2006 Edhy Sutanta Makalah Maret 2006 WAHANA ILMIAH Hal 37-57 Beberapa Metode Penyelesaian Collision Pd H…

1/19


2/19


3/19


4/19


5/19

1

BEBERAPA METODE PENYELESAIAN COLLISION

PADA ORGANISASI BERKAS SECARA HASHING

Edhy Sutanta Jurusan Teknik Informatika, Fakultas Teknologi Industri,

Institut Sains & Teknologi AKPRIND Yogyakarta

Jl. Kalisahak 28, Komplek Balapan, Yogyakarta 55222

Phone: 0274-563029-121, Fax: 0274-563847, email: [email protected]

INTISARI

Hashing merupakan metode pengaksesan data yang dilakukan dengan cara

memetakan/mengkonversikan himpunan kunci record menjadi himpunan alamat memori

(posisi subscript dalam larik), sehingga range address menjadi kecil. Fungsi untuk

mengkoversikan nilai kunci aktual menjadi lokasi alamat disebut fungsi hash, sedangkan

metode pencarian yang memanfaatkan fungsi hash disebut sebagai hashing atau hash

addressing. Tujuan utama fungsi hash adalah agar dua buah nilai kunci (=r) mempunyai

nilai hash yang berbeda. Jika tidak, maka akan terjadi collision/mash clash. Fungsi hashyang sering digunakan antara lain adalah metode K MOD N , K MOD P, midsquaring,

penjumlahan digit, multiplication, trunction, folding, konversi Radix, polynomial hashing,

serta alphabetic keys.

Dalam implementasinya, kenyataan menunjukkan bahwa setiap fungsi hash tidak bisa

terlepas dari collision, yaitu terjadinya tabrakan dalam penempatan data I nilai kunci pada suatu

alamat I nomor indeks tabel yang sama. Fungsi hash yang memberikan kemungkinan semakin

kecil terjadinya collision berarti fungsi hash tersebut semakin baik. Cara untuk meminimalkan

terjadinya collision adalah mengganti fungsi hash atau mengganti metode hashing yang

digunakan.

Makalah ini membahas tentang beberapa metode untuk penyelesaian masalah

collision pada organisasi berkas hashing, juga mengenai kelebihan dan kelemahan pada

masing-masing metode.

Kata-kata kunci: hashing, fungsi hash, key, address, collision.

PENDAHULUAN

Hashing merupakan metode pengaksesan data yang dilakukan dengan cara

memetakan/mengkonversikan himpunan kunci record menjadi himpunan alamat memori

(posisi subscript dalam larik), sehingga range address menjadi kecil. Fungsi untuk

mengkoversikan nilai kunci aktual menjadi lokasi alamat disebut fungsi hash, sedangkan

metode pencarian yang memanfaatkan fungsi hash disebut sebagai hashing atau hash

addressing. Tujuan utama fungsi hash adalah agar dua buah nilai kunci (=r) mempunyai

nilai hash yang berbeda. Jika tidak, maka akan terjadi collision/mash clash. Untuk

menentukan suatu fungsi hash H, diperlukan asumsi sebagai berikut:

1. Kunci yang diletakkan adalah primary key

2. Tidak ada altemate key 3. Satu alamat digunakan untuk satu primary key

4. Primary key diasumsikan tersusun atas sebuah atribut (simple key)

5. Memori terbatas 1 blok dengan alamat dinormalkan, yaitu 0 sampai maksimum

blok (virtual address). Nilai fungsi hash terletak pada range hash: 0..P-1, dimana

P adalah bilangan prima terkecil yang lebih besar dari cacah kunci.

Sebagai gambaran, berikut ini diberikan ilustrasi perlunya fungsi hash dalam

penyimpanan data. Misal, suatu toko buku menjual 100 judul buku yang masing-masing


6/19

2

mempunyai 2 digit kode buku sebagai pengenal. Cara paling sederhana untuk menyimpan

data-data tersebut adalah memanfaatkan kode buku sebagai subscript larik buku. Contoh

deklarasi dalam bahasa PASCAL untuk penyimpanan data tersebut adalah sebagai

berikut: TYPE No_Buku = ARRAY (0..100) OF STRINGVAR Buku: No_Buku;

Dalam deklarasi tersebut, No_Buku dimanfaatkan sebagai subscript dari larik

buku. Apabila dalam perkembangnnya toko tersebut menjual 1000 judul buku, maka

setiap buku dikelompokan sehingga memerlukan 7 digit No_Buku (10 juta elemen). Jika

tetap disimpan dalam larik menjadi tidak efisien, sehingga No_Buku 1002372 dan

1002772 akan mempunyai jarak yang lebih besar dibandingkan jarak No_Buku 0001998

dan 519298. Dalam contoh ini jarak antara No_Buku 1002372 dan 1002771 adalah 400,

sedangkan jarak antara No-Buku 0001996 dan 519298 adalah 2.

Kondisi di atas memerlukan suatu metode yang dapat mengkonversikan nomor

buku (7 digit) menjadi bilangan integer dalam batas tertentu. Dalam kasus di atas, jumlah

judul buku


7/19

3

Metode Untuk Mengatasi Collision pada Hashing Penyelesaian collision pada organisasi berkas hashing, dapat diklasifikasikan

dalam tiga kelompok, yaitu: 1. Menggunakan penghubung (link ), yang termasuk kelompok ini adalah metode coalesced

hashing. Dalam metode ini, record -record hanya memuat field - field data saja.

2. Tanpa menggunakan penghubung (without link ), yang termasuk kelompok ini adalah

metode progressive overflow, linear quotient , dan buckets., Dalam metode ini, record -

record memuat field - field data dan link field .

3. Menggunakan link semu ( pseudolink ) yang termasuk kelompok ini adalah metode

computed chaining. Dalam metode ini, record -record memuat field - field data dan field

untuk menghitung alamat indeks.

1. Metode Coalesced Hashing

Metode coalesced hashing merupakan penyelesaian collision menggunakan pointer

sebagai penghubung (link ) alamat asal (home address) ke alamat indeks yang ditunjuk

berikutnya. Penggunaan link ini akan membentuk suatu rantai record yang mempunyaihome address sama. Metode coalesced hashing mempunyai beberapa varian, yaitu:

1. Tipe LISCH ( Late Insertion Standard Coalesced Hashing)

2. Tipe EISCH ( Early Insertion Standard Coalesced Hashing)

3. Tipe LICH ( Late Insertion Coalesced Hashing)

4. Tipe EICH ( Early Insertion Coalesced Hashing)

5. Tipe BEISCH ( Bidirectional Early Insertion Standard Coalesced Hashing)

6. Tipe BLISCH ( Bidirectional Late Insertion Standard Coalesced Hashing)

7. Tipe REISCH ( Random Early Insertion Standard Coalesced Hashing)

8. Tipe RLISCH ( Random Late Insertion Standard Coalesced Hashing)

Berikut ini akan ditinjau empat metode pertama dari setiap varian metode coalesced

hashing tersebut, yaitu LISCH, EISCH, LICH, dan EICH.

Metode Coalesced Hashing Tipe LISCH Penyelesaian collision dengan metode coalesced hashing tipe LISCH dilakukan

dengan cara sebagai berikut:

1. Menggunakan link

2. Link menunjuk ke alamat kunci yang mengalami collision

3. Nilai kunci yang mengalami collision ditempatkan pada bagian akhir tabel

4. Fungsi hash yang digunakan adalah H(K)=K MOD P, dimana P adalah bilangan

prima terkecil yang lebih dari jumlah kunci

5. P merupakan ukuran tabel index

Contoh:

Jika diketahui nilai-nilai kunci sebagai berikut:

27, 18, 29, 28, 39, 13, 16

Maka penempatan setiap nilai kunci akan dilakukan sebagai berikut ini.

Penyelesaian: N = 7, P = 11, Alamat indeks: 0 s/d 10

Perhitungan:

H(27) Æ 27 MOD 11 = 5

H(18) Æ 18 MOD 11 = 7

H(29) Æ 29 MOD 11 = 7 (collision)

(ditempatkan pada akhir tabel yang kosong)

Æ 10 masih kosong, sehingga H(29) Æ 10


8/19

4

Æ home address 7 diberi link ke indeks 10

H(28) Æ 28 MOD 11 = 6


(ditempatkan pada akhir tabel yang kosong) Æ 9 masih kosong, sehingga H(39) Æ 9

Æ home address 6 diberi link ke indeks 9.

H(13) Æ 13 MOD 11 = 2





Maka penempatan nilai-nilai kunci tersebut ditampilkan dalam Tabel 1. Rata-rata untuk

akses suatu nilai kunci adalah:

= ( 7+3 )/7 = 10/7 = 1,42 Keterangan:7: Langkah penempatan setiap kunci pada home address 3: Langkah penempatan kunci 16, 39, 29 (mengalamicollision)

Tabel 1: Penempatan kunci dengan metode coalesced hashing tipe LISCH (1) Record Kunci Link

012 13345 27 86 28 9

7 18 108 169 39

10 29

Permasalahan:

Bagaimana jika akan menyisipkan nilai kunci 42 dan 17 ? Penyelesaiannya adalah

sebagai berikut ini.









Hasil yang diperoleh ditampilkan pada Tabel 2. Rata-rata untuk akses suatu nilai kunci setelah penyisipan kunci 42 dan 17 adalah:

= ( 9 + 4 + 3 )/9 = 16/9 = 1,78 Keterangan:9: Langkah penempatan setiap kunci pada home address 4: Langkah penempatan kunci 16, 39, 29, 42 (mengalami collision)3: Langkah penempatan kunci 17 (home address 6, pindah ke indeks 3, link)


9/19

5

Tabel 2: Penempatan kunci dengan metode coalesced hashing tipe LISCH (2) Record Kunci Link

01

2 133 17

4 42 35 27 86 28 97 18 10

8 169 39 410 29

Metode Coalesced Hashing Tipe EISCH

Penyelesaian collision dengan metode coalesced hashing tipe EISCH dilakukan


1. Mirip dengan coalesced hashing tipe LISCH 2. Perbedaannya, dalam tipe ini jika terjadi lebih dari 1 kali collision, maka nilai kunci

terakhir yang mengalami collision akan ditunjuk langsung oleh home address

Contoh:

Jika diketahui nilai-nilai kunci sebagai berikut (sama dengan contoh sebelumnya):

27, 18, 29, 28, 39, 13, 16

Maka penempatan setiap nilai kunci akan dilakukan sebagai berikut ini.

Penyelesaian:

N = 7, P = 11, Alamat indeks: 0 s/d 10

Perhitungan:

H(27) Æ 27 MOD 11Æ 5

H(18) Æ 18 MOD 11Æ 7

H(29) Æ 29 MOD 11Æ 7 (collision)

(ditempatkan pada akhir tabel yang kosong ) Æ 10 masih kosong, sehingga H(29) Æ 10


H(28) Æ 28 MOD 11Æ 6

H(39) Æ 39 MOD 11Æ 6 (collission)




H(13) Æ 13 MOD 11Æ 2

H(16) Æ 16 MOD 11Æ 5 collision




Maka penempatan nilai-nilai kunci tersebut ditampilkan dalam Tabel 3. Rata-rata untuk


= ( 7 + 3 )/7 = 10/7 = 1,42 Keterangan:7: Langkah penempatan setiap kunci pada home address 3: Langkah penempatan kunci 16, 39, 29 (mengalamicollision)


10/19

6

Record Kunci Link

012 133 17 94 42

5 27 86 28 37 18 10

8 169 39 4

10 29

Tabel 3: Penempatan kunci dengan metode coalesced hashing tipe EISCH (1) Record Kunci Link

01

2 133

45 27 86 28 97 18 10

8 169 3910 29

Catatan:

Karena mulai nilai kunci 27 hingga 16 tidak ada collision yang lebih dari 1 kali,

maka penempataanya sama dengan tipe LISCH.

Selanjutnya, ketika disisipkan nilai kunci 42 dan 17, maka:

H(42) Æ 42 MOD 11Æ 9 (collision) (ditempatkan pada akhir tabel yang kosong)



H(17) Æ 17 MOD 11Æ 6 (collision)

(terjadi collision lebih dari 1 kali pada home address 6, maka alamat akan

di-link secara langsung dari home address, yaitu 6)



Hasilnya tampak sebagaimana ditampilkan dalam Tabel 4. Rata-rata untuk akses suatu

nilai kunci setelah penyisipan nilai kunci 42 dan 17 adalah:

= ( 9 + 6 )/9 = 15/9 = 1,67 Keterangan:

9: Langkah penempatan setiap kunci pada home address 6: Langkah penempatan kunci 16, 39, 42, 17, 17 (mengalami collision)

Tabel 4: Penempatan kunci dengan metode coalesced hashing tipe EISCH (2)

Metode Coalesced Hashing Tipe LICH

Salah satu cara untuk menurunkan collision adalah memodifikasi organisasi

tabel, yaitu dengan tipe Late Insertion Coalesced Hashing/LICH. Metode coalesced

hasing tipe LICH adalah metode coalesced hasing tipe LISCH yang menggunakan cellar

area, yaitu dengan cara membagi tabel menjadi 2 bagian, yaitu:


11/19

7

Record Kunci Link0 28 81 292 163 17

4 18 105 6 27 97 8 429 1310 39

1. Bagian primary area digunakan sebagai alamat nilai kunci hash

2. Bagian cellar area/overflow area, hanya digunakan sebagai alamat untuk nilai kunci

yang mengalami overflow

Dalam hal ini, maka address_factor merupakan perbandingan antara primary area danukuran tabel. Address_factor dihitung dengan formula sebagai berikut: Address_factor = Primary_area/ukuran_tabel

Contoh:


17, 28, 39, 48, 59, 63, 76

Address factor = 64%

Maka penempatan setiap nilai kuncinya adalah sebagai berikut.

Penyelesaian:

N = 7, P = 11, Alamat = 0 s/d 10

Primary area = 64% x 11 = 7 Æ indeks: 0 s/d 6

Cellar area = 11 - 7 = 4 Æ indeks: 7 s/d 10

Jika fungsi hash yang digunakan adalah K MOD N, maka:

H(27) Æ 27 MOD 7 Æ 6 H(18) Æ 18 MOD 7 Æ 4

H(29) Æ 29 MOD 7 Æ 1

H(28) Æ 28 MOD 7 Æ 0

H(39) Æ 39 MOD 7 Æ 4 (collision)

(ditempatkan pada nomor indeks terbesar yang kosong)







H(16) Æ 16 MOD 7 Æ 2

H(42) Æ 42 MOD 7 Æ 0 (collision) (ditempatkan pada nomor indeks terbesar yang kosong)



H(17) Æ 17 MOD 7 Æ 3

Hasilnya tampak sebagaimana ditampilkan dalam Tabel 5.

Tabel 5: Penempatan kunci dengan metode coalesced hashing tipe LICH

primary area

oferflow area /cellar area

Rata-rata untuk akses suatu nilai kunci adalah:

= ( 9 + 3 )/9 = 12/9 = 1,33


12/19

8

Record Kunci Link0 281 2 163 4 18 105 6 27 97 8 299 1310 39

Keterangan:9: Langkah penempatan setiap kunci pada home address 3: Langkah penempatan kunci 16, 39, 42, 17, 17 (mengalami collision)

Metode Coalesced Hashing Tipe EICH

Penyelesaian collision dengan metode coalesced hashing tipe EICH dilakukan

dengan cara menggunakan algoritma EISCH, dengan modifikasi tabel menjadi 2 bagian,

yaitu bagian primary area dan cellar area.

Contoh:


27, 18, 29, 28, 39, 13, 16, 42, 17

Maka penempatan setiap nilai kunci tersebut dengan metode coalesced hasing tipe EICH

adalah sebagai berikut ini.

Penyelesaian:

N = 9, P = 11, Alamat = 0 s/d 10

Address factor = 64 %, maka:

Primary area = 64% x 11 = 7 Æ alamat indeks: 0 - 6

Overflow area = 11 - 7 = 4 Æ alamat indeks: 7 s/d 10

Perhitungan:

H(27) Æ 27 MOD 7 Æ 6

H(18) Æ 18 MOD 7 Æ 4

H(29) Æ 29 MOD 7 Æ 8

H(28) Æ 28 MOD 7 Æ 0







Æ 9 masih kosong, sehingga H(13) Æ 9 Æ home address 6 diberi link ke indeks 9

H(16) Æ 16 MOD 7 Æ 2

Hasilnya tampak sebagaimana ditampilkan dalam Tabel 6.

Tabel 6: Penempatan kunci dengan metode coalesced hashing tipe EICH (1)

primaryarea

overflow area / cellar area

Rata-rata untuk penempatan/ pencarian/akses suatu nilai kunci adalah:

= ( 7 + 2 )/7 = 9/7 = 1,29 Keterangan:7: Langkah penempatan setiap kunci pada home address


13/19

9

Record Kunci Link0 28 71 2 163 174 18 105 6 27 97 428 299 1310 39

2: Langkah penempatan kunci 39, 13 (mengalamicollision)

Selanjutnya, untuk menempatkan nilai kunci 42 dan 17 dilakukan dengan cara yang sama

dengan tipe LICH, yaitu:





H(17) Æ 17 MOD 7 Æ 3

Hasilnya yang diperoleh tampak sebagaimana ditampilkan dalam Tabel 7. Rata-rata untuk


= ( 7 + 2 + 3)/9 = 12/9 = 1,29 Keterangan:7: Langkah penempatan setiap kunci pada home address 2: Langkah penempatan kunci 18, 27 (mengalami collision)3: Langkah penempatan nilai kunci 28 (mengalami collision)

Tabel 7: Penempatan kunci dengan metode coalesced hashing tipe EICH (2)

primaryarea

overflow area / cellar area

2. Metode Progressive Overflow

Metode coaleced hashing membutuhkan media penyimpan tambahan untuk

menyimpan link field . Pada saat media penyimpan tidak mungkin untuk menerima

penambahan lagi, maka penggunaan metode tersebut bukan merupakan pilihan yang

tepat. Metode konvensional sederhana untuk mengatasi masalah tersebut adalah

menggunakan metode progressive overflow/liniear probing. Dalam metode ini, jika suatu

kunci mengalami collision, maka nilai kunci tersebut akan diletakkan pada indeks

selanjutnya yang masih kosong. Jika hingga indeks terakhir sudah penuh, maka pencarian

lokasi dilakukan mulai dari awal tabel, sehingga membentuk struktur indeks circular.

Algoritma metode progressive overflow/liniear probing adalah sebagai berikut: 1. Konversikan nilai kunci untuk mendapatkanhome address 2. Jika home address kosong, maka sisipkan kunci pada lokasi tersebut. Jika isi, maka lakukan proses

berikut:a. Tentukan nilai penambahan (increment) dengan cara mencari sisa bagi nilai kunci dengan ukuran

tabel, jika hasilnya 0 (nol) set nilai variabel increment menjadi 1b. Set nilai pencacah (counter ) untuk pencarian lokasi kosong menjadi 1c. Selama nilai pencacah (counter )kurang dari ukuran tabel, maka lakukan proses berikut:

1). Hitung lokasi selanjutnya dengan cara menambahkan nilai/indeks alamat sekarang dengannilai increment dan kemudian hasilnya di modulo dengan ukuran tabel

2). Jika alamat kosong, sisipkan kunci pada lokasi tersebut. Jika tidak kosong, tambahkan nilaipencacah (counter ) dengan 1 dan kembali ke langkah-1)


14/19

10

Record Kunci

012 13345 276 287 188 29

9 3910 16

d. Akhiri dengan komentar “Tabelpenuh…..”

Contoh:


27, 18, 29, 28, 39, 13, 16

Penempatan nilai-nilai kunci tersebut dengan metode progressive overflow adalah sebagai

berikut ini.

Penyelesaian:

N = 7, P = 11, Alamat = 0 s/d 10

Perhitungan:

H(27) Æ 27 MOD 11 Æ 5

H(18) Æ 18 MOD 11 Æ 7


Ditempatkan pada lokasi berikutnya yang kosong: 8

H(28) Æ 28 MOD 11 Æ 6



H(13) Æ 13 MOD 11 Æ 2 H(16) Æ 16 MOD 11 Æ 5 (collision)


Hasil perhitungan tersebut ditampilkan dalam Tabel 8. Rata-rata untuk akses suatu nilai

kunci adalah:

= ( 7 + 1 + 3 + 5 )/7 = 11/7 = 2,3 Keterangan:7: Langkah penempatan setiap kunci pada home address 1: Langkah penempatan kunci 29 (mengalamicollision)3: Langkah penempatan kunci 39 (mengalamicollision)5: Langkah penempatan kunci 16 (mengalamicollision)

Tabel 8: Penempatan kunci dengan metode progressive overflow (1)

Selanjutnya, jika akan disisipkan nilai kunci baru, yaitu 42 dan 17, maka dilakukan






Hasil penempatan nilai kunci setelah penyisipan nilai kunci 42 dan 17 tersebut

ditampilkan dalam Tabel 9. Rata-rata untuk akses suatu nilai kunci adalah:

= ( 9 + 1 + 3 + 5 + 2 + 6 )/9 = 26/9 = 2,89 Keterangan:


15/19

11

Record Kunci

0 2812 163 17

4 1856 277 42

8 299 1310 39

9: Langkah penempatan setiap kunci pada home address 1: Langkah penempatan kunci 29 (mengalamicollision)3: Langkah penempatan kunci 39 (mengalamicollision)5: Langkah penempatan kunci 16 (mengalamicollision)

2: Langkah penempatan kunci 42 (mengalamicollision)6: Langkah penempatan kunci 17 (mengalamicollision)

Tabel 9: Penempatan kunci dengan metode progressive overflow (2)

3. Metode Linear Quotient

Metode linear quotient mirip dengan metode progressive overflow. Dalam metode

progressive overflow nilai increment adalah tetap, yaitu 1 (satu). Sedangkan dalam

metode linear quotient nilai increment dapat dipilih di antara dua pilihan berikut:

1. Menggunakan hasil quotient (hasil bagi (div) nilai kunci dengan ukuran tabel)

2. Menggunakan fungsi hash yang lain, sehingga metode ini sering pula disebut sebagai

metode double hashing. Fungsi hash kedua ini berbeda (H1 untuk fungsi hash

pertama dan H2 untuk fungsi hash kedua)

Metode quotient ini akan menghasilkan distribusi yang lebih baik, sehingga akan

meminimalkan terjadinya collision secara berulang sebagaimana terjadi pada metode progressive overflow.

Contoh:

Fungsi yang digunakan untuk menentukan penambahan nilai pada variabel increment,

adalah sebagai berikut: 1. H1 = Quotient (K DIV P) MOD P

2. H2 = (K MOD (P - 2)) + 1

Jika penambahan nilai pada variabel increment, yaitu fungsi hash kedua dalam metode ini

menggunakan fungsi hash pertama (secara linier), yaitu: H2 = Quoient (K DIV P) MOD P

Maka lokasi baru untuk nilai kunci yang mengalami collision dihitung dengan formula

sebagai berikut: BARU = ( HomeAddress + Increment) MOD P

Algoritma metode linear quotient adalah sebagai berikut: 1. Konversikan nilai kunci/hashing untuk mendapatkanhome address kunci2. Jika home address kosong, maka sisipkan kunci pada lokasi tersebut. Jika tidak, maka lakukan proses

berikut:a. Tentukan nilai increment dengan cara mencari sisa bagi kunci dengan ukuran tabel, jika hasilnya 0

(nol) set nilai variabel increment menjadi 1b. Set nilai pencacah (counter ) untuk pencarian lokasi kosong menjadi 1c. Selama nilai pencacahkurang dari ukuran tabel, lakukan:


16/19

12

1) Hitung pencarian lokasi selanjutnya dengan cara menambahkan nilai indeks alamat sekarangdengan nilai increment dan kemudian hasilnya dimodulo dengan ukuran tabel

2) Jika alamat kosong, sisipkan kunci pada lokasi tersebut. Jika tidak kosong, tambahkan nilaipencacah (counter ) dengan 1 dan kembali ke langkah -1)

d. Diakhiri dengan komentar: “Tabelpenuh…” Contoh:


27, 18, 29, 28, 39, 13, 16

Maka penempatan nilai-nilai kunci tersebut dengan metode linear quotient adalah sebagai

berikut ini.

Penyelesaian:

N = 7, P = 11, Alamat indeks = 0 s/d 10

H2 = Quotient (K DIV P) MOD P

Perhitungan:

H(27) Æ 27 MOD 11 Æ 5

H(18) Æ 18 MOD 11 Æ 7


Ditempatkan pada lokasi baru Increment Æ (29 DIV 11) MOD 11 Æ 2

Lokasi baru Æ 7 + 2 Æ 9

H(28) Æ 28 MOD 11Æ 6


Ditempatkan pada lokasi baru

Increment Æ (39 DIV 11) MOD 11 Æ 3



Increment Æ 3


Æ 12 MOD 11 Æ 1

H(13) Æ 13 MOD 11 Æ 2



Increment Æ (16 DIV 11) MOD 11 Æ 1



Increment Æ 1



Increment Æ 1


Hasil perhitungan tersebut ditampilkan pada Tabel 10. Rata-rata untuk akses suatu nilai

kunci adalah:

= ( 7 + 1 + 2 + 3 )/7 = 13/7 = 1,86 Keterangan:7: Langkah penempatan setiap kunci pada home address 1: Langkah penempatan kunci 29 (mengalamicollision)2: Langkah penempatan kunci 39 (mengalamicollision)3: Langkah penempatan kunci 16 (mengalamicollision)


17/19

13

Record unci

01 392 13345 276 287 188 169 2910

Tabel 10: Penempatan kunci dengan metode linear quotient

4. Metode Buckets Pembicaraan metode hashing sebelumnya mengasumsikan bahwa hanya ada

sebuah record yang dapat menempati sebuah indeks. Banyaknya jumlah pengaksesan kemedia penyimpan sekunder dapat diminimalkan dengan teknik penyimpanan multi

record . Jika hal ini dilakukan, maka penanganannya akan dilakukan oleh blok (=halaman

=bucket ). Bucket merupakan sebuah unit yang dapat digunakan ketika data/record

disimpan ke atau diakses dari media penyimpan sekunder. Bucket memuat lokasi indeks

tidak sebenarnya dari record , tetapi sebagai indeks ke dalam suatu array pointer . Setiap

bucket terdiri atas satu untaian record yang bersama-sama menempati alamat hash yang

sama. Jumlah record yang dapat disimpan dalam array pointer disebut sebagai faktor

blok (blocking factor) (sama dengan banyaknya bucket). Semakin besar nilai faktor blok,

maka semakin kecil kemungkinan terjadi collision, karena record -record yang

mengalami collision dapat disimpan ke dalam satu indeks.

Contoh:


27, 18, 29, 28, 39, 13, 16 Ukuran bucket yang digunakan= 2. Fungsi hash yang digunakan sama dengan contoh

pada metode progressive overflow, yaitu:

H(K) = K MOD PÆ H(K) = K MOD 11

Penempatan nilai-nilai kunci tersebut dengan metode bucket adalah sebagai berikut ini.

Penyelesaian:

N = 7, P = 11, Alamat = 0 s/d 10

Perhitungan:

H(27) Æ 27 MOD 11 Æ 5

H(18) Æ 18 MOD 11 Æ 7


Tetap disisipkan pada indeks 7

Perlu menggeser bucket , ditempatkan pada bucket 2

H(28) Æ 28 MOD 11Æ 6 H(39) Æ 39 MOD 11 Æ 6 (collision)


Tidak perlu menggeser bucket , ditempatkan pd bucket 2

H(13) Æ 13 MOD 11 Æ 2



Tidak perlu menggeser bucket , ditempatkan pd bucket 2


18/19

14

Record Bucket 1 Bucket 2

012 13345 27 16

6 28 397 18 298

910

Record Bucket 1 Bucket 2

012 1334

5 27 166 28 39

7 18 298 40910

Hasil perhitungan tersebut ditampilkan pada Tabel 11. Rata-rata untuk akses adalah:

= ( 7 )/22 = 0,32 Keterangan:7: Langkah penempatan setiap kunci pada home address 22: Jumlah alamat indeks penyimpanan

Tabel 11: Penempatan kunci dengan metode bucket (1)

Jika diperlukan untuk penyisipan record baru, misal 40, maka akan dilakukan dengan

cara sebagai berikut:

H(40) Æ 40 MOD 11 Æ 7 (mengalami collision)

Collision terjadi bucket 1 dan bucket 2

Nilai kunci 40 akan dipindah ke lokasi indeks terdekat selanjutnya

dengan metode progressive overflow

Lokasi baru adalah: 8 (buckets 1)

Sehingga hasil yang diperoleh setelah penyisipan nilai kunci 40 adalah seperti

ditampilkan pada Tabel 12. Rata-rata untuk akses adalah:

= ( 8 )/22 = 0,36 Keterangan:8: Langkah penempatan setiap kunci pada home address 22: Jumlah alamat indeks penyimpanan

Tabel 12: Penempatan kunci dengan metode bucket (2)

5. Metode Computed Chaining Metode computed chaining merupakan metode kelompok ke-3 yang memadukan

antara metode coalesced hashing dan linear quotient . Metode ini tidak menggunakan alamat


19/19

15

fisik record , tetapi berupa pseudolink dimana alamat sesungguhnya masih harus dihitung

terlebih dahulu. Dalam metode computed chaining, penentuan lokasi berikutnya untuk kunci

yang mengalami collision ditentukan berdasarkan hasil pembagian (div) terhadap nilai

kuncinya. Kelebihan metode computed chaining adalah: 1. Memberikan unjuk kerja yang cukup baik, berada di antara metode kelompok

pertama dan kelompok kedua

2. Memerlukan ruang penyimpanan yang relatif kecil, berada di antara metode

kelompok pertama dan kelompok kedua

Adapun kelemahan metode computed chaining adalah masih memerlukan

tambahan ruang untuk pseudolink sekalipun kecil. Metode ini baik digunakan dalam

kondisi terdapat ruang tambahan, unjuk kerja dan waktu penyisipan sangat penting

KESIMPULAN

Berdasarkan pembahasan di atas, diperoleh beberapa kesimpulan sebagai berikut:

1. Fungsi hash yang memberikan kemungkinan semakin kecil terjadinya collision berarti

fungsi hash tersebut semakin baik. Secara alamiah tidak ada jaminan bahwa aspek ke-2

dapat dipenuhi tanpa terlebih dahulu mengetahui kunci-kunci yang ada. 2. Dalam metode coalesced hashing, jika dibandingkan antara tipe LISCH dan EISCH, maka

tipe EISCH lebih efisien. Secara normal, untuk packing factor 90% tipe EISCH

membutuhkan rata-rata sekitar 4% lebih hemat daripada tipe LISCH.

3. Secara umum, metode coalesced hashing memiliki unjuk kerja yang sangat baik, dan

sesuai digunakan jika didukung oleh ketersediaan ruang yang cukup, sedangkan

kelemahannya adalah memerlukan ruang tambahan untuk menyimpan link field .

4. Secara umum, metode progressive overflow/liniear probing memiliki kelebihan karena

tidak memerlukan ruang tambahan dan algoritma yang sederhana, sedangkan

kelemahannya adalah unjuk kerjanya sangat buruk, sehingga jarang diterapkan.

5. Secara umum, metode linear quotient memiliki kelebihan tidak memerlukan ruang

tambahan untuk menyimpan link field dan unjuk kerjanya cukup baik, sedangkan

kelemahannya adalah memiliki unjuk kerja di bawah metode lainnya.

6. Secara relatif penerapan metode bucket memberikan unjuk kerja yang lebih baik dari pada metode progresive overflow dengan nilai rata-rata sebesar 0,64.

7. Secara umum metode yang menggunakan link mempunyai unjuk kerja yang lebih baik,

tetapi memerlukan ruang penyimpanan yang lebih besar (tambahan untuk link ).

Sedangkan metode yang tidak menggunakan link mempunyai unjuk kerja yang kurang

baik, tetapi memerlukan ruang penyimpanan yang lebih kecil.

8. Penggunaan metode computed chaining yang menggunakan link semu memberikan unjuk

kerja di antara metode kelompok pertama (menggunakan link ) dan kelompok kedua (tidak

menggunakan link ) dan memerlukan ruang penyimpanan yang kecil.

PUSTAKA

[1]. Austing, R.H., 1988, File Organzation and Acces, DC Heat & Co., USA

[2]. Harbon, T.R., 1988, File Systems, Prentice Hall, USA

[3]. Lomis, E.S., 1989, Data Management and File Structures, Prentice Hall, USA[4]. Sutanta, E., 2004, Sistem Basis Data, Graha Ilmu, Yogyakarta

[5]. Tharp, A.L. 1988, File Organization and Processing, John Wiley & Sons Inc.,

Singapore

[6]. Wiederhold, G., 1988, File Organization for Database Design, 2nd edition, McGraw

Hill Inc., Singapore

2006 edhy sutanta makalah maret 2006 wahana ilmiah hal 37-57 beberapa metode penyelesaian collision...

Documents