We developers often think about time complexity. We are familiar with the fact that time complexity is the main factor, which helps us create really powerful algorithms. When we need to store data requiring random access, we use hash sets or dictionaries. Why do we do this? Because we know, that time complexity is O(1) for that kind of stores.

When we use Dictionary<TKey,TValue> we think that access via key is really fast. We expect O(1) time complexity. We are right when we think about algorithms usually implemented inside dictionaries. The truth is that we are right only when we consider dictionary implementation only. What we are missing sometimes is the time complexity of two operations that must be calculated while accessing the value by the key. Those operations are:

Read More