Coalesced Hashing
Coalesced Hashing adalah metode penanganan
collision yang menggunakan penunjuk untuk menghubungkan bagian-bagian yang
memiliki persamaan kunci. Sebagai gambaran, proses ini digunakan untuk
menyisipkan dan menghubungkan suatu record.
Coalesced Hashing meliki link, link
ini menunjuk ke address dimana kunci yang collision ditempatkan. kunci yang
mengalami collision diletakkan mulai dari akhir tabel. hash (key) = key mod P,
dan P adalah bilangan prima ukuran tabel
Contoh :
Daftar kunci berikut akan disimpan secara
langsung ke memory address
dengan mod 10
201431309 è 20, 01, 14, 43, 31, 13, 30, 09
Peyelesaian
Hash (20) = 20 mod 10 = 0
Hash (01) = 01 mod 10 = 1
Hash (14) = 14 mod 10 = 4
Hash (43) = 43 mod 10 = 3
Hash (31) = 31 mod 10 = 1
Hash (13) = 13 mod 10 = 3
Hash (30) = 30 mod 10 = 0
Hash (09) = 09 mod 10 = 9
Langkah
:
·
20 diletakan di posisi 0 karena 20 mod 10 = 0, dan posisi 0
masih kosong
·
Selanjutnya 1
diletakan di posisi 1 karena 01 mod 10 = 1,
dan 1 masih kosong
·
14 diletakkan di
posisi 4, karena posisi 4 masih
kosong
·
Selanjutnya yang 43 diletakkan di posisi 3 karena posisi
tersebut masih kosong
·
31 seharusnya diletakan di posisi 1, tapi karena posisi 1 sudah terisi 1 maka 31
ditempatkan di posisi paling akhir yang masih kosong yaitu 2. Karena posisi 1 sudah terisi oleh 31. Maka pada medan
penghubung posisi 1 diisi dengan 2.
·
13 seharusnya diletakan
di posisi 3, tapi karena posisi 3 sudah terisi oleh 43 maka 13
ditempatkan di posisi paling akhir yang masih kosong yaitu 5, Maka pada medan
penghubung posisi 3 diisi dengan 5.
·
30 seharusnya diletakan di posisi 0, tapi karena posisi 0 sudah terisi 0 maka 30
ditempatkan di posisi paling akhir yang masih kosong yaitu 6. Dan pada medan penghubung posisi 1
diisi dengan 2 dan 6.
·
09 diletakan di posisi 8
|
ALAMAT
|
REKAMAN
|
MEDAN PENGHUBUNG
|
|
0
|
20
|
0
|
|
1
|
1
|
1
|
|
2
|
13
|
4
|
|
3
|
43
|
3
|
|
4
|
14
|
1,3,5
|
|
5
|
31
|
2
|
|
6
|
30
|
0,2,4,6
|
|
7
|
|
|
|
8
|
9
|
|
|
|
|
|
OPEN ADDRESING
Contoh :
Daftarkan kunci
berikut dengan linear probing jarak 2
dan f(key) = key mod 10.
20, 01, 14, 43, 31, 13, 30, 09
Penyelesaian
|
Kunci
|
F(key)
|
Proses
|
Address
|
|
Kunci
|
|
20
|
0
|
0
|
0
|
0
|
20
|
|
01
|
1
|
1
|
1
|
1
|
1
|
|
14
|
4
|
4
|
4
|
2
|
30
|
|
43
|
3
|
3
|
3
|
3
|
43
|
|
31
|
1
|
1, 3, 5
|
5
|
4
|
14
|
|
13
|
3
|
3, 5, 7
|
7
|
5
|
31
|
|
30
|
1
|
1, 3, 5, 7, 0, 2
|
2
|
6
|
13
|
|
9
|
9
|
3, 5, 7, 0, 2, 4, 6
|
6
|
7
|
13
|
|
|
|
|
|
8
|
|
Penjelasan
Ø Pada
kunci 31 yang pertama seharusnya diletakkan di posisi 1 tetapi karena sudah
berisi maka letakkan di posisi dengan lompatan 2 dari posisi 1 yaitu 3 tetapi
posisi 3 juga sudah berisi sehingga lompat lagi ke posisi 5.
Ø Untuk
kunci yang 13 seharusnya berada di posisi 3 namun posisi itu njuga sudah berisi
jadi lakkukan lompatan sebanyak 2 lompatan ke posisi 5, namun posisi 5 juga
sudah berisi maka lompat lagi ke posisi 7.
Ø Untuk
kunci 30 yang kedua yang seharusnya berada di posisi 1 harus lompat ke posisi 3
tapi sudah penuh, ke posisi 5 lalu 7 lalu 0 kemudian 2 karena itu posisi yang
masih kosong.
Ø Lalu
pada kunci 9 terakhir letakkan di posisi 7 karena berdasarkan lompatannya maka
kunci 9 berada di posisi 7 yang masih kosong.
