AL Tutorium 4

Welche Datenstruktur ist am besten geeignet?

Uni will Student*in-Objekte verwalten

• Hashtabelle

• Liste

• Array

• Aktenordner

Welche Dinge sind beim Hashing involviert?

• Key

• Array

• Universum

• Liste

Was beschreibt das Universum U am besten?

• Bild(h)

• Schlüsselmenge

• Urbild(h)

• Objektmenge

Was ist für eine Schlüsselfunktion wünschenswert?

• Kleines Bild

• Injektivität

• Surjektivität

• Bijektivität

Welche Operationen unterstütz eine Hashtabelle?

• get

• push

• remove

• find

Hashfunktionen sind immer

• injektiv

• nicht injektiv

• surjektiv

• besser als Arrays

Was gilt für Hashfunktionen?

• immer kollisionsfrei

• nie kollisionsfrei

• invertierbar

• ermöglichen schnellen Zugriff

Was gilt für universelle Familien?

• Menge an Hashfunktionen

• Zufällig gezogene h1, h2 erzeugen immer wenig Kollisionen

• Für alle Paare h1,h2 ist die Kollisionswsk. gering

• Sind kollisionsfrei

Wie lassen sich kollisionen vermeiden?

• Tabellenvergrößerung

• Listen einfügen

• andere Hashfunktion wählen

• garnicht