Jaká je charakteristika rychlosti hledání prvků ve struktuře dat Dictionary?

Ve struktuře dat Dictionary (například v C#) má hledání prvku podle klíče obvykle amortizovanou složitost O(1), což znamená velmi rychlé a prakticky konstantní v čase.

Toho se dosahuje použitím hash tabulky, kde je klíč převeden na hash kód, který umožňuje rychle najít index v poli.

V nejhorším případě (například při velkém počtu kolizí) se může doba hledání zhoršit na O(n), kde n je počet prvků, ale takové situace jsou vzácné při dobrém rozložení hash funkce.

Příklad hledání v Dictionary v C#:

var dict = new Dictionary<string, int>();
dict["apple"] = 5;
int value = dict["apple"]; // Hledání v O(1)