Doppeltes Hashing verläuft in "Endlosscheife" beim rechnen per Hand

[Binary.Coder]

Hallo zusammen,

habe folgendes Problem bei einer Klausuraufgabe:

1.Hashfunktion lautet: h(x)=(3+x) mod 13
2.Hashfunktion lautet: g(x)=3 + (x mod 11)

Einzufügen ist: 29
Bereits belegt ist u.a. Stelle 6

h(29)=6
g(29)=10

h(6+10)=h(16)=6
Und jetzt kommt das Problem der Endlosscheife. Ich müsste ja jetzt das Ergebnis von h(16) also die 6 wieder mit dem Ergebnis von g(29) also 10 addieren und wieder in h(x) einsetzen und da so lange, bis ich an einer freien Stelle angelangt bin. Normalerweise sollten dadurch ja auch immer neue Zahlen entstehen aber hier lange ich in einer Endlosschleife.

Habe ich etwas falsch gemacht? In der Vorlesung wurde nichts über die Behandlung solcher Fälle erzählt, also ist es entweder ein Klausurfehler oder man soll hinschreiben das es nicht geht oder ich habe das Konzept des doppelten Hashings missverstanden.

Über eure Hilfe würde ich mich freuen.
Besten Gruß und Dank

Binary

 

[ice-breaker]

Eine endlose Schleife kann es bei deiner Funktion nicht geben.
Beim doppelten Hashing wird erst mit der 1. Hashfunktion der Platz in der Hashtabelle berechnet, ist diese belegt, wird die 2. Hashfunktion genutzt.

Also quasi so:
h(29)=6 --> Feld 6 ist belegt
g(29)=10 --> Feld 10 ist nicht belegt, einfügen


Da aber keine deiner Funktionen eine Sondierung hat (lineares Sondieren, quadratisches Sondieren ...) gibt es bei deiner Hashing-Methode keine Möglichkeit einen Wert einzufügen, wenn die 1. und die 2. Funktion eine Kollision haben.


Korrekt müsste die Funktion in etwa so aussehen (Position berechnen mit f(x)):

f(x) = (h(x) + i * g(x)) mod 13
h(x) = (3 + x) mod 13
g(x) = 3 + (x mod 11)

 

[eRaaaa]

ne, moment, ist es nicht wie folgt?

1. hashfunktion = 6 --> 6 ist belegt, rechne zweite aus
2. hashfunltion = 10 --> bedeutet, dass ich vom platz 6, 10 weiterschaue, also ist platz 16 frei? wenn ja, füge dort ein, wenn nein, addiere weiter 10 (also schaue dir platz 26 an) usw.

 

[Binary.Coder]

Danke für deine Antwort.
Bei uns verwenden wir offene Adressierung und die Aussage: "Da aber keine deiner Funktionen eine Sondierung hat (lineares Sondieren, quadratisches Sondieren ...) gibt es bei deiner Hashing-Methode keine Möglichkeit einen Wert einzufügen, wenn die 1. und die 2. Funktion eine Kollision haben." wiederspricht sich mit dem was wir in den Übungen gemacht und mit dem, was passieren würde, wenn ich meine Methode auf das Wikibeispiel anwende:

Doppel-Hashing ? Wikipedia

Diese Tabelle würde mit der oben beschriebenen Funktion, also wenn bei der zweiten Funktion eine Kollision stattfindet, das Ergebnis der 1. und der 2. Hashfunktion addieren und in die Erste einsetzen und falls dies nicht klappt, das erhaltene Ergebnis wieder mit dem (1. und einzigen) Ergebnis von g(x) addieren und wieder in h(x) einsetzen usw. funktionieren. Vielleicht auch einfach nur Zufall in diesen Fall?

Das Wikipediaverfahren unterscheid sich ja in meinem und dies möchte ich nicht nehmen, da der Prof. da schon strikt möchte, dass meine das in der Vorlesung gelernte umsetzt.

0 1 2 3 4 5 6
31 22 16 10 - 19 -

Edit: @eRaaaa hm, verwechselst du das vielleicht mit dem linearen sondieren bzw. verschmolzenen Ketten?

Ich wende mal mein Wikibeispiel hier mit meiner Methode an.

Nehmen wir mal an, wir haben folgende Tabelle

0 1 2 3 4 5 6
31 22 - 10 - 19 -

Die beiden Hashfunktionen lauten:

h1(k)=k mod 7
h2(k)=1 + (k mod 5)

Eingefügt werden soll nun 14:
h1(14) = 0 //schon belegt
h2(14) = 5 //auch schon belegt

Laut ice-breaker wäre hier schluß und laut dir müsste ich jetzt immer 5 Stellen weiter schauen. ich mache mal nach "meiner" Methode weiter:

h1(0+5)=h1(5)=5 //god damn'it auch schon belegt, also weiter im Programm
h1(5+5)=h1(10)=3 //auch belegt
h1(5+3)=h1(8)=1 //auch belegt
h1(5+1)=h1(6)=6 //Yeah endlich frei! ->

0 1 2 3 4 5 6
31 22 16 10 - 19 14

So wollte ich auch in meinem Fall vorgehen, leider ohne Erfolg.

 

[ice-breaker]

ne, moment, ist es nicht wie folgt?

1. hashfunktion = 6 --> 6 ist belegt, rechne zweite aus
2. hashfunltion = 10 --> bedeutet, dass ich vom platz 6, 10 weiterschaue, also ist platz 16 frei? wenn ja, füge dort ein, wenn nein, addiere weiter 10 (also schaue dir platz 26 an) usw.

das ist genau was ich eben beschrieben habe Die 2. Hashfunktion wird dann zur linearen Sondierung genutzt:

f(x) = h(x) + i * g(x)

Bei dir fehlt aber noch das Modulo um nicht über die Größe der Tabelle hinauszukommen

Danke für deine Antwort.
Bei uns verwenden wir offene Adressierung und die Aussage: "Da aber keine deiner Funktionen eine Sondierung hat (lineares Sondieren, quadratisches Sondieren ...) gibt es bei deiner Hashing-Methode keine Möglichkeit einen Wert einzufügen, wenn die 1. und die 2. Funktion eine Kollision haben." wiederspricht sich mit dem was wir in den Übungen gemacht und mit dem, was passieren würde, wenn ich meine Methode auf das Wikibeispiel anwende:

Wie gesagt, diese Methode die du beschreibst ist mir noch nie untergekommen und habe ich auch eben in keinem Referenzwerk zu Hashing gefunden, auf Grund der möglichen Endlosschleife ist diese Art der Berechnung auch genauso unsinnig wie die Keys mit der Midsquare-Methode zu berechnen.

Doppel-Hashing ist ein feste Art des Hashings und ist haargenau das, was im Wikipedia-Artikel beschrieben wird.

 

[Binary.Coder]

Bitte noch mal oben schauen, habe den Beitrag grad editiert.

Danke

 

[ice-breaker]

ja, nach der korrekten Doppelhashing-Methode ist Schluss, weil die Definition deiner Hashfunktionen unvollständig ist.

Wie du es machen sollst, können wir nicht beurteilen ohne die genauen Definitionen deines Professors in der Vorlesung zu kennen.

 

[Binary.Coder]

Hm, was ist denn deiner Meinung nach die korrekte Doppelhashing-Methode?
Weil die, die du meinst (nach zwei mal ist Schluß) kann in keinen Fall stimmen (laut Wikipedia geht es ja auch).

Habe mir grad zu einer anderen Aufgabe, wo es auch eine Lösung gibt das ganze mal angeschaut und da machen die das genauso wie ich es beschrieben habe.

In den einen Fall lasse ich es halt offen und frag mal die Kollegen wobei da wahrscheinlich auch keiner weiter weiß...

Trotzdem danke für eure Hilfe.

 

[ice-breaker]

Hm, was ist denn deiner Meinung nach die korrekte Doppelhashing-Methode?
Weil die, die du meinst (nach zwei mal ist Schluß) kann in keinen Fall stimmen (laut Wikipedia geht es ja auch).

die Wikipedis-Definition stimmt mit der, die ich geschrieben habe überein.
Ich habe nur gesagt, dass bei den Hashfunktionen, die du oben genannt hast, nach dem 2. Hashversuch Schluss ist, da keine Sondierung angegeben wurde, die Definition also unvollständig ist.