PROGRESSIVE & BUCKETSAbdul

Haris,S.Kom

Progressive Overflow Salah satu konvensi yang sederhana adalah

penggunaan overflow yang progresif. Sesuai namanya, bila lokasi yang akan ditempati telah terisi. Maka lokasi selanjutnya dilihat apakah belum terisi atau tidak.

Pertimbangkan berkas yang memiliki struktur yang melingkar dengan lokasi pertama berada tepat sesudah lokasi terakhir. Pencarian dilanjutkan sampai ditemukan slot kosong atau sampai ditemukan home address rekaman yang kedua kalinya yang menandakan berkas telah penuh.

Contoh Kasus

Akan disisipkan rekaman dengan kunci : 38,51,40,61,83,24,60,20 dan 94 pada berkas dengan kapasitas 11 maka fungsi hashnya adalah :

Hash (Kunci) = kunci modulus 11

Menentukan Home Address

Kunci Kunci Mod 11

35 2

51 7

40 7

61 6

83 6

24 2

60 5

20 9

94 6

Penyisipan kedalam berkas dengan kapasitas 11

Alamat Kunci

0

1

2

3

4

5

6

7

8

9

10

Tanpak memerlukan medan penghubung

Pembahasan

Kelemahan utama progressive overflow adalah rata – rata probe yang sangat tinggi dibandingkan dengan teknik yang dibahas sebelumnya, oleh karena itu progressive overflow bukan teknik yang tepat untuk mereduksi kolisi. Meskipun demikian, progressive overflow lebih efektif dibanding dengan berkas sekuensial.

Buckets

Buckets didefinisikan sebagai unit penyimpanan yang berada diantara rekaman dengan berkas, juga sebuah unit dengan informasi yang dapat diakses dan dipindahkan antar peralatan penyimpanan. Jumlah rekaman yang dapt diletakan pada satu buckets disebut Faktor blocking, jika faktor blocking meningkat jumlah akses terhadap penyimpanan akan mengecil karena beberapa rekaman yang berkolisi dapat disimpan dalam satu alamat yang sama.

Contoh Kasus

Sisipkan rekaman – rekaman dengan kunci : 38,51,40,61,83,24,60,20 dan 94 pada berkas dengan kapasitas 11 dan faktor blocking = 2 maka fungsi hashnya adalah :

Hash (kunci) = modulus 11

Penyelesaian Kunci Kunci Mod 11

38 5

51 7

40 7

61 6

83 6

24 2

60 5

20 9

94 6

Penyisipan pada media rekaman

Alamat Kunci 1 Kunci 2

0

1

2

3

4

5

6

7

8

9

10

Dengan Faktor Blocking = 2

Pembahasan Dengan bucket yang berisi 2 rekaman,

hanya rekaman kolisi yang ketiga yang menyebabkan perlunya mencari bucket lain yang kosong untuk menempatkan rekaman karena tidak perna ada rekaman sinonim rekaman sinonim ketiga yang dapat disimpan dalam alamat yang sama.

Dalam bucket diperlukan adanya pemisah antara satu rekaman dengan rekaman lain yang berada dalam satu lokasi yang sama.

Terima Kasih