🧠Core Concept of a HashMap
A HashMap stores data as a collection of Entry objects, each consisting of:
- A key (used to identify the value)
- A value (the actual data associated with the key)
Internally, it uses a hash table—an array of buckets where entries are stored based on the hash code of the key.
🧩 How It Works Step by Step
1. Hashing the Key
When you put a key-value pair in the map:
map.put("apple", 100);Java computes the hash code of "apple" using hashCode(), then applies a function (often (hash & (n-1))) to find the index in the array.
2. Bucket Storage
The hash code determines which bucket (slot in the array) the entry goes into.
Each bucket holds a linked list (or tree if too many collisions) of entries with the same hash index.
3. Handling Collisions
When two keys map to the same index, Java stores them in the same bucket using a linked list:
put("cat", 1);
put("act", 2); // Might hash to the same bucket as "cat"Java uses equals() to differentiate them.
Since Java 8, if a bucket gets too long (more than 8 entries), it converts the bucket to a balanced tree (like Red-Black Tree) to improve performance.
4. Retrieving a Value
When calling:
map.get(“apple”);
- Java computes the hash code → finds bucket index
- Then it iterates through the bucket to find the correct key using
equals() - Finally, it returns the associated value
🧠Behind-the-Scenes Data Structure
[Bucket0] → null
[Bucket1] → Entry("apple", 100)
[Bucket2] → Entry("banana", 200) → Entry("berry", 150)
...Each Entry has:
- Key
- Value
- Hash
- next (pointer to the next entry)
âš¡ Key Takeaways for Interviews
| Topic | Summary |
|---|---|
| Core structure | Array of buckets storing key-value pairs as linked entries |
| Hashing | Uses hashCode() + compression function to find index |
| Collision handling | Uses linked list; Java 8+ upgrades to tree if bucket is too long |
| Lookup time | Best: O(1), Worst (pre-Java 8): O(n), Java 8+: O(log n) with trees |
| Key methods | put(key, value), get(key), remove(key), containsKey(key) |
