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

On average, searching for an element by key in a HashMap hash table is performed in O(1) — constant time. This is achieved by computing the hash code of the key and quickly accessing the corresponding bucket. However, in the worst case, if there are many collisions and elements are stored as a linked list or tree, the time can increase to O(n), where n is the number of elements in the bucket. Starting from Java 8, when there are many collisions, linked lists are converted into balanced trees, reducing the worst-case search time to O(log n).