Universelles Hashing

Sei eine endliche Menge von Hashfunktionen. Wenn für jedes Paar mit gilt, dass die Zahl der Hashfunktionen mit maximal ist, dann heißt universell.

Anwendung

• Zur Laufzeit wählt der Algorithmus zufällig eine Hashfunktion aus
• Gutes mittleres Laufzeitverhalten

Laufzeit

Für das Einfügen, Suchen und Löschen hat universelles Hashing eine erwartete Komplexität von