Care este caracteristica vitezei de căutare a elementelor în structura de date Dictionary?

În structura de date Dictionary (de exemplu, în C#), căutarea unui element după cheie are de obicei o complexitate amortizată de O(1), adică foarte rapidă și practic constantă în timp.

Acest lucru se realizează prin utilizarea unui tabel de dispersie, unde cheia este transformată într-un cod hash, care permite găsirea rapidă a indicelui în array.

Totuși, în cel mai rău caz (de exemplu, cu multe coliziuni), timpul de căutare poate să se degradeze până la O(n), unde n este numărul de elemente, dar astfel de situații sunt rare cu o distribuție bună a funcției hash.

Exemplu de căutare în Dictionary în C#:

var dict = new Dictionary<string, int>();
dict["apple"] = 5;
int value = dict["apple"]; // Căutare în O(1)