Hashing: “sudah pernah lihat belum?”

1. Cerita

Kamu admin keuangan. Ada tumpukan invoice dengan nomor 5, 3, 8, 2, 8. Bos tanya: “Ada nomor invoice yang dobel nggak?”

Cara A: ambil invoice pertama, bandingkan dengan semua sisanya. Lalu invoice kedua, bandingkan dengan semua sisanya. Dan seterusnya. Capek.

Cara B: siapkan satu buku catatan. Tiap ambil invoice, cek dulu: “nomor ini sudah ada di buku?” Kalau sudah → dobel! Kalau belum → tulis di buku, lanjut.

Cara B itu persis yang dilakukan database saat kamu pasang UNIQUE index di kolom invoice_no: tiap INSERT, database langsung tahu nomor itu sudah ada atau belum, tanpa membaca ulang seluruh tabel. Di Python, “buku catatan” itu namanya set / dict (keduanya hash map).

2. Kenapa

Masalahnya: mencari ulang. Tanpa catatan, tiap pertanyaan “sudah pernah lihat?” memaksa kita membaca ulang semua data. Hash map menjawab pertanyaan itu seketika, berapa pun banyaknya isi buku.

Sinyal di soal: kata-kata seperti duplicate, pernah muncul, pasangan yang jumlahnya X, hitung frekuensi, kelompokkan.

3. Brute force & 4. Aha

Klik Next di kedua kotak. Hitung langkahnya.

Aha: brute force membandingkan 5 dengan 3, lalu nanti membandingkan 3 dengan yang lain lagi. Ia lupa semua yang sudah dilihat. Hash map mengingat: tiap angka cukup dilihat sekali.

Dengan 5 invoice: 9 vs 5 langkah. Dengan 10.000 invoice: ±50 juta vs 10.000 langkah. Itulah bedanya.

5. Kode

Brute force: dua loop, “tiap item lawan tiap item lain”.

def contains_duplicate(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

O(n²) = kalau datanya n, kerjanya kira-kira n × n. Data 2× lebih banyak → kerja 4× lebih lama.

Hashing: satu loop + buku catatan.

def contains_duplicate(nums):
    seen = set()            # buku catatan kosong
    for x in nums:
        if x in seen:       # sudah pernah lihat? (seketika)
            return True
        seen.add(x)         # belum → catat
    return False

O(n) = lihat setiap item sekali. Data 2× → kerja 2×.
Harganya: buku catatan butuh memori, O(n) space. Tukar memori demi kecepatan — itu trade-off klasik hashing.

Kenapa x in seen seketika? Set menghitung “alamat” dari nilai x (namanya hash), lalu langsung lompat ke laci itu — seperti rak arsip berlabel, bukan membaca satu per satu. Untuk list, x in list justru membaca satu per satu: O(n).

6. Giliranmu

Two Sum — leetcode.com/problems/two-sum. Cari dua angka yang jumlahnya = target.

Salin template: cp templates/problem.py patterns/01_hashing/two_sum_mine.py
Tulis brute force dulu (pasti dua loop). Hitung Big-O-nya.
Lalu tanya diri sendiri pertanyaan hari ini: “angka apa yang sedang aku cari, dan sudah pernah lihat belum?”
uv run pytest patterns/01_hashing/two_sum_mine.py

Jangan buka two_sum.py yang lama — itu contoh jawaban. Stuck? Minta hint ke tutor: hint. Hint naik bertahap, satu per permintaan. Ada yang belum jelas? Tanya saja ke agent, kapan pun.

Sumber utama: NeetCode roadmap → Arrays & Hashing.