X'inhu hash table u kif jilħaq O(1) lookup?

Question

Accepted Answer

A **hash table** (hash map) iħażen **key → value** pairs u joffri **medja O(1)** insert, lookup, u delete. Taħdem billi tgħaddi kull key permezz ta' **hash function** li tmappaha għal index fl-array sottostant ("bucket").

## Kif taħdem

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

## Eżempju

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

## Ikkomplessità

| Operazzjoni | Medja | Agħar każ |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |

L-**agħar każ** O(n) jiġri meta ħafna keys joqgħodu f'collision fl-istess bucket.

## Trade-offs

- **Ħwienet:** aċċess iżjed mgħaġġel ibbażat fuq key; keys flessibli.
- **Debolezzi:** l-ebda ordering tal-keys; memorja żejda; O(n) fl-agħar każ; teħtieġ hash function tajjeb.

## Għaliex hu importanti

Hash tables huma probabbilment l-istruttura l-aktar użata fil-prattika — wara dictionaries, sets, caches, indexes tal-database, u deduplication.

Illokwa linear scan b'hash lookup hija waħda mill-modi l-aktar komuni biex taqleb algoritmu O(n²) għal O(n).