What is the average-case time complexity of searching for an element in a HashMap?

On average, the operation of searching for an element in a HashMap in Java has a time complexity of O(1) — constant time.

This is achieved through the use of a hash function that calculates the index of the bucket for storing the key-value pair. With an ideal distribution of elements across buckets, the search occurs directly.

However, in the worst case (for example, with a large number of collisions), the complexity can degrade to O(n), where n is the number of elements in the HashMap, if all elements end up in one bucket. Modern Java implementations (starting from Java 8) use balanced trees (TreeNodes) within buckets when there are many collisions, which reduces the worst case to O(log n).

Thus, in most practical cases, the search in a HashMap can be considered an operation with an amortized complexity of O(1).