Kāda ir datu struktūras Dictionary elementu meklēšanas ātruma raksturojums?

Datu struktūra Dictionary (piemēram, C#) meklēšana pēc atslēgas parasti ir amortizēta sarežģītība O(1), tas ir, ļoti ātra un praktiski nemainīga laikā.

Tas tiek panākts, izmantojot haštabulu, kur atslēga tiek pārveidota par haškodu, kas ļauj ātri atrast indeksu masīvā.

Tomēr sliktākajā gadījumā (piemēram, ar daudzām kolīzijām) meklēšanas laiks var samazināties līdz O(n), kur n ir elementu skaits, bet šādas situācijas ir retas ar labu hašfunkcijas sadalījumu.

Piemērs meklēšanai Dictionary C#:

var dict = new Dictionary<string, int>();
dict["apple"] = 5;
int value = dict["apple"]; // O(1) meklēšana