Java 7 HashMap Source Code Analysis

Word count: 3.1kReading time: 19 min

 2015/08/05

Finding a value in an unsorted array or linked list without an additional index can require scanning every element. A hash table uses a hash to locate a bucket and supports constant-time basic lookup when hashes are well distributed; it does not guarantee O(1) lookup for every input.

HashMap is an implementation of the Map interface based on a hash table. This implementation provides all optional mapping operations and permits null values and null keys. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

This article follows the source through the array-and-list structure, constructors, put and resizing, get, and the iterator checks using modCount. A final section covers changes in later JDKs.

Version note (reviewed 2026-10-13): This preserves the original 2015 source analysis, checked against OpenJDK jdk7u21-b11. Eager array allocation, Entry chains, and alternative hashing are historical implementation details, not descriptions of every later release—even Java 7 updates differ. These are JDK source excerpts, not standalone classes to copy and run. Android implementations must be checked against the relevant libcore version.

1. HashMap Data Structure

This version uses an array and linked lists: each array slot holds the head of a bucket chain, or null for an empty bucket. The excerpt below shows only the Entry fields; its methods are in the linked source.

HashMap Structure

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
    // Methods omitted; see the linked source.
}

Entry is a package-private static nested class implementing Map.Entry<K,V>. Its next reference points to the following node. A final key reference does not make the key object immutable: do not change state used by its hashCode() or equals() while it is stored as a key.

2. Constructors

HashMap has four constructors:

HashMap(): Constructs an empty HashMap with the default initial capacity (16) and default load factor (0.75).
HashMap(int initialCapacity): Constructs an empty HashMap with a specified initial capacity and the default load factor (0.75).
HashMap(int initialCapacity, float loadFactor): Constructs an empty HashMap with a specified initial capacity and load factor.
HashMap(Map<? extends K,? extends V> m): Constructs a new HashMap with the same mappings as the specified Map.

In essence, these boil down to two types: one where you specify initial capacity and load factor, and another that generates a new HashMap from an existing map. Let’s look at the first type:

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);

    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;

    this.loadFactor = loadFactor;
    threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    init();
}

initialCapacity requests an initial bucket count, not the number of mappings that fit without resizing. This version allocates the array in the constructor. Negative requests are rejected, requests above MAXIMUM_CAPACITY are clamped to 1 << 30, and the capacity is rounded up to a power of two; a request of 0 produces an array of length 1. The defaults are 16 buckets and a load factor of 0.75.

The constructor calculates threshold using capacity * loadFactor and the expression shown above. Do not treat (1 << 30) + 1 as a lifetime threshold limit: resize sets it to Integer.MAX_VALUE when maximum capacity is reached. The bucket limit of 1 << 30 does not guarantee enough heap memory to allocate that array.

As shown below, addEntry requests resizing only for a new key when the pre-insertion size >= threshold and the destination bucket is nonempty. Reaching the threshold alone does not immediately trigger a resize.

The constructor throws IllegalArgumentException if the load factor is nonpositive or NaN, the special floating-point “not a number” value.

3. put Operation

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

Since HashMap allows null keys, it first checks if the key is null and performs special handling.

/**
 * Offloaded version of put for null keys
 */
private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

A null key is always inserted at index 0 of the array. If an entry already exists at that position with a null key, its value is replaced; otherwise, a new entry is added. We’ll examine the addEntry function shortly.

Question: If a null key is always inserted into table[0], why do we still need to traverse the linked list?

For a non-null key, put calls hash(key). This mixes bits from the key’s hashCode(); when alternative hashing is enabled, it also uses a seed and a separate String path. Here is the complete method from this version:

final int hash(Object k) {
    int h = 0;
    if (useAltHashing) {
        if (k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h = hashSeed;
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

useAltHashing, hashSeed, and sun.misc.Hashing are implementation details, not public APIs for application code. This tag defaults the alternative-hashing threshold to Integer.MAX_VALUE, so an ordinary map should not be assumed to use that path. indexFor then selects a bucket:

/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length - 1);
}

There is a neat trick in that one-line indexFor method. Remember the restriction on the array length? Because length is a positive power of two, length - 1 is a mask of low-order ones. The bitwise AND produces an index from 0 to length - 1. This is not unconditionally equivalent to Java’s h % length: a negative h can produce a negative remainder, whereas this index is nonnegative. For other lengths, the mask would not cover all buckets evenly. The operator alone does not establish a performance advantage on every runtime.

This also answers the previous question. Since indexFor returns values ranging from 0 to (length - 1), it’s possible for non-null keys to also map to table[0]. Thus, we must traverse the linked list to find the exact key.

The bucket chain is searched for a matching hash and a key matching by identity or equals(); equal hashes alone do not imply equal keys. Replacing an existing value returns before modCount++. The count is incremented only on the new-key path here, before addEntry; it tracks structural changes for fail-fast checks, not every value write.

/**
 * Adds a new entry with the specified key, value and hash code to
 * the specified bucket.  It is the responsibility of this
 * method to resize the table if appropriate.
 *
 * Subclass overrides this to alter the behavior of put method.
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

addEntry takes the hash, key, value, and bucket index; the last comes from indexFor(hash, table.length). It attempts to double capacity only when size >= threshold and the destination bucket is nonempty. Inserting into an empty bucket does not lengthen an existing chain, so this version can defer resizing. After a resize, it recalculates the pending key’s hash and bucket index before calling createEntry.

/**
 * Rehashes the contents of this map into a new array with a
 * larger capacity.  This method is called automatically when the
 * number of keys in this map reaches its threshold.
 */
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    boolean oldAltHashing = useAltHashing;
    useAltHashing |= sun.misc.VM.isBooted() &&
            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = oldAltHashing ^ useAltHashing;
    transfer(newTable, rehash);
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

resize first checks if the table has already reached its maximum capacity (1 << 30). If so, the threshold is set to Integer.MAX_VALUE to prevent further resizing. Otherwise, the addEntry call path shown here creates an array with double the previous length. Because capacities are powers of two up to MAXIMUM_CAPACITY, this doubling does not exceed that limit. The transfer function then migrates the elements.

/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

transfer moves the existing nodes. It calls hash(key) again for non-null keys only when rehash is true, meaning that resizing switched alternative hashing on. Otherwise, it uses each node’s cached hash to calculate its new bucket index.

Doubling capacity does not move every node to a different index. With an unchanged hash, the new index is either the old index or that index plus the old capacity. Head insertion during migration can reverse node order within a chain. resize then replaces table and updates the threshold. Applications must not depend on HashMap iteration order, even without resizing.

Choosing capacity from an expected data size can reduce migration, but excessive capacity costs memory and traversal time: iteration scans both the bucket array and its nodes, not just size entries.

Back in addEntry, after potentially resizing, a new entry is created:

/**
 * Like addEntry except that this version is used when creating entries
 * as part of Map construction or "pseudo-construction" (cloning,
 * deserialization).  This version needn't worry about resizing the table.
 */
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

createEntry uses the same parameters as addEntry. Its logic is closely tied to the Entry constructor:

/**
 * Creates new entry.
 */
Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
}

The constructor takes an Entry object (n) and sets it as the next value for the new entry. Effectively, createEntry takes the existing list at table[bucketIndex], attaches it to the end of the new entry, and then places the new entry at the head of table[bucketIndex].

Entry Insertion

This concludes the put function. If a new key-value pair is inserted, it returns null.

4. get Operation

/**
 * Returns the value to which the specified key is mapped,
 * or {@code null} if this map contains no mapping for the key.
 */
public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

Like put, it first handles null keys:

/**
 * Offloaded version of get() to look up null keys. Null keys map
 * to index 0.
 */
private V getForNullKey() {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

For non-null keys, it calls getEntry:

/**
 * Returns the entry associated with the specified key in the
 * HashMap. Returns null if the HashMap contains no mapping
 * for the key.
 */
final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

getEntry calculates the hash and bucket index, searches the chain, and returns a matching node or null. The outer get returns the node’s value. Thus, get(key) == null can mean either a missing key or a key mapped to null; use containsKey(key) when that distinction matters. The two calls do not form an atomic concurrent operation.

5. Fail-Fast Mechanism

/**
 * The number of times this HashMap has been structurally modified.
 * Structural modifications are those that change the number of mappings in
 * the HashMap or otherwise modify its internal structure (e.g.,
 * rehash). This field is used to make iterators on Collection-views of
 * the HashMap fail-fast.
 */
transient int modCount;

HashMap is not thread-safe. Fail-fast checks detect structural changes during iteration, such as adding or removing mappings through the map. A modification outside the iterator in the same thread can also trigger the check; a second thread is not required. Merely replacing an existing key’s value is not a structural change here.

modCount is an ordinary int, not volatile, and supplies no synchronization. transient affects default serialization, not cross-thread visibility. The iterator saves expectedModCount at construction and compares the counts in nextEntry() and remove(). Here is the complete internal iterator class:

private abstract class HashIterator<E> implements Iterator<E> {
    Entry<K,V> next;        // next entry to return
    int expectedModCount;   // For fast-fail
    int index;              // current slot
    Entry<K,V> current;     // current entry

    HashIterator() {
        expectedModCount = modCount;
        if (size > 0) { // advance to first entry
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Entry<K,V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();

        if ((next = e.next) == null) {
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
        current = e;
        return e;
    }

    public void remove() {
        if (current == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Object k = current.key;
        current = null;
        HashMap.this.removeEntryForKey(k);
        expectedModCount = modCount;
    }
}

hasNext() only checks whether a node remains; it does not compare modification counts. The iterator’s own remove() updates expectedModCount after deletion, so that permitted operation does not invalidate the iterator because of its own change.

Note: Fail-fast is a best-effort bug detector. It cannot guarantee detection of unsynchronized concurrent modification, and correctness must not depend on ConcurrentModificationException. Shared reads and writes need suitable synchronization or a concurrent-container design. A value replacement that leaves the count unchanged is not automatically safe across threads.

6. Changes in Later JDKs (2026 Update)

OpenJDK jdk7u80-b15: An ordinary empty-map constructor no longer allocates the bucket array immediately. table starts as EMPTY_TABLE, and the first put calls inflateTable. The 7u21 allocation timing does not describe every Java 7 update.
OpenJDK jdk8-b132: Entries use Node, and collision chains can become red-black trees. TREEIFY_THRESHOLD = 8 and MIN_TREEIFY_CAPACITY = 64, but the insertion path and capacity also matter: the eighth node does not unconditionally trigger treeification. A small table is resized first. Resizing ordinary chains splits them into low and high groups while preserving relative order within each group, unlike the old head-insertion transfer.
Java SE 19 onward: HashMap.newHashMap(expectedMappings) accepts an expected mapping count and uses the default load factor. This differs from the constructor’s initial bucket-capacity argument. Checked here against the Java SE 25 API documentation.

These changes do not make HashMap ordered or thread-safe. For modern JDK implementations, follow putVal, resize, and treeifyBin in the relevant release. For Android, check platform API availability and libcore as well: the JDK selected for compilation alone does not establish on-device behavior.

References

Original reference: Core Java (edition not specified in the original).
OpenJDK 7u21-b11 HashMap.java
OpenJDK 7u80-b15 HashMap.java
OpenJDK 8-b132 HashMap.java
Java SE 25 HashMap API

About Me && Blog

Below are my personal details and links. I look forward to connecting and sharing knowledge with fellow developers!

About Me: Includes my WeChat and WeChat group links.
Blog Navigation: A guide to the content on this blog.
Curated Android Performance Articles: A collection of must-read performance optimization articles. Self-nominations/recommendations are welcome!
Android Performance Knowledge Planet: The paid community stopped operating in 2026 and no longer accepts new members; this link preserves its history.