How complex is key search in a hash table?

Searching for a key in a hash table on average takes O(1) time — that is very fast, regardless of the size of the table. This is achieved by computing the hash code of the key and directly accessing the corresponding cell.

However, in the worst case, if many keys collide into the same bucket, the search can degrade to O(n), where n is the number of elements in that bucket. In modern implementations, such as in Python, when there are many collisions, the bucket is converted into a balanced tree, reducing the worst case to O(log n).

Thus:

• Average case: O(1)
• Worst case: O(n) or O(log n) in modern implementations

Example in Python:

my_dict = {'a': 1, 'b': 2, 'c': 3}
value = my_dict.get('b')  # Search for key 'b' in O(1)