Under what conditions can the search time for an element in a hash table increase to linear complexity?

The time to search for an element in a hash table is usually close to constant (O(1)), but can increase to linear complexity (O(n)) under the following conditions:

• Poor hash function: if the hash function distributes keys unevenly, many elements will end up in the same bucket, leading to long chains or lists.

• High load factor: when the number of elements significantly exceeds the number of buckets, collisions increase.

• Lack of or inefficient collision resolution: if the collision resolution method (e.g., chaining or open addressing) cannot handle a large number of collisions, search slows down.

• Specific attacks: in some cases, an attacker can deliberately choose keys that cause collisions, leading to performance degradation.

Example: if all keys fall into one bucket and collision resolution is implemented via a linked list, searching for an element will traverse this list, resulting in linear complexity O(n).