In‑Depth Analysis of Java HashMap Implementation and Usage

HashMap is a widely used Java collection that stores key‑value pairs based on a hash table implementation. Prior to JDK 1.8 it relied on an array combined with linked lists (the "separate chaining" method) to resolve hash collisions.

Starting with JDK 1.8, when a bucket's linked list exceeds a threshold (default 8), it is transformed into a red‑black tree to improve lookup performance. The article explains this transition and its impact on search time.

Underlying data structure

The hash function used to disperse keys is defined as:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

In JDK 1.7 the hash method performed more perturbations:

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

The HashMap class contains several important constants and fields (default capacity, load factor, thresholds, etc.) that control resizing and treeification.

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    private static final long serialVersionUID = 362498820763181265L;
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;
    transient Node<K,V>[] table;
    transient Set<Map.Entry<K,V>> entrySet;
    transient int size;
    int threshold;
    final float loadFactor;
}

The internal node representation is:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // getters, setters, hashCode, equals omitted for brevity
}

Tree nodes extend LinkedHashMap.Entry and add parent/child links and a color flag:

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}

Core methods

The put operation delegates to putVal, which handles initialization, bucket selection, collision resolution (direct replace, tree insertion, or list insertion), and triggers resizing when the size exceeds the threshold.

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // initialization and bucket selection omitted for brevity
    // collision handling logic (replace, treeify, or list append)
    // update size, modCount, and possibly resize
}

The get method locates the appropriate bucket and searches either the tree or the linked list:

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    // bucket lookup and traversal logic
}

The resize method doubles the table size (subject to maximum limits), recomputes thresholds, and rehashes existing entries, which can be costly and should be avoided when possible.

final Node<K,V>[] resize() {
    // compute new capacity and threshold
    // allocate new table and rehash entries
    return newTab;
}

Practical example

A small demo program shows typical HashMap usage: inserting entries, iterating over keys, values, and entry sets, and invoking common methods such as size(), isEmpty(), remove(), containsKey(), and replace().

import java.util.*;

public class HashMapDemo {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();
        map.put("san", "张三");
        map.put("si", "李四");
        map.put("wu", "王五");
        map.put("wang", "老王");
        map.put("wang", "老王2"); // overwrite
        map.put("lao", "老王");
        System.out.println(map);
        // iterate keys
        for (String key : map.keySet()) {
            System.out.print(key + " ");
        }
        System.out.println();
        // iterate values
        for (String value : map.values()) {
            System.out.print(value + " ");
        }
        System.out.println();
        // iterate entries
        for (Map.Entry<String, String> e : map.entrySet()) {
            System.out.println(e.getKey() + "--" + e.getValue());
        }
        // other operations
        System.out.println("size=" + map.size());
        System.out.println("remove san=" + map.remove("san"));
        System.out.println("containsKey si=" + map.containsKey("si"));
        System.out.println("replace si=" + map.replace("si", "李四2"));
    }
}

The article also discusses the significance of the load factor (default 0.75) and the threshold calculation ( threshold = capacity * loadFactor), explaining how they influence when resizing occurs.

Overall, the piece serves as a detailed reference for developers seeking to understand the internal mechanics of Java's HashMap, compare JDK 1.7 and JDK 1.8 implementations, and apply best practices when using this collection.