Algorithmen I, SS 2015, gehalten am 04.05.2015, Vorlesung 07
1 hour 11 minutes Posted Dec 1, 2015 at 8:59 am.
Hashing (Streuspeicherung)
Hashtabellen
Hashing: Anwendungen
Ein (über)optimistischer Ansatz
Hashing: Anwendungen
Hashtabellen
Exkurs: Konventionen für Elemente
Überblick
Erste Ideen zu Implementierungen
Ein (über)optimistischer Ansatz
Kollisionen
Kollisionsauflösung
Hashing mit verketteten Listen
Beispiel
Analyse
Etwas Wahrscheinlichkeitstheorie für den Hausgebrauch
Beispiel: Variante des Geburtstagsparadoxon
Mehr zum Geburtstagsparadoxon
Analyse für zufällige Hash-Funktionen
Zufällige Hash-Funktionen?
Universelles Hashing
Analyse für zufällige Hash-Funktionen
Universelles Hashing
Eine einfache universelle Familie
Beispiel für H
Beweis
Bit-basierte Universelle Familien
0:00
1:11:31
Show notes
07: Vorlesung |
Watch Video
