Cara Mengatasi Bentrokan Pada Nilai Hash Menggunakan Metode Open Addressing | amatirkode

Alhamdulillah, dengan kesehatan ini saya masih bisa memanfaatkannya untuk hal-hal kebaikan diantaranya untuk berbagi ilmu dengan teman-teman.

Untuk postingan kali ini saya akan membahas tentang Hashing. Apa itu hashing? Oke saya jawab dengan simple saja, hashing adalah transformasi aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya. Itu pengertian secara singkatnya, untuk versi lengkapnya bisa dicari di google. Disini saya fokus di Metode Addresing.

Ok  lanjut ke permasalahan utamanya

Fungsi hash yang umum digunakan diantaranya:

-Division Remainder Method (Metode Pembagian Bersisa)

-Mid Square Hashing

-Folding Hashing

Disini saya akan bahas yang Division Remainder Method saja

Deskripsi:

Jumlah lokasi memori yang tersedia dihitung, kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa. Sisa tersebut adalah nilai hashnya. Secara umum, rumusnya h(k) = k mod m. Dalam hal ini m adalah jumlah lokasi memori yang tersedia pada array. Fungsi hash tersebut menempatkan record dengan kunci k pada suatu lokasi memori yang beralamat h(k). Metode ini sering menghasilkan nilai hash yang sama dari dua atau lebih nilai aslinya atau disebut dengan bentrokan. Karena itu, dibutuhkan mekanisme khusus untuk menangani bentrokan yang disebut kebijakan resolusi bentrokan.

Sebagai contoh, saya akan memberikan contoh nilai yang tidak bentrokan dan nilai yang bentrokan.

Contoh untuk nilai yang tidak bentrokan

Asumsikan ukuran tabel = 11 dan satu file dengan 8 record menggunakan nilai kunci sebagai berikut:

12, 21, 68, 38, 52, 70, 44, 18

Jika:

m = 11

Maka:

h(k) = k mod m

(12 mod 11) + 1 = 1 + 1 = 2 ---------------------> simpan 12 di lokasi 2

(21 mod 11) + 1 = 10 + 1 = 11 ------------------> simpan 21 di lokasi 11

(68 mod 11) + 1 = 2 + 1 = 3 ---------------------> simpan 68 di lokasi 3

(38 mod 11) + 1 = 5 + 1 = 6 ---------------------> simpan 38 di lokasi 6

(52 mod 11) + 1 = 8 + 1 = 9 ---------------------> simpan 52 di lokasi 9

(70 mod 11) + 1 = 4 + 1 = 5 ---------------------> simpan 70 di lokasi 5

(44 mod 11) + 1 = 0 + 1 = 1 ---------------------> simpan 44 di lokasi 1

(18 mod 11) + 1 = 7 + 1 = 8 ---------------------> simpan 18 di lokasi 8

Sehingga lokasi memori h(k):

Untuk memahami diatas teman-teman harus paham modulus

Contoh:

5 mod 2 = 1

4 mod 2 = 0

7 mod 4 = 3

Jadi dapat disimpulkan modulus ialah nilai sisa dari hasil pembagian.

Contoh untuk nilai yang bentrokan

Asumsikan ukuran tabel = 10 dan satu file dengan 5 record menggunakan nilai kunci sebagai berikut:

20, 170, 20, 1000, 24

Jika:

m = 10

Maka:

h(k) = k mod m

(20 mod 10) + 1 = 0 + 1 = 1 ---------------------> simpan 20 di lokasi 1

(170 mod 10) + 1 = 0 + 1 = 1 ------------------> simpan 170 di lokasi 1

(20 mod 10) + 1 = 0 + 1 = 1 ---------------------> simpan 20 di lokasi 1

(1000 mod 10) + 1 = 0 + 1 = 1 ---------------------> simpan 1000 di lokasi 1

(24 mod 10) + 1 = 4 + 1 = 5 ---------------------> simpan 24 di lokasi 5

Sehingga lokasi memori h(k) akan mengalami masalah karena lokasi 1 seharusnya hanya berisi 1 record.

Terus bagaimana cara mengatasi masalah tersebut?

Kita langsung ke metode open addressing

Asumsikan ukuran tabel = 10 dan satu file dengan 5 record menggunakan nilai kunci sebagai berikut:

20, 170, 20, 1000, 24

Jika:

m = 10

Maka:

h(k) = k mod m

NB : Kebijakan Resolusi bentrokan yang dipakai adalah Open Addressing dengan linear probing jarak 3

Sehingga lokasi memori h(k):

Oke, saya rasa cuma itu yang bisa saya sampaikan terkait masalah hashing yang bentrokan. Jangan lupa untuk terus berkunjung ke blog AmatirKode. Saya buka komentar untuk teman-teman yang belum memahami materi ini.

Atas kunjungan saya ucapkan terimakasih!