Seite 1 von 1

Double Hashing in Linear-Probingaufgabe

Verfasst: 12. Sep 2015 12:35
von NonStop
Hallo,

habe gestern in einer Linearprobingaufgabe (e508e48f4767a400322c4472f330cc45) folgende Funktion bekommen:
Bild

Ist das aber nicht Double Hashing? Schrittweite ist zwar konstant, aber nicht 1 und es sind sogesehen 2 verschiedene Funktionen, eine für die Berechnung des Indexes, zweite für die Berechnung der Schrittweite.

Re: Double Hashing in Linear-Probingaufgabe

Verfasst: 14. Sep 2015 13:23
von Nullmann
Ich stimme dir zu. Linear Probing ist sogar fast identisch mit Double Hashing. Der einzige Unterschied hierbei ist, dass man nicht immer das Doppelte der eigentlichten Zahl addiert (K + (K mod N)), sondern mit einer beliebigen Zahl X + K ( (X + (K mod N)) ).
Linear.png
Linear.png (32.79 KiB) 502 mal betrachtet
Wie man an dem Beispiel schön sieht, hat das Ganze rein gar nichts mit Linear Probing zu tun.

Meine Auffassung von linear Probing war bisher: Man errechnet ein Wert, z.B. mit der Formel K mod N. Wenn diese Stelle in der Hashtable besetzt ist, werden linear alle anderen Stellen abgerufen. Sodass sich praktisch eine Formel der Form K mod N + (i-1) entsteht.

Re: Double Hashing in Linear-Probingaufgabe

Verfasst: 14. Sep 2015 13:24
von Nullmann
Bitte löschen. Bin versehentlich auf den Zitieren-Button gekommen.