Kuckucksn Hashing pseudocode

Question

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

Answer 1

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