How is the complexity of searching for an element by key in a dictionary determined?

The complexity of searching for an element by key in a dictionary is usually considered to be close to O(1) — constant, thanks to the use of hash tables. This means that the search time does not depend on the number of elements in the dictionary.

However, in the worst case (for example, in case of hash collisions), the complexity can increase to O(n), where n is the number of elements. But modern dictionary implementations use efficient collision resolution methods, so in practice, search is very fast.

Example in C#:

var dict = new Dictionary<int, string>();
dict[1] = "one";
string value = dict[1]; // Search by key — approximately O(1)