Kokia yra duomenų struktūros Dictionary elementų paieškos greičio charakteristika?

Duomenų struktūra Dictionary (pavyzdžiui, C#) elemento paieška pagal raktą paprastai turi amortizuotą sudėtingumą O(1), tai yra labai greita ir praktiškai pastovi laiko atžvilgiu.

Tai pasiekiama naudojant maišos lentelę, kur raktas paverčiamas į maišo kodą, leidžiantį greitai rasti indeksą masyve.

Tačiau blogiausiu atveju (pavyzdžiui, dėl daugybės kolizijų) paieškos laikas gali sumažėti iki O(n), kur n yra elementų skaičius, tačiau tokios situacijos yra retos su geru maišos funkcijos paskirstymu.

Pavyzdys paieškai Dictionary C#:

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