Kas yra hešo lentelė ir kaip ji pasiekia O(1) paiešką?

Question

Accepted Answer

**Hešo lentelė** (hešo žemėlapis) saugo **raktas → reikšmė** poras ir suteikia vidutinę **O(1)** įterpimą, paiešką ir trynimą. Tai veikia, perduodant kiekvieną raktą per **hešo funkciją**, kuri jį susieja su indeksu pagrindinėje matricoje ("dėžutėje").

## Kaip tai veikia

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

## Pavyzdys

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

## Sudėtingumas

| Operacija | Vidutine | Blogiausia |
|---|---|---|
| įterpimas | O(1) | O(n) |
| paieška | O(1) | O(n) |
| trynimas | O(1) | O(n) |

**Blogiausia situacija** O(n) atsiranda, kai daug raktų susiduria toje pačioje dėžutėje.

## Kompromisai

- **Stiprybės:** itin greita paieška pagal raktą; lanksčiai raktai.
- **Silpnybės:** raktų nėra išrikioti; papildoma atmintis; O(n) blogiausioje situacijoje; reikalinga gerą hešo funkciją.

## Kodėl tai svarbu

Hešo lentelės yra galbūt labiausiai naudojama struktūra praktikoje — žodynų, aibių, cache, duomenų bazės indeksų ir duplikatų šalinimo atžvilgiu.

Tiesinę paiešką pakeitus hešo paieška yra vienas iš labiausiai paplitusių būdų, kaip O(n²) algoritmą paversti O(n).