Hash-tabeller og dictionaries

Kommunikation og IT A · HTX · A-niveau · Datastrukturer og algoritmer

💻 Hash-tabeller

En hash-tabel mapper nøgler til værdier med næsten O(1) opslag, indsæt og sletning.

Hash-funktion: konverterer nøgle til indeks i array.

```python

indeks = hash("nøgle") % tabelstørrelse

```

Kollisioner: to nøgler giver samme indeks. Løsninger:

• Chaining: hvert indeks er en liste af (nøgle, værdi)-par
• Open addressing: find næste ledige plads

Python dict er en hash-tabel:

```python

d = {"navn": "Alice", "alder": 25}

d["by"] = "København" # O(1) indsæt

print(d["navn"]) # O(1) opslag

"navn" in d # O(1) membership test

```

Load factor: antal elementer / tabel-størrelse. Når > 0.7 → tabel-resize (kopiér alt = O(n)).

Anvendelser: caches, databaseindekser, symbol-tabeller i compilere, Python set og dict.

Læringsmål

• Forklare hvordan hash-funktioner og hash-tabeller fungerer
• Implementere en simpel hash-tabel med chaining
• Analysere kollisioner og deres løsninger
• Bruge Python dict effektivt og forstå dens kompleksitet

Sådan kan du arbejde med emnet

• Forklar hvordan en hash-funktion afgør hvor et element gemmes i en hash-tabel
• Beskriv hvad der sker ved en kollision, og hvordan den kan håndteres
• Brug en dictionary til at tælle hvor mange gange hvert ord forekommer i en tekst

Træningsforslag

• Implementér en simpel hash-tabel fra bunden med chaining
• Byg et enkelt cache-system med dict
• Løs LeetCode #1 (Two Sum) med hash-tabel-tilgang