Hash table: cara kerja, kode Python, dan kompleksitasnya

Masalah apa yang diselesaikan hash table

Misalkan Anda menyimpan satu juta data pengguna dan perlu mencari satu berdasarkan email. Memindai list itu O(n). Menjaga list tetap terurut memungkinkan binary search O(log n), tetapi insert menjadi lambat. Hash table menemukan data dalam waktu O(1) rata-rata, berapa pun jumlah datanya, dan insert serta delete sama cepatnya.

Itulah mengapa hash table ada di mana-mana: dictionary dan set di bahasa pemrograman, hash index database, cache, symbol table di compiler, dan deduplikasi.

Ide dasarnya dengan bahasa sederhana

Bayangkan tempat penitipan jaket dengan 100 gantungan bernomor. Alih-alih memeriksa semua gantungan untuk mencari jaket Anda, petugas menghitung nomor gantungan dari nama Anda lalu langsung ke sana. Fungsi yang menghitung nomor itu adalah fungsi hash. Fungsi hash yang baik itu cepat, selalu menghasilkan angka yang sama untuk key yang sama, dan menyebar key yang berbeda secara merata ke seluruh gantungan.

1. Hitung h = hash(key).
2. Pilih bucket: index = h % capacity.
3. Cari key hanya di dalam bucket itu.

Contoh langkah demi langkah: collision dengan chaining

Ambil tabel dengan 4 bucket dan fungsi hash mainan: jumlah posisi huruf (a = 1, b = 2, ...).

act dan bee bertabrakan dengan cat. Mencari bee sekarang berarti memeriksa tiga entri di bucket 0. Dengan fungsi hash yang buruk (jumlah huruf mengabaikan urutan) atau bucket yang terlalu sedikit, rantai menjadi panjang dan tabel melambat. Fungsi hash yang sebenarnya mencampur semua bit dari key, dan tabel yang sebenarnya membesar saat sudah terlalu penuh.

Implementasi Python dengan separate chaining

Setiap bucket adalah list berisi pasangan [key, value]. Ketika jumlah item melebihi 0,75 kali jumlah bucket (load factor), tabel menggandakan kapasitasnya dan memasukkan ulang semuanya.

class HashTable:
    def __init__(self, capacity=8):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0
    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]
    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value        # update existing key
                return
        bucket.append([key, value])
        self.size += 1
        if self.size > 0.75 * len(self.buckets):
            self._resize()
    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default
    def delete(self, key):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False
    def _resize(self):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.buckets = [[] for _ in range(2 * len(self.buckets))]
        self.size = 0
        for k, v in old:
            self.put(k, v)

t = HashTable()
for i, word in enumerate(["red", "green", "blue", "cyan", "pink", "gold", "gray"]):
    t.put(word, i)
t.put("red", 100)
t.delete("blue")
print(t.get("red"), t.get("blue"), t.size, len(t.buckets))  # 100 None 6 16

Perbandingan strategi collision

dict di CPython memakai open addressing dengan urutan probe yang diperturbasi dan, sejak Python 3.7, menjamin iterasi mengikuti urutan penyisipan. HashMap di Java memakai chaining dan mengubah rantai yang panjang menjadi balanced tree.

Kompleksitas waktu dan ruang

O(1) rata-rata bergantung pada fungsi hash yang baik dan load factor yang terbatas. Python mengacak hash string per proses (hash seeding) agar penyerang tidak mudah mengirim banyak key yang bertabrakan dan memperlambat server menjadi O(n) per request.

Kesalahan umum

• Memakai objek mutable sebagai key, atau mendefinisikan __eq__ pada kelas tanpa __hash__ yang sesuai. Objek yang sama harus punya hash yang sama.
• Mengharapkan urutan terurut. Hash table memberi lookup cepat, bukan urutan; gunakan sorted list atau balanced tree (binary search tree) ketika Anda butuh range query atau key minimum.
• Mengandalkan nilai hash() antar eksekusi: hash string berubah antar proses Python kecuali PYTHONHASHSEED ditetapkan. Gunakan hashlib untuk hash yang stabil.
• Menganggap hash table sebagai primitif keamanan. Hash table memakai hash cepat non-kriptografis; password butuh fungsi password hashing khusus.

Kapan dipakai dan penggunaan khas di wawancara

Gunakan hash table setiap kali Anda perlu menjawab "sudahkah saya melihat ini?" atau "nilai apa yang dimiliki key ini?" dengan cepat. Gunakan binary search tree atau sorted array ketika Anda juga butuh urutan, rentang, atau key terdekat.

Soal klasik: two sum (simpan indeks tiap angka, cari target - x), menghitung frekuensi (collections.Counter), mengelompokkan anagram berdasarkan huruf terurut, mendeteksi duplikat, dan memoization hasil pada dynamic programming.

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i
    return None
print(two_sum([2, 7, 11, 15], 9))  # (0, 1)