BEBERAPA METODE PENYELESAIAN COLLISION PADA ORGANISASI BERKAS SECARA HASHING

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 hash yang 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 dataInilai kunci pada suatu alamatInomor 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

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 STRING VAR 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<1000, sehingga cukup menyediakan larik 0…999, dan memanfaatkan 3 digit terakhir No_Buku untuk menempatkan semua No_Buku pada larik yang diketahui (jarak antar No_Buku hanya ditentukan oleh 3 digit terkhir). Hal ini berarti perlu fungsi untuk mengkoversikan No_Buku ke dalam nomor posisi dari larik yang diketahui. Fungsi hash mengkoversikan nilai kunci aktual menjadi lokasi alamat memori yang dinyatakan sebagai berikut: H: K→L Keterangan: K : himpunan nilai kunci L : himpunan alamat dalam memori (posisi subscript dalam larik)

Fungsi hash yang 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. Aspek penting yang perlu diperhatikan dalam penentuan fungsi hash adalah: 1. Fungsi H harus mudah dan cepat dicari/dihitung 2. Fungsi H sedapat mungkin memetakan setiap nilai kunci secara uniform sepanjang himpunan L tabrakan (collision) akan minimal PEMBAHASAN Collision pada Hashing Setiap fungsi hash tidak bisa terlepas dari collision, yaitu terjadinya tabrakan dalam penempatan nilai kunci pada nomor indeks tabel alamat memori yang sama. Fungsi hash yang memberikan kemungkinan semakin kecil terjadinya collision berarti fungsi hash tersebut semakin baik. Cara untuk meminimalkan terjadinya collision adalah: 1. Mengganti fungsi hash 2. Mengganti metode hashing 3. Menurunkan packing factor Packing factor menyatakan nilai perbandingan jumlah data yang disimpan terhadap kapasitas berkas, yang dihitung dengan formula berikut: Packing_factor = jumlah_record / jumlah_lokasi_penyimpanan

Berdasarkan formula tersebut, maka: 1. Nilai packing factor berbanding lurus dengan kemungkinan terjadinya collision 2. Nilai packing factor berbanding lurus dengan rata-rata waktu pencarian nilai suatu kunci dalam berkas 3. Rata-rata waktu pencarian nilai suatu kunci dalam berkas berbanding lurus dengan kemungkinan terjadinya collision

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, recordrecord 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 mempunyai home 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

4

Æ home address 7 diberi link ke indeks 10 H(28) Æ 28 MOD 11 = 6 H(39) Æ 39 MOD 11 = 6 (collision) (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 H(16) Æ 16 MOD 11 = 5 (collision) (ditempatkan pada akhir tabel yang kosong) Æ 8 masih kosong, sehingga H(16) Æ 8 Æ home address 5 diberi link ke indeks 8 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 (mengalami collision)

Tabel 1: Penempatan kunci dengan metode coalesced hashing tipe LISCH (1) Record 0 1 2 3 4 5 6 7 8 9 10

Kunci

Link

13 27 28 18 16 39 29

8 9 10

Permasalahan: Bagaimana jika akan menyisipkan nilai kunci 42 dan 17 ? Penyelesaiannya adalah sebagai berikut ini. H(42) Æ 42 MOD 11 = 9 (collision) (ditempatkan pada akhir tabel yang kosong) Æ 4 masih kosong, sehingga H(42) Æ 4 Æ home address 9 diberi link ke indeks 4 H(17) Æ 17 MOD 11 = 6 (collision) (ditempatkan pada akhir tabel yang kosong) Æ 3 masih kosong, sehingga H(17) Æ 3 Æ home address 6 diberi link ke indeks 3 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)

5

Tabel 2: Penempatan kunci dengan metode coalesced hashing tipe LISCH (2) Record 0 1 2 3 4 5 6 7 8 9 10

Kunci 13 17 42 27 28 18 16 39 29

Link

3 8 9 10 4

Metode Coalesced Hashing Tipe EISCH Penyelesaian collision dengan metode coalesced hashing tipe EISCH dilakukan dengan cara sebagai berikut: 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 Æ home address 7 diberi link ke indeks 10 H(28) Æ 28 MOD 11Æ 6 H(39) Æ 39 MOD 11Æ 6 (collission) (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 H(16) Æ 16 MOD 11Æ 5 collision (ditempatkan pada akhir tabel yang kosong) Æ 8 masih kosong, sehingga H(16) Æ 8 Æ home address 5 diberi link ke indeks 8 Maka penempatan nilai-nilai kunci tersebut ditampilkan dalam Tabel 3. 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 (mengalami collision)

6

Tabel 3: Penempatan kunci dengan metode coalesced hashing tipe EISCH (1) Record 0 1 2 3 4 5 6 7 8 9 10

Kunci

Link

13 27 28 18 16 39 29

8 9 10

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) Æ 4 masih kosong, sehingga H(42) Æ 4 Æ home address 9 diberi link ke indeks 4 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) Æ 3 masih kosong, sehingga H(17) Æ 3 Æ home address 6 diberi link ke indeks 3 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) Record 0 1 2 3 4 5 6 7 8 9 10

Kunci 13 17 42 27 28 18 16 39 29

Link

9 8 3 10 4

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:

7

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 dan ukuran tabel. Address_factor dihitung dengan formula sebagai berikut: Address_factor = Primary_area/ukuran_tabel

Contoh: Jika diketahui nilai-nilai kunci sebagai berikut: 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) Æ 10 masih kosong, sehingga H(39) Æ 10 Æ home address 4 diberi link ke indeks 10 H(13) Æ 13 MOD 7 Æ 6 (collision) (ditempatkan pada nomor indeks terbesar yang kosong) Æ 9 masih kosong, sehingga H(13) Æ 9 Æ home address 6 diberi link ke indeks 9 H(16) Æ 16 MOD 7 Æ 2 H(42) Æ 42 MOD 7 Æ 0 (collision) (ditempatkan pada nomor indeks terbesar yang kosong) Æ 8 masih kosong, sehingga H(42) Æ 8 Æ home address 0 diberi link ke indeks 8 H(17) Æ 17 MOD 7 Æ 3 Hasilnya tampak sebagaimana ditampilkan dalam Tabel 5. Tabel 5: Penempatan kunci dengan metode coalesced hashing tipe LICH Record 0 1 2 3 4 5 6 7 8 9 10

Kunci 28 29 16 17 18

Link 8

27

9

primary area

10 oferflow area /cellar area

42 13 39

Rata-rata untuk akses suatu nilai kunci adalah: = ( 9 + 3 )/9 = 12/9 = 1,33

8

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: Jika diketahui nilai-nilai kunci sebagai berikut: 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 H(39) Æ 39 MOD 7 Æ 4 (collision) (ditempatkan pada nomor indeks terbesar yang kosong) Æ 10 masih kosong, sehingga H(39) Æ 10 Æ home address 4 diberi link ke indeks 10 H(13) Æ 13 MOD 7 Æ 6 (collision) (ditempatkan pada nomor indeks terbesar yang kosong) Æ 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) Record 0 1 2 3 4 5 6 7 8 9 10

Kunci 28

Link

primary area

16 18

10

27

9

overflow area / cellar area

29 13 39

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

9

2: Langkah penempatan kunci 39, 13 (mengalami collision)

Selanjutnya, untuk menempatkan nilai kunci 42 dan 17 dilakukan dengan cara yang sama dengan tipe LICH, yaitu: H(42) Æ 42 MOD 7 Æ 0 (collision) (ditempatkan pada nomor indeks terbesar yang kosong) Æ 7 masih kosong, sehingga H(42) Æ 7 Æ home address 0 diberi link ke indeks 7 H(17) Æ 17 MOD 7 Æ 3 Hasilnya yang diperoleh tampak sebagaimana ditampilkan dalam Tabel 7. Rata-rata untuk akses suatu nilai kunci adalah: = ( 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) Record 0 1 2 3 4 5 6 7 8 9 10

Kunci 28

Link 7

16 17 18

10

27 42 29 13 39

9

primary area

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. 2.

Konversikan nilai kunci untuk mendapatkan home address 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 1 b. Set nilai pencacah (counter) untuk pencarian lokasi kosong menjadi 1 c. Selama nilai pencacah (counter) kurang dari ukuran tabel, maka lakukan proses berikut: 1). Hitung lokasi selanjutnya dengan cara menambahkan nilai/indeks alamat sekarang dengan nilai increment dan kemudian hasilnya di modulo dengan ukuran tabel 2). Jika alamat kosong, sisipkan kunci pada lokasi tersebut. Jika tidak kosong, tambahkan nilai pencacah (counter) dengan 1 dan kembali ke langkah-1)

10

d. Akhiri dengan komentar “Tabel penuh…..”

Contoh: Jika diketahui nilai-nilai kunci sebagai berikut: 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 H(29) Æ 29 MOD 11 Æ 7 (collision) Ditempatkan pada lokasi berikutnya yang kosong: 8 H(28) Æ 28 MOD 11 Æ 6 H(39) Æ 39 MOD 11 Æ 6 (collision) Ditempatkan pada lokasi berikutnya yang kosong: 9 H(13) Æ 13 MOD 11 Æ 2 H(16) Æ 16 MOD 11 Æ 5 (collision) Ditempatkan pada lokasi berikutnya yang kosong: 10 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 (mengalami collision) 3: Langkah penempatan kunci 39 (mengalami collision) 5: Langkah penempatan kunci 16 (mengalami collision)

Tabel 8: Penempatan kunci dengan metode progressive overflow (1) Record 0 1 2 3 4 5 6 7 8 9 10

Kunci 13 27 28 18 29 39 16

Selanjutnya, jika akan disisipkan nilai kunci baru, yaitu 42 dan 17, maka dilakukan dengan cara sebagai berikut: H(42) Æ 42 MOD 11 Æ 9 (collision) Ditempatkan pada lokasi berikutnya yang kosong: 0 H(17) Æ 17 MOD 11 Æ 6 (collision) Ditempatkan pada lokasi berikutnya yang kosong: 1 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:

11

9: Langkah penempatan setiap kunci pada home address 1: Langkah penempatan kunci 29 (mengalami collision) 3: Langkah penempatan kunci 39 (mengalami collision) 5: Langkah penempatan kunci 16 (mengalami collision) 2: Langkah penempatan kunci 42 (mengalami collision) 6: Langkah penempatan kunci 17 (mengalami collision)

Tabel 9: Penempatan kunci dengan metode progressive overflow (2) Record 0 1 2 3 4 5 6 7 8 9 10

Kunci 28 16 17 18 27 42 29 13 39

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. 2.

Konversikan nilai kunci/hashing untuk mendapatkan home address kunci 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 1 b. Set nilai pencacah (counter) untuk pencarian lokasi kosong menjadi 1 c. Selama nilai pencacah kurang dari ukuran tabel, lakukan:

12

1)

Hitung pencarian lokasi selanjutnya dengan cara menambahkan nilai indeks alamat sekarang dengan nilai increment dan kemudian hasilnya dimodulo dengan ukuran tabel 2) Jika alamat kosong, sisipkan kunci pada lokasi tersebut. Jika tidak kosong, tambahkan nilai pencacah (counter) dengan 1 dan kembali ke langkah -1) d. Diakhiri dengan komentar: “Tabel penuh…”

Contoh: Jika diketahui nilai-nilai kunci sebagai berikut: 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 H(29) Æ 29 MOD 11 Æ 7 (collision) Ditempatkan pada lokasi baru Increment Æ (29 DIV 11) MOD 11 Æ 2 Lokasi baru Æ 7+2Æ 9 H(28) Æ 28 MOD 11Æ 6 H(39) Æ 39 MOD 11 Æ 6 (collision) Ditempatkan pada lokasi baru Increment Æ (39 DIV 11) MOD 11 Æ 3 Lokasi baru Æ 6+3Æ 9 Ditempatkan pada lokasi baru Increment Æ3 Lokasi baru Æ 9 + 3 Æ 12 Æ 12 MOD 11 Æ 1 H(13) Æ 13 MOD 11 Æ 2 H(16) Æ 16 MOD 11 Æ 5 (collision) Ditempatkan pada lokasi baru Increment Æ (16 DIV 11) MOD 11 Æ 1 Lokasi baru Æ 5+1Æ 6 Ditempatkan pada lokasi baru Increment Æ1 Lokasi baru Æ 6+1Æ 7 Ditempatkan pada lokasi baru Increment Æ1 Lokasi baru Æ 7+1Æ 8 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 (mengalami collision) 2: Langkah penempatan kunci 39 (mengalami collision) 3: Langkah penempatan kunci 16 (mengalami collision)

13

Tabel 10: Penempatan kunci dengan metode linear quotient Record 0 1 2 3 4 5 6 7 8 9 10

Kunci 39 13 27 28 18 16 29

4. Metode Buckets Pembicaraan metode hashing sebelumnya mengasumsikan bahwa hanya ada sebuah record yang dapat menempati sebuah indeks. Banyaknya jumlah pengaksesan ke media 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: Jika diketahui nilai-nilai kunci sebagai berikut: 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 H(29) Æ 29 MOD 11 Æ 7 (collision) 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) Tetap disisipkan pada indeks 6 Tidak perlu menggeser bucket, ditempatkan pd bucket 2 H(13) Æ 13 MOD 11 Æ 2 H(16) Æ 16 MOD 11 Æ 5 (collision) Tetap disisipkan pada indeks 6 Tidak perlu menggeser bucket, ditempatkan pd bucket 2

14

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) Record 0 1 2 3 4 5 6 7 8 9 10

Bucket 1

Bucket 2

13 27 28 18

16 39 29

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) Record 0 1 2 3 4 5 6 7 8 9 10

Bucket 1

Bucket 2

13 27 28 18 40

16 39 29

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

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