Schnell und platzsparend

• Kombiniere rautavistisches Hashing mit Möglichkeit 3

• Zeit zum Speichern: O(1)

  • konstante Faktoren sogar noch kleiner

• Platzverbrauch: O(1) bei n Elementen

• Formal: Rautavistische Hashfunktion h´R: h´R: {x1, x2, … , xn}  {1, … , 1} h´R(xi) := hR(x1) = 1

• Laufzeitbeweis: analog; hier: Strukturenzinduktion über alle ariden Gebiete ´G mit ammonitischen Radiolarien

Notizen: