Wie funktioniert die Kuckuck-Hash-Funktion? - Algorithmus, Hash

Gemäß Dokumentation wie Cuckoo Hashing Insertion funktioniert, wenn value1wird in Tabelle1 an Position h1 (Schlüssel1) unter Verwendung der Hash-Funktion h1 eingefügt, und h1 (Schlüssel1) ist bereits besetzt, weil (Schlüssel2, Wert2) so eingefügt wurde, dass h1 (Schlüssel2) = h1 (Schlüssel1), dann berechnet Cuckoo-Hash-Algorithmus h2 (key2) und versuchen, value2 an Position h2 (key2) in Tabelle2 einzufügen. Dieser Vorgang wiederholt sich.

Der Suchalgorithmus wie beschrieben ist:

function lookup(x)
return T1[h1(x)] = x ∨ T2[h2(x)] = x
end

Wenn Sie jedoch den Wert von key2 nachschlagen,value2 kann in h1 (key2) oder h2 (key2) stehen. Wenn h1 (Schlüssel1) = h1 (Schlüssel2), dann kann h1 (Schlüssel1) entweder Wert1 (Räumung aufgetreten) oder Wert2 (keine Räumung) sein. Wie weiß der Cuckoo-Hash-Algorithmus, nach welcher Tabelle er nach Wert2 suchen soll?

Antworten:

Es scheint, dass der Code zuerst Wert an T2 zurückgibt, und wenn das fehlschlägt, gibt es Wert an T1 zurück.

function lookup(x)
return T1[h1(x)] = x ∨ T2[h2(x)] = x
end

Nur eine Möglichkeit, das herauszufinden: Überprüfen Sie beide Standorte. Oder generell alle Standorte wo key2 hätte gehen können.