How does HashMap work internally in Java?

Understanding HashMap internals — hashing, buckets, collisions, resizing, and treeification — is one of the most commonly asked Java interview topics at mid-to-senior level.

// Internal structure:
// - Node[] table  — array of buckets (initially null, lazily allocated)
// - Default capacity: 16, load factor: 0.75
// - When size > capacity * loadFactor → resize (double capacity)

// put(key, value) steps:
// 1. Compute hash: (h = key.hashCode()) ^ (h >>> 16)  — spread high bits
// 2. Bucket index: hash & (capacity - 1)
// 3. If bucket empty: insert new Node
// 4. If bucket occupied (collision):
//    - Walk linked list: if key equals an existing node, update value
//    - Else append to linked list
//    - If list length >= TREEIFY_THRESHOLD (8) AND capacity >= 64:
//      convert to balanced Red-Black tree (O(log n) instead of O(n))

// Performance characteristics
// Best case (no collisions): O(1) get, put
// Worst case (all in one bucket, pre-Java 8): O(n)
// Worst case (all in one bucket, Java 8+): O(log n) after treeification

// Why the spread: hashCode() of strings/integers often has poor high-bit distribution
// The XOR spread: (h) ^ (h >>> 16) mixes high and low 16 bits

// Thread safety
// HashMap is NOT thread-safe
// ConcurrentHashMap: segments replaced by per-bin locking in Java 8
// Hashtable: fully synchronized (legacy, slow)
// Collections.synchronizedMap: wraps HashMap, one lock for all ops

Map map = new HashMap<>(32, 0.75f); // pre-size to avoid rehash

The load factor trade-off: a lower load factor (e.g., 0.5) means fewer collisions but more memory wasted on empty buckets. A higher load factor (e.g., 0.9) uses memory efficiently but increases collision probability, degrading performance toward O(log n) or O(n). The default 0.75 is the empirically best trade-off for general use.

Invest now in Acorns!!! 🚀
Join Acorns and get your $5 bonus!

Acorns is a micro-investing app that automatically invests your "spare change" from daily purchases into diversified, expert-built portfolios of ETFs. It is designed for beginners, allowing you to start investing with as little as $5. The service automates saving and investing. Disclosure: I may receive a referral bonus.

Invest now!!! Get Free equity stock (US, UK only)!

Use Robinhood app to invest in stocks. It is safe and secure. Use the Referral link to claim your free stock when you sign up!.

The Robinhood app makes it easy to trade stocks, crypto and more.

Webull! Receive free stock by signing up using the link: Webull signup.