Jak hash mapy optymalizują algorytmy?

Question

Accepted Answer

**Hash map** (słownik) oferuje **O(1) średnio** dla operacji wyszukiwania, wstawiania i usuwania. Wymiana O(n) pamięci na szybkość zamienia wiele algorytmów O(n²) na O(n), zastępując powtarzane skanowania natychmiastowymi wyszukiwaniami.

## Idea

Zamiast przeszukiwać listę za każdym razem, przechowuj wartości, które widziałeś w hash mapie i sprawdzaj członkowstwo w stałym czasie.

## Przykład: two-sum w O(n)

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

Bez mapy to O(n²); z nią, jedno przejście.

## Typowe zastosowania

- **Deduplikacja / członkowstwo** za pomocą zbioru.
- **Liczenie częstotliwości** (`Counter`).
- **Grupowanie / indeksowanie** po kluczu.
- **Cachowanie / memoizacja** wyników.

## Złożoność

- **Średnia:** O(1) na operację. **Najgorsza:** O(n) przy dużej liczbie kolizji. **Przestrzeń:** O(n).

## Pułapki

Klucze muszą być **hashowalne** i niezmienne. Kolizje w najgorszym przypadku obniżają wydajność. Hash mapy są nieuporządkowane (użyj wariantów uporządkowanych, jeśli kolejność ma znaczenie).

## Dlaczego to ważne

Hashowanie to najczęstsza optymalizacja w rozmowach o kodowanie i rzeczywistych systemach — zamienia „szukaj ponownie i ponownie