0 Daumen
445 Aufrufe

Frage:

könnte jemanden mir bitte helfen

ich muss ein Pseudocode für die Funktion cuckoo_insert(T0 , T1 , h0 , h1 , k) schreiben, die für
zwei gegebene Hashtabellen T0, T1 und zwei gegebene Hashfunktionen h0, h1 den übergebenen Schlüssel k mithilfe von Kuckucks-Hashing einfügt.

das Algorithmus soll true
zurückgeben, wenn der Schlüssel eingefügt werden konnte und false, wenn es beim Einfügen zu einem Zyklus kommt.

die Hashtabellen sollen im Falle eines Zyklus nicht erweitern.

alle verwendeten Schlüssel paarweise unterschiedlich sind, alle Einträge der Hashtabellen mit −1 initialisiert wurden und alle
Schlüssel natürliche Zahlen sind

Avatar von

1 Antwort

+1 Daumen

Gegeben:

Kuckucks-Hashing.

Die Hashtabellen sollen im Falle eines Zyklus nicht erweitert werden.

Alle verwendeten Schlüssel sind paarweise unterschiedlich. (keine Zahl kommt also doppelt vor)

Alle Einträge der Hashtabellen wurden mit −1 vorinitialisiert.

Alle Schlüssel sind natürliche Zahlen.


Der Algorithmus gibt true zurück, wenn der Schlüssel eingefügt werden konnte und false falls es zu einem Zyklus kommt.

Da alle verwendeten Schlüssel paarweise unterschiedlich sind lässt sich ein Zyklus feststellen, wenn beim Verfahren der eingefügte Schlüssel k erneut auftaucht.


Pseudocode:

cuckoo_insert(T_0, T_1, h_0, h_1, k)
// überprüfen ob k bereits in T_0 gespeichert werden kann
if (T_0[h_0(k)] == -1) then
T_0[h_0(k)] = k
return true
end

// überprüfen ob k bereits in T_1 gespeichert werden kann
if (T_1[h_1(k)] == -1) then
T_1[h_1(k)] = k
return true
end

k' = k; // k' um auf Zyklus prüfen zu können
while (true) do
k <-> T_0[h_0(k)] // <-> = tausche
if (k == -1) then // k konnte eingefügt werden
return true
end
if (k == k') then // k konnte nicht eingefügt werden, Zyklus
return false
end

k <-> T_1[h_1(k)]
if (k == -1) then
return true
end
if (k == k') then
return false
end
end
Avatar von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
0 Antworten
0 Daumen
1 Antwort

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community