How Does HashMap Work Internally in Java?

HashMap uses array of Node objects (buckets) and hashing to store key-value pairs. Understanding internal working is crucial for interviews.

Internal Structure

// Simplified internal structure of HashMap
class HashMap {
    static class Node {
        final int hash;
        final K key;
        V value;
        Node next;  // For collision handling (linked list)
        
        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    
    Node[] table;        // Array of buckets (default size 16)
    int size;                 // Number of key-value pairs
    int threshold;            // Capacity * load factor
    final float loadFactor;   // Default 0.75f
    
    // Treeify threshold (Java 8+)
    static final int TREEIFY_THRESHOLD = 8;   // Convert list to tree
    static final int UNTREEIFY_THRESHOLD = 6; // Convert tree back to list
    static final int MIN_TREEIFY_CAPACITY = 64;
}

How put() Works - Step by Step

public class PutMethodDemo {
    public static void main(String[] args) {
        Map map = new HashMap<>();
        
        // Step by step put operation
        map.put("java", "programming");
        
        // Internal steps:
        // 1. Calculate hash code:
        //    hashCode("java") = 3254818 (example)
        // 
        // 2. Apply hash spread function:
        //    hash = hashCode ^ (hashCode >>> 16)
        //    This spreads higher bits to lower bits
        // 
        // 3. Calculate bucket index:
        //    index = (n - 1) & hash
        //    where n = current capacity (default 16)
        // 
        // 4. Check if bucket is empty:
        //    - If empty: create new Node and place it
        //    - If not empty: check for existing key
        // 
        // 5. If key exists: replace value
        // 6. If key doesn't exist and collision: add to linked list
        // 7. If list length >= 8 and capacity >= 64: convert to tree
        
        System.out.println("Put operation completed");
    }
}

Hash Function Implementation

public class HashFunctionDemo {
    // Java's actual hash function for keys
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    public static void main(String[] args) {
        String key = "java";
        
        // Step 1: Get hashCode
        int hashCode = key.hashCode();
        System.out.println("hashCode: " + hashCode);
        System.out.println("hashCode (binary): " + Integer.toBinaryString(hashCode));
        
        // Step 2: Apply hash function (spread higher bits)
        int hash = hash(key);
        System.out.println("hash: " + hash);
        System.out.println("hash (binary): " + Integer.toBinaryString(hash));
        
        // Step 3: Calculate bucket index (n = capacity, default 16)
        int n = 16;
        int index = (n - 1) & hash;
        System.out.println("Bucket index: " + index);
        
        // Why & instead of %? Bitwise AND is faster than modulo
        System.out.println("Using modulo: " + (hash % n));
        System.out.println("Using bitwise: " + (index));
        // Both give same result but & is faster
    }
}

Collision Handling (Chaining)

public class CollisionDemo {
    static class BadKey {
        int value;
        
        BadKey(int value) {
            this.value = value;
        }
        
        @Override
        public int hashCode() {
            return 1;  // Bad hash code - always returns same value
        }
        
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            BadKey badKey = (BadKey) obj;
            return value == badKey.value;
        }
    }
    
    public static void main(String[] args) {
        Map map = new HashMap<>();
        
        // All keys go to same bucket (index = 1 & (n-1))
        map.put(new BadKey(1), "One");
        map.put(new BadKey(2), "Two");
        map.put(new BadKey(3), "Three");
        map.put(new BadKey(4), "Four");
        map.put(new BadKey(5), "Five");
        
        // Internal structure:
        // Bucket 1: [BadKey(1)] -> [BadKey(2)] -> [BadKey(3)] -> [BadKey(4)] -> [BadKey(5)]
        
        System.out.println("Size: " + map.size()); // 5
        
        // Searching requires traversing linked list - O(n)
        System.out.println("Value for key 3: " + map.get(new BadKey(3)));
        
        // Java 8+ improvement: Convert to tree after 8 collisions
        // Treeify threshold: When list length >= 8 and array size >= 64
        // Tree improves search from O(n) to O(log n)
    }
}

Resize (Rehashing) Process

public class ResizeDemo {
    public static void main(String[] args) {
        Map map = new HashMap<>(4);  // Initial capacity 4
        
        System.out.println("Initial capacity: 4");
        System.out.println("Load factor: 0.75");
        System.out.println("Threshold: " + (4 * 0.75) + " = 3");
        System.out.println();
        
        for (int i = 0; i < 12; i++) {
            map.put("Key" + i, i);
            System.out.println("Added Key" + i + ", Size: " + map.size());
            
            // Check if resize occurred
            // When size > threshold, capacity doubles
            // 4 -> 8 -> 16 -> 32
        }
        
        // Resize process details:
        // 1. Create new bucket array (double the size)
        // 2. Rehash all existing entries
        // 3. Redistribute entries to new buckets
        // 4. Update threshold = newCapacity * loadFactor
        // 
        // This is expensive O(n) operation
        // That's why initial capacity should be estimated
        
        System.out.println("
Best practice: ");
        System.out.println("If you know you'll store 100 items:");
        System.out.println("Map map = new HashMap<>(150);");
        System.out.println("// 150/0.75 = 200 capacity, prevents resizing");
    }
}

get() Method Internals

public class GetMethodDemo {
    public static void main(String[] args) {
        Map map = new HashMap<>();
        map.put("java", "language");
        map.put("python", "scripting");
        map.put("c++", "system");
        
        String value = map.get("java");
        System.out.println("Value for 'java': " + value);
        
        // Internal steps of get():
        // 1. Calculate hash("java")
        // 2. Find bucket index: index = (n-1) & hash
        // 3. Get first node at bucket[index]
        // 4. Traverse linked list/tree at that bucket
        // 5. Compare keys using equals() method
        // 6. Return value if found, else null
        
        // Example of equals() importance
        Map personMap = new HashMap<>();
        Person p1 = new Person("John");
        Person p2 = new Person("John");
        
        personMap.put(p1, "Developer");
        System.out.println("With proper equals: " + personMap.get(p2)); // null if equals not overridden
        
        // HashMap relies on both hashCode() and equals()
        // Rule: If equals() returns true, hashCode() must return same value
    }
}

class Person {
    String name;
    Person(String name) { this.name = name; }
    
    @Override
    public int hashCode() {
        return name.hashCode();
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Person person = (Person) obj;
        return Objects.equals(name, person.name);
    }
}

Tree Conversion (Java 8+)

public class TreeConversionDemo {
    public static void main(String[] args) {
        Map map = new HashMap<>();
        
        // Adding many keys with same hash (causes collision)
        for (int i = 0; i < 20; i++) {
            map.put(new BadHashKey(i), "Value" + i);
        }
        
        // Java 8+ Improvements:
        // - When list length >= TREEIFY_THRESHOLD (8)
        // - AND array size >= MIN_TREEIFY_CAPACITY (64)
        // - Convert linked list to balanced Tree (TreeNode)
        // 
        // - Tree improves worst-case performance from O(n) to O(log n)
        // - When list length falls below UNTREEIFY_THRESHOLD (6)
        // - Convert tree back to linked list
        
        System.out.println("Tree conversion improves collision handling");
    }
}

class BadHashKey {
    int value;
    BadHashKey(int value) { this.value = value; }
    
    @Override
    public int hashCode() {
        return 1; // Bad hash - all keys go to same bucket
    }
}

Key Points Summary

public class HashMapSummary {
    public static void main(String[] args) {
        // Important Constants
        System.out.println("=== HashMap Internal Constants ===");
        System.out.println("Default initial capacity: 16");
        System.out.println("Default load factor: 0.75");
        System.out.println("Default threshold: 12 (16 * 0.75)");
        System.out.println("Resize: 2x capacity when size > threshold");
        System.out.println("Treeify threshold: 8 (convert linked list to tree)");
        System.out.println("Untreeify threshold: 6 (convert tree back to list)");
        System.out.println("Min treeify capacity: 64");
        
        // Best Practices
        System.out.println("
=== Best Practices ===");
        System.out.println("1. Override hashCode() and equals() correctly");
        System.out.println("2. Use immutable keys when possible");
        System.out.println("3. Initial capacity = (expected size / load factor) + 1");
        System.out.println("4. For thread-safe: use ConcurrentHashMap");
        System.out.println("5. Set initial capacity to avoid resizing overhead");
        
        // Example: Proper initial capacity
        int expectedSize = 100;
        int initialCapacity = (int) (expectedSize / 0.75f) + 1;
        Map optimized = new HashMap<>(initialCapacity);
        System.out.println("Optimal initial capacity for 100 items: " + initialCapacity);
    }
}

Deep understanding of HashMap internals helps write better code. Learn more at Online Learner!