Hash-Verfahren

Hash-Verfahren versuchen, die Ermittlung eines Datensatzes in Abhängigkeit eines Schlüssels k K mit Hilfe einer Hash-Funktion h: K -> M zu vereinfachen, die einen Schlüssel k in eine Speicherposition m M abbildet.

Leider ist es nicht trivial, selbst für eine auch nur relativ kleine vorgegebene Menge von Schlüsseln K eine Hash-Funktion zu finden, die injektiv ist, d.h.
k₁, k₂ K: h(k₁) h(k₂)

Entsprechend sind Kollisionen auch bei geringen Mengen an Schlüsseln sehr wahrscheinlich (Geburtstagsproblem).

Problemstellungen:

Wie wird mit Kollisionen umgegangen?

Wie könnte eine ``gute'' Hash-Funktion aussehen?