LICHLICH((Late Insertion Standard Late Insertion Standard

Coalesced HashingCoalesced Hashing))

Beberapa varian dari coaleced hashing dapat Beberapa varian dari coaleced hashing dapat diklasifikasikan ke dalam tiga cara :diklasifikasikan ke dalam tiga cara :

1.1. Mengorganisasi berkas (dengan atau tanpa Mengorganisasi berkas (dengan atau tanpa overflow)overflow)

2.2. Menghubungkan item yang terkoalisi ke dalam Menghubungkan item yang terkoalisi ke dalam rantairantai

3.3. Memilih lokasi yang belum ada penghuninyaMemilih lokasi yang belum ada penghuninya

KolisiKolisi mungkin dapat direduksi (dikurangi)dengan mungkin dapat direduksi (dikurangi)dengan memodifikasi organisasi berkas, dengan cara memodifikasi organisasi berkas, dengan cara memisahkan antara area untuk data primer dangan area memisahkan antara area untuk data primer dangan area untuk data overflow yang disebut teknik untuk data overflow yang disebut teknik LICH LICH (Late (Late Insertion Coalesced Hashing),Insertion Coalesced Hashing), karena rekaman yang karena rekaman yang baru disisipkan pada akhir rantai sinonim. baru disisipkan pada akhir rantai sinonim.

Dalam LICH terdapat dua bagian berkas/index Dalam LICH terdapat dua bagian berkas/index untuk mengurangi kolisiuntuk mengurangi kolisi

1.1. Area primerArea primer

ruang alamat yang cocok dengan fungsi hashruang alamat yang cocok dengan fungsi hash

2.2. Area overflowArea overflow

area yang hanya berisi rekaman-rekaman area yang hanya berisi rekaman-rekaman yang bersinonim yang bersinonim

Untuk mencari faktor alamat di Untuk mencari faktor alamat di gunakan rumus sebagai berikutgunakan rumus sebagai berikut

Dilakukan penyisipan rekaman-rekaman dengan kunci Dilakukan penyisipan rekaman-rekaman dengan kunci

38 51 40 61 83 24 60 38 51 40 61 83 24 60

Ke dalam berkas kapasitas 11 Ke dalam berkas kapasitas 11

Jawab Jawab

Hash semua kunci rekaman dengan kunci modulus 7 Hash semua kunci rekaman dengan kunci modulus 7 (kapasitas berkas pada area primer)(kapasitas berkas pada area primer)

Di lakukan penyisipan rekaman-rekaman dengan kunci Di lakukan penyisipan rekaman-rekaman dengan kunci

26 36 46 56 65 66 76 86 96 26 36 46 56 65 66 76 86 96

Ke dalam berkas kapasitas 11Ke dalam berkas kapasitas 11

Di lakukan penyisipan rekaman-rekaman dengan kunci Di lakukan penyisipan rekaman-rekaman dengan kunci

2929 4545 5555 3333 5151 6363 7373 8383

Ke dalam berkas kapasitas 12Ke dalam berkas kapasitas 12

Di lakukan penyisipan rekaman-rekaman dengan kunci Di lakukan penyisipan rekaman-rekaman dengan kunci

1212 2121 3232 2323 4343 6161 9999 111111

Ke dalam berkas kapasitas 13Ke dalam berkas kapasitas 13