Seite 1 von 1

Nabla - Linear Probing - korrekt?

Verfasst: 12. Jun 2017 00:48
von nozyde
Ich hätte eine Frage zu den Nabla Aufgabe zu linear Probing. Im Video zu Hashtables und auch in sonstigen Quellen die ich finden konnte, verfährt linear Probing immer so, dass bei einer besetzten Position, immer der nächste freie Slot verwendet wird.

Also die Funktion:
F(i,N,K):=(K mod N)+(i−1)

Die in Nabla genannte und erwartete Funktion ist aber:
F(i,N,K):=(K mod N+(i−1)⋅(C+(K mod N))) mod N wobei C eine Konstante ist.

Konkretes Beispiel:

F(i,17,K):=(K mod 17+(i−1)⋅(5+(K mod 17))) mod 17

Diese Funktion erwartet aber doch von mir, dass ich in einer zweiten Iteration eine neue Kalkulation durchführe die deutlich anders endet als einfach den Index +1 zu nehmen.

Bsp.: K1 = 3, K2 = 20
(3 mod 17 + (1 - 1) ⋅ (5 + (3 mod 17))) mod 17
(3 + 0 ⋅ (5 + 3)) mod 17
(3) mod 17 = 3 => frei

(20 mod 17 + (1 - 1) ⋅ (5 + 20 mod 17))) mod 17
(3 + 0 ⋅ (5 + 3)) mod 17
(3) mod 17 = 3 => belegt ... nun würde eigentlich den nächsten Slot nehmen, also die 4 - Nabla möchte von mir aber:

(20 mod 17 + (2 - 1) ⋅ (5 + 20 mod 17))) mod 17
(3 + 1 ⋅ (5 + 3)) mod 17
(3 + 8) mod 17
(11) mod 17 = 11

Kann mir das bitte irgendwer erklären? Mir ist zwar bewusst, dass durch das Multiplizieren eine Clusterbildung verhindert wird, aber, was hat das dann noch mit linear Probing zu tun? Bedeutet linear hier dann nur noch die schrittweise Inkrementierung des Parameters i?

Danke!

Re: Nabla - Linear Probing - korrekt?

Verfasst: 14. Jun 2017 11:02
von SophiaLi1
nozyde hat geschrieben:
12. Jun 2017 00:48
Bedeutet linear hier dann nur noch die schrittweise Inkrementierung des Parameters i?
Ja, anscheinend schon. Bei den Hashtabellen-Aufgaben immer die angegebene Formel verwenden. Bei Linear Probing ist die Formel linear abhängig von i. Bei Quadratic Probing ist die Formel quadratisch abhängig von i.