Hash-tabeller og dictionaries

It A · STX · A-niveau · Datastrukturer og algoritmer

💻 Hash-tabeller og dictionaries

Hash-tabel: datastruktur med O(1) gennemsnitlig søgning, indsæt, slet.

Hash-funktion: mapper en nøgle til et indeks i en array. God hash-funktion: uniform fordeling, deterministisk, hurtig.

Kollisioner (to nøgler → samme indeks): løses ved Chaining (liste ved hvert indeks) eller Open addressing (linear probing, quadratic probing, double hashing).

Load factor (α = n/m, antal elementer/tabel-størrelse): ved α > 0,7 rehashes tabellen (dobler og genindekserer).

Python dict: hash-tabel implementering. Nøgler skal være hashable (immutable: int, str, tuple). {key: value} syntax. O(1) opslag.

Anvendelser

database-indeksering, caching (memoization), deduplicering (find unikke elementer), frekvens-optælling (Counter).

SHA-256 og kryptografiske hashes: envejs-funktion (kan ikke inverteres). Bruges til password-lagring (bcrypt = hash + salt + iterationer), digital signatur, blockchain.

Birthday paradox: 50% chance for kollision ved √n elementer i tabel af størrelse n — vigtigt for kryptografisk styrke.

Læringsmål

• Redegøre for hvordan en hash-funktion fordeler data i en hash-tabel
• Forklare håndtering af kollisioner i hash-tabeller
• Anvende dictionaries til effektiv opslag i et program

Sådan kan du arbejde med emnet

• Forklar, hvad en hashfunktion gør, og hvad en kollision er i en hashtabel
• Implementér en simpel hashtabel i Python med separate chaining til at håndtere kollisioner
• Beregn, hvad den gennemsnitlige tidskompleksitet for søgning i en hashtabel er, og hvad der kan gøre det værre

Arbejd iterativt med prototyper og dokumentation. Test, evaluér og dokumentér.