Wie ist die Suchgeschwindigkeit von Elementen in der Datenstruktur Dictionary?

In der Datenstruktur Dictionary (z.B. in C#) hat die Suche nach einem Element anhand des Schlüssels in der Regel eine amortisierte Komplexität von O(1), also sehr schnell und praktisch konstant in der Zeit.

Dies wird durch die Verwendung einer Hashtabelle erreicht, bei der der Schlüssel in einen Hash-Code umgewandelt wird, der es ermöglicht, den Index im Array schnell zu finden.

Im schlimmsten Fall (z.B. bei vielen Kollisionen) kann sich die Suchzeit auf O(n) verschlechtern, wobei n die Anzahl der Elemente ist, aber solche Situationen sind bei guter Verteilung der Hash-Funktion selten.

Beispiel für die Suche in Dictionary in C#:

var dict = new Dictionary<string, int>();
dict["apple"] = 5;
int value = dict["apple"]; // Suche in O(1)