Каква е характеристиката на скоростта на търсене на елементи в структурата данни Dictionary?

В структурата данни Dictionary (например, в C#) търсенето на елемент по ключ обикновено има амортизирана сложност O(1), тоест много бързо и практически постоянно във времето.

Това се постига чрез използване на хеш таблица, където ключът се преобразува в хеш код, който позволява бързо намиране на индекса в масива.

Въпреки това, в най-лошия случай (например, при много колизии) времето за търсене може да се деградира до O(n), където n е броят на елементите, но такива ситуации са редки при добро разпределение на хеш функцията.

Пример за търсене в Dictionary в C#:

var dict = new Dictionary<string, int>();
dict["apple"] = 5;
int value = dict["apple"]; // Търсене в O(1)