Kita mungkin kadang terpikirkan bagaimana search engine seperti google bisa mencari sesuatu berdasarkan kata kunci yang kita masukan atau social media yang mampu mencari ID dari seorang penggunanya dengan sekejap mata?
Beberapa dari kalian mungkin pernah terpikirkan bahwa google mencari sebuah situs seperti halnya kita mencari sebuah bola berwarna hitam dari sekumpulan bola berwarna-warni. Namun, tahukah kalian bahwa metode pencarian google seperti halnya kita mencari buku di perpustakaan atau seperti kita mencari sabun di sebuah supermarket? Yak benar kita langsung menuju ke tempat yang kita cari. Kita tidak mungkin mencari sebuah buku novel yang berada di tengah rak buku sedangkan kita harus menelusuri seluruh rak buku benarkan?
Metode yang google dan teman-temannya lakukan untuk melakukan hal tersebut disebut HASHING. Kalian mungkin pernah belajar tentang struktur data beserta kompleksitasnya contohnya binary tree, B+ tree, dll. Hashing juga termasuk ke dalam struktur data hanya saja dia bisa mencari suatu data dengan kompleksitas O(1). Yak O(1)! Itu berarti dia bisa mencari apapun datanya namun waktu pengerjaanya tetap sama.
Hashing bekerja dengan cara kita membuat sebuah ruang penyimpanan agap saja sebuah rak yang sudah dinomori lalu data yang ingin kita masukan (misal kita ingin memasukan data 150) ke dalam sebuah fungsi hashingnya untuk mendapatkan nomor tempat dimana data tersebut akan disimpan.
Langsung ke contohnya misal kita ingin memasukan nilai 150 tadi ke dalam struktur data kita dan kita mempunyai fungsi hash yaitu h(k) = k mod 11 dengan anggapan kita mempunya 10 space kosong.
h(150) = 150 mod 11 = 7
Berarti berdasarkan fungsi tadi kita akan menyimpan data 150 ke dalam index 7 di struktur data kita.
Jika kita ingin mencari datanya bagaimana? Mudah, metodenya sama seperti kita menyimpan data.
Pertama, kita masukan data yang ingin kita cari misal 150 ke dalam fungsi hash kita. Lalu, didapatlah indexnya yaitu 7. Kemudian, kita tinggal mencari apakah di index 7 ada data yang ingin kita cari atau tidak.
Itukan kalau angka, bagaimana kalau sebuah kata atau kalimat? Metodenya sama hanya saja yang dicari itu kata atau kalimat. Ingat, setiap karakter mempunyai nilai ASCII-nya masing-masing jadi mesin tetap mencari hash-key-nya sama seperti mencari data tadi.
Wah metodenya mudah sekali ya? Eits.... Jangan senang dulu oke anggap kita sudah menyimpan nilai 150. Sekarang, kita akan menyimpan data 128.
h(128) = 128 mod 11 = 7
Lho, kenapa hasilnya sama? Hal ini disebabkan karena fungsi hash kita tidak menghasilkan hasil yang unik sehingga terjadi collision yaitu data yang berbeda tetapi mempunyai key yang sama. Berikut adalah kriteria hashing yang baik :
Beberapa dari kalian mungkin pernah terpikirkan bahwa google mencari sebuah situs seperti halnya kita mencari sebuah bola berwarna hitam dari sekumpulan bola berwarna-warni. Namun, tahukah kalian bahwa metode pencarian google seperti halnya kita mencari buku di perpustakaan atau seperti kita mencari sabun di sebuah supermarket? Yak benar kita langsung menuju ke tempat yang kita cari. Kita tidak mungkin mencari sebuah buku novel yang berada di tengah rak buku sedangkan kita harus menelusuri seluruh rak buku benarkan?
Metode yang google dan teman-temannya lakukan untuk melakukan hal tersebut disebut HASHING. Kalian mungkin pernah belajar tentang struktur data beserta kompleksitasnya contohnya binary tree, B+ tree, dll. Hashing juga termasuk ke dalam struktur data hanya saja dia bisa mencari suatu data dengan kompleksitas O(1). Yak O(1)! Itu berarti dia bisa mencari apapun datanya namun waktu pengerjaanya tetap sama.
Hashing bekerja dengan cara kita membuat sebuah ruang penyimpanan agap saja sebuah rak yang sudah dinomori lalu data yang ingin kita masukan (misal kita ingin memasukan data 150) ke dalam sebuah fungsi hashingnya untuk mendapatkan nomor tempat dimana data tersebut akan disimpan.
Langsung ke contohnya misal kita ingin memasukan nilai 150 tadi ke dalam struktur data kita dan kita mempunyai fungsi hash yaitu h(k) = k mod 11 dengan anggapan kita mempunya 10 space kosong.
h(150) = 150 mod 11 = 7
Berarti berdasarkan fungsi tadi kita akan menyimpan data 150 ke dalam index 7 di struktur data kita.
Jika kita ingin mencari datanya bagaimana? Mudah, metodenya sama seperti kita menyimpan data.
Pertama, kita masukan data yang ingin kita cari misal 150 ke dalam fungsi hash kita. Lalu, didapatlah indexnya yaitu 7. Kemudian, kita tinggal mencari apakah di index 7 ada data yang ingin kita cari atau tidak.
Itukan kalau angka, bagaimana kalau sebuah kata atau kalimat? Metodenya sama hanya saja yang dicari itu kata atau kalimat. Ingat, setiap karakter mempunyai nilai ASCII-nya masing-masing jadi mesin tetap mencari hash-key-nya sama seperti mencari data tadi.
Wah metodenya mudah sekali ya? Eits.... Jangan senang dulu oke anggap kita sudah menyimpan nilai 150. Sekarang, kita akan menyimpan data 128.
h(128) = 128 mod 11 = 7
Lho, kenapa hasilnya sama? Hal ini disebabkan karena fungsi hash kita tidak menghasilkan hasil yang unik sehingga terjadi collision yaitu data yang berbeda tetapi mempunyai key yang sama. Berikut adalah kriteria hashing yang baik :
- Hasil perhitungannya cepat.
- Mempunyai hasil yang unik sehingga data yang disimpan merata di setiap index.
- Kemungkinan collision yang minim.
- Seperate chaining.
- Open addressing.
- Linear probing.
- Double hashing.
- Quadratic probing.
- Primary clustering.
Akan tetapi hashing mempunyai kelemahan dibanding struktur data yang berupa tree:
- Tidak bisa mencari data terbesar dan terkecil.
- Tidak bisa mencari successor dan predecessor.
- Tidak bisa mencari data dengan range tertentu.
- Menampilkan data secara terurut.
Sekian artikel ini semoga bisa menambah wawasan kalian untuk informasi lebih dalam kalian bisa mencari di google "hashing" tanpa tanda petik, jangan lupa kredit apabila kalian ingin menjadikan artikel ini sebagai referensi kalian, dan jangan sungkan untuk membagikan artikel ini ke teman-teman kalian terima kasih.
No comments:
Post a Comment