Vad är en hashtabell och hur uppnår den O(1)-sökning?

Question

Accepted Answer

En **hashtabell** (hash map) lagrar **key → value**-par och erbjuder **i genomsnitt O(1)** infogning, sökning och borttagning. Det fungerar genom att köra varje nyckel genom en **hashfunktion** som mappar den till ett index i en underliggande array (en "bucket").

## Hur det fungerar

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

## Exempel

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

## Tidskomplexitet

| Operation | Genomsnitt | Värsta fall |
|---|---|---|
| infogning | O(1) | O(n) |
| sökning | O(1) | O(n) |
| borttagning | O(1) | O(n) |

**Värsta fall** O(n) inträffar när många nycklar kolliderar i samma bucket.

## Avvägningar

- **Styrkor:** extremt snabb nyckelbaserad åtkomst; flexibla nycklar.
- **Svagheter:** ingen ordning av nycklar; extra minne; O(n) värsta fall; behöver en god hashfunktion.

## Varför det är viktigt

Hashtabeller är troligen den mest använda strukturen i praktiken — bakom ordböcker, uppsättningar, cacheminnen, databasindex och deduplicering.

Att ersätta en linjär sökning med en hashsökning är ett av de vanligaste sätten att förvandla en O(n²)-algoritm till O(n).