Milline on andmestruktuuri Dictionary elementide otsimise kiiruse omadus?

Andmestruktuur Dictionary (näiteks C#-s) elementide otsimine võtme järgi on tavaliselt amortiseeritud keerukusega O(1), mis tähendab, et see on väga kiire ja praktiliselt konstantne ajas.

See saavutatakse kasutades hash-tabelit, kus võti muudetakse hash-koodiks, mis võimaldab kiiresti leida indeksi massiivis.

Kuid halvimal juhul (näiteks palju kokkupõrkeid) võib otsinguaeg halveneda O(n)-ni, kus n on elementide arv, kuid sellised olukorrad on haruldased heade hash-funktsioonide jaotuse korral.

Näide otsingust Dictionarys C#-s:

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