# Portabilitaet: UNIVERSAL
# Zuletzt validiert: 2026-01-28 (Gemini)
# Naechste Pruefung: 2027-01-28
# Quellen: [informatik/datenstrukturen/README.txt]

HASHMAPS & HASHING
==================

Stand: 2026-01-28

DIE MAGIE VON O(1)
------------------
Hashmaps (in Python `dict`, in JS `Object`/`Map`) sind die Arbeitspferde moderner Software.
Sie erlauben es, Daten anhand eines Schlüssels (Key) sofort zu finden, ohne zu suchen.
`map.get("Alice")` -> Geht direkt zur Adresse, keine Schleife, kein Baum.

WIE FUNKTIONIERT ES?
--------------------
1. **Hash-Funktion:** Nimmt den Key ("Alice") und rechnet ihn in eine Zahl um (Hashcode, z.B. 123).
2. **Mapping:** Rechnet die Zahl auf die Groesse des internen Arrays runter (`123 % 10 = Index 3`).
3. **Speichern:** Legt den Wert an Index 3 im Array ab.

KOLLISIONEN
-----------
Was, wenn "Bob" zufaellig auch Index 3 ergibt? Das ist eine Kollision.
Loesungen:
- **Chaining:** An Index 3 liegt eine verkettete Liste. Alle Kollisionen kommen in die Liste.
- **Open Addressing:** Wenn 3 voll ist, probier 4, dann 5...

PERFORMANCE
-----------
- **Ideal:** O(1) - Zugriff ist konstant schnell.
- **Worst Case:** O(n) - Wenn alle Keys auf den gleichen Index hashen (alles landet in einer Liste). Das passiert bei schlechten Hash-Funktionen oder DoS-Attacken.

HASHSET (MENGE)
---------------
Ein Hashset ist eine Hashmap, die nur Keys und keine Values speichert.
Perfekt fuer:
- Dubletten entfernen.
- Schnelle Pruefung "Ist X schon da?".

ANWENDUNGEN
-----------
- Caching (Key=URL, Value=Content).
- Datenbank-Indizierung.
- Symboltabellen in Compilern.
- Zaehlen (Wort-Haeufigkeit).

IN PYTHON
---------
Pythons `dict` ist hochoptimiert.
- Keys muessen "hashable" sein (immutable: int, string, tuple). Listen koennen keine Keys sein!

SIEHE AUCH
----------
wiki/informatik/algorithmen/suche.txt
wiki/informatik/algorithmen/komplexitaet.txt
