Hashtabelle

Funktionsweise

Ziel einer Hashtabelle ist es, Daten mit anderen Daten zu verknüpfen. Input wird gehasht und somit zu einem kürzeren Wert verarbeitet. Dieser Hash verweist auf die Zieldaten und muss nicht eindeutig sein Anzahl der abzugleichenden Daten ist gering und das Ergebnis wird schnell gefunden, da mehrere Werte als "Übersetzung" vorhanden sind und somit aus einer kleineren Liste die Daten gefunden werden müssen Daten werden sogesehen also gruppiert, um sie dann aus einer kürzeren Liste schneller auslesen zu können.

SondierenDaten eintragen kann ein Problem darstellen. Zunächst muss eine freie Stelle in der Tabelle gefunden werden. Linear: Oben anfangen und nach unten durchlaufen Quadratisch: Optimierung, die weniger Kollisionen verursacht als Linear. Man findet also schneller eine freie Stelle. DoppelhashingMan bildet zwei Hashes mit verschiedenen Verfahren und versucht, dadurch die Wahrscheinlichkeit von Kollisionen (doppelten Einträgen) auszuschließen.Linear: https://www.youtube.com/watch?v=NbgTir1OzT8Quadratisch: https://www.youtube.com/watch?v=y-ShN91uVDYDoppeltes Hashing: https://www.youtube.com/watch?v=6LR7zXAXZnU