Struktur Data : Hashing Python

Haloo sobat kodingers, kembali lagi bersama saya 😅. pada postingan sebelumnya kita telah membahas tentang searching dan sorting. kali ini kita akan melangkah lebih maju dengan membentuk struktur data yang disebut "hashing".

Untuk melakukan ini, kita perlu tahu lebih banyak tentang di mana barang-barang yang memungkinkan untuk kita cari dalam koleksi. Jika setiap item berada di tempat yang seharusnya, maka pencarian dapat menggunakan perbandingan tunggal untuk menemukan keberadaan suatu item. Akan tetapi, ini bukan kasusnya.

Tabel hash adalah kumpulan item yang disimpan sedemikian rupa untuk memudahkan menemukannya nanti. Setiap posisi tabel hash, sering disebut slot, dapat menyimpan item dan diberi nama oleh nilai integer mulai dari 0. Sebagai contoh, kita akan memiliki slot bernama 0, slot bernama 1, slot bernama 2, dan seterusnya di. Awalnya, tabel hash tidak berisi item sehingga setiap slot kosong. Kita dapat mengimplementasikan tabel hash dengan menggunakan daftar dengan setiap elemen diinisialisasi dengan nilai None. Gambar di bawah ini akan menunjukkan tabel hash berukuran m = 11. Dengan kata lain, ada slot m di dalam tabel, berindex 0 hingga 10.

index	0	1	2	3	4	5	6	7	8	9	10
value	77	None	None	None	26	93	17	None	None	31	54

Pemetaan antara item dan slot tempat item yang termasuk dalam tabel hash disebut fungsi hash. Fungsi hash akan mengambil item apa pun dalam koleksi dan mengembalikan integer dalam kisaran nama slot, antara 0 dan m-1. Asumsikan bahwa kita memiliki set item integer 54, 26, 93, 17, 77, dan 31. Fungsi hash pertama kami, kadang-kadang disebut sebagai "metode sisa," hanya mengambil item dan membaginya dengan ukuran tabel, mengembalikan sisanya sebagai nilai hashnya (h (item) = item% 11). Tabel 4 memberikan semua nilai hash untuk contoh item kami. Perhatikan bahwa metode sisa ini (aritmatika modulo) biasanya akan hadir dalam beberapa bentuk di semua fungsi hash, karena hasilnya harus dalam kisaran nama slot.

item%11 (11 adalah banyaknya slot yang kita buat sisa dari mod tersebut akan dijadikan index untuk menempatkan item yang kita buat)

item	index
54	10
26	4
93	5
17	6
77	0
31	9

Sekarang ketika kita ingin mencari item, kita cukup menggunakan fungsi hash untuk menghitung nama slot untuk item dan kemudian periksa tabel hash untuk melihat kosong tidaknya tabel tersebut. ketika dalam tabel berisikan None. maka, akan dimasukkan angka yang telah ditentukan indexnya.

mungkin kalian akan bertanya bagaimana jika ada index yang bertabrakan kan?. take it easy 😅
hal tersebut biasa dinamakan collision (tabrakan) ketika item bertabrakan ada beberapa metode yang dapat kita gunakan antara lain ada open addressing dan close addressing. open addressing terdiri dari linier hashing dan kuadratic hashing. sedangkan close addressing berdiri sendiri.

sekarang kita bisa membuat permisalan atau list baru

item	index
54	10
44	4
93	5
17	6
77	0
55	0

dalam list tersebut terdapat 2 value dengan posisi index yang sama (77 dan 44 pada index 0) dalam kondisi ini terjadi tabrakan atau collision. bagaimana penyelesaiannya? pertama kita akan selesaikan menggunakan linier hashing kemudian akan dilanjut dengan binary hashing dan close address.

Linier Hashing

linier hashing adalah cara penyelesaian collision pada hashing dengan memindahkan angka yang collision dengan index_collision=index_collision+1%panjang_index sehingga ketika ada collision pada index 0(seperti contoh) maka akan di tempatkan pada 0+1%panjang_index maka, akan ditempatkan pada index 1. namun saat pada index 1 terdapat item didalamnya maka akan bergeser lagi pada index 1+1%panjang_index (index menjadi 2) begitu seterusnya.

index	0	1	2	3	4	5	6	7	8	9	10
value	44	77	55	None	None	93	17	None	None	None	54

Binary Hashing

binary hashing adalah cara penyelesaian collision pada hashing dengan memindahkan angka yang collision dengan index_collision=index_collision+(i**2)%panjang_index (i bermula dari angka 1 dengan increment +1) sehingga kita akan tempatkan item yang bertabrakan pada index +(1**2,2**2,dst) hingga menemukan posisi yang kosong.

index	0	1	2	3	4	5	6	7	8	9	10
value	44	77	None	None	55	93	17	None	None	None	54

dapat kita lihat perbedaan pada penempatan index dengan value 55 pada list tersebut. pada Linier hashing value 55 terletak pada index 2. sedangkan pada binary hashing value 55 terletak pada index ke 4.

Close Address
close address adalah cara penyelesaian collision pada hashing dengan menyatukan item-item collision dalam list baru sehingga tidak perlu bergeser-geser lagi. pada data di atas akan didapat 3 item yang collision pada index 0. dengan menggunakan metode close address akan didapati pada index ke 0 berisi [44,77,55]

index	0	1	2	3	4	5	6	7	8	9	10
value	[44,77,55]	None	None	None	None	93	17	None	None	None	54