“How does HashMap work?” sounds like one Java interview question, but it is really a ladder. A weak answer stops at key-value storage. A useful answer explains how a key reaches a bucket, how collisions are handled, why resizing matters, and what the equals() and hashCode() contract protects.
Build the answer in those layers so you can stop at the depth the interviewer wants or keep going when the follow-up arrives.
Layer 1: hashing a key to an index
HashMap first obtains the key's hashCode(). In the Java implementation, it spreads information from the high bits into the low bits with a calculation equivalent to:
hash = h ^ (h >>> 16);For a bucket-array length n that is a power of two, the index is:
index = (n - 1) & hash;Consider an illustrative map with n = 16. Suppose three key objects produce effective spread hashes 5, 21 and 7. Their indices are:
Key A:
(16 - 1) & 5 = 15 & 5 = 5Key B:
(16 - 1) & 21 = 15 & 21 = 5Key C:
(16 - 1) & 7 = 15 & 7 = 7
Key A and Key B reach bucket 5 even though their hashes differ. Key C reaches bucket 7. Check the arithmetic another way: masking with 15 keeps the lowest four binary bits. Both 5 and 21 end in 0101, which is 5, while 7 ends in 0111.
The spreading step matters because the mask uses low bits. If a class varies mainly in higher hash bits, mixing those bits down improves distribution.
Layer 2: collisions and bucket chains
A collision means two distinct keys select the same bucket. It does not mean the map overwrites one of them. A bucket can hold a chain of nodes, and each node contains a hash, key, value and link to the next node.
On put(key, value), the map examines the selected bucket. If it finds an existing key with the matching hash and an equals() match, it replaces that key's value. If no matching key exists, it adds a new node to the bucket structure.
On get(key), it recomputes the hash and index, enters the same bucket, then checks candidate keys. Hash comparison is a quick filter. equals() establishes logical key equality.
Good hash distribution keeps chains short. Poor distribution sends many keys to a few buckets and makes lookup do more equality checks. That is why the hashing and collision resolution fundamentals remain relevant even when Java hides the array from you.
Layer 3: load factor and resizing
A HashMap cannot keep accepting entries into one fixed bucket array without degrading. Its capacity is the array length, and its load factor determines the resize threshold. With the usual default load factor of 0.75, capacity 16 gives a threshold of:
16 x 0.75 = 12 entries
An insertion that takes the size beyond that threshold causes the table to grow, normally by doubling. Entries must then be redistributed for the new capacity. This resize is expensive at that moment, but ordinary put and get operations are expected constant time when hashes are well distributed. Repeated inserts therefore have amortised expected constant-time behaviour rather than a guarantee that every insertion costs the same.
Power-of-two capacity makes index calculation a fast bit mask, and it also makes redistribution cheap. Doubling capacity 16 to 32 widens the mask from 15 to 31, so exactly one more hash bit enters the index: the bit worth 16. An entry whose hash has that bit clear keeps its old index, and an entry whose hash has it set moves up by exactly the old capacity.
Run the three keys from Layer 1 through the wider table:
Key A:
(32 - 1) & 5 = 31 & 5 = 5, and the bit worth 16 is clear, so it stays in bucket 5.Key B:
(32 - 1) & 21 = 31 & 21 = 21, and the bit worth 16 is set, so it moves to bucket 5 + 16.Key C:
(32 - 1) & 7 = 31 & 7 = 7, and the bit worth 16 is clear, so it stays in bucket 7.
Key A and Key B no longer share a bucket. That is why growing the table often repairs a distribution problem without any change to the keys. The threshold rises with the capacity:
32 x 0.75 = 24 entries
If you know that a map will hold many entries, choosing a suitable initial capacity can avoid repeated growth. Do not mechanically choose a huge table, though. Empty buckets consume space, and capacity planning is a time-space decision.
Layer 4: treeification since Java 8
Since Java 8, a heavily populated bucket can change from a linked structure to a balanced tree. Tree lookup limits the damage caused by many collisions, improving that bin's worst-case search from linear towards logarithmic time.
The implementation does not treeify every small collision chain. A bin reaches the treeification threshold at eight entries, and the table must have capacity at least 64. At a smaller capacity, the map prefers resizing because a wider table may distribute the keys naturally. These are implementation details worth knowing for interviews, not a reason to design keys that collide.
The clean answer is: chaining handles normal collisions, and treeification protects a sufficiently large, collision-heavy bin.
The equals and hashCode contract
The key rule is precise: if two objects are equal according to equals(), they must return the same hashCode(). Unequal objects may share a hash, because the bucket logic can still separate them through equals().
A classic broken-key demo uses a mutable field in both methods:
Create a
UserKeywhoseidis 42. Its hash is derived from 42.Insert it into the map. The entry is stored in the bucket chosen from that hash.
Change the same object's
idto 99.Call
get()with the mutated object. The map now computes a hash from 99 and searches a different bucket.The lookup can return
nulleven though the entry still occupies the original bucket.
The map has not moved the node when the field changed. That is why keys should be immutable, or at least must not change fields used by equals() and hashCode() while stored. The same immutability idea appears in Java string handling and the string pool.
Common HashMap follow-up questions
Those four layers answer the main question. Interviewers then probe the edges of the contract, usually by contrasting HashMap with its neighbours in the Java Collections Framework.
Can HashMap store null?
Yes. HashMap permits one null key and permits null values. A null result from get() is therefore ambiguous: it can mean no mapping or a mapping to null. Use containsKey() when the distinction matters.
HashMap vs Hashtable
HashMap is not thread-safe and allows nulls. Hashtable is a legacy synchronized class and rejects null keys and values. Saying “Hashtable is thread-safe” is incomplete because synchronizing individual methods does not automatically make a multi-step compound action safe.
HashMap vs ConcurrentHashMap
ConcurrentHashMap is designed for concurrent access with much finer coordination than one lock around an entire map. It rejects null keys and values, which avoids ambiguity during concurrent reads. Choose it for shared mutable maps, then use its atomic operations such as computeIfAbsent() when a read-modify-write action must be treated as one operation.
The short version and next step
The interview answer is a pipeline: hashCode(), spread the hash, mask it to an index, resolve collisions within the bucket, resize after the threshold, and treeify a large collision-heavy bin. equals() confirms a key match, and immutable keys keep the lookup path stable.
Revise the wider collection contracts through the Complete Java Course, then practise choosing maps, sets and lists from the Coding and Skill Development route. If you can reproduce the 16-bucket example and explain the mutable-key failure, your answer has the depth most follow-ups are testing.
