How is the performance of key-based element search operation in HashMap evaluated?

The performance of searching for an element by key in a HashMap is usually estimated as O(1) — constant time on average. This is achieved through the use of a hash function that converts the key into an array index, where a linked list or a tree with elements is stored.

However, in the worst case, with a large number of collisions (when different keys have the same hash), performance can degrade to O(n), where n is the number of elements in a particular bucket. Modern implementations (for example, in Java) convert linked lists into balanced trees when the collision threshold is exceeded, which improves the worst-case to O(log n).

Thus, under typical conditions, searching in a HashMap is very fast and close to constant time.