Kuinka hajautustaulukot optimoivat algoritmeja?

Question

Accepted Answer

**Hajautustaulukko** (sanakirja) tarjoaa **O(1) keskimäärin** hakujen, lisäysten ja poistamisten osalta. Korvaamalla toistuvat haut pikahauilla muutetaan monet O(n²) algoritmit O(n):ksi O(n) muistin hinnalla.

## Perustava idea

Sen sijaan, että haettaisiin luetteloa joka kerta, tallenna näkemäsi arvot hajautustaulukkoon ja tarkista jäsenyys vakioajassa.

## Esimerkki: two-sum O(n):ssä

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

Ilman karttaa tämä on O(n²); sen kanssa vain yksi läpiajo.

## Yleiset käyttötavat

- **Duplikaattien poistaminen / jäsenyys** joukon kanssa.
- **Taajuuksien laskeminen** (`Counter`).
- **Ryhmittäminen / indeksointi** avaimen mukaan.
- **Välimuistitus / muistiinpano** tuloksista.

## Monimutkaisuus

- **Keskimäärin:** O(1) operaatiota kohden. **Pahin tapaus:** O(n) raskaiden törmäysten yhteydessä. **Tila:** O(n).

## Sudenkuopat

Avainten on oltava **hajautettavissa** ja muuttumattomia. Pahimman tapauksen törmäykset heikentävät suorituskykyä. Hajautustaulukot ovat järjestämättömiä (käytä järjestettyjä muunnelmia, jos järjestys on tärkeä).

## Miksi se on tärkeää

Hajautus on yksittäin yleisin optimointi ohjelmointihaastattelijoissa ja todellisissa järjestelmissä — se muuttaa "hae uudelleen ja uudelleen" muotoon "etsi se kerran".

Tilan ja ajan vaihtaminen on toistumallinen insinööriliikerata.

Taajuuksien laskeminen, välimuistitus ja indeksointi kaikki perustuvat tähän yhteen ideaan.