Understanding Java HashMap: Overview, Data Structure, and Source Code Analysis

HashMap inherits from AbstractMap and implements Map, Cloneable, and Serializable. Both keys and values may be null, the map is unordered, and it is not synchronized; a thread‑safe version can be obtained via Collections.synchronizedMap. Map map = Collections.synchronizedMap(new HashMap()); The two most important parameters are the initial capacity and the load factor (default 0.75f). When the number of entries exceeds capacity × loadFactor, a rehash (doubling the bucket array) is performed. A larger load factor improves space utilization but raises collision probability, while a smaller load factor reduces collisions at the cost of more unused space.

Internally, HashMap is an array of buckets, each bucket holding a singly‑linked list of Entry objects. The hash code of a key is transformed by the hash(int h) method and then masked with h & (length‑1) to obtain the bucket index, enabling fast indexing without a modulo operation.

The Entry class stores the key, value, hash, and a reference to the next entry in the same bucket. It implements Map.Entry and provides standard methods such as getKey(), getValue(), setValue(), equals(), hashCode(), and toString().

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;
    Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; }
    public final K getKey() { return key; }
    public final V getValue() { return value; }
    public final V setValue(V newValue) { V old = value; value = newValue; return old; }
    public final boolean equals(Object o) { /* omitted for brevity */ }
    public final int hashCode() { return (key==null?0:key.hashCode()) ^ (value==null?0:value.hashCode()); }
    public final String toString() { return key + "=" + value; }
    void recordAccess(HashMap<K,V> m) {}
    void recordRemoval(HashMap<K,V> m) {}
}

Key operations such as get, put, and remove traverse the appropriate bucket list, updating or returning values as needed. Insertion adds new entries at the head of the list, and if the size reaches the threshold, resize() doubles the bucket array and re‑hashes existing entries.

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold) resize(2 * table.length);
}

When the key is null, a special handling path stores the entry in table[0] using putForNullKey and retrieves it with getForNullKey.

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) { V old = e.value; e.value = value; e.recordAccess(this); return old; }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

The hash(int h) method mixes the high bits of the original hash code to improve distribution, while indexFor(int h, int length) computes the bucket index efficiently.

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) { return h & (length-1); }

Overall, HashMap provides constant‑time average performance for basic operations, but its performance depends on proper capacity and load‑factor tuning, as well as understanding its internal chaining mechanism.