Hashing (Mengen speichern Teil 4)

Bei Hashtabellen werden die Elemente einer Menge in ein Array einsortiert, und zwar an die Stelle, die von einer Hashfunktion vorgegeben wird. Problematisch wird es allerdings, wenn verschiedene Objekte gleichzeitig in dieselbe Zelle abgelegt werden sollen. Damit das nur selten passiert, braucht man eine gute Hashfunktion. Am besten wählt man die Hashfunktion zufällig aus einer Klasse möglicher Hashfunktionen aus. 00:00 - Intro 00:19 - Opas Schrank voller Schrauben 01:35 - Grundidee Hashtabelle 05:05 - Kollisionen 06:38 - Beispiel für Chaining 09:46 - Eigenschaften von Hashfunktionen 13:01 - Beispiele für Hashfunktion 16:55 - Rehashing 19:47 - Universelles Hashing 21:45 - Beispiele für universelle Hashfunkionen 26:38 - Mengen in Hashfunktionen speichern 30:52 - Überblick: Laufzeiten unterschiedlicher Datenstrukturen für Mengen - Mengen in unsortierten Listen - lineare Suche: https://youtu.be/VdeUrRgPYAw - Mengen in sortierten ArrayListen - Binärsuche: https://youtu.be/oBoJn1IbnaA - Mengen in Suchbäumen: https://youtu.be/I1vcEaeZnPg