How to determine the time complexity of the get method in a HashMap data structure?

In Java, the HashMap data structure is implemented based on an array of buckets, where each bucket contains a linked list or a tree (since Java 8). The get method generally operates in O(1) — constant time, as it computes the hash of the key and directly accesses the required bucket.

However, in the worst case, if all keys hash to the same bucket (collisions), and the structure inside the bucket is a linked list, the search time will be O(n), where n is the number of elements in the bucket. Since Java 8, with a high number of collisions, the linked list is converted into a balanced tree (e.g., red-black tree), which reduces the worst-case time to O(log n).

Example usage:

HashMap<String, Integer> map = new HashMap<>();
map.put("key", 42);
Integer value = map.get("key"); // Average time complexity O(1)