Hogyan optimalizálják a hash térképek az algoritmusokat?

Question

Accepted Answer

A **hash térkép** (dictionary) **O(1) átlagos** keresést, beszúrást és törlést biztosít. Az O(n) memória sebességért való cseréje sok O(n²) algoritmust O(n) algoritmusá alakít a többszöri vizsgálatok helyettesítésével azonnali keresésekkel.

## Az ötlet

Ahelyett, hogy minden alkalommal listában keresne, tárolt értékeket tároljunk egy hash térképben és az állandó időben ellenőrizze a tagsági viszonyokat.

## Példa: két szám összege O(n)-ben

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

Térkép nélkül ez O(n²); vele egy menet.

## Gyakori felhasználások

- **Deduplikáció / tagsági** egy halmazmal.
- **Gyakoriságok számlálása** (`Counter`).
- **Csoportosítás / indexelés** kulcs szerint.
- **Gyorsítótárazás / memorizálás** eredmények.

## Komplexitás

- **Átlagos:** O(1) műveletre. **Legrosszabb:** O(n) nehéz ütközéseken. **Tér:** O(n).

## Csapdák

A kulcsok **hashelhetőek** és változtathatatlanok kell legyenek. A legrosszabb esetben az ütközések teljesítményleadást okoznak. A hash térképek rendezetlen (ha a sorrend számít, használjon rendezett változatokat).

## Miért fontos

A hashelés az egyetlen leggyakoribb optimalizálás a kódolási interjúkban és valós rendszerekben – a "keress újra és újra" helyett "keress fel egyszer" alakítódik át.

A hely-idő kompromisszum visszatérő mérnöki eszköz.

A gyakoriságszámlálás, gyorsítótárazás és indexelés mind erre az egy ötletre alapul.