Hash Table

Penyimpanan key-value yang memakai hash function untuk memetakan key ke index bucket, sehingga pencarian rata-rata O(1).

Kompleksitas

Waktu (Terbaik)

O(1)

Waktu (Rata-rata)

O(1)

Waktu (Terburuk)

O(n)

Memori

O(n)

Poin Penting

›Rata-rata O(1) untuk insert, delete, dan lookup
›Hash collision (dua key masuk ke bucket yang sama) bisa menurunkan performa hingga O(n) di kasus terburuk
›Strategi umum menangani collision: chaining (linked list per bucket) atau open addressing
›Load factor (n/kapasitas) yang terlalu tinggi (biasanya > 0.75) memicu resize
›Key harus bisa di-hash; urutannya tidak dijamin (gunakan LinkedHashMap jika butuh urutan penyisipan)

Contoh Kode

Swift

// Swift uses Dictionary as its hash table
var table: [String: Int] = [:]

// Insert/Update — O(1) avg
table["apple"] = 5
table["banana"] = 3
table["cherry"] = 8

// Lookup — O(1) avg
if let count = table["apple"] {
    print("apple: \(count)")   // apple: 5
}

// Delete — O(1) avg
table.removeValue(forKey: "banana")

// Check existence — O(1) avg
let exists = table["cherry"] != nil

// Iterate — O(n)
for (key, value) in table {
    print("\(key): \(value)")
}

print(table.count)  // 2

Latihan Soal

Two Sum

MudahLeetCode ↗

Contains Duplicate

MudahLeetCode ↗

Group Anagrams

SedangLeetCode ↗

Longest Consecutive Sequence

SedangLeetCode ↗