Apa itu hash table dan bagaimana cara mencapai O(1) lookup?

Question

Accepted Answer

A **hash table** (hash map) menyimpan pasangan **key → value** dan menawarkan **average O(1)** insert, lookup, dan delete. Ini bekerja dengan menjalankan setiap key melalui **hash function** yang memetakannya ke indeks dalam array dasar (sebuah "bucket").

## Cara kerjanya

```text
key "cat" --hash()--> 3   buckets:
key "dog" --hash()--> 0     [0] -> ("dog", 5)
                            [1]
                            [2]
                            [3] -> ("cat", 9)
```

## Contoh

```python
phone = {}
phone['alice'] = 555_1234   # insert -> hash 'alice' to a bucket
num = phone['alice']        # lookup -> hash again, jump to bucket
del phone['alice']          # delete
'bob' in phone              # membership -> O(1) average
```

## Kompleksitas

| Operation | Average | Worst |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |

**Worst case** O(n) terjadi ketika banyak key bertabrakan ke dalam bucket yang sama.

## Trade-offs

- **Strengths:** akses berbasis key yang sangat cepat; key yang fleksibel.
- **Weaknesses:** tidak ada pengurutan key; memori tambahan; O(n) worst case; membutuhkan hash function yang baik.

## Mengapa ini penting

Hash table adalah struktur yang paling sering digunakan dalam praktik — di balik dictionaries, sets, caches, database indexes, dan deduplication.

Mengganti linear scan dengan hash lookup adalah salah satu cara paling umum untuk mengubah algoritma O(n²) menjadi O(n).