Aku pakai hash map untuk menyimpan hitungan dan mengingat value yang udah muncul. Daripada mencari lagi di input, aku mengambil value yang tersimpan lewat key-nya.
Hash map sebagai penyimpanan key value
Hash map menyimpan pasangan key value. Key menentukan lokasi, jadi lookup nggak perlu men-scan setiap value yang tersimpan. Biaya rata-ratanya O(1), walaupun collision dan implementasi yang dipilih memengaruhi detailnya.
Untuk frequency count, key-nya berupa karakter dan value-nya berupa jumlah kemunculan. Untuk cek keanggotaan, value cukup mencatat bahwa key itu udah muncul.
Contoh dalam kode
Function ini menghitung kemunculan setiap karakter di string:
function countChars(str) {
const counts = {};
for (let char of str) {
counts[char] = (counts[char] || 0) + 1;
}
return counts;
}
Untuk array berisi angka, versi ini berhenti ketika sebuah value muncul dua kali:
function hasDuplicate(nums) {
const seen = {};
for (let num of nums) {
if (seen[num]) return true;
seen[num] = true;
}
return false;
}
Kapan struktur lain lebih cocok
Aku menghindari hash map kalau butuh key yang terurut atau range query. Pemakaian memorinya juga bisa jadi batasan. Tree atau struktur terurut lainnya bisa menjawab query semacam itu dengan lebih langsung.
Lookup yang cepat tetap butuh memori: menyimpan n key berbeda biasanya memakai O(n) space. Aku pakai hash map kalau state itu menghindari pekerjaan yang berulang.

Memuat komentar...