Double Hashing in Linear-Probingaufgabe

NonStop
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 18. Apr 2015 19:15

Double Hashing in Linear-Probingaufgabe

Beitrag 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.

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Double Hashing in Linear-Probingaufgabe

Beitrag 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) 480 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.
Zuletzt geändert von Nullmann am 14. Sep 2015 13:26, insgesamt 1-mal geändert.

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Double Hashing in Linear-Probingaufgabe

Beitrag von Nullmann »

Bitte löschen. Bin versehentlich auf den Zitieren-Button gekommen.

Antworten

Zurück zu „Archiv“