 (54).png)
Custom Implementation of HashMap in Java
When we talk about Java collections, HashMap is one of the most commonly used and powerful data structures. It forms the foundation for many others — like HashSet, LinkedHashMap, and even ConcurrentHashMap.
But what actually happens when you write something like this?
Map map = new HashMap<>();
map.put("Apple", 10);
map.put("Banana", 20);
map.put("Orange", 30);
How are these key-value pairs stored?
How does Java ensure fast lookups in O(1) time on average?
To truly understand this, let’s build our own custom HashMap implementation — step by step — from scratch.
1. What Is a HashMap?
A HashMap in Java is a data structure that stores key-value pairs, allowing you to quickly access values based on their keys.
It’s based on the concept of hashing — converting a key (like a string) into a hash code (an integer), which determines where the key-value pair is stored internally in an array.
Internally, a HashMap uses:
- An array of buckets.
- Each bucket holds a linked list (or a balanced tree since Java 8) of entries.
- Each entry holds a key, a value, and a reference to the next entry.
2. Internal Structure of HashMap
HashMap
└── Bucket Array
├── [0] → null
├── [1] → (Key=Apple, Value=10) → (Key=Banana, Value=20)
├── [2] → (Key=Orange, Value=30)
└── [3] → null
Each bucket corresponds to an index in the internal array, and multiple keys can map to the same bucket if their hash codes collide — forming a linked list.
3. Core Operations
Let’s briefly understand how each operation works before coding.
| Operation | Description |
|---|---|
| put(key, value) | Stores a key-value pair by computing the hash and placing it in the correct bucket. |
| get(key) | Retrieves the value by finding the bucket and searching the linked list. |
| remove(key) | Removes the entry if found in its bucket. |
| rehash() | When load factor exceeds threshold (default 0.75), the capacity doubles. |
4. Hashing Mechanism
When you insert a key, the HashMap:
- Calculates the key’s hash code using key.hashCode().
Applies a modulo operation to find the index:
index = hashCode % capacity;- Stores the entry at that index in the bucket array.
5. Let’s Build Our Own Custom HashMap
We’ll call it MyHashMap.
Step 1: Define the Entry Class
Each entry will store a key, a value, and a reference to the next entry (for chaining).
class Entry {
K key;
V value;
Entry next;
public Entry(K key, V value) {
this.key = key;
this.value = value;
this.next = null;
}
}
Step 2: Define the MyHashMap Class
We’ll use an array of Entry objects as buckets.
public class MyHashMap {
private final int INITIAL_CAPACITY = 16; // default capacity
private Entry[] buckets;
public MyHashMap() {
buckets = new Entry[INITIAL_CAPACITY];
}
Step 3: Hash Function and Index Calculation
We’ll use Java’s built-in hashCode() and compress it within our array bounds.
private int getBucketIndex(K key) {
return Math.abs(key.hashCode()) % INITIAL_CAPACITY;
}
Step 4: Implement the put() Method
The core of any HashMap — adding key-value pairs.
public void put(K key, V value) {
int index = getBucketIndex(key);
Entry newEntry = new Entry<>(key, value);
Entry existing = buckets[index];
if (existing == null) {
buckets[index] = newEntry;
} else {
// Traverse linked list to check if key exists
Entry prev = null;
while (existing != null) {
if (existing.key.equals(key)) {
existing.value = value; // replace value
return;
}
prev = existing;
existing = existing.next;
}
prev.next = newEntry; // add new entry at the end
}
}
Step 5: Implement the get() Method
Retrieve a value using the key.
public V get(K key) {
int index = getBucketIndex(key);
Entry entry = buckets[index];
while (entry != null) {
if (entry.key.equals(key)) {
return entry.value;
}
entry = entry.next;
}
return null;
}
Step 6: Implement the remove() Method
Remove a key-value pair from the map.
public void remove(K key) {
int index = getBucketIndex(key);
Entry entry = buckets[index];
Entry prev = null;
while (entry != null) {
if (entry.key.equals(key)) {
if (prev == null) {
buckets[index] = entry.next;
} else {
prev.next = entry.next;
}
return;
}
prev = entry;
entry = entry.next;
}
}
}
Step 7: Testing Our Custom HashMap
public class Main {
public static void main(String[] args) {
MyHashMap map = new MyHashMap<>();
map.put("Apple", 10);
map.put("Banana", 20);
map.put("Orange", 30);
System.out.println("Apple: " + map.get("Apple"));
System.out.println("Banana: " + map.get("Banana"));
map.remove("Banana");
System.out.println("Banana after remove: " + map.get("Banana"));
}
}
Output:
Apple: 10
Banana: 20
Banana after remove: null
Full Code — Custom HashMap Implementation in Java
// MyHashMap.java
import java.util.Objects;
/**
* Custom implementation of a simplified HashMap in Java.
* Supports put(), get(), and remove() operations using separate chaining.
*/
public class MyHashMap<K, V> {
// Default initial capacity of the bucket array
private static final int INITIAL_CAPACITY = 16;
// Array of Entry objects representing the buckets
private Entry<K, V>[] buckets;
// Number of key-value pairs stored
private int size = 0;
/**
* Constructor — initializes the bucket array.
*/
@SuppressWarnings("unchecked")
public MyHashMap() {
buckets = new Entry[INITIAL_CAPACITY];
}
/**
* Inner class representing a key-value pair (node in a linked list).
*/
static class Entry<K, V> {
K key;
V value;
Entry<K, V> next;
public Entry(K key, V value) {
this.key = key;
this.value = value;
this.next = null;
}
}
/**
* Computes the index for a given key within the bucket array.
*/
private int getBucketIndex(K key) {
return Math.abs(Objects.hashCode(key)) % INITIAL_CAPACITY;
}
/**
* Adds or updates a key-value pair in the HashMap.
*/
public void put(K key, V value) {
int index = getBucketIndex(key);
Entry<K, V> newEntry = new Entry<>(key, value);
Entry<K, V> existing = buckets[index];
if (existing == null) {
// Empty bucket — place entry directly
buckets[index] = newEntry;
} else {
// Traverse linked list to find if key already exists
Entry<K, V> prev = null;
while (existing != null) {
if (existing.key.equals(key)) {
// Key already exists — update value
existing.value = value;
return;
}
prev = existing;
existing = existing.next;
}
// Key not found — append new entry at the end
prev.next = newEntry;
}
size++;
}
/**
* Retrieves a value by key.
*/
public V get(K key) {
int index = getBucketIndex(key);
Entry<K, V> entry = buckets[index];
while (entry != null) {
if (entry.key.equals(key)) {
return entry.value;
}
entry = entry.next;
}
return null; // Key not found
}
/**
* Removes a key-value pair if it exists.
*/
public void remove(K key) {
int index = getBucketIndex(key);
Entry<K, V> entry = buckets[index];
Entry<K, V> prev = null;
while (entry != null) {
if (entry.key.equals(key)) {
if (prev == null) {
// First node in the bucket
buckets[index] = entry.next;
} else {
// Middle or last node
prev.next = entry.next;
}
size--;
return;
}
prev = entry;
entry = entry.next;
}
}
/**
* Returns number of key-value pairs stored.
*/
public int size() {
return size;
}
/**
* Displays all entries for debugging / visualization.
*/
public void printMap() {
for (int i = 0; i < INITIAL_CAPACITY; i++) {
Entry<K, V> entry = buckets[i];
if (entry != null) {
System.out.print("Bucket " + i + ": ");
while (entry != null) {
System.out.print("[" + entry.key + "=" + entry.value + "] -> ");
entry = entry.next;
}
System.out.println("null");
}
}
}
}
✅ Example Usage — Testing the Custom HashMap
// Main.java
public class Main {
public static void main(String[] args) {
MyHashMap<String, Integer> map = new MyHashMap<>();
map.put("Apple", 10);
map.put("Banana", 20);
map.put("Orange", 30);
System.out.println("Apple: " + map.get("Apple"));
System.out.println("Banana: " + map.get("Banana"));
System.out.println("Orange: " + map.get("Orange"));
// Update value
map.put("Banana", 25);
System.out.println("Banana (updated): " + map.get("Banana"));
// Remove key
map.remove("Banana");
System.out.println("Banana after remove: " + map.get("Banana"));
// Print map contents
System.out.println("\nCurrent HashMap contents:");
map.printMap();
}
}
🧾 Sample Output
Apple: 10
Banana: 20
Orange: 30
Banana (updated): 25
Banana after remove: null
Current HashMap contents:
Bucket 1: [Apple=10] -> null
Bucket 5: [Orange=30] -> null
6. How HashMap Handles Collisions
When two keys produce the same hash index (collision), HashMap uses chaining — multiple entries stored in a linked list at that bucket.
Example:
index = hash("ABC") % 16 = 5
index = hash("PQR") % 16 = 5
Both will go into bucket 5 → forming a linked list.
In Java 8 and above, if a bucket becomes too long (more than 8 elements), it automatically converts to a balanced tree (Red-Black tree) for faster lookups.
7. Rehashing and Load Factor
Rehashing happens when the number of entries exceeds the load factor threshold.
By default:
- Capacity = 16
- Load factor = 0.75
- Threshold = 16 × 0.75 = 12 entries
When we exceed 12 entries, HashMap doubles capacity (32) and reassigns existing keys to new buckets.
This maintains efficiency by preventing too many collisions.
8. Time and Space Complexity
| Operation | Average Case | Worst Case |
|---|---|---|
| put() | O(1) | O(n) (all keys in one bucket) |
| get() | O(1) | O(n) |
| remove() | O(1) | O(n) |
| rehash() | O(n) | O(n) |
Space Complexity: O(n)
9. How Java’s Real HashMap Differs
Your custom implementation captures the basic concept, but Java’s real HashMap includes:
- Dynamic resizing with rehashing.
- Tree-based buckets (since Java 8) for high-collision scenarios.
- Thread-safety in concurrent versions (ConcurrentHashMap).
- Fail-fast iterator support.
- Hash spreading (using hash(key.hashCode()) ^ (hash >>> 16)) to minimize collisions.
10. Advantages of HashMap
- Constant time performance for put() and get().
- Efficient key-value lookup.
- Allows one null key and multiple null values.
- Flexible — works with custom key objects (with proper equals() and hashCode()).
11. Disadvantages
- Not synchronized (not thread-safe).
- Order of entries not guaranteed.
- Poorly implemented hashCode() can lead to collisions and performance issues.
- Higher memory consumption due to buckets and linked nodes.
12. When to Use HashMap
Use HashMap when:
- You need fast lookups by key.
- You don’t care about insertion order.
- You want to store unique keys mapped to values.
13. Key Takeaways
| Concept | Summary |
|---|---|
| Hashing | Converts key to integer index. |
| Buckets | Array of linked lists (or trees). |
| Collision Handling | Uses chaining or tree structure. |
| Rehashing | Resizes map when load factor exceeded. |
| Thread Safety | Not thread-safe; use ConcurrentHashMap instead. |
Conclusion
By building our own MyHashMap, we’ve understood the why and how behind one of Java’s most important data structures.
When you next use a HashMap, remember: behind that single put() call lies an elegant system of hashing, collision handling, and memory management.
Understanding these internals is the first step toward mastering Java’s Collections Framework — and the foundation for creating your own optimized data structures.
Next Blog in Series:
👉 Custom Implementation of HashSet in Java (Internal Working + Code Example)
 (17).png)
.png)
 (53).png)
 (18).png)
.png)
.png)
 (1).png)
 (2).png)
 (3).png)
 (4).png)
 (5).png)
 (6).png)
 (9).png)
 (7).png)
 (10).png)
 (8).png)
 (10).png)
 (12).png)
 (13).png)
 (13).png)
 (15).png)
 (16).png)
 (19).png)
 (20).png)
 (21).png)
 (22).png)
 (23).png)
 (24).png)
 (25).png)
 (26).png)
 (27).png)
 (28).png)
 (29).png)
 (30).png)
 (31).png)
 (32).png)
 (33).png)
 (34).png)
 (35).png)
 (36).png)
 (37).png)
 (38).png)
 (39).png)
 (40).png)
 (41).png)
 (42).png)
 (45).png)
 (46).png)
 (47).png)
 (48).png)
 (55).png)
 (50).png)
 (51).png)
 (52).png)
 (56).png)
.png)
 (44).png)
