Hur optimerar hash-tabeller algoritmer?

Question

Accepted Answer

En **hash-tabell** (dictionary) ger **O(1) i genomsnitt** för sökningar, infogningar och borttagningar. Genom att byta O(n) minne mot hastighet omvandlas många O(n²)-algoritmer till O(n) genom att ersätta upprepade genomsökningar med direkta uppslagningar.

## Grundidén

Istället för att söka igenom en lista varje gång lagrar du värden du sett i en hash-tabell och kontrollerar medlemskap på konstant tid.

## Exempel: två-sum i 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)
```

Utan hash-tabellen är detta O(n²); med den endast ett pass.

## Vanliga användningsfall

- **Deduplikering / medlemskap** med en uppsättning.
- **Räkning av frekvenser** (`Counter`).
- **Gruppering / indexering** efter nyckel.
- **Cachning / memoisering** av resultat.

## Komplexitet

- **Genomsnitt:** O(1) per operation. **Värsta fall:** O(n) vid kraftiga kollisioner. **Utrymme:** O(n).

## Fallgropar

Nycklarna måste vara **hashbara** och oföränderliga. Värsta fall-kollisioner försämrar prestanda. Hash-tabeller är oordnade (använd ordnade varianter om ordning spelar roll).

## Varför det är viktigt

Hashning är den enskilt vanligaste optimeringen i kodningsintervjuer och verkliga system — det förvandlar "sök igen och igen" till "slå upp en gång".

Bytandet av minne mot tid är en återkommande ingenjörsräknation.

Frekvensräkning, cachning och indexering vilar alla på denna enda idé.