Internal Working of Hashmap
🔍 Internal Working of HashMap in Java
✅ Step-by-Step Explanation
1. Adding a Key-Value Pair
map.put("name", "John");
We start by adding a key-value pair to the HashMap.
2. Hash Code Generation
Java computes a hash code for the key using:
int hash = key.hashCode(); // "name".hashCode()
3. Converting Hash to Array Index
To reduce collision risk, it computes the index in the underlying array:
index = (hash & (array.length - 1));
4. Bucket Check
If the bucket at the index is empty, the entry is stored directly. If not, a collision has occurred.
5. Collision Handling
On collision, Java uses:
- LinkedList chaining for simple conflicts
- Red-Black Tree (since Java 8) if bucket size > 8 and capacity > 64
Bucket[5] → ("id", 101) → ("name", "John")
6. Retrieving a Value
map.get("name");
HashMap recalculates the hash and index, then looks for the matching key in the bucket.
7. Resizing
When the size exceeds 75% of capacity (load factor = 0.75), the array is resized and entries are rehashed.
📌 Quick Summary
| Step | What Happens |
|---|---|
| 1 | Calculate key’s hashCode() |
| 2 | Convert hash to index using bitwise AND |
| 3 | Store entry in calculated bucket |
| 4 | Handle collisions with LinkedList or Tree |
| 5 | Resize when 75% full and rehash all keys |
🧪 Example Usage
HashMap<String, String> map = new HashMap<>();
map.put("a", "apple");
map.put("b", "banana");
map.put("c", "carrot");
For each key:
- Hash code is generated
- Converted to an array index
- Stored in corresponding bucket
Comments
Post a Comment