Java.Collections.What is the worst case runtime of get(key) for a key that is in the HashMap?

🚀 TL;DR:

The worst-case runtime of get(key) when the key is in the map is:

• O(n) in Java versions before 8 (linked list buckets),
• O(log n) in Java 8 and later, thanks to treeified buckets,
• O(1) in the average case (with a good hash function and even distribution).

---

🔍 Breakdown:

🔴 Pre-Java 8: Linked List Buckets

If many keys hash to the same bucket:

• All those entries are stored in a singly linked list.
• get(key) will scan the entire list to find the matching key via equals().

📉 Worst-case: the key is at the end → O(n) time.

---

🟢 Java 8+: Treeified Buckets

• If a bucket gets ≥ 8 entries and the map’s capacity is ≥ 64, the bucket is converted into a red-black tree.
• Lookup in a tree is O(log k), where k is the number of elements in that bucket.

📈 Even in the worst-case (all entries in one bucket), lookup is O(log n).

---

✳️ But why is it still fast in practice?

Most HashMap usage assumes:

• Good hashCode() implementation,
• Uniform distribution of keys,
• Small average bucket size.

So in most practical situations:

• Buckets have very few entries (often ≤ 1),
• get(key) performs in O(1) time — almost instant.

---

Summary Table:

Java Version	Worst-case structure	Worst-case get(key)
Java 7 or earlier	Linked list	O(n)
Java 8+	Red-black tree	O(log n)
Typical case	Few collisions	O(1)