Seite 1 von 1

foo: Double Hashing Trick

Verfasst: 5. Sep 2015 22:27
von sqrt(2)
Hallo,
kennt einer eine schnellere Variante um die nächstmögliche Position bei einem error zu berechnen,
als wiederholtes rechnen mit i++?

Danke im voraus!
Gruß

Re: foo: Double Hashing Trick

Verfasst: 5. Sep 2015 23:56
von headhumper
Das gilt nur für die gegebenen Funktionen, nicht für beliebige:

Position für ersten Versuch ausrechnen, sagen wir das ist x.
Wenn belegt => immer 2x addieren ergibt die nächste Position.

Bsp.: N = 17 und die erste Position ist x = 15, die aber belegt ist.
Man kann hier noch zusätzlich den Trick anwenden, und die 15 durch -2 ersetzen.
Dann ergibt sich für die nächsten Positionen: 11, 7, etc...

Re: foo: Double Hashing Trick

Verfasst: 6. Sep 2015 10:18
von sqrt(2)
Dankeschön :)