Metode Open Addressing dan Coalesced Hashing

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.