HashMap

Internal Structure of HashMap

HashMap uses a hash table internally. It consists of an array of "buckets" (also called bins). Each bucket holds a linked list (or tree) of entries that hash to the same bucket index.

Key fields:

• table — the array of buckets (Node[])
• size — number of key-value pairs
• capacity — length of the table array (always a power of 2)
• loadFactor — threshold for resizing (default 0.75)
• threshold — capacity * loadFactor

Java 8+ improvement: When a bucket has more than 8 entries, the linked list converts to a red-black tree for O(log n) lookup instead of O(n).

import java.util.*;

public class HashMapInternalDemo {
    public static void main(String[] args) {
        // Create HashMap
        Map<String, Integer> map = new HashMap<>();

        // Internal structure visualization
        // table[0] -> null
        // table[1] -> Entry("apple", 1) -> Entry("banana", 2) -> null
        // table[2] -> null
        // table[3] -> Entry("cherry", 3) -> null
        // ...

        // How hashing works
        String key1 = "apple";
        String key2 = "banana";
        String key3 = "cherry";

        System.out.println("apple hash: " + key1.hashCode());
        System.out.println("banana hash: " + key2.hashCode());
        System.out.println("cherry hash: " + key3.hashCode());

        // Bucket index = hash & (capacity - 1)
        // This is why capacity must be a power of 2
        int capacity = 16; // default initial capacity
        System.out.println("\napple bucket: " + (key1.hashCode() & (capacity - 1)));
        System.out.println("banana bucket: " + (key2.hashCode() & (capacity - 1)));
        System.out.println("cherry bucket: " + (key3.hashCode() & (capacity - 1)));

        // Putting entries
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("cherry", 3);
        System.out.println("\nMap: " + map);

        // Default capacity and load factor
        Map<Object, Object> defaultMap = new HashMap<>();
        System.out.println("Default capacity: 16");
        System.out.println("Default load factor: 0.75");
    }
}

Key design decisions:

• Capacity is always a power of 2 for efficient index calculation
• Load factor of 0.75 balances space usage and collision probability
• Java 8+ uses treeification (red-black tree) for buckets with >8 entries

Core Methods of HashMap

HashMap provides methods for inserting, retrieving, removing, and checking for keys.

import java.util.*;

public class HashMapMethodsDemo {
    public static void main(String[] args) {
        // Creating
        Map<String, Integer> scores = new HashMap<>();

        // put - insert or update
        scores.put("Alice", 95);
        scores.put("Bob", 87);
        scores.put("Charlie", 92);
        scores.put("Alice", 98); // overwrites previous value
        System.out.println("Map: " + scores);

        // get - retrieve value by key
        Integer aliceScore = scores.get("Alice");
        System.out.println("Alice: " + aliceScore); // 98

        // getOrDefault - return default if key not found
        Integer daveScore = scores.getOrDefault("Dave", 0);
        System.out.println("Dave: " + daveScore); // 0

        // containsKey / containsValue
        System.out.println("Has Alice? " + scores.containsKey("Alice")); // true
        System.out.println("Has 95? " + scores.containsValue(95)); // false (was overwritten)

        // remove
        scores.remove("Bob");
        scores.remove("Charlie", 92); // remove only if value matches
        System.out.println("After removes: " + scores);

        // replace
        scores.replace("Alice", 100); // replace value
        scores.putIfAbsent("Eve", 75); // only put if absent
        System.out.println("After replace: " + scores);

        // compute - transform value based on current value
        scores.compute("Alice", (key, val) -> val == null ? 0 : val + 10);
        System.out.println("After compute: " + scores);

        // merge - combine values
        Map<String, Integer> map1 = new HashMap<>(Map.of("a", 1, "b", 2));
        Map<String, Integer> map2 = new HashMap<>(Map.of("b", 3, "c", 4));
        map2.forEach((key, val) -> map1.merge(key, val, Integer::sum));
        System.out.println("After merge: " + map1); // {a=1, b=5, c=4}

        // keySet, values, entrySet
        System.out.println("Keys: " + scores.keySet());
        System.out.println("Values: " + scores.values());
        System.out.println("Entries: " + scores.entrySet());

        // iteration
        for (Map.Entry<String, Integer> entry : scores.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

Hash Collision Handling

A hash collision occurs when two different keys produce the same bucket index. HashMap handles collisions using separate chaining (linked lists in each bucket).

Collision resolution in Java 8+:

1. Each bucket starts as a linked list
2. When a bucket has >8 entries, the list converts to a red-black tree (treeification)
3. When a bucket shrinks below 6 entries, the tree converts back to a list (untreeification)

import java.util.*;

public class CollisionHandlingDemo {
    // Custom class with intentional hash collisions
    static class CollidingKey {
        private int id;

        public CollidingKey(int id) {
            this.id = id;
        }

        @Override
        public int hashCode() {
            return 42; // All keys hash to same value!
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            CollidingKey other = (CollidingKey) obj;
            return id == other.id;
        }

        @Override
        public String toString() {
            return "Key(" + id + ")";
        }
    }

    public static void main(String[] args) {
        // Demonstrate collision handling
        Map<CollidingKey, String> map = new HashMap<>();

        // All these keys have the same hashCode!
        for (int i = 0; i < 20; i++) {
            map.put(new CollidingKey(i), "Value " + i);
        }

        System.out.println("Map size: " + map.size()); // 20
        System.out.println("All values still accessible:");
        for (int i = 0; i < 20; i++) {
            System.out.println("  " + map.get(new CollidingKey(i)));
        }

        // Good hashCode example
        Map<String, Integer> goodMap = new HashMap<>();
        for (int i = 0; i < 1000; i++) {
            goodMap.put("key" + i, i);
        }
        // Even distribution across buckets
    }
}

Best practices for hashCode():

• Use all significant fields in the hash calculation
• Distribute hash values evenly across the integer range
• If a.equals(b), then a.hashCode() == b.hashCode()

Load Factor and Resizing

The load factor determines when HashMap resizes. When the number of entries exceeds capacity * loadFactor, HashMap creates a new table with double the capacity and rehashes all entries.

Default values:

• Initial capacity: 16
• Load factor: 0.75
• Threshold: 16 * 0.75 = 12 (resize after 12 entries)

import java.util.*;

public class LoadFactorDemo {
    public static void main(String[] args) {
        // Default: capacity 16, load factor 0.75
        Map<Integer, Integer> defaultMap = new HashMap<>();
        for (int i = 0; i < 12; i++) {
            defaultMap.put(i, i * 10);
        }
        System.out.println("Default map (12 entries): capacity still 16");
        System.out.println("Adding 13th entry triggers resize to 32");
        defaultMap.put(12, 120);

        // Custom load factor
        Map<Integer, Integer> lowLoad = new HashMap<>(16, 0.5f);
        for (int i = 0; i < 8; i++) {
            lowLoad.put(i, i * 10);
        }
        System.out.println("\nLow load factor (0.5): resize after 8 entries");

        // High load factor
        Map<Integer, Integer> highLoad = new HashMap<>(16, 0.9f);
        for (int i = 0; i < 14; i++) {
            highLoad.put(i, i * 10);
        }
        System.out.println("High load factor (0.9): resize after 14 entries");

        // Pre-sizing for performance
        int expectedSize = 1000;
        int initialCapacity = (int) (expectedSize / 0.75f) + 1;
        Map<Integer, String> optimized = new HashMap<>(initialCapacity);
        System.out.println("\nPre-sized for 1000 entries: initial capacity = " + initialCapacity);

        // The resize process
        System.out.println("\nResize process:");
        System.out.println("1. Create new table with 2x capacity");
        System.out.println("2. Rehash all entries into new table");
        System.out.println("3. Discard old table");
    }
}

Tradeoffs:

• Lower load factor (0.5): fewer collisions, more memory, more frequent resizing
• Higher load factor (0.9): more collisions, less memory, less frequent resizing
• 0.75 is the sweet spot for most use cases

HashMap Time Complexity

*Worst case O(n) occurs when all keys hash to the same bucket (bad hashCode).
With Java 8+ treeification, worst case is O(log n) for get/put/remove.

import java.util.*;

public class HashMapComplexityDemo {
    public static void main(String[] args) {
        // Average case: O(1)
        Map<String, Integer> map = new HashMap<>();
        map.put("key1", 1); // O(1) average
        int val = map.get("key1"); // O(1) average
        map.remove("key1"); // O(1) average

        // containsValue is always O(n)
        map.put("a", 1);
        map.put("b", 2);
        map.put("c", 3);
        boolean has = map.containsValue(2); // O(n) - must scan all values

        // Iteration is O(capacity), not O(size)
        Map<Integer, Integer> small = new HashMap<>(2);
        small.put(1, 10);
        small.put(2, 20);
        // Internal array has 2 slots, iterating visits all 2

        // Demonstrate O(1) performance
        Map<Integer, Integer> large = new HashMap<>();
        for (int i = 0; i < 1_000_000; i++) {
            large.put(i, i);
        }

        long start = System.nanoTime();
        for (int i = 0; i < 1_000_000; i++) {
            large.get(i); // O(1) each
        }
        long time = System.nanoTime() - start;
        System.out.println("1M gets: " + time / 1_000_000 + "ms");
        System.out.println("Average per get: " + time / 1_000_000.0 + "ns");

        // When HashMap is slow
        System.out.println("\nHashMap is slow when:");
        System.out.println("1. Bad hashCode() causes many collisions");
        System.out.println("2. Load factor too high (>0.9)");
        System.out.println("3. containsValue() which scans all entries");
    }
}