Double Hashing - Korrekte Funktionen?

Jannis
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 15. Apr 2015 17:10

Double Hashing - Korrekte Funktionen?

Beitrag von Jannis »

Hallo,

sind die im Foo-Beispiel gewählten Funktionen wirklich "passend" zum Prinzip vom Double Hashing?
Gegeben sind ja die Funktionen

F(i,N_max,K) = (F1+(i-1)*F2) mod N_max
F1(N_max,K) = K mod N_max
F2(N_max,K) = K + (K mod N_max)

Was mir jetzt aufgefallen ist, ist Folgendes: wenn wir nun unterschiedliche Werte K=a*N_max mit a in N einfügen wollen, dann werden diese ja immer wieder an die selbe Stelle gesteckt. Beispiel wäre z.B. N_max = 5 und zuerst K = 0 (welcher ja an die Stelle 0 im Array einsortiert wird) und danach K =5.

Dann gilt:
F(1,5,5) = (5 mod 5+(1-1)*(5 + (5 mod 5))) mod N_max = (0+(1-1)*(5)) mod N_max = 0
F(2,5,5) = (0+(1)*(5)) mod N_max = 0
F(3,5,5) = (0+(2)*(5)) mod N_max = 0
.. und so weiter

Das heißt, dass wir in diesem Fall nie an eine Stelle ohne Kollision kommen würden, obwohl unsere Liste erst 1 von 5 Elementen belegt. Würde man in solchen Fällen einfach extra-Abfragen in der Implementierung einrichten, die z.B. nach N_max/2 Versuchen die Liste einfach noch einmal linear durchwandern? - Aber dann könnte man die Werte ja überhaupt nicht mehr finden, ausser man merkt sich, wo sie standen :(

In Wikipedia wird erwähnt, dass F1 und F2 "voneinander unabhängig sein müssen" damit man Double Hashing betreiben kann.. für zwei Keys k und y müsse gelten, dass F1(k)=F1(y) und F2'(k)=F2'(y) nur zu einer Wahrscheinlichkeit von höchstens 1/N_max^2 auftritt.

In unserem Fall trifft es aber bei N_max = 5 offensichtlich zu 20% zu, da alle Zahlen, die sich durch 5 ohne Rest teilen lassen, in 0 einsortiert werden.

Allerdings ist mir natürlich klar dass wir hier nur ein "einfaches Beispiel" haben um vor allem das Konzept im Kopf durchzuspielen.. ich glaube niemand würde gerne mit großen Primzahlen im Kopf umherhantieren :lol:
Was würde man in einer "echten Anwendung", selbst wenn man eine deutlich geringere Wahrscheinlichkeit für eine doppelte Kollision hat, in einem solchen Fall tun?

Und PS: Wird bei Foo geprüft, dass eine solche Situation nicht vorkommen kann? Mir ist es bis jetzt nicht passiert und ich kann mir gut vorstellen dass man sich das schon vorher gedacht hat - aber ich will lieber einmal sicher gehen. Ansonsten habe ich sowas dann im Testat und denke mir dann nur: "hätte ich lieber mal gefragt :roll: "

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

Re: Double Hashing - Korrekte Funktionen?

Beitrag von Nullmann »

Jannis hat geschrieben: N_max = 5 und zuerst K = 0 (welcher ja an die Stelle 0 im Array einsortiert wird) und danach K =5.
Inwiefern ändert sich denn K bei dir?
Wenn ich das richtig verstanden habe, dann meinst du ein Beispiel wie N_max = 5 und K=5, wodurch bei den Foo-Formeln F1=5mod5=0 und F2 = 5+(5mod5)=5+0=5 und somit F=(0+(i-1)*5)mod5 = 0 raus kommen würde, unabhängig von i.
Würde mich auch interessieren, wie das in der Praxis gehandhabt wird. Bei meinen Foo-Durchgängen ist mir sowas allerdings auch noch nicht passiert, sodass ich davon ausgehen würde, dass das nicht vor kommt.

Jannis
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 15. Apr 2015 17:10

Re: Double Hashing - Korrekte Funktionen?

Beitrag von Jannis »

Inwiefern ändert sich denn K bei dir?
Das war vielleicht ein wenig doof formuliert von mir.. ich meinte damit, dass das ja auftritt wenn man zwei solche "immer gleich" gemappten Werte in das Array einfügen will.
Zum Beispiel bei N_max = 5 die 0 und danach die 5

Antworten

Zurück zu „Archiv“