What is the maximum time it can take to retrieve an element by key from a HashMap data structure?

In Java's HashMap data structure, retrieving an element by key typically takes O(1) time — constant time. However, in the worst case, when all keys hash to the same bucket due to collisions and are stored as a linked list, retrieval time can degrade to O(n), where n is the number of elements in the HashMap.

Starting with Java 8, when there are many collisions, linked lists in buckets are converted into balanced trees (TreeNode), which improves the worst-case access time to O(log n). Nevertheless, in theory, the worst-case access time can be linear if the data structure degrades.

Example:

HashMap<String, String> map = new HashMap<>();
map.put("key1", "value1");
String value = map.get("key1"); // Average O(1), worst O(n)