Hash-Maps (Dictionaries)

Hash-Map = Schlüssel-Wert-Paare mit O(1) Zugriff. Der Trick: Hash-Funktion mappt Schlüssel auf Index.

Wie es funktioniert

hash("alice") → 7234   → bucket[7234] → ["alice", "[email protected]"]
hash("bob")   → 219    → bucket[219]  → ["bob",   "[email protected]"  ]

Suche: hash(key) → direkter Bucket → vergleiche → fertig

Komplexität

Worst-Case bei vielen Kollisionen (gleicher Hash). Moderne Implementierungen (Java HashMap, Python dict) verwenden Tree-Buckets oder gute Hash-Funktionen.

Beispiele

// JavaScript
const m = new Map();
m.set('alice', 7);
m.get('alice');     // 7
m.has('bob');       // false
m.delete('alice');

// Python
d = {'alice': 7}
d['bob'] = 5
'alice' in d        # True
del d['alice']

Sets — Hash-Maps ohne Werte

Set = nur Schlüssel, keine Werte. Perfekt für: "ist dieses Element schon drin?"

const seen = new Set();
seen.add('alice');
seen.has('alice');   // true — O(1)

Wann Hash-Map?

• Lookup per Schlüssel — der Hauptanwendungsfall
• Deduplizieren (Set)
• Caching
• Counter (Wort-Häufigkeit, Statistiken)

Wann NICHT?

• Reihenfolge wichtig (es gibt Insertion-Order in modernen Maps, aber keine sortierte Reihenfolge)
• Range-Queries ("alle User mit Alter 20-30")
• Speicher knapp — Hash-Map hat Overhead