Metode Open Addresing dan Metode Closed Hashing

Hai teman teman, hari ini penulis ngeblog lagi nih. Ini materi di perkuliahan penulis minggu lalu. Minggu lalu kita pada ngebahas metode open addressing dan metode closed hassing. Yuk di cek, semoga bermanfaat ^^

Pengertian Hasing

Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.

Hashing adalah transformasi aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya. Menurut bahasanya, hashberarti memenggal dan kemudian menggabungkan. Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data, dan penghapusan data dapat dilakukan dengan cepat. Ide dasarnya adalah menghitung posisi recordyang dicari dalam array, bukan membandingkan record dengan isi pada array. Fungsi yang mengembalikan nilai atau kunci disebut fungsi hash (hashfunction) dan array yang digunakan disebut tabel hash (hash table). Hash tablemenggunakan struktur data array asosiatif yang mengasosiasikan recorddengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut.

1.    Metode Open Addresing

·         Bersifat linear probing, contoh sesuai dengan namanya jika lokasi yang telah ditempati telah terisikan dilihat lokasi selanjutnya, apakah masih kosong atau sudah terisi

·         Fungsi hash yang dipakai adalah

f(key) = key mod n

Contoh :

Dengan ketentuan sebagai berikut :

1.      Ruang alamat yang tersedia misalkan 10

2.      Metode collosin resolution yang dipakai adalah open addressing dengan linear probing janrak 3

3.      Ukuran kunci yang masuk adalah 20, 31, 33, 40, 10,12, 30 dan 15

Penyelesaian :

Kunci	f(key)	Proses	Address		Kunci
20	0	0	0	0	20
31	1	1	1	1	31
33	3	3	3	2	12
40	0	0, 3, 6	6	3	33
10	0	0, 3, 6, 9	9	4
12	2	2	2	5	30
30	0	0, 3, 6, 9, 2, 5	5	6	40
15	5	5, 8	8	7
				8	15
				9	10

Maka :

Probe total = 19

Probe total rata rata = 19/8 = 2

2.        Metode Clossed Hassing

·        Bila terjadi tumbukan dalam pemasukan kunci rekaman maka, dapat dicari alamat yang paling benar atau alamat yang paling akhir

·         Gabungan dari chaining dan openaddressing. Coalesced hashingmenghubungkan ke tabel itu sendiri. Seperti open addressing, metode ini memiliki keunggulan pada penggunaan tempat dan cache dibanding metodechaining. Seperti chaining, metode ini menghasilkan lokasi penyimpanan yang lebih menyebar, tetapi pada metode ini record yang disimpan tidak  mungkin lebih banyak daripada ruang yang disediakan tabel.

Contoh :

1.      Jika ingin dilakukan penyisipan rekaman rekaman dengan kunci 38, 51, 40, 6183, 24, dan 60

2.      Langkah 1 lakukan proses hassing semua kunci dengan kunci modular 11 ( 11 adalah kapasitas berkas) maka dihasilkan :

Penyelesaian :

Kunci	f(key)	Alamat	Rekaman	Medan Penghubung
38		0
51		1
40		2	24
61		3
83		4
24		5	38	10
60		6	61	9
		7	51	8
		8	40
		9	83
		10	60

Latihan Soal

Dengan ketentuan :

1.      Dengan metode open addressing, jika terjadi kolisi terhadap kunci dengan urutan rekaman kunci yang masuk adalah NIM masing masing (201431251)

2.      Format : 201431251 = 20, 01, 24, 43, 32, 12, 25, 51

3.      Ruang alamat yang tersedia = 9 alamat

4.      Metode collision resolution yang digunakan adalah open addressing  linear probing jarak 2 dan metode cloased hassing

Penyelesaian :

a.       Metode Open Addresing

Kunci	f(key)	Proses	Addres		Kunci
20	0	0	0	0	20
01	1	1	1	1	01
14	4	4	4	2	12
43	3	3	3	3	43
31	1	1, 3, 5	5	4	14
12	2	2	2	5	31
25	5	5, 7	7	6	51
51	1	1, 3, 5, 7, 0, 2, 4, 6	6	7	25
				8

b.      Metode Cloased Hassing

Alamat	Rekaman	Medan Penghubung
0	20
1	01	2, 7
2	31	5
3	43
4	14
5	12	6
6	25
7	51
8
9