Hiprup

How does HashMap work internally in Java?

A HashMap stores key-value pairs in an internal array of buckets, indexed by the key's hash.

  • Hashing — key.hashCode() is rehashed and modulo-mapped to a bucket index.

  • Collision handling — entries with the same bucket form a linked list; if it grows past 8 nodes it becomes a balanced tree (Java 8+) for O(log n) lookup.

  • Load factor & resize — default load factor 0.75; when exceeded the table doubles and entries are rehashed.

  • equals + hashCode contract — equal keys must produce the same hash, otherwise lookups silently fail.

  • Not thread-safe — concurrent writes can corrupt the structure; use ConcurrentHashMap.

// Internal structure (simplified)
public class HashMap<K, V> {
    Node<K,V>[] table;  // Array of buckets
    int size;
    float loadFactor = 0.75f;
    
    static class Node<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next; // Linked list for collisions
    }
    
    public V put(K key, V value) {
        int hash = hash(key);                    // Step 1: Hash the key
        int index = hash & (table.length - 1);   // Step 2: Find bucket
        // Step 3: Handle collision (add to chain or update existing)
        // Step 4: Resize if size > capacity * loadFactor
    }
}

// Why hashCode/equals contract matters
Map<Person, String> map = new HashMap<>();
Person p = new Person("John");
map.put(p, "value");
p.setName("Jane");          // Mutating the key!
map.get(p);                  // null! Hash changed, wrong bucket

The table array holds buckets. Each bucket starts as a linked list of Nodes (key-value pairs with the same bucket index).

The hash determines the bucket, and equals finds the exact entry. The mutable key example shows why immutable keys are essential: changing the key after insertion changes its hash, making it unreachable in the wrong bucket.

Know the Java 8 treeification (linked list -> tree at threshold 8). The resize mechanism (double capacity, rehash all) explains why initial capacity matters.

The mutable key bug is a classic interview scenario.

How does HashMap work internally in Java? | Hiprup