Infobratik 2: Hashing

Motivation

• Wir sollen wie immer komisch motiviert werden
• Ich weiss nicht zu was das führen soll
• Scheinbar gibt es das Szenario öfter, dass wir daten anhand von einem numerischen Schlüssel abspeichern und dann suchen
• Beispielsweise
  • Die doofen Studis mit ner Matrikelnummer
  • Menschen mit IDs
  • Bürger einer Stadt mit Ausweisnummer (hold up, da sind Buchstaben drin)
• Leider ist unsere Schlüsselmenge gerade ein bissl zu groß
  • Wir können die also dann auch verringern

Danzer sagt, dass das Intuitiv ist:

• Wir nehmen eine kleinere schlüsselmenge und bilden die ab und versuchen gleichzeitig Kollisionen zu vermeiden.
• Beispiel: Die unibib will aus dem Archiv bestellte Bücher in Regalfächern nach der Matrikelnummer bereitstellen.

Hashtabellen

• Operationen sind breus
• Hashtabellen implementieren halt das Dictionary (jedenfalls nennt glasi das so)
• Mir wird zugeflüstert, dass man das auf Deutsch auch "assoziatives Array" nennt, noch nie gehört ehrlich gesagt
• Die dinger haben ein paar (mehr oder weniger) sinnvolle operationen
  • aufbauen
  • einfügen
  • löschen
  • suchen
• Zum vergleich:
  • Queues erlauben nur insert und deleteMin (also älteste element löschen)
  • Sortierte Folgen erlauben locate, insert und delete
• Wir brauchen also $O(n)$ Platzbedarf und verarbeiten alles idealerweise in $O(1)$ Zeit.
• Wir betrachten die Menge $S$ von Eintragen mit Schlüsseln $key(e)\in Key$
  • Am ende nutzen wir eine Hashfunktion
    • Wenn wir was reinwerfen kriegen wir den hash (also ne Zahl in diesem fall) raus
  • Und die hashtabelle (dat einfach nen Array)
• Leider können in diesem Approach immernoch Elemente / indizes Kollidieren, was es zu vermeiden gilt
• Daher müssen wir uns dafür eine Alternative Ausdenken
• 
• Hier können wir ein "Tolles" beispiel sehen, wie man hashtabellen anwenden kann
• leichzeitig können wir aber auch sehen, wie "einfach" kollisionen passieren können
• Dementsprechend suchen wir jetzt ein paar wege mit denen man Kollissionen vermeiden / umgehen kann
• Dafür gibt es verschiedene Lösungsansätze
  • Hashing mit Verketting
  • Hashing mit offener Addressierung (in der VL stehen hier noch die englischen namen, aber ich glaube ihr seit schlau genug, dass ihr das auch so kapiert weil naja, englisch ist irgenwie nen requirement)
• Gleichzeitig müssen wir uns überlegen welche Hashfunktion am besten passt
  • Passt für unsere Anwendung besser eine einfache, aber individuelle
  • oder eine (warscheinlich kompliziertere) universelle Hashfunktion

Hashing mit Verkettung

• Wenn wir bei jedem Index, also jeder Zelle in der Hashtabelle eine Verkettete Liste speichern, können wir mehrere sachen auf einmal speichern, die den selben Hashwert haben
• Jedes element $e$ wird dann dementsprechend in der Liste in $t[h(e)]$ gespeichert.
• Das ding hat dann logischer weise auch wieder einige operationen
  • Find
  • remove
  • insert
  • build
• Alle "access" funktionen durchsuchen die Folge
• 
• Da stellt sich die Frage, ob es Hashfunktionen geben kann, die eine Kleine bzw. kurze Liste garantieren
  • Leider gibt es das nicht, da wir nicht garantieren können, dass der "letzte" schlüssel gegrabbled wird
• Wie(so) ist Hashibg dabb immernoch effizient?
• Dafür haben wir verschieden Ansätze
  • Durchschnittsanalyse
  • Randomisierung
  • Perfektes Hashing für statische Schlüsselmenge

Durchschnittsanalyse

• 
• Wir folgern, dass wir linearen Platzbedarf und konstante erwartete Ausführungzeiten der Operationen durch $m=\Theta (n)$ erreichen.
  Dabei passen wir dann die Tabellengröße an, so wie wir das schon bei unbeschränkten arrays gesehen haben

Universelle Hashfunktionen

• Die sollen so viele verschiede Themenbereiche wie möglich abdecken, und das am besten auch noch möglichst effizient machen.
• Für Mehr infos einfach VL 12 Folien 43-60 anstarren :)