cards-deck: 100-199_university::111-120_theoretic_cs::111_algorithms_datastructures

Hashing | Daten Komprimieren:

anchored to [[111.00_anchor]]

Intuition:

Mit Hashing bezeichnen wir meistens die Grundidee, dass wir eine Menge von Daten durch eine Funktion verarbeiten und auf eine kleinere, eindeutige Menge abbilden.

[!Tip] Intuition wie können wir das Prinzip mathetmatisch beschreiben? #card Wir möchten also eine Menge $X$ zu $Y$ umwandeln, wobei $Y$ als ein eindeutiger Key agieren kann ( indem dieser Key nur mit gegebener Value $x_i\in X$ resultiert wird )

Beispiel: Wir sind ein Online-Shop welcher Informationen über Menschen, die die Seite nutzen, sammelt. Wir möchten etwa tracken welche Seite sie in den letzten 20 Min angeklickt hatten. Problem: –> Personen sind konstant off / online, wie tracken wir das passend? Ip-Adressen, können eindeutig Personen ausfindig machen! aaber, wie können wir das am Besten schnell ausfindig machen / abrufen?

^1704708679188

Wir können das Problem mit Hash-funktionen lösen. was zeichnet sie aus? #card

• Wir wollen dabei jeder Ip einen nickname geben, den wir aus der Adresse selbst berechnen können.
• er sollte am besten eindeutig sein
• also eine Funktion $f:Ip⟶hash$, wobei sie im idealen injektiv ist!
• die Größe / Menge der Nicknames sollte entsprechend klein sein –> sonst suchen wir wieder lang.
• Wir speichern diese Informationen in einem Array und nennen diesen Hash-tables ^1704708679193

[!Example] Visualisierung des Konzeptes: ![[Pasted image 20221028114705.png]]

Wir betrachten also ein Universum von keys auf diese wir möglichst einfach und effizient mappen wollen. Damit die Suche anschließend auch entsprechend schnell ( und nicht so lang, wie die Suche in der Ausgangsmenge) ist, sollten wir dieses Universum der Keys entsprechend klein wählen, und es kleiner sein, als die Ausgangsmenge!

-> Wir müssen nicht alles betrachten, und können somit nur einen kleinen Ausschnitt aus dem Universum betrachten.

formale Definition:

Mathematisch beschreiben wir sie also folgend: wie? was ist unsere Zielmenge? Was meinen wir mit Belegungsfaktor? #card $$U=[0,\dots ,N-1]=\text{alle Ip-Adressen},S\subset U,|S|=n,\text{beschreibt Menge von Kund*innen online}$$ Wir bezeichnen den Hash-Table: $T[0,\dots ,m-1]$ wobei er Größe $m$ hat und möchten wir jetzt noch die Hash-Funktion definieren $h:U⟶[0,\dots ,m-1]$ , die die Elemente $a\in U$ auf den entsprechenden Hash-Table abbildet. Also $T[h(a)]$ Wir möchten ferner den Belegungsfaktor definieren: $\beta =\frac{n}{m}$ ^1704708679201

wir möchten jetzt einige Funktionalitäten beschreiben:

1. Zugreifen :: -> also abrufen eines Wertes $a$ und dessen entsprechender Hash-Wert $\in S$ ^1704708679206

2. Einfügen :: -> einfügen eines neuen Hash-werts, aufbauend auf einen gegeben Wert $a\in U$ ^1704708679211

3. Streichen/Entfernen :: -> einen entsprechenden Wert aus dem Hashing-Table entfernen, also entsprechend zu einem Wert $a\in U$ den Hashing-Wert entnehmen. ^1704708679216

[!Attention] Kollisionen können auftreten wann? #card Hash-Kollisionen treten dann auf, wenn die Hashes von zwei verschiedenen Werten getroffen werden ( und somit die Abbildung offentsichtlich nicht mehr injektiv ist) Wir beschreiben es auch folgend: $$x\ne y\wedge h(x)=h(y)$$ ^1704708679221

Hashing mit Chaining/Verkettung

[!Tip] coping with collisions considering chaining, how could we solve collisions in the hash-table? #card Wir haben oben gesehen, dass es auftreten kann, dass die Hash-Function Kollisionen verursacht und somit manche Elemente in den gleichen Platz des Hash-Tables fallen würden.

Um dagegen vorzugehen bzw. das Problem zu minimieren können wir: -> jeden Eintrag in dem Hash-Table als Linked-List konzipieren diese linked-list sammelt dann alle Elemente, die den gleichen hash-key haben. ^1704708679225

Mit gegebenem Beispiel können wir es noch visualisieren und sehen da, dass so einfach überlappende Items ( mit selbigem Hash-Wert) in einer linked list gesammelt werden. ![[Pasted image 20221031142804.png]] Welches Problem kann damit auftreten? #card Mit dieser Struktur werden Elemente des gleichen Hashwertes in die selbe linked list geschrieben. Dadurch wird sie also sehr groß, wenn das sehr oft auftritt –>

• wir müssen komplett durch Liste traversieren, wenn wir ein Element in ihr suchen. Das kann ( je nach Größe) viel Zeit kosten
• Linked Lists sind in ihrem Speicherplatz dynamisch aufgebaut und brauchen somit unterschiedlich viel Speicherplatz. Weiterhin sind sie dann im Heap zu verordnen, wo der Speicherplatz grundsätzlich etwas langsamer ist ( was wir hier nicht betrachten) ^1704708679231

Welcher Worst-Case könnte hier noch auftreten? #card

• angenommen jedes Element, was wir durch die Hashfunction abbilden, bildet auf den gleichen Hash ab. Dann müssen wir in der entsprechenden linked list im Worst-Case alle $n$ Elemente durchsuchen. ^1704708679237

Die Analyse für die Average-Laufzeit von Hashing mit Verkettung ist deutlich besser angesetzt. Betrachten wir dafür folgend:

1. $h(x)in\mathcal{O}(1)$, die Berechnung ist relativ einfach.
2. jetzt wird die Hash-Funktion optimalerweise die Elemente $U$ gleichmäßig auf $T$ verteilen. Beschrieben mit $$|h^{-1}(i)|=\frac{|U|}{m},\forall i:0\le i\le m-1$$
3. Wenn wir jetzt $n$-Operationen auf die Elemente durchführen, gilt folgend: $$prob(x=\text{Element der j-ten Operation})=\frac{1}{N},x\in U$$ Also die Operationen sind immer gleichverteilt ( das sehen wir durch $\frac{1}{N}$ was für alle Elemente gilt!)
4. Somit sind dann auch die Hash-Werte gleichverteilt, denn $prob(h(x_k)=i)=\frac{1}{m}$, wobei wir mit $x_k$ Ein Element meinen, dass wir einfügen und verarbeiten lassen.

Wir möchten noch eine Funktion definieren, die angibt, ob zwei Eingabe-Werte kollidieren oder nicht; ${\gamma }_h(x,y)\left(\begin{array}{cc}1& \text{falls }h(x)=h(y),x\ne y\\ 0& \text{sonst}\end{array}\right)$ Wir definieren noch die gesamte Summe dieser Werte für eine Menge $S$, denn wir brauchen sie, um die Laufzeit bestimmen zu können. $${\gamma }_h(x,S)=\sum _{y\in S}{\gamma }_H(x,y)=\text{Kosten Operation }XYZ(x)=\mathcal{O}(1+{\gamma }_h(x,S))$$

[!Definition] Satz | Erwartete Kosten von $XYZ(x)$ wie sind sie definiert? #card Mit der zuvor beschriebenen Definition folgt fürs uns jetzt: Die erwartetenden Kosten sind: $1+\beta =1+\frac{n}{m}$ ^1704708679242

–> es werden also die Listen bei dieser Verteilung sehr wahrscheinlich nicht zu lang und eher kurz gehalten, wenn sich alle Elemente entsprechend verteilen können.

Jetzt stellt sich noch eine Frage:

Wie lang ist die längste Liste (in einer verketteten Hashmap)?

Wir wollen dafür zufällig eine Menge $S\subset U$ wählen, also eine Menge, die wir mit der Hashfunktion abbilden möchten. Wir beschreiben jetzt die Wahrscheinlichkeit, dass ein Wert aus $S$ auf einen Eintrag des Hash-Tables abbildet. Beschrieben wird es mit $prob(h(x_k)=i)=\frac{1}{m}$, also auch hier sehen wir eine Gleichverteilung!.

Wir werden jetzt noch einige Schritte durchgehen, um dann die obige Frage lösen zu können:

1. Schätze ab, ob die Liste $i$ die Länge $\ge j$ hat ( j beschreibt die j-te Operation die wir durchführen)

2. Schätze weiter ab, ob die längste Liste eine Länge $\ge j$ hat

3. Wir bilden folgend den Erwartungswert dieser längsten Liste $L$.

4. Daraus können wir dann schließen bzw. abschätzen, wie groß sie ist / sein kann: $E(L)\in \mathcal{O}\left(\frac{\log n}{\log \log n}\right)$ Wir brauchen hier nochmals den Belegungsfaktor $\beta$ und können jenachdem, wie er gesetzt ist folgern:

5. Ist $\beta \le 1$ -> dann ist die Laufzeit gut ( also entsprechend $\mathcal{O}(1)$)

6. Für $\beta \ge \frac{1}{4}$ -> die Platzausnutzung wird hier gut sein

7. jeder andere Wert ist für uns suboptimal –> die Laufzeit wird zu hoch sein oder die Platzausnutzung unpassend

–> Ein Problem was hierbei ensteht: Durch Operationen, wie dem Einfügen / Streichen verändert sich auch $\beta$ –> also wird es schwierig diese Struktur passend zu definieren.

Rehashing:

https://en.wikipedia.org/wiki/Double_hashing

Wir möchten jetzt das Prinzip von Rehashing betrachten. Dafür benötigen wir $n$-Viele Hash-tables $T_0,T_1$ die in ihrer Größe in zweier Schritten skalieren, also $m,2m,4m,\dots$

Wenn wir jetzt bei einer Tafel der Größe $T_i⟹|T_i|=2^{i}m$ einen Belegungsfaktor $\beta =1=\frac{n}{m}=\frac{n}{2^{i}m}$ -> $n$ definiert die Menge von Elementen, die wir betrachten / abbilden, $m$ -> ist die Größe des Hash-Tables, beobachten, dann ist das ein Indikator, dass dieser Table ist. Folgende Schritte werden wir jetzt durchführen, um die Belegung aufzulockern: welche?, wie ändert sich dadurch $\beta$ #card

1. Ist also $\beta =1$ bei der Tafel $T_i,|T_i|=2^{i}m$, dann werden wir
2. die Elemente in die Tafel $T_{i+1}$ kopieren –> damit wird also die Größe verdoppelt und die Belegung wird folgend halbiert.
3. Jetzt ist $\beta =\frac{1}{2}$! ^1704708679247

Wir können diese Operation auch umkehren, um etwa Speicherplatz sparen zu können. Folgende Prozedere werden dann durchgeführt welche? was gilt für $\beta$ hier?:

1. Ist $\beta \le \frac{1}{4}$ ( also sie nur zu einem Viertel belegt), dann
2. Kopiere die Elemente dieses Hashing-Tables in den kleineren $T_{i-1}$, also von $T_i$ nach $T_{i-1}$ –> da hier auch die Größe skaliert $2^{i-1}m$!
3. dadurch wird $\beta$ halbiert und ist jetzt $\beta =\frac{1}{2}$!

[!Definition] Probleme mit Rehashen: Rehashen kann helfen, Platzprobleme vorerst zu verhindern, und dennoch Platzsparend zu agieren ( indem man die Werte nicht zu sehr ausreizt und zu viel leeren Platz bereitstellt)

Wenn wir Rehashen, dann kostet das sehr viel, was wir folgend noch betrachten werden.

armotisierte Zeit-Analyse:

Nehmen wir an, dass wir soeben von $T_{i-1}$ zu $T_i$ rehashed haben. Ferner gehen wir noch von Hashing-Table $T_i$ nach $T_{i+1}$ über. -> Da wir von $T_{i-1}$ hoch traversierten, haben wir vorerst $\beta =\frac{1}{2}$ als Resultat. Wir werden jetzt erst $\frac{m_2^i}{2}$ Elemente hinzufügen müssen, bis der Belegungsfaktor $\beta =1$ erreicht.

Das Rehashen wird in seiner Operation also folgende Zeit kosten $\mathcal{O}(m_2^{i+1})$ (was teuer ist). Zwischen diesen großen Sprüngen ( also dem Rehashen), muss immer noch der Table wieder gefüllt werden: also werden wir $m\cdot 2^{i-1}$ Operationen durchführen, die dann mit $\mathcal{O}(1)$ laufen ( wir fügen nur ein!)

[!Tip] Wir können diese beiden Operationen folgend zusammenführen: und mit welcher Laufzeit für Rehashing resultieren? #card

• diese $m\cdot 2^{i-1}+1$ Operationen kosten mit der nächsten Rehashing-Operation etwa $\mathcal{O}(m_2^i)$ –> sind also linear abhängig von m. –> wir verdoppeln oder vervierfachen hier also maximal. ^1704708679251

Wir sehen, dass Listen zwar viel Platz geben, aber schnell teuer werden und uns viel Platz nehmen kann.

Eine Lösung dafür wäre jetzt, dass wir überlappende Einträge einfach woanders in der Hash-Map speichern, statt Listen einzuführen.

Hashing mit open addressing:

Wir beschreiben hiermit noch eine weitere Möglichkeit mit Kollisionen umzugehen.

[!Tip] Ziel von Open Addressing #card

• mit Open Addressing möchten wir jeden Eintrag eines Hash-Tables maximal einmal belegen
• dennoch alle Elemente, die abgebildet werden, einfügen!
• kollidieren zwei Einträge ( eingefügt und schon vorhanden), dann suchen wir einen neuen Platz, um sie zu speichern! ^1704708679258

Dafür gibt es einige Ansätze, alle zielen darauf ab, bei einer Kollision ein nächstes freies Feld zu finden. Diese Findung ist dabei abhängig von der Herangehensweise, wie das nächste Feld bestimmt werden soll.

Linear Probing:

[!Definition] Prinzip von Linear probing wie funktioniert es? wie können wir Kollisionen lösen? #card Wir werden für ein gegebenes Element $k$ den Hashwert $h(k)$ berechnen und dann versuchen, ihn an der bestimmten Stelle abzulegen. -> ist diese Belegt, dann schauen wir uns die nächsten $n$ Einträge an, bis wir einen freien Platz finden. Wir beschreiben es mit $h_j=(h(x()+i)||m$ -> wobei $i$, einfach den Offset, vom eigentlichen Feld im Hash-Table beschreibt, wo sich der Wert danach befindet.

Intuitiv möchten wir also bei einer Kollision den nächsten freien Eintrag mit unserem Wert beschreiben. ^1704708679264

Daraus können wir dann einige Betrachtungen finden und Invarianten bestimmen:

[!Tip] Invariante $k⟶h(k)+x$ was meinen wir damit, und was können wir über die anderen Einträge sagen #card Wenn der Wert $k$ auf den $h(k)+x$ Eintrag im Hash-Table abbildet, dann können wir jetzt sagen:

• der Ursprungswert wird wohl belegt sein ( sonst kein Offset nötig!)
• alle Felder von $h(k),h(k)+1,\dots h(k)+x-1,h(k)+x$ sind wohl auch belegt! ^1704708679268

Wir möchten aber noch betrachten, wie man jetzt ein Element innerhalb dieses Hash-Tables finden kann.

[!Definition] Suchen im Hash-Table mit linear probing wie finden wir ein element $k$ in diesem Table? #card Sofern es keine Überschneidung gab, wäre der Inhalt bei $h(k)$ zu finden. Wenn es überschneidungen gibt, ist dieser Wert dann bei $h(k)+x$ zu finden, wobei wir x “bestimmen”, indem wir einfach traversieren, bis wir den Eintrag finden ( dann existiert $k$ schon!) oder bis wir einen freien Eintrag finden –> dann ist $k$ nicht enthalten und wir könnten anschließend den neuen Wert eintragen ^1704708679273

Löschen wird schwierig, weil wir sonst etwa ein Element $k$, was durch ein Offset woanders liegt, nicht wiederfinden. -> Betrachte etwa zwei Werte (12) und (2). 12 wurde zuerst hinzugefügt und auf Position 2 gesetzt. Danach kam jetzt Wert 2 und konnte da nicht platziert werden und sitzt irgendwo sonst im Hash-Table –>Löschen wir jetzt $(12)$, dann ist dieser Bereich wieder frei und wir könnten $2$ darauf verschieben machen wir das aber nicht!, dann wird beim nächsten Suchen von 2 in dem Feld kein Eintrag gefunden –> und es resultiert, dass $2$ nicht enthalten ist, obwohl sie es ja ist!

Es bilden sich jetzt zwei Lösungen:

Löschen eines Elementes:

Spezialsymbole:

Mit diesem Konzept beschreiben wir folgendes: was meint das Löschen mit Spezialsymbolen? was sind vorteile und nachteile? #card

• Wenn wir einen Eintrag löschen, dann setzen wir ein Element (etwa # ) um das Feld weiterhin als belegt zu setzen.
• Dadurch müssen wir die anderen Inhalt nicht anpassen
• Aber der Hash-Table wird immer voller, obwohl wir nicht so viele Werte speichern ^1704708679277

Als Lösung dieser wachsenden Menge können wir etwa :: in gegebenen Zeitabständen die ganze Liste neu sortieren und die Spezialsymbole entfernen. Das kostet aber wieder Zeit! ^1704708679283

Shift-Lösung:

Dieses Konzept versucht die Nachteile (Platz Verschwendung) von der Löschung mit Spezialsymbolen zu verhindern wie wird das gelöst? was müssen wir tun? #card

• Wenn wir einen Eintrag gelöscht haben, dann testen wir die nachfolgenden Einträge und schauen, ob sie an der richtigen Stelle sind
• Sind sie nicht korrekt, dann setzen wir sie um eins nach links
• Finden wir einen richtigen Eintrag $k^{\prime }$, dann suchen wir noch weiter, bis wir eine Lücke finden –> dann halten wir an!
• oder einen neuen Eintrag $k^{\prime \prime }$ wo $h(k^{\prime \prime })<h(k^{\prime })$ -> also der Hash-wert kleiner ist und somit vor diesem platziert werden müsste ( und nicht bei diesem eingeordnet werden muss!). Diesen Eintrag setzen wir dann auch in die Lücke vor dem gefundenen Eintrag $k^{\prime }$, also $h(k^{\prime })-1$ –> wir fahren anschließend fort in der Sortierung ^1704708679287

Ergebnisse zu Open Addressing:

[!Definition] Satz | Offen Adressierung Unter der Annahme, dass alle Hashwerte gleich wahrscheinlich vorkommen, und dass $\beta$ den Belegungsfaktor des Hash-Tables angibt, gelten folgende Kosten zum Einfügen/Löschen $\frac{1}{1-\beta }$

Was wir hieraus ziehen können:

[!Tip] Merke für Open Addressing was sehen wir in Relation zur Fülle eines Hash-tables? #card Betrachten man diese Gleichung mit ein paar Beispielen: -> $\beta =0.5$ -> $1/(1-\beta )=2$ -> $\beta =0.9$ -> $1/(1-\beta )=10$ Also es wird teurer, desto voller der Hash-Table!

Ist der Hash-table relativ leer, ist offene Adressierung eine gute Idee. Ist er zu voll, dann wird die Performanz stark darunter leiden! ^1704708679292

[!Warning] beste Hash-Funktion existiert nicht NEIN, es gibt keine Hashfunktion, die für alle Mengen von Schlüsseln am besten funktionieren kann!

[!Tip] Aber jenachdem, ob man die Menge kennt kann man bestimmte Abwägungen machen: welche? unter welcher Betrachtung? #card -> Universelles Hashing: fur eine gegebene Datenmenge funktionieren die meisten universellen Hashingfunktionen ganz gut –> irgendeine Nehmen lol -> Perfektes Hashing: Sei eine Menge von festen Schlüsseln gegeben, dann kann man unter dieser Prämisse kollisionsfreie Hashfunktionen bauen. Da man hier einen endlich dimensionalen Raum betrachtet, und so passend abgewogen werden kann! (die Abbildung muss injektiv sein) ^1704708679297

weiterführend:

wir nutzen Hash-Funktions etwa für [[111.11_bloom_filters]]!