Apa itu Hash table ?
Tulisan ini saya mulai dengan cerita persiapan saya melamar ke beberapa tech company. Kebanyakan dari tahapan interview yang ada pasti melewati coding test. Dulu waktu kuliah beberapa konsep penting yang digunakan untuk coding test itu dipelajari di semester 3, dulu kayaknya matkul ini jadi momok buat angkatan karena dosen yang ngajar selalu bilang banyak dari kakak tingkat yang ngulang di matkul ini. Karena konsep ini udah lama gak dipelajari, saya coba inget-inget kembali. Saya akan coba menjelaskan salah satu konsepnya yaitu tentang Hash table sekaligus dengan contoh pengaplikasiannya ketika menyelesaikan 1 soal di Hackerrank.
Soal Ice Cream Parlor
Jadi beberapa waktu yang lalu saya coba untuk solve soal yang ini. Sederhananya dalam soal ini kita diminta untuk mendapatkan indeks dari dua buah elemen array (cost) yang mana kalau nilai elemennya dijumlahkan hasilnya adalah bilangan lain yang sudah ditentukan (money). Indeks tadi ditampilkan ke layar dengan urutan indeks yang lebih kecil keluar lebih dulu. Untuk lebih jelasnya bisa dibaca disini.
Solusi
Sebelum keluar dengan kode yang ini, sebelumnya juga saya sudah coba dengan code yang lain tapi selalu gagal karena time limit. Jadi saya coba mencari beberapa petunjuk. Saya liat dari judul problem-nya dan diskusi paling atas sepertinya penyelesaiannya bisa menggunakan Hash Table.
Apa itu Hash table ?
Secara sederhananya Hash table itu struktur data yang menyimpan datanya menggunakan pasangan key dan value. Komponen inti dari struktur data ini adalah adanya Hash function. Hash function ini berfungsi untuk mengubah key yang dipakai menjadi nilai Hash, nah nilai Hash ini akan digunakan untuk meng-indeks value yang ada di Hash table.
Apa keuntungan menggunakan hash table ?
Beberapa keuntungan menggunakan hash table menurut saya adalah:
- Berbeda dengan array dimana kita harus mendefinisikan terlebih dahulu jumlah elemen yang mau disimpan, hash table umumnya bisa selalu menampung elemen secara dinamis tanpa perlu mendefinisikan jumlahnya selama memori komputer belum penuh. Tapi ada bentuk array yang telah dimodifikasi untuk dapat menampung jumlah elemen secara dinamis di beberapa bahasa pemrograman.
- Average time untuk search, insert, dan delete adalah O(1). Jadi sangat cepat.
- Key yang digunakan bisa dengan berbagai macam tipe, jadi tidak harus integer.
Hash table di c++
Karena dulu mata kuliah algoritma dan struktur data menggunakan bahasa c++, jadi saya lebih terbiasa menggunakan c++ untuk mengerjakan coding challenge. Untuk menggunakan hash table di c++ kita tidak perlu mengimplementasikannya dari awal karena sudah ada yang siap pakai yaitu tipe data std::unordered_map. Lalu bagaimana menggunakan hash table untuk menyelesaikan soal Ice Cream Parlor ?
Penyelesaian saya adalah seperti ini:
- Kita siapkan hash table untuk menyimpan data dengan key adalah nilai dari elemen array dan value adalah indeks elemen array.
- Kita telusuri array yang diberikan dari indeks pertama.
- Di setiap iterasi kita simpan selisih dari nilai yang dicari dengan nilai elemen indeks saat ini.
money — cost[i]. - Lalu kita cek adakah elemen hash table dengan key-nya adalah nilai selisih tadi. Kalau ada, kita tampilkan nilai elemen tersebut dan juga indeks saat ini. Kalau tidak ada, kita masukkan nilai elemen array beserta indeks saat iterasi tersebut ke hash table.
Semoga teman-teman tidak kesulitan memahami algoritma penyelesaian saya ya… 😅. Kalau masih bingung, mungkin akan lebih jelas dengan membaca kode penyelesaian saya dibawah.
Kalau teman-teman ada cara penyelesaian yang lain, boleh dong di-share. Terimakasih buat yang udah baca, semoga bermanfaat ya.
