Hash Verfahren
-
Ich brauche dringend Hilfe. Kann mir einer erklären wie man darauf kommt.
Gegeben die Folgende Hashtabelle der Länge 11, die mittels Divisionsrestverfahrens mit
Kollisionsauflösung geschieht durch offene Adressierung gebildet wurde.
Index Key
0 43
1
2 13
3 24
4
5 16
6 38
7 29
8 60
9
10 32a) Wie viele Kollisionen sind bei der Speicherung aufgetreten?
b) Bestimmen Sie eine Mögliche Reigenfolge, in der die Elemente eingefügt
wurden.
-
Der Index bestimmt sich durch key % 11, jetzt musst du nur noch zählen, bei welchem Index der Divisionsrest gleich dem Index ist. Wenn der Rest gleich dem Index ist gab´s keine Kollision, sonst schon.
-
kannst du mir bei einem key ein beichspiel geben
-
@tariker nur beim key 2 gabs keine Kollision oder?
-
@tariker
32 % 11 = ?
-
@DocShoe achso ich hab mal 11% genommen, nicht dividiert.
-
@DocShoe ich komm trotzem nicht drauf. ich hab folgende s raus
Index Key
0 43----->3,9
1
2 13----->1,81
3 24----->1,45
4
5 16----->1,45
6 38--->3,45
7 29--->2,6
8 60---->5,45
9
10 32--->2,9ich verstehe nicht den zusammenhang
-
@tariker
Du kennst aber den % operator (Modulo, Divisionsrest, Nein, das hat nichts mit Prozentrechnung zu tun)? Du dividierst, das ist was anderes.
-
Ich habe folgendes raus. hab mit modulo gerechnet.:
Index Key
0 43----->10
1
2 13----->2
3 24----->2
4
5 16----->5
6 38--->5
7 29--->7
8 60---->5
9
10 32--->10Ich weiß aber nicht weiter
-
Beispiel Index 0:
Am Index 0 liegt der Wert 43. Der Hashwert für 43 ist allerdings 10 (43%11 = 10). Eigentlich sollte 43 am Index 10 liegen, dass er jetzt an 0 liegt zeigt, dass er auf Grund einer Kollision nicht an dem Index abgelegt wurde, wo er eigentlich hingehört. Für die übrigen Daten kannst du das jetzt selbst prüfen.
-
@DocShoe vielen dank nochmals