Apa iku hash table lan kepiye cara gawe O(1) lookup?

Question

IT Interview Practice · Accepted Answer

A **hash table** (hash map) nyimpen pasangan **key → value** lan menehi rata-rata **O(1)** insert, lookup, lan delete. Iki gumana kanthi njalani saben kunci lumantar **hash function** sing peta menyang indeks ing array ndasar (a "bucket").

## Carane gumana

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

## Conto

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

| Operasi | Rata-rata | Paling parah |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |

Kesuwene **paling parah** O(n) dumadi nalika akeh kunci tabrakan menyang bucket sing padha.

## Trade-off

- **Kaunggulan:** akses adhedhasar kunci sing banter sekali; kunci sing fleksibel.
- **Kalemahan:** ora ana pangaturan kunci; memori tambahan; O(n) kesuwene paling parah; butuh fungsi hash sing apik.

## Mengapa iku penting

Hash table bisa dadi struktur paling akeh digunakake ing praktik — ing tulikane kamus, himpunan, cache, indeks basis data, lan deduplikasi.

Ngganti sekedheng linear kanthi hash lookup minangka salah siji cara paling umum kanggo ngowahi algoritma O(n²) menyang O(n).

Carane gumana

Conto

Kompleksitas

Trade-off

Mengapa iku penting

Pitakon sing gegandhengan