HashMap, HashSet & TreeMap Internals — Interview Questions

How to use this lesson

"How does HashMap work internally?" is the most asked Java collections question. Walk through it as a sequence: hash → bucket index → collision handling → equals → resize, and you'll handle every follow-up.

Q1. How does a HashSet guarantee no duplicates?

Short answer: A HashSet is backed by a HashMap. Each element is stored as a key, with a shared dummy value. Map keys are unique, so add of an equal element just finds the existing key and returns false.

Set<String> skus = new HashSet<>();
skus.add("A-1");     // true
skus.add("A-1");     // false: already present, set unchanged

Key points to cover:

• "Equal" means hashCode() locates the bucket, and then equals() confirms the match. So a HashSet of your own objects works only if they implement both methods correctly.

Learn it in depth → HashMap Deep Dive

Q2. How do hashCode() and equals() work together in hash-based collections?

Short answer: hashCode() decides which bucket an object belongs in. equals() decides whether two objects in that bucket are the same key. A lookup computes the hash, jumps straight to one bucket, and compares only the few entries there with equals.

Key points to cover:

• The contract:
  • Equal objects must have equal hash codes.
  • Unequal objects may share a hash code (a collision).
  • Both methods must be consistent while the object sits in a collection.

Learn it in depth → equals() and hashCode()

Q3. Why must you override hashCode() when you override equals()?

Short answer: If two objects are equal but have different hash codes, they land in different buckets. HashMap and HashSet then never compare them with equals, so lookups fail, and "duplicate" entries appear.

Q4. What happens if you don't?

Short answer: Hash collections misbehave silently: contains returns false for an equal object, get returns null, and sets hold logical duplicates.

class Sku {
    final String code;
    Sku(String code) { this.code = code; }
    @Override public boolean equals(Object o) { return o instanceof Sku s && s.code.equals(code); }
    // hashCode() NOT overridden → identity hash, different for every instance
}
Set<Sku> set = new HashSet<>();
set.add(new Sku("A-1"));
set.contains(new Sku("A-1"));    // false (almost always): different bucket, equals never called
set.add(new Sku("A-1"));         // a second "equal" element is stored

Key points to cover:

• Fix: @Override public int hashCode() { return code.hashCode(); }, use Objects.hash(...), or just declare a record, which generates both methods.

Q5. When is a TreeSet more appropriate than a HashSet?

Short answer: When you need the elements sorted, or need range and nearest-value queries. Examples: displaying customer names alphabetically, finding the next free appointment slot after 3 pm, or getting the top-N scores. You accept O(log n) operations instead of O(1).

Key points to cover:

• TreeSet uses compareTo (or the comparator) for uniqueness, not equals. Elements that compare as 0 count as duplicates.

Learn it in depth → TreeMap & LinkedHashMap

Q6. How does HashMap work internally?

Short answer: HashMap is an array of buckets (a Node<K,V>[] table). Here's what put(key, value) does:

1. It computes key.hashCode() and spreads it: h ^ (h >>> 16), which mixes the high bits into the low ones.
2. It finds the bucket index: (n - 1) & hash. n is the table size, always a power of two.
3. If the bucket is empty, it stores a new node there. Otherwise it walks the bucket, and if a node has the same hash and equals the key, it replaces the value. If not, it appends a new node.
4. If the size exceeds capacity × loadFactor (16 × 0.75 = 12 by default), it resizes: doubles the table and redistributes the entries.

get(key) follows the same steps, and returns the matching node's value, or null.

Key points to cover:

• One null key is allowed, and it always goes to bucket 0. Multiple null values are allowed.
• There are no ordering guarantees. Iteration order can even change after a resize.

Learn it in depth → HashMap Deep Dive

Q7. What happens when two keys have the same hash code?

Short answer: That's a hash collision. Both entries go into the same bucket, and HashMap tells them apart with equals(). The keys are different, so both entries are kept. A lookup scans the bucket's entries, comparing hashes first and then equals.

Key points to cover:

• Collisions are normal. Heavy collisions (from a bad hashCode, such as one that always returns 1) degrade the map towards a linked list.

Q8. How does HashMap handle collisions, and what changed in Java 8?

Short answer: Before Java 8, each bucket was a linked list, so a badly colliding bucket made lookups O(n). Since Java 8, when a bucket holds more than 8 entries (and the table has at least 64 buckets), it's converted into a red-black tree, which makes the worst case O(log n). It turns back into a list if the bucket shrinks to 6 or fewer.

Key points to cover:

• Treeification helps most when keys are Comparable. It also defends against hash-flooding attacks, where many keys are crafted to collide.
• If the table is still small (fewer than 64 buckets), the map resizes instead of treeifying.

Q9. Can you use your own class as a HashMap key?

Short answer: Yes. Any object can be a key, but it must implement equals() and hashCode() consistently, and it should be immutable. If a key's fields change after insertion, its hash changes, and the entry becomes unreachable in its old bucket.

record OrderKey(String customerId, LocalDate date) { }        // immutable, equals/hashCode generated
Map<OrderKey, BigDecimal> dailyTotals = new HashMap<>();
dailyTotals.merge(new OrderKey("c42", LocalDate.now()), new BigDecimal("499.00"), BigDecimal::add);

Common trap: a mutable key. map.put(key, v); key.setName("x"); map.get(key) returns null, and the entry leaks.

Q10. What is ConcurrentHashMap, and how does it improve multi-threaded performance?

Short answer: It's a thread-safe Map that allows many threads to read and write at the same time without locking the whole map:

• Reads are mostly lock-free, because they rely on volatile reads.
• Writes use CAS (compare-and-swap) to put a node into an empty bin, or lock only the single bin being modified.

Key points to cover:

• Java 7 split the map into 16 segments, each with its own lock. Java 8 replaced segments with per-bin locking plus CAS, which gives finer granularity and better scalability.
• It gives you atomic compound operations (putIfAbsent, computeIfAbsent, merge), so there's no need for check-then-act races.
• It allows no null keys or values, because null would be ambiguous with "absent" under concurrency.

Learn it in depth → HashMap Concurrency Variants

Q11. What's the time complexity of HashMap/HashSet versus TreeMap/TreeSet?

Common trap: saying "the worst case is O(n) because of rehashing". Resizing costs O(n) occasionally, but it's amortised to O(1) per insert. The O(n) worst case for lookups comes from collisions.

Q12. What data structures do HashMap, TreeMap, HashSet and TreeSet use internally?

Short answer:

• HashMap: an array of buckets. Each bucket is a linked list, or a red-black tree when it has many collisions.
• TreeMap: a red-black tree, a self-balancing binary search tree ordered by key.
• HashSet: wraps a HashMap.
• TreeSet: wraps a TreeMap. In both sets, the elements are stored as keys.

Q13. What's the difference between HashMap and TreeMap?

Short answer: HashMap is unordered, with O(1) average operations, and allows one null key. TreeMap keeps keys sorted, has O(log n) operations, offers navigation (firstKey, floorKey, subMap), and doesn't allow null keys with natural ordering, because compareTo would throw an NPE.

Q14. When would you prefer a TreeMap over a HashMap?

Short answer: When you need keys in sorted order, or range queries. Examples: showing a price list sorted by product name, finding "the tax slab for this income" with floorEntry(income), or pulling all events between two timestamps with subMap(from, to). Otherwise, HashMap is faster.

Q15. Can any object be a key in a TreeMap?

Short answer: Only if the keys can be compared: either they implement Comparable, or you pass a Comparator to the TreeMap constructor. Otherwise, the first put throws a ClassCastException.

TreeMap<Employee, String> byName = new TreeMap<>(Comparator.comparing(Employee::name));

Follow-up questions this topic invites — and their answers

Q: Why is the HashMap capacity always a power of two? A: So the bucket index can be computed with a cheap bitwise AND ((n - 1) & hash) instead of the modulo operator, and so that entries split neatly into "same index" or "index + old capacity" when the table doubles.

Q: What is the load factor? A: How full the table may get before it resizes. The default of 0.75 balances memory use against collision chains. If you know you'll store n entries, create the map with enough capacity up front, using HashMap.newHashMap(n) (Java 19+).

Q: Is HashMap thread-safe? What can go wrong? A: No. Concurrent writes can lose updates, or corrupt the structure. In Java 7, concurrent resizing could even create a cycle that sent get into an infinite loop. Use ConcurrentHashMap instead.

Q: Hashtable vs HashMap? A: Hashtable is legacy: every method is synchronised, and it allows no null keys or values. HashMap is unsynchronised, and allows one null key. For thread safety, use ConcurrentHashMap, not Hashtable.