We’ll define a transition as a significant operation or decision point the HashMap makes to retrieve a value. This includes hashing, indexing, and comparisons.
🔍 Step-by-step: map.get(key)
Here’s what happens internally:
✅ 1. Call key.hashCode()
- The key’s hash code is computed.
- This is a virtual method call if
hashCode()is overridden.
📌 Transition #1
✅ 2. Apply internal hash transformation
- HashMap applies a bit-mixing function to spread bits for better distribution:
int hash = (h = key.hashCode()) ^ (h >>> 16);
- This reduces clustering in buckets.
📌 Transition #2
✅ 3. Compute bucket index
- The hash value is used to compute the index in the internal array (
Node[] table):
int index = (n - 1) & hash;
📌 Transition #3
✅ 4. Access the bucket
- Get the head node of the bucket at
table[index].
📌 Transition #4
✅ 5. Search for the key in the bucket
Now there are two paths depending on the structure of the bucket:
a) Linked List (usual case):
- Traverse the list using
equals()to compare keys.
Each comparison is: 📌 Transition #5 (and possibly #6, #7…) — one per node visited.
b) TreeNode (if bucket is treeified):
- Use either:
compareTo()if the keys areComparable, orhashCode()+System.identityHashCode()as fallback.
- Red-black tree traversal follows O(log n) comparisons.
Still: 📌 Transition #5…n — up to log(n) comparisons in tree mode.
✅ 6. Return the value
- Once the matching key is found, its value is returned.
📌 Final transition
✅ So how many transitions?
For a key that exists, typical transition count is:
| Structure | Estimated transitions |
|---|---|
| Good hash, small map (best case) | ~5 transitions (hashing → index → head → compare → return) |
| Moderate collision (short linked list) | ~5–7 transitions |
| Heavy collision (treeified bucket) | ~5–log(n) transitions |
🔥 Summary (with numbers)
If the key exists:
- At minimum: ~5 transitions
- At worst (heavy collisions): O(log n) transitions (still fast)
- Average case: ~5–7 transitions with 1–2 key comparisons