Understanding Java HashMap: Collision Resolution and Performance

The article is part of a series on interview preparation and focuses on the internal implementation of Java's HashMap, illustrating how hash collisions are handled and how performance is affected by load factor and capacity.

HashMap is not thread‑safe; to obtain a synchronized version, use Collections.synchronizedMap .

Map map = Collections.synchronizedMap(new HashMap());

1. Overview of HashMap

HashMap implements the Map interface based on a hash table. It allows null keys and values, does not guarantee ordering, and is not synchronized.

2. Data Structure of HashMap

The underlying structure consists of an array of Entry objects, each holding a key, value, hash, and a reference to the next entry, forming a singly linked list to resolve collisions.

HashMap uses two main collision‑resolution strategies: chaining (linked lists) and open addressing. Java's implementation uses chaining.

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

3. Source Code Analysis

Key Fields

transient Entry[] table; // array of buckets
transient int size; // number of entries
int threshold; // resize threshold (capacity * loadFactor)
final float loadFactor; // default 0.75
transient int modCount; // structural modifications count

The load factor balances space utilization and collision probability: a larger factor saves memory but increases collisions; a smaller factor reduces collisions but wastes space.

Constructors

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);
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor);
    table = new Entry[capacity];
    init();
}

public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); }

Storing Data (put)

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    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;
}

If the key is null, the entry is stored in bucket 0. Otherwise the hash code is transformed, an index is computed, and the entry is either updated or added to the head of the bucket's linked list.

Resizing

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];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

Resizing occurs when size exceeds threshold. The new capacity is typically double the old one, and all entries are rehashed into the new array.

Retrieving Data (get)

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    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.equals(k)))
            return e.value;
    }
    return null;
}

The method computes the hash, locates the bucket, and traverses the linked list to find the matching key.

4. Performance Parameters

HashMap() : initial capacity 16, load factor 0.75.

HashMap(int initialCapacity) : custom capacity, default load factor 0.75.

HashMap(int initialCapacity, float loadFactor) : custom capacity and load factor.

initialCapacity : size of the underlying array.

loadFactor : ratio of stored entries to array size; default 0.75 balances memory use and lookup speed.

When the number of entries exceeds capacity * loadFactor, the map resizes, which is an expensive operation because all entries must be rehashed.

Understanding these internals helps developers write more efficient code and answer interview questions about HashMap behavior.