Какова характеристика скорости поиска элементов в структуре данных 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)