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

It depends on the internal structure of the HashMap and how collisions are handled.

---

⚙️ In theory:

Java Version	Collision Handling	Worst-case get(key)
Pre-Java 8	Linked list in buckets	O(n)
Java 8+	Tree in heavy buckets	O(log n)

Where:

• n is the number of elements in the HashMap.
• Collisions are when multiple keys hash to the same bucket index.

---

💥 Worst-case scenario explained:

1. Many keys hash to the same bucket (extreme collision).
2. Your target key is not in the map.
3. HashMap has to scan the entire bucket to confirm it’s missing.

🔴 Pre-Java 8:

• Buckets are linked lists → worst-case get() is O(n).

🟢 Java 8+:

• If a bucket gets too big (≥ 8 elements), and map size is large (≥ 64), it becomes a red-black tree.
• Tree lookup time is O(log k) where k is the number of elements in that bucket.
• So worst-case get() becomes O(log n) in a large map with treeified buckets.

---

✅ Best and average case (what we usually get):

• Constant time: O(1) for well-distributed hash codes and small buckets.

---

TL;DR:

Worst-case get(key) runtime in a HashMap is:

• O(n) in Java < 8 (linked list buckets),
• O(log n) in Java 8+ (treeified buckets),
• But usually O(1) in practice with good hashing.