LeetCode Grinding
Data Structures1 menit baca

Pengenalan Hash Map

Hash map menyimpan pasangan key dan value untuk lookup, insertion, dan deletion.

Di artikel ini 3 bagian

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:

javascript
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:

javascript
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.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan