Che cos'è una hash table e come raggiunge lookup O(1)?

Question

Accepted Answer

Una **hash table** (hash map) memorizza coppie **key → value** e offre insert, lookup e delete **medi O(1)**. Funziona eseguendo ogni chiave attraverso una **hash function** che la mappa a un indice in un array sottostante (un "bucket").

## Come funziona

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

## Esempio

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

## Complessità

| Operazione | Media | Peggiore |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |

Il **caso peggiore** O(n) si verifica quando molte chiavi collidono nello stesso bucket.

## Trade-off

- **Punti di forza:** accesso estremamente veloce basato su chiave; chiavi flessibili.
- **Punti deboli:** nessun ordinamento delle chiavi; memoria aggiuntiva; O(n) nel caso peggiore; richiede una buona hash function.

## Perché è importante

Le hash table sono probabilmente la struttura più utilizzata nella pratica — dietro dizionari, insiemi, cache, indici di database e deduplicazione.

Sostituire una scansione lineare con un lookup hash è uno dei modi più comuni per trasformare un algoritmo O(n²) in O(n).