Pendekatan Terhadap Masalah Collision dalam Sistem Berkas
COLLISION:: Key yang berbeda dapat berada dalam lokasi/indeks yang sama Hal ini disebut collision
:: key yang ber-collising disebut synonyms.
:: Usaha / prosedur untuk memecahkan masalah yang timbul akibat collision disebut collision resolution
Collision Resolution
Collision resolution merupakan proses untuk menangani kejadian dua atau lebih key di-hash ke alamat yang sama.
Cara yang dilakukan jika terjadi collision adalah mencari lokasi yang kosong dalam tabel Hash secara terurut.
Cara lainnya adalah dengan menggunakan fungsi Hash yang lain untuk mencari lokasi kosong tersebut.
Pendekatan terhadap masalah Collision
1. Open Addressing
Menemukan address yang bukan home address untuk K2 dalam berkas relatif.
Contoh :
K1 = 1 K2 = 1
R1 R2
Menemukan address untuk K2 diluar dari primary area dalam berkas relatif, yaitu di overflow area yang dipakai hanya untuk menyimpan record-record yang tak dapat disimpan di home addressnya.
Contoh :
Teknik untuk mengatasi collision :
1. Linier Probing, yang merupakan teknik open addresing.
Merupakan sebuah proses pencarian secara sequential/linear dari home address sampai lokasi yang kosong.
Contoh linier probing Ukuran tabel = 11 dan file berisi 8 record dengan nilai kunci sebagai berikut:12,21,68,32,56,77
Maka alamat awal hash dengan metode pembagian sisa:
(12 mod 11)+1=1+1=2; simpan 12 dilokasi 2
(21 mod 11)+1=10+1=11; simpan 21 dilokasi 11
(68 mod 11)+1=2+1=3; simpan 68 dilokasi 3
(32 mod 11)+1=10+1=11; diuji (probe) di dilokasi 11; terjadi kolisi sehingga: (11 mod 11)+1=0+1=1; simpan 32 dilokasi 1
(56 mod 11)+1=1+1=2; diuji (probe) di dilokasi 2; terjadi kolisi sehingga:
(2 mod 11)+1=2+1=3; diuji di lokasi 3; terjadi kolisi sehingga:
(3 mod 11)+1=3+1=4; simpan 56 dilokasi 4
(77 mod 11)+1=0+1=1; diuji di lokasi 1; terjadi kolisi sehingga:
(1 mod 11)+1=1+1=2; diuji di lokasi 2; terjadi kolisi sehingga:
(2 mod 11)+1=2+1=3; diuji di lokasi 3; terjadi kolisi sehingga:
(3 mod 11)+1=3+1=4; diuji di lokasi 4; terjadi kolisi sehingga:
(4 mod 11)+1=4+1=5; simpan 77 di lokasi 5
Maka hashing dengan metode pembagian sisa dengan linear probing: 
2.Linear Quotient (metode bagi hasil secara linier)
Ukuran tabel = 11 dan file berisi 8 record dengan nilai kunci sebagai berikut: 12,21,68,32,56,77
Maka alamat awal hash dengan metode pembagian sisa:(12 mod 11)+1=1+1=2; simpan 12 dilokasi 2
(21 mod 11)+1=10+1=11; simpan 21 dilokasi 11
(68 mod 11)+1=2+1=3; simpan 68 dilokasi 3
(32 mod 11)+1=10+1=11; diuji (probe) di dilokasi 11; terjadi kolisi (q=2)->32:11=2 sisa 10 // jika q=0 maka di set menjadi q=1
((11+2) mod 11)+1=2+1=3; diuji di lokasi 3; terjadi kolisi (q=1)
((3+1) mod 11)+1=4+1=5; simpan 32 dilokasi 5
(56 mod 11)+1=1+1=2; diuji (probe) di dilokasi 2; terjadi kolisi (q=5)->56:11=5 sisa 1
((2+5) mod 11)+1=4+1=5; simpan 56 dilokasi 5 (q=1)
..........
(77 mod 11)+1=0+1=1; simpan 77 dilokasi 1
Maka hashing dengan metode pembagian sisa dengan linear probing:
0 komentar:
Post a Comment