Algorithmen und Datenstrukturen · Senior · Frage 50 von 75
Welche Aussage über Durchschnitt und schlimmsten Fall von Hashtabellen-Operationen stimmt?
- 1Durchschnittlich O(1) setzt einen guten Hash voraus; der schlimmste Fall bleibt O(n)
- 2Durchschnitt und schlimmster Fall sind in modernen Engines beide O(1)
- 3Beide sind O(log n), weil Buckets Bäume sind
Antwort zeigen
Richtige Antwort: Durchschnittlich O(1) setzt einen guten Hash voraus; der schlimmste Fall bleibt O(n)
Erklärung
Erwartetes O(1) beruht darauf, dass sich Schlüssel gleichmäßig verteilen. Manche Umsetzungen (Java 8 HashMap) wandeln lange Ketten in Bäume um und begrenzen den schlimmsten Fall auf O(log n), allgemein verspricht eine Hashtabelle aber nur Tempo im Durchschnitt.