Çfarë është një tabelë hash dhe si arrin kërkimin O(1)?

Question

Accepted Answer

Një **tabelë hash** (hash map) ruan çifte **key → value** dhe ofron futje, kërkime dhe fshirje me kompleksitet **mesatarisht O(1)**. Ajo funksionon duke ekzekutuar çdo çelës përmes një **funksioni hash** që e pasqyron atë në një indeks në një array themelor (një "bucket").

## Si funksionon

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

## Shembull

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

## Kompleksiteti

| Operacioni | Mesatare | Më i keq |
|---|---|---|
| futje | O(1) | O(n) |
| kërkimi | O(1) | O(n) |
| fshirje | O(1) | O(n) |

Rasti **më i keq** O(n) ndodh kur shumë çelësa përplasen në të njëjtin bucket.

## Këmbimet

- **Përparësi:** qasje jashtëzakonisht e shpejtë e bazuar në çelës; çelësa fleksibël.
- **Disavantazhe:** pa renditje të çelësave; memorie shtesë; O(n) në rastin më të keq; kërkon një funksion hash të mirë.

## Pse është e rëndësishme

Tabelat hash janë ndoshta struktura më e përdorur në praktikë — në themel të fjalorëve, grupeve, memeve meminë, indekseve të bazës së të dhënave dhe deduplikimit.

Zëvendësimi i një kërkimi linear me një kërkimi hash është një nga mënyrat më të zakonshme për të shndërruar një algoritëm O(n²) në O(n).