Java HashMap Implementation

Key Takeaways

• OpenJDK HashMap maps keys to array buckets using a spread hash and a power-of-two index mask.
• Collisions are resolved within a bucket using linked nodes or, conditionally, a red-black tree.
• Growth redistributes entries using their stored hashes; it doesn't call every existing key's hashCode() again.
• Size a map for its expected mappings, not just its constructor capacity. HashMap.newHashMap(expectedMappings) makes that distinction explicit.

The Java HashMap implementation stores key-value entries in an array of buckets. A key's hash selects a bucket, equality identifies the correct entry inside it, and resizing adds buckets as the map grows. Good hash distribution makes basic operations efficient; sensible sizing reduces growth overhead.

Hashing in Action

Think of a bucket as an array slot that can lead to several entries. In OpenJDK, an ordinary entry node stores the spread hash, key, value, and a reference to the next node. It isn't a separate java.util.LinkedList object.

For a non-null key, OpenJDK derives its internal hash from the key's hashCode(). The following method is an implementation excerpt, not a public method you call:

// OpenJDK implementation excerpt; place inside a class if experimenting.
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

The expression h ^ (h >>> 16) mixes upper bits into lower bits. The >>> operator shifts right with zero fill, and ^ performs bitwise exclusive OR. OpenJDK assigns the null key a spread hash of zero.

If you need the public operations first, start with the Java HashMap overview.

Index Calculation

For an allocated table of length n, OpenJDK selects the bucket with this expression:

// Fragment: n is the table length; hash is the spread hash.
int index = (n - 1) & hash;

The table length is a power of two. If n is 16, then n - 1 is binary 1111, so the mask keeps only the lowest four hash bits. The result is an index from 0 through 15.

For non-negative hashes, this mask produces the same result as remainder by a power-of-two capacity. Unlike Java's % with a negative dividend, the mask still gives a non-negative bucket index. Don't treat this as a general replacement for modulo with arbitrary capacities.

Rationale for Bit Manipulation

A small table ignores most hash bits during indexing. Consider these two hypothetical hash codes at capacity 16:

Raw hash       Raw hash & 15   Spread hash    Spread hash & 15
0x00010000     0               0x00010001     1
0x00020000     0               0x00020002     2

Without spreading, both land in bucket 0 despite differing in their upper bits. After spreading, they land in different buckets. This is a worked example of the operators above—not a guarantee that spreading eliminates collisions. Identical hash codes still produce identical spread hashes.

Handling Collisions

A collision occurs when different keys select the same bucket. Their full hash codes don't have to match: the index mask may simply discard the bits that distinguish them.

A lookup such as myMap.get("key1") therefore does more than access tab[index]. That expression is only a conceptual bucket selection. OpenJDK checks the stored spread hash, then key identity or equality; if the first node doesn't match, it searches the remaining list or tree.

The key contract matters: equal keys must return equal hash codes, but unequal keys may share a hash code. HashMap uses equality to distinguish colliding keys. See equals() and hashCode() in Java for the contract in detail.

Linked Nodes vs. Tree Bins

A tree bin uses a red-black tree—a search tree that maintains balance as entries change. It is a fallback for heavily populated buckets, not the normal representation of every bucket.

OpenJDK 25 defines TREEIFY_THRESHOLD = 8 and MIN_TREEIFY_CAPACITY = 64. For ordinary put() insertion into a list, adding a ninth distinct entry to a bucket with eight entries requests treeification. If the table has fewer than 64 buckets, that request causes resizing instead.

Tree bins can become lists again. During resize splitting, a resulting bin with six or fewer entries is untreeified; removal uses a tree-shape test rather than a universal “size falls to six” rule.

Step-by-Step Usage

This executable example preserves the simple name mapping and adds two distinct keys that deliberately collide. Save it as HashMapDemo.java and run java HashMapDemo.java with JDK 25.

import java.util.HashMap;
import java.util.Map;

public class HashMapDemo {
    record Key(String id) {
        @Override
        public int hashCode() {
            return 7; // Deliberately poor hashing for this demonstration.
        }
    }

    public static void main(String[] args) {
        Map<String, String> myMap = new HashMap<>();
        myMap.put("Name", "Sam");
        System.out.println(myMap.get("Name")); // Sam

        Map<Key, String> entries = new HashMap<>();
        entries.put(new Key("A"), "first");
        entries.put(new Key("B"), "second");
        System.out.println(entries.get(new Key("B"))); // second

        entries.put(new Key("A"), "updated");
        System.out.println(entries.get(new Key("A"))); // updated
        System.out.println(entries.size()); // 2
    }
}

The record's generated equals() compares its id component. All these keys share hash code 7, but A and B remain separate mappings; a new Key containing A replaces A's value. Constant hashing satisfies the equal-keys contract here, but deliberately gives poor distribution.

For the OpenJDK put() path, read the operation in this order:

1. Compute the spread hash; allocate the table if needed.
2. Calculate the bucket index.
3. If the bucket is empty, create its first node.
4. Otherwise, check the first node's hash and key.
5. If necessary, traverse linked nodes or search the tree bin.
6. If an equal key exists, replace its value without increasing the mapping count.
7. If no key matches, insert a new entry and consider treeification.
8. After adding a mapping, increase the size and resize if it exceeds the growth threshold.

These are different paths through the implementation, not a requirement that every insertion traverse a list. For more public API patterns, see Java HashMap examples.

Resizing Mechanics

Capacity means bucket count; size means mapping count. The default initial capacity is 16 and the default load factor is 0.75. In OpenJDK, the no-argument constructor defers table allocation until the first insertion.

The load factor controls a growth threshold, approximately capacity × loadFactor. At capacity 16 with the default factor, that threshold is 12; adding the thirteenth mapping triggers growth unless collision handling has already grown the table. Replacing a value doesn't increase size.

The threshold comparison is cheap. The expensive operation is allocating a larger array and redistributing entries when growth actually occurs.

How the Resize Split Works

When a power-of-two table doubles, its index mask gains one bit. An entry at old index i either stays there or moves to i + oldCapacity, depending on (storedHash & oldCapacity). OpenJDK uses the stored hash instead of calling the existing key's hashCode() again.

Example: capacity 16 grows to 32; stored hashes are 5 and 21.

Old bucket 5: [hash 5] -> [hash 21]
                   |              |
              5 & 16 == 0    21 & 16 != 0
                   |              |
New bucket 5: [hash 5]    New bucket 21: [hash 21]
                              5 + 16

In this worked example, the added mask bit separates entries that previously collided. The insertion that triggers growth still hashes its own key; redistribution doesn't re-hash all existing keys.

Choosing Initial Capacity for Expected Entries

new HashMap<>(1_000) doesn't mean “hold 1,000 mappings before growth.” In OpenJDK 25, that request rounds to 1,024 buckets, whose default-load-factor threshold is 768. These numbers follow from power-of-two rounding and 1,024 × 0.75.

For expected mapping counts, prefer HashMap.newHashMap(int numMappings), available since Java 19. It uses the default load factor and chooses an initial capacity intended to accommodate that count.

// Fragment inside a method; import java.util.HashMap and java.util.Map.
int expectedMappings = 1_000;
Map<String, Integer> counts = HashMap.newHashMap(expectedMappings);

// Constructor alternative, including for JDKs without newHashMap():
float loadFactor = 0.75f;
int requestedCapacity =
        (int) Math.ceil(expectedMappings / (double) loadFactor);
Map<String, Integer> otherCounts =
        new HashMap<>(requestedCapacity, loadFactor);

The constructor calculation requests 1,334 buckets. OpenJDK rounds that to 2,048, giving a threshold of 1,536 at load factor 0.75. This example addresses load-driven growth; small maps can still grow because collision handling requests a resize.

Efficiency and Performance

With well-distributed hashes, get() has expected constant-time behavior, and ordinary put() is amortized constant time: occasional growth costs are spread across many insertions. Tree bins mitigate many severe-collision cases, but don't guarantee logarithmic lookup for every possible key type.

Initial capacity is a trade-off, not a setting to maximize. Oversizing consumes bucket-array memory, and HashMap iteration takes time proportional to capacity plus size. The default load factor of 0.75 is a practical time-space compromise, not a universally optimal value.

For interview preparation, explain the expected case, collision paths, and resize costs separately rather than answering with a single complexity label. Practice with these Java HashMap interview questions.

Common Mistakes

• Changing a key's identity fields: don't mutate state used by equals() or hashCode() while the key is stored. The Map contract leaves behavior unspecified when mutation affects key equality.
• Depending on observed iteration order: HashMap doesn't guarantee insertion order. A default LinkedHashMap preserves insertion order when you need that behavior.
• Sharing an unsynchronized map for concurrent updates: HashMap isn't synchronized; concurrent structural modification requires external synchronization. ConcurrentHashMap is a concurrent alternative, but unlike HashMap it rejects null keys and values.
• Interpreting every null result as absence: HashMap permits null values, so get() returning null is ambiguous. Use containsKey() when you must distinguish an absent key from a null-valued mapping.

FAQ

How does HashMap work internally in Java?

In OpenJDK 25, HashMap spreads a key's hash code, selects an array bucket with a bit mask, and searches that bucket for an equal key. Buckets contain linked nodes or red-black tree nodes, and the table grows as mappings accumulate.

How does HashMap handle collisions?

Colliding keys share a bucket, not necessarily a mapping. OpenJDK checks stored hashes and key equality within linked nodes or a tree bin to find the correct entry.

When does a HashMap bucket become a red-black tree?

In OpenJDK 25, ordinary put() insertion requests treeification when it adds a ninth distinct entry to a list bin containing eight entries. The table must have at least 64 buckets; otherwise that request causes resizing instead.

Does resizing a HashMap call hashCode() again?

Normal OpenJDK table growth redistributes existing entries using their stored spread hashes rather than calling their keys' hashCode() methods again. The insertion that triggers growth still computes the hash for its own key.

How do I set HashMap capacity for an expected number of entries?

On Java 19 and later, use HashMap.newHashMap(expectedMappings). If you use a constructor instead, account for the load factor and power-of-two capacity rounding; the constructor argument isn't an expected mapping count.

These answers distinguish the public API from the OpenJDK implementation discussed above.

Further Reading

• HashMap API documentation — public behavior, sizing, load factor, and synchronization requirements.
• OpenJDK 25 HashMap source — hashing, lookup, treeification, and resize splitting.
• Object.equals() and hashCode() — the contract custom keys must satisfy.
• Map API documentation — key uniqueness and mutable-key restrictions.
• Java Language Specification: expressions — shift, bitwise, and remainder operators.
• Record API documentation — generated equality behavior used by the collision example.
• LinkedHashMap API documentation — predictable encounter order.
• ConcurrentHashMap API documentation — concurrent access and differences from HashMap.