Come i hash map ottimizzano gli algoritmi?

Question

Accepted Answer

Un **hash map** (dizionario) fornisce lookups, inserimenti e cancellazioni in **O(1) media**. Scambiare O(n) memoria per velocità trasforma molti algoritmi O(n²) in O(n) sostituendo scansioni ripetute con lookups istantanei.

## L'idea

Invece di cercare in una lista ogni volta, memorizza i valori visti in un hash map e verifica l'appartenenza in tempo costante.

## Esempio: two-sum in O(n)

```python
def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:               # O(1) lookup
            return (seen[need], i)
        seen[x] = i
    return None

two_sum([2, 7, 11, 15], 9)             # -> (0, 1)
```

Senza la map questo è O(n²); con essa, una sola passata.

## Usi comuni

- **Deduplicazione / appartenenza** con un set.
- **Conteggio delle frequenze** (`Counter`).
- **Raggruppamento / indicizzazione** per chiave.
- **Caching / memoizzazione** dei risultati.

## Complessità

- **Media:** O(1) per operazione. **Peggiore:** O(n) in caso di molte collisioni. **Spazio:** O(n).

## Insidie

Le chiavi devono essere **hashable** e immutabili. Collisioni nel peggiore dei casi degradano le prestazioni. Gli hash map sono non ordinati (usa varianti ordinate se l'ordine è importante).

## Perché è importante

L'hashing è la singola ottimizzazione più comune nei colloqui di codifica e nei sistemi reali — converte "cercare ancora e ancora" in "cercalo una volta".

Lo scambio spazio-tempo è una leva di ingegneria ricorrente.

Il conteggio delle frequenze, il caching e l'indicizzazione si basano tutti su questa un'idea.