What is the complexity of searching for an element by key in a HashMap?

Average complexity — O(1), in the worst case — O(n).

• Average case (O(1)): With a good hash function and uniform distribution of elements across buckets, the search reduces to computing the hash of the key and directly accessing the corresponding bucket in the array. Inside the bucket, if there are no collisions, the element is found in constant time.
• Worst case (O(n)): Occurs when all elements hash to the same bucket. In this case, the search becomes a linear traversal of elements in a linked list (or a balanced tree in Java 8+ for buckets with many elements, but even traversing the tree can take O(log n), which with a very high number of collisions in one bucket still approaches O(n) relative to the total number of elements if all fall into one bucket).

Starting from Java 8, for buckets containing more than a certain threshold (TREEIFY_THRESHOLD, default 8) elements, the linked list is transformed into a balanced tree (Red-Black Tree). This improves the worst-case search within a single bucket to O(log n), but if all keys have the same hash, the overall search can still be close to O(n).