Aká je charakteristika rýchlosti vyhľadávania prvkov v dátovej štruktúre Dictionary?

V dátovej štruktúre Dictionary (napríklad v C#) má vyhľadávanie prvku podľa kľúča zvyčajne amortizovanú zložitosť O(1), čo znamená veľmi rýchle a prakticky konštantné v čase.

Toto sa dosahuje použitím hash tabuľky, kde je kľúč prevedený na hash kód, ktorý umožňuje rýchle nájdenie indexu v poli.

V najhoršom prípade (napríklad pri veľkom počte kolízií) sa môže doba vyhľadávania zhoršiť na O(n), kde n je počet prvkov, ale takéto situácie sú zriedkavé pri dobrej distribúcii hash funkcie.

Príklad vyhľadávania v Dictionary v C#:

var dict = new Dictionary<string, int>();
dict["apple"] = 5;
int value = dict["apple"]; // Vyhľadávanie v O(1)