Ce este o tabelă de dispersie și cum realizează căutare O(1)?

Question

Accepted Answer

O **tabelă de dispersie** (hash map) stochează perechi **key → value** și oferă **O(1)** mediu pentru insert, lookup și delete. Funcționează prin trecerea fiecărei chei printr-o **funcție de dispersie** care o mapează la un indice dintr-un array subiacent (un "bucket").

## Cum funcționează

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

## Exemplu

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

## Complexitate

| Operație | Mediu | Caz grav |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |

Cazul **grav** O(n) apare când multe chei se ciocnesc în acelaşi bucket.

## Compromisuri

- **Puncte forte:** acces extremă rapid bazat pe chei; chei flexibile.
- **Puncte slabe:** fără ordonare a cheilor; memorie suplimentară; O(n) caz grav; necesită o bună funcție de dispersie.

## De ce conteaza

Tabelele de dispersie sunt probabil cea mai folosită structură în practică — în spatele dicționarelor, seturilor, cache-urilor, indexurilor de baze de date și deduplicării.

Înlocuirea unei scanări liniare cu o căutare de dispersie este una dintre cele mai frecvente moduri de a transforma un algoritm O(n²) în O(n).