Wenn wir über Asymptotic Komplexitäten sprechen nehmen wir in der Regel in Betracht sehr große n. Nun zur Kollisionsverarbeitung in einer Hash-Tabelle sind einige der Methoden verkettet & lineares Sondieren. In beiden Fällen können zwei Dinge passieren (die Ihnen bei der Beantwortung Ihrer Frage helfen können): 1. Möglicherweise müssen Sie die Größe der Hash-Tabelle ändern, damit sie voll wird. 2. Es kann zu Kollisionen kommen.
Im schlimmsten Fall hängt es davon ab, wie Sie Ihre Hash-Tabelle implementiert haben, sagen in linearen Sondieren Sie die Nummer nicht finden, Sie bewegen sich weiter und die Nummer, die Sie suchten, war am Ende. Hier kommt die O (n) worst case Laufzeit. Wenn eine Kollision auftritt, sagen wir, dass wir die Schlüssel in einem ausgeglichenen Binärbaum gespeichert haben, so dass die Worst-Case-Laufzeit O (log n) wäre.
Nun zu bester Fall Laufzeit kommt, glaube ich, gibt es keine Verwirrung ist, in beiden Fällen wäre es O (1) sein.
O (n) würde im schlimmsten Fall passieren, und nicht in einem durchschnittlichen Fall eine gute entworfen Hash-Tabelle. Wenn das passiert, beginnt im durchschnittlichen Fall Hash-Tabellen nicht einen Platz in Datenstrukturen finden, weil dann ausgeglichene Bäume im Durchschnitt geben würden Sie O (n log) immer und obendrein den Auftrag zu erhalten.
Leider dies zu sagen, aber leider Ihr Freund ist richtig. Ihr Fall würde in Worst-Case-Szenarien passieren.
Auch hier suchen informatives Zeug heißt die fortgeführten Anschaffungslaufzeit: Time complexity of Hash table
ich Yavar Antwort hinzufügen möchte: denken Sie daran, dass O (1) ist keine One op. Es könnte eine große Konstante sein, aber das ist egal, wenn sie nicht von einer Variablen wie n abgeleitet ist. Selbst wenn Sie 20 Knoten durchlaufen müssen, um einen Hash zu setzen, ist es immer noch ein O (1). Natürlich funktioniert das nur für Hashtabellen, wenn einige Bedingungen erfüllt sind, aber für gut gestaltete Hashtabellen, die im Durchschnitt 0 (1) sind. – Archeg