Kuliah Struktur Data a.k.a StrukDat pekan ini membahas tentang hashing. Kata Ibu Dosen ini nanti nyambung sama enkripsi. Terus hashing juga disambung-sambungin dengan sandi-menyandi,, cerita-cerita detektif… (wah bakal seru nih)
Awal pembahasan kita mereview tentang operasi-operasi yang umumnya dikerjakan pada struktur data ttt: insert, delete, dan search. Lalu kita review struktur datanya, tentang seberapa besar kompleksitas masing-masing struktur data dalam melakukan operasi-operasi tersebut.
Terus,, ternyata array itu mempunyai performa big O(1) dengan syarat datanya diakses langsung melalui indeks array tersebut. Mekanisme hashing adalah bagaimana kita memetakan data-data yang kita punya ke suatu integer(secara indeksnya Array kan integer ya) agar bisa mencapai O(1).
Baru sadar juga… ternyata selama ini proses searching biasanya dilakukan dengan membandingkan nilai yang dicari dengan nilai-nilai yang ada pada struktur data yang kita punya, jadi kalau pake BST worst case nya ya O(n) (cari teruss… sampai ujung…:). Nah dengan hashing,, za pikir, awalnya kita yang harus sedikit lebih memutar otak, pikir-pikir bagaimana cara memetakannya.. tapi nanti kalau mau akses performa nya bisa lebih bagus(meski pada kasus-kasus tertentu tidak juga..)..
Kembali ke hashing. Jadi hashing itu terdiri atas 2 komponen (atau apalah namanya) yaitu : 1) hash table, yang ukurannya harus lebih besar daripada data yang akan diinputkan (kenapa? Ya soalnya kalau lebih sedikit nanti datanya nggak masuk semua.. (ya iyalah…):p) 2) hash function, fungsi yang memetakan data ke lokasinya, h(k).
Sedikit dibahas tentang beberapa cara memetakan data.
- Hash Function Truncation à diambil bagian tertentu dari data lalu di concat(dirangkai)
Seinget za spt ini: 655 345 279 menjadi 539
217 286 475 menjadi 725
339 530 607 menjadi 957
(aduh bisi salah euy,, nggak lihat sumber ni…)
- Hash Function Folding à bagian data dipecah-pecah, lalu dijumlahkan
Misalnya : 62538194 dipetakan ke 625 + 381 + 94 = 1100
OOT: Jadi inget sandi-sandi waktu dulu pramuka smp… ada yang namanya sandi AN kalau nggak salah begini : A B C D E F G H I J K L M
N O P Q R S T U V W X Y Z
Kuncinya, huruf yang ada di atas tukeran sama yang ada di bawah, begitu sebaliknya. Jadi kalau ada tulisan : MVMN maka itu artinya apa ayo… 
Ada juga sandi AZ, bedanya dengan sandi AN tadi, kalau sandi AZ, alphabet N nya mulai dari sebelah kanan (di bawah M). Jenis sandi lain yang cukup terkenal dan rada belibet menghafalnya tapi za suka yaitu .. sandi Morse,, yang ditemukan oleh Samuel Finley Breese Morse (heu heuy masih inget, bener gituh penulisannya..?maaf kalau salah). Tapi sekarang sudah nggak begitu inget sandinya karena nggak pernah dipakai. Kalau nggak salah begini menulis kata CINTA dalam ’bahasa’ Morse : -.-. / .. / -. / – /.-
Euup.. kembali ke Hashing. Nah,, ada sedikit masalah yang muncul dalam penggunaan hashing ini. Masalah itu dikenal dengan sebutan Collision. Hash function yang ideal akan memetakan satu ke satu, artinya setiap data yang berbeda ditempatkan ke dua lokasi yang berbeda. Collision terjadi saat data-data yang berbeda ternyata memiliki mapping location yang sama. Nah terus gimana dong…?
Ya… itu mungkin artinya kita harus pandai-pandai menentukan mapping function mana yang paling ideal untuk data kita (dengan kata lain, mencari mapping function dengan kemungkinan terjadi kolisi paling sedikit). Selain itu, jika memang kolisi terjadi, bisa dilakukan Collision Resolution.
Ada dua jenis collision resolution, yaitu yang close dan yang open (wah nyampur2 nih bahasa teh kumaha sih za). Close hashing, atau juga disebut Open addressing (sukanya yang open2 ya,,), memiliki beberapa metode/mekanisme penanggulangan kolisi :
- Linear Probing à jika terjadi kolisi, data yang hendak masuk ke tempat yang sudah terisi akan mencari tempat terdekat dari tempat seharusnya ia berada. Data tersebut akan ‘berjalan’ selangkah demi selangkah mencari tempat yang kosong.
> karena itulah meski mudah, dengan metode ini masih mungkin terjadi peristiwa di mana kita harus mengakses keseluruhan array (karena ditelusurinya satu tempat-satu tempat).
- Quadratic Probing à seperti namanya, data yang mengalami kolisi akan melakukan ’lompatan-lompatan’ kuadratik untuk mencari tempat yang kosong. ’Lompat-lompat’ kuadratik mengikuti fungsi berikut :
Lokasi yang akan ditempati = h(k) + i*i ; dengan i mulai dari nol, dan i akan bertambah satu jika ternyata untuk i=0 tempat yang dimaksud telah terisi, begitu seterusnya.
- Double Hashing à jika terjadi kolisi, data yang mengalami kolisi akan dipindahkan ke lokasi yang sesuai dengan fungsi hasing ke-2. (jadi ada 2 hash function).
Lokasi yang akan ditempati = h(k) + i * fHash2(k); i mulai dari 0.
Sedangkan Open Hash, adalah menambah/ melebarkan/ memberi tempat baru untuk data-data yang mengalami kolisi. Misalnya pada indeks ke-i, ditambahkan tautan (linked list) untuk menapung data-data yang dipetakan ke-i.
Sekian. Karena tulisan ini hanyalah review dengan memanggil kembali memori yang mungkin sebagiannya volatil, maka isi tulisan tidak terjamin. Untuk itu, penulis menyarankan pembaca untuk merujuk kembali kepada referensi-referensi yang lebih meyakinkan.
Teteup semangat…
