Apakah jadual hash dan bagaimana ia mencapai pencarian O(1)?

Question

Accepted Answer

**Jadual hash** (peta hash) menyimpan pasangan **kunci → nilai** dan menawarkan purata **O(1)** sisip, pencarian, dan padam. Ia berfungsi dengan menjalankan setiap kunci melalui **fungsi hash** yang memetakannya ke indeks dalam array asas ("bucket").

## Bagaimana ia berfungsi

```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
```

## Kerumitan

| Operasi | Purata | Paling teruk |
|---|---|---|
| sisip | O(1) | O(n) |
| pencarian | O(1) | O(n) |
| padam | O(1) | O(n) |

Kes **paling teruk** O(n) berlaku apabila banyak kunci berlanggar ke bucket yang sama.

## Pertukaran

- **Kekuatan:** akses berasaskan kunci yang sangat cepat; kunci yang fleksibel.
- **Kelemahan:** tiada pengurutan kunci; memori tambahan; O(n) kes paling teruk; memerlukan fungsi hash yang baik.

## Mengapa penting

Jadual hash mungkin struktur yang paling digunakan dalam praktik — di sebalik kamus, set, cache, indeks pangkalan data, dan penyingkiran duplikat.

Menggantikan imbasan linear dengan pencarian hash adalah salah satu cara paling biasa untuk mengubah algoritma O(n²) menjadi O(n).