$InformatikII$ Übung 07

• Wenn wir etwas mit verkettung hashen wollen, müssen wir kram dann auch irgendwie sortieren, aber das machen wir einfach nicht, denn wir fügen einfach immer ganz am ende an :)
• Denen ist aufgefallen, dass der Pseudocode aus der Vorlesung fürs Hashen mit verschieben, bzw lücken füllen (dat mit den blöcken) warscheinlich falsch ist (yay)
  • In Vorlesung 13, Folie 3-12ff. muss es in Zeile 27
  • $if(h(f)\le i<j\vee j<k\le h(f))$

Aufgabe 1: Hashing mit Verkettung

a)

Hashfunktion: $h_a\in H^{SP}$ mit $h_a(x)=a\cdot xmodm$
$a=(2,7)$ und $m=11$
Einzufügen:

1. $e_1=(2,3)$
2. $e_2=(1,2)$
3. $e_3=(3,0)$
4. $e_4=(2,1)$
5. $e_5=(0,2)$
6. $e_6=(3,3)$
7. $e_7=(4,4)$

Mit Hashfunktion: $h_a((x_1,x_2))=\left(\begin{array}{cc}2& x_1\\ 7& x_2\end{array}\right)mod11$

1. Iteration:

$h_a((2,3))=3$

2. Iteration:

$h_a((1,2))=5$

3. Iteration:

$h_a((3,0))=6$

4. Iteration:

$h_a((2,1))=0$

5. Iteration:

$h_a((0,2))=3$

6. Iteration:

$h_a((3,3))=5$

7. Iteration:

$h_a((4,4))=3$

Tabelle:

b)

$h_0(x)=(x+5)mod3=(x+2)mod3$
$h_0(x)=(x+7)mod3=(x+1)mod3$
$h_0(x)=(x+9)mod3=xmod3$

Für alle zwei unterschiedlichen schlüssel (in der schlüsselmenge der natürlichen Zahlen) darf es höchstens eine Hashfunktion geben bei der beide eingegebenen Zahlen den selben Hashwert haben, damit das dann 1 Universell ist $\forall x\ne y\in \mathbb{N}:|\{h\in H|h(x)=h(y)\}|\le \frac{c\cdot |H|}{m}$

=> $H$ ist nicht $1$-universell für $Key=\mathbb{N}$

Aufgabe 2: Hashing mit linearem Sondieren

Mit Hashfunktion: $h(x)=xmod11$

a)

Schlüssel $14,42,19,3,17,20,6,31,25,28$ mit obiger Hashfunktion in eine leere Hashtabelle einfügen

$Insert(14)$

$Insert(42)$

$Insert(19)$

$Insert(3)$

$Insert(17)$

$Insert(20)$

$Insert(6)$

$Insert(31)$

$Insert(25)$

$Insert(28)$

Insgesamt: (Lösung)

• (Der Hashwert, wird normalerweise nicht gespeichert)
• Wir wrappen around, damit wir nicht nen ewigen "overflowpool" bauen, und um effizienter zu sein
• Die Länge der Hashtabelle ist $m$, also die Maximale anzahl an Indizes (jedenfalls beim linearen sondieren)

b)

Mit markieren als gelöscht:

Nachdem wir gelöscht haben, mmüssen wir einmal komplett über das ding iterieren und schauen, ob eine Zahl gut in das jetzt leere feld passt, spricht hochrücken will
Das machen wir so lange, bis es keinen "besseren Fit" mehr gibt.

Mit verschieben:

Jetzt schauen wir in der Leeren Zeile und applien wieder das oben erwähnte