How complex is key lookup in a hash table?

In the average case, searching for a key in a hash table has a time complexity of O(1), which is very fast. This is achieved because the hash function converts the key into an array index where the value is stored.

In the worst case, when there are many collisions (different keys that are mapped to the same index) and linear probing or linked lists are used to resolve them, the time complexity can reach O(n), where n is the number of elements in the table. This is equivalent to searching in a list.

The efficiency of the search heavily depends on the quality of the hash function and the collision resolution method. A good hash function minimizes collisions.