Ի՞նչ է տվյալների կառուցվածք Dictionary-ում տարրերի որոնման արագության բնութագիրը։

Տվյալների կառուցվածք Dictionary (օրինակ՝ C#-ում) որոնումը տարր ըստ բանալիի սովորաբար ունի ամորտիզացված բարդություն O(1), այսինքն՝ շատ արագ և գործնականում մշտական ժամանակում:

Դա հասնում է հեշ-թերթի օգտագործմամբ, որտեղ բանալին փոխարկվում է հեշ-կոդի, որը թույլ է տալիս արագ գտնել ինդեքսը զանգվածում:

Սակայն, ամենավատ դեպքերում (օրինակ՝ շատ բախումների դեպքում), որոնման ժամանակը կարող է դեգրադացնել մինչև O(n), որտեղ n տարրերի քանակն է, բայց նման իրավիճակները հազվադեպ են լավ հեշ-ֆունկցիայի բաշխումով:

C#-ում Dictionary-ով որոնման օրինակ:

var dict = new Dictionary<string, int>();
dict["apple"] = 5;
int value = dict["apple"]; // O(1) որոնում