Detailed explanation
HashMap stores key-value mappings in an array of buckets, represented internally by Node references in typical OpenJDK implementations. Each ordinary node contains a cached hash, key, value, and next reference. The backing array is allocated lazily on first insertion, and its capacity is a power of two. HashMap permits one null key and multiple null values, but provides no iteration-order guarantee and is not thread-safe. Interviewers expect you to connect this structure to lookup performance rather than just repeat implementation constants.
For a non-null key, HashMap spreads its hashCode using h ^ (h >>> 16), bringing information from higher bits into lower bits. A null key receives hash zero. It selects the bucket using (capacity - 1) & hash, not an explicit modulo operation. During put, it checks the bucket for an existing mapping by comparing the stored hash and then key identity or equals. A matching key has its value replaced; otherwise, a new node is inserted. get follows the same hashing and matching process.
Different keys can reach the same bucket, creating a collision. Initially, colliding entries form a linked list. Java 8 introduced red-black tree bins to reduce the impact of heavily populated buckets. The treeification threshold constant is 8, but saying 'the eighth entry always creates a tree' is inaccurate: the ordinary put list path typically requests treeification when adding the ninth entry. Treeification also requires a table capacity of at least 64; below that, HashMap resizes instead. Tree-bin lookup can approach O(log n), although equal-hash, non-comparable keys can require broader searches.
With the default load factor of 0.75, a capacity of 16 normally has a resize threshold of 12. Inserting a new mapping that pushes size above this threshold normally doubles capacity. During resizing, cached hashes let entries stay at their old index or move by the old capacity; key hashCode methods need not be called again. With well-distributed hashes, get is expected O(1) and put is amortized O(1), but resizing costs O(n). Correctness also depends on consistent equals and hashCode implementations and keys whose equality-relevant state remains unchanged while stored.
Key points to remember
- Buckets hold nodes containing a cached hash, key, value, and link to another node.
- The spread hash selects a bucket through (capacity - 1) & hash.
- Keys match through identity or equals after the stored hash matches; replacing a value does not increase size.
- Collisions use lists or red-black tree bins; treeification requires sufficient bin length and capacity of at least 64.
- The default load factor is 0.75; resizing usually doubles capacity, supporting amortized constant-time insertion.
Common mistakes candidates make
- Claiming every eighth collision automatically creates a tree, without mentioning the minimum table capacity or insertion-path details.
- Assuming equal hash codes mean equal keys, or changing a stored key's equality-relevant fields.
- Claiming HashMap always provides O(1) operations, preserves insertion order, or safely supports concurrent mutation.
Likely follow-up questions
Why must equals and hashCode be consistent?
Keys that are equal according to equals must return the same hash code so HashMap can locate them through the same hashing process. Unequal keys may share a hash code; HashMap distinguishes them using identity or equals.
What happens if a key is modified after insertion?
If the modification changes its hash code or equality behaviour, lookup or removal may fail even when you pass the same object. The node retains its original cached hash and placement, so immutable keys are usually safer.
What should you use when multiple threads access the map?
For concurrent reads and updates, consider ConcurrentHashMap, which also provides atomic operations such as compute and putIfAbsent. A Collections.synchronizedMap wrapper is another option, but compound actions and iteration require appropriate external synchronization.
Interview tip: Walk through put and get first, then explain collisions, treeification conditions, resizing, and the equals–hashCode contract.