Sei h : N → [m] eine Hashfunktion definiert als h(n) = (n mod m)+1. Sei m = 7.

Question

Text erkannt:

AUFGABE 2
Sei \( h: \mathbb{N} \rightarrow[m] \) eine Hashfunktion definiert als \( h(n)=(n \bmod m)+1 \). Sei \( m=7 \). Führen Sie nacheinander folgende Operationen durch. Gehen Sie davon aus, dass die Hashtabelle zu Beginn leer ist. Geben Sie die Hashtabelle nach jeder Teilaufgabe aus.
a) insert(1), insert(3), insert(7), insert(4), insert(2)
b) insert(14), insert(15), insert(25), insert(51)
c) search(7), \( \operatorname{search}(51) \) Geben Sie hier zusätzlich die Hashberechnung an.
d) delete(51), delete(52)

Aufgabe:

Answer 1

a)   

0	1	2	3	4	5	6

insert(1)  h(1)=2

0	1	2	3	4	5	6
		1

insert(3)    h(3)=4 also

0	1	2	3	4	5	6
		1		3

insert(7) h(7)=1

0	1	2	3	4	5	6
	7	1		3

insert(4) h(4)=5 

0	1	2	3	4	5	6
	7	1		3	5

insert(2)   h(2)=3 

0	1	2	3	4	5	6
	7	1	2	3	5

insert(14)  h(14) = 1

Jetzt Kollision, Welche Strategie ?

Bei "next fit" wäre es

0	1	2	3	4	5	6
	7	1	2	3	5	14

Comments

Insert(14) ist h(14)=1 aber du hast es bei 6 gesetzt

Hier würde schon die Kollision kommen.

Ich denke es wir dann einfach als weitere value hinzugefügt. Datenverluste sollte man ja eigentlich vermeiden noch besser den Hash direkt aufbauen dass es nicht vorkommt.

---

Ein Hash von 0 ist ja eh nicht möglich da immer +1 trotzdem in der Tabelle aufzählen?

---

Ups hatte es zuerst falsch verstanden next fit ist natürlich 6.

Aber ich sitze in der gleichen Vorlesung hier heißt es

wenn m < |S|, kann es zu Kollisionen kommen.
Deshalb speichern wir die Einträge nicht einfach in einem Array ab stattdessen legen wir m einfach verkettete Listen L = (L1, . . . , Lm ) an. Liste Li speichert Elemente mit Hash i