Mi az a hash table (hash térkép) és hogyan éri el az O(1) keresést?

Question

Accepted Answer

A **hash table** (hash térkép) **kulcs → érték** párokat tárol, és átlagosan **O(1)** beszúrást, keresést és törlést kínál. Úgy működik, hogy minden kulcsot egy **hash függvényen** keresztül futtat, amely egy alapul szolgáló tömbben (egy "bucket"-ben) lévő indexre képezi le.

## Hogyan működik

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

## Példa

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

## Komplexitás

| Operáció | Átlagos | Legrosszabb |
|---|---|---|
| beszúrás | O(1) | O(n) |
| keresés | O(1) | O(n) |
| törlés | O(1) | O(n) |

A **legrosszabb eset** O(n) akkor fordul elő, amikor sok kulcs ugyanabba a bucket-be ütközik.

## Kompromisszumok

- **Erősségek:** rendkívül gyors kulcs alapú hozzáférés; rugalmas kulcsok.
- **Gyengeségek:** a kulcsok nincsenek rendezve; extra memória; O(n) legrosszabb eset; jó hash függvényre van szükség.

## Miért fontos

A hash table-ek gyakorlatilag a leggyakrabban használt adatstruktúrák — szótárak, halmazok, cache-ek, adatbázis indexek és deduplikáció mögött állnak.

A lineáris keresés hash keresésre cserélése az egyik leggyakoribb módja annak, hogy egy O(n²) algoritmust O(n)-re alakítsunk át.