HashMap Implementation with Collision Handling
In Java, a HashMap internally handles collisions using buckets and linked lists (or trees in certain conditions). When two keys hash to the same bucket (i.e., a collision), Java stores the key-value pairs in a linked list or a balanced tree structure (if the bucket size exceeds a certain threshold).
Here’s a simplified implementation of a HashMap with collision handling using separate chaining (linked lists). Each bucket will store a list of key-value pairs in case of a collision.
HashMap Implementation with Collision Handling:
import java.util.LinkedList;
class CustomHashMap<K, V> {
private static final int INITIAL_CAPACITY = 16;
private LinkedList<Entry<K, V>>[] table;
// Constructor
public CustomHashMap() {
table = new LinkedList[INITIAL_CAPACITY];
}
// Nested class for the entries (key-value pairs)
private static class Entry<K, V> {
K key;
V value;
Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
// Hash function
private int hash(K key) {
return key.hashCode() % table.length;
}
// Put method to insert key-value pairs
public void put(K key, V value) {
int index = hash(key);
if (table[index] == null) {
table[index] = new LinkedList<>();
}
// Check if the key already exists in the list, and update the value if so
for (Entry<K, V> entry : table[index]) {
if (entry.key.equals(key)) {
entry.value = value;
return;
}
}
// If the key doesn't exist, add a new entry
table[index].add(new Entry<>(key, value));
}
// Get method to retrieve the value by key
public V get(K key) {
int index = hash(key);
if (table[index] != null) {
for (Entry<K, V> entry : table[index]) {
if (entry.key.equals(key)) {
return entry.value;
}
}
}
return null; // Return null if the key is not found
}
// Remove method to delete a key-value pair
public void remove(K key) {
int index = hash(key);
if (table[index] != null) {
for (Entry<K, V> entry : table[index]) {
if (entry.key.equals(key)) {
table[index].remove(entry);
return;
}
}
}
}
// Size method to get the current size of the HashMap
public int size() {
int size = 0;
for (LinkedList<Entry<K, V>> bucket : table) {
if (bucket != null) {
size += bucket.size();
}
}
return size;
}
// Display method to show the contents of the HashMap
public void display() {
for (int i = 0; i < table.length; i++) {
if (table[i] != null) {
System.out.print("Bucket " + i + ": ");
for (Entry<K, V> entry : table[i]) {
System.out.print("[" + entry.key + "=" + entry.value + "] ");
}
System.out.println();
}
}
}
}
public class Main {
public static void main(String[] args) {
// Create an instance of CustomHashMap
CustomHashMap<String, Integer> map = new CustomHashMap<>();
// Adding key-value pairs
map.put("apple", 10);
map.put("banana", 20);
map.put("cherry", 30);
map.put("apple", 50); // Updating value for "apple"
// Display the contents of the HashMap
map.display();
// Retrieve values
System.out.println("Value for 'apple': " + map.get("apple"));
System.out.println("Value for 'banana': " + map.get("banana"));
// Remove a key-value pair
map.remove("banana");
map.display();
// Get the size of the map
System.out.println("Size of map: " + map.size());
}
}
Explanation:
Entry class: This is a simple key-value pair that stores the key and value. It’s used to store entries in the hash map.
hash(K key): This method calculates the hash code of a key and determines the bucket index using the modulo operation (hashCode() % table.length).
put(K key, V value): This method inserts key-value pairs into the map. If a collision occurs (i.e., the bucket is already occupied), it stores the key-value pair in a LinkedList at the corresponding bucket index. If the key already exists in the list, it updates the value.
get(K key): This method retrieves the value for a given key. If the key exists in the corresponding bucket (after hashing), it returns the value; otherwise, it returns null.
remove(K key): This method removes the key-value pair from the map if the key is found in the appropriate bucket.
size(): This method returns the number of key-value pairs stored in the map.
display(): This is a utility method to display the contents of the map, which shows all the buckets and their respective entries.
Collision Handling:
- In this implementation, separate chaining is used, where each bucket is a linked list (using LinkedList<Entry<K, V>>).
- When multiple keys hash to the same index (i.e., a collision), the entries are stored in a linked list at that index.
Performance:
- Insertions: On average, the insertion is O(1) unless there are many collisions.
- Lookups: On average, lookups are O(1) if there are few collisions.
- Collisions: In the worst case, all keys could hash to the same index, resulting in O(n) for retrieval and insertion, where n is the number of elements. However, this is rare if a good hash function is used.
This implementation is a basic example of handling collisions in a hash map using separate chaining.
If the size of the CustomHashMap reaches a certain threshold (typically when the load factor exceeds a given limit), we need to resize the underlying array (i.e., increase the number of buckets) and rehash all existing entries into the new buckets.
Steps for Resizing & Rehashing:
- Double the capacity: Create a new array with double the size of the old one.
- Rehash the entries: Iterate through the existing entries and insert them into the new array based on the new hash values.
- Update the reference: Point the original table to the new array.
Updated Implementation with Resizing
This version includes a resize method that dynamically increases the capacity when a threshold is exceeded.
class CustomHashMap<K, V> {
private static final int INITIAL_CAPACITY = 16;
private static final double LOAD_FACTOR = 0.75; // When to resize
private int size = 0; // Number of key-value pairs
private LinkedList<Entry<K, V>>[] table;
// Constructor
public CustomHashMap() {
table = new LinkedList[INITIAL_CAPACITY];
}
// Nested class for storing key-value pairs
private static class Entry<K, V> {
K key;
V value;
Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
// Hash function
private int hash(K key, int capacity) {
return (key.hashCode() & 0x7FFFFFFF) % capacity; // Ensure positive index
}
// Resize method to double the table size when threshold is reached
private void resize() {
int newCapacity = table.length * 2;
LinkedList<Entry<K, V>>[] newTable = new LinkedList[newCapacity];
for (LinkedList<Entry<K, V>> bucket : table) {
if (bucket != null) {
for (Entry<K, V> entry : bucket) {
int newIndex = hash(entry.key, newCapacity);
if (newTable[newIndex] == null) {
newTable[newIndex] = new LinkedList<>();
}
newTable[newIndex].add(entry);
}
}
}
table = newTable; // Update the table reference
}
// Put method (Insert or Update)
public void put(K key, V value) {
if ((double) size / table.length > LOAD_FACTOR) {
resize(); // Resize when load factor threshold is exceeded
}
int index = hash(key, table.length);
if (table[index] == null) {
table[index] = new LinkedList<>();
}
// Check if the key already exists
for (Entry<K, V> entry : table[index]) {
if (entry.key.equals(key)) {
entry.value = value;
return;
}
}
// If the key does not exist, add a new entry
table[index].add(new Entry<>(key, value));
size++;
}
// Get method
public V get(K key) {
int index = hash(key, table.length);
if (table[index] != null) {
for (Entry<K, V> entry : table[index]) {
if (entry.key.equals(key)) {
return entry.value;
}
}
}
return null; // Key not found
}
// Remove method
public void remove(K key) {
int index = hash(key, table.length);
if (table[index] != null) {
for (Entry<K, V> entry : table[index]) {
if (entry.key.equals(key)) {
table[index].remove(entry);
size--;
return;
}
}
}
}
// Size method
public int size() {
return size;
}
// Display method for debugging
public void display() {
for (int i = 0; i < table.length; i++) {
if (table[i] != null) {
System.out.print("Bucket " + i + ": ");
for (Entry<K, V> entry : table[i]) {
System.out.print("[" + entry.key + "=" + entry.value + "] ");
}
System.out.println();
}
}
}
}
public class Main {
public static void main(String[] args) {
CustomHashMap<String, Integer> map = new CustomHashMap<>();
// Adding values
map.put("apple", 10);
map.put("banana", 20);
map.put("cherry", 30);
map.put("date", 40);
map.put("elderberry", 50);
map.put("fig", 60);
map.put("grape", 70);
map.put("honeydew", 80);
map.put("kiwi", 90);
map.put("lemon", 100);
// Display the map
map.display();
// Retrieve values
System.out.println("Value for 'apple': " + map.get("apple"));
System.out.println("Value for 'banana': " + map.get("banana"));
// Remove a key-value pair
map.remove("banana");
map.display();
// Get the size
System.out.println("Size of map: " + map.size());
}
}
New Features:
Dynamic Resizing
- If the load factor (size / capacity) exceeds 0.75, the resize() method doubles the table size and rehashes all keys into the new table.
- Efficient Hashing
- Uses (key.hashCode() & 0x7FFFFFFF) % capacity to ensure positive indices.
- Uses newCapacity = table.length * 2 when resizing.
Separate Chaining for Collision Handling
- Collisions are handled with linked lists.
- If multiple keys map to the same index, they are stored as a list of entries.
Time Complexity Analysis:
Operation Average Case Worst Case Insert (put) O(1) O(n) (if all keys collide) Search (get) O(1) O(n) (worst case with collisions) Delete (remove) O(1) O(n) (worst case with collisions) Resize O(n) O(n) (rehashing all elements)
Since resizing happens rarely, the average time complexity for put(), get(), and remove() remains O(1).
Why is Resizing Important?
- If the number of elements exceeds the threshold, the map becomes inefficient, leading to frequent collisions.
- Resizing prevents excessive collisions, keeping the operations fast.
- Without resizing, performance degrades to O(n) for insertion and lookup.
Final Thoughts
This implementation provides a basic but effective HashMap with:
- Collision handling using separate chaining (Linked Lists)
- Dynamic resizing and rehashing when the load factor exceeds 0.75
- O(1) average time complexity for insert, delete, and lookup
This mimics Java’s built-in HashMap behavior but in a simplified way. 🚀
📚 Want to go deeper?
Grab these resources: 🛒 Full Editions (use code FRIENDS20 for 20% off):
Grokking the Java Interview: link
Grokking the Spring Boot Interview: link
250+ Spring Professional Certification Practice Questions: link
🆓 Try before you buy — Free Sample Copies:
Grokking the Java Interview [Free Sample Copy]
Grokking the Spring Boot Interview [Free Sample Copy]
Spring Boot Certification Practice Questions [Free Sample Copy]
HashMap Implementation with Collision Handling was originally published in Javarevisited on Medium, where people are continuing the conversation by highlighting and responding to this story.
This post first appeared on Read More