Czym jest tablica mieszająca i jak osiąga wyszukiwanie O(1)?

Question

Accepted Answer

**Tablica mieszająca** (hash map) przechowuje pary **key → value** i oferuje średnio **O(1)** insert, lookup i delete. Działa poprzez przepuszczenie każdego klucza przez **funkcję mieszającą**, która mapuje go na indeks w podstawowej tablicy ("bucket").

## Jak to działa

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

## Przykład

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

## Złożoność

| Operacja | Średnia | Najgorszy przypadek |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |

**Najgorszy przypadek** O(n) występuje, gdy wiele kluczy zderza się w tym samym bucket.

## Kompromisy

- **Mocne strony:** niezwykle szybki dostęp oparty na kluczach; elastyczne klucze.
- **Słabe strony:** brak uporządkowania kluczy; dodatkowa pamięć; O(n) w najgorszym przypadku; wymaga dobrej funkcji mieszającej.

## Dlaczego to ważne

Tablice mieszające są prawdopodobnie najczęściej używaną strukturą w praktyce — za słownikami, zbiorami, pamięciami podręcznymi, indeksami baz danych i deduplikacją.

Zastąpienie skanowania liniowego wyszukiwaniem hash jest jednym z najczęstszych sposobów zamiany algorytmu O(n²) w O(n).