Mikä on hajautustaulukko ja miten se saavuttaa O(1) haun?

Question

Accepted Answer

**Hajautustaulukko** (hash map) tallentaa **key → value** pareja ja tarjoaa keskimäärin **O(1)** lisäyksen, haun ja poiston. Se toimii ajamalla jokaisen avaimen **hajautusfunktion** läpi, joka kartoittaa sen pohjana olevan taulukon indeksiin ("ämpäriin").

## Kuinka se toimii

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

## Esimerkki

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

## Monimutkaisuus

| Operaatio | Keskimäärin | Pahin tapaus |
|---|---|---|
| lisäys | O(1) | O(n) |
| haku | O(1) | O(n) |
| poisto | O(1) | O(n) |

**Pahin tapaus** O(n) tapahtuu, kun monet avaimet törmäävät samaan ämpäriin.

## Kompromissit

- **Vahvuudet:** erittäin nopea avainpohjainen käyttö; joustavat avaimet.
- **Heikkoudet:** ei avainten järjestystä; ylimääräinen muisti; O(n) pahin tapaus; vaatii hyvän hajautusfunktion.

## Miksi sillä on merkitystä

Hajautustaulukot ovat käytännössä todennäköisesti eniten käytetty tietorakenne — sanakirjojen, joukkojen, välimuistien, tietokannan indeksien ja päällekkäisyyden poistamisen takana.

Lineaarisen skannauksen korvaaminen hajautushaulla on yksi yleisimmistä tavoista muuttaa O(n²) algoritmi O(n):ksi.