Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 77 ยท Java Interview Questions

Java: Collections and HashMap Internals

Prepare Java interview answers on ArrayList vs LinkedList, how HashMap buckets and resizes, ConcurrentHashMap and fail-fast iterators, with a runnable model.

"How does a HashMap work?" is probably the most repeated Java interview question. Behind it sit related ones: ArrayList versus LinkedList, why iterators throw ConcurrentModificationException, and how ConcurrentHashMap stays thread-safe. This lesson gives answers you can say in a minute and then back up with details.

Real Java is read-only here. The runnable examples are JavaScript stand-ins that model the algorithms, and each one says what it simplifies. For full tutorials see How HashMap Works, ArrayList, LinkedList, Concurrent Collections and Choosing a Collection.

The collections family

List Ordered, duplicates allowed.
Set No duplicates.
Map Key to value pairs.
Queue / Deque Process in order.

Map is separate from Collection, but it is part of the framework.

1 / 2

ArrayList versus LinkedList

Q: When would you pick each? ArrayList is backed by an array: get(i) is O(1), appending is amortized O(1), inserting or removing in the middle is O(n) because elements shift, and the memory is compact and cache-friendly. LinkedList is a doubly linked list: adding or removing at the ends is O(1), but get(i) is O(n) because you walk the nodes, and each element costs an extra node object.

In practice ArrayList wins almost always, even for many inserts, because of cache locality. LinkedList is a reasonable choice only when you mainly add and remove at both ends (and then ArrayDeque is usually better still). A good interview line: "I default to ArrayList, and I would measure before choosing anything else."

Java
List<String> names = new ArrayList<>(1000);  // pre-size when you know the size
names.add("Ada");
Deque<Integer> queue = new ArrayDeque<>();   // preferred queue/stack
queue.addLast(1);
queue.pollFirst();

How a HashMap works

Q: Explain how HashMap stores and finds a value. Say it in four steps:

  1. Compute hashCode() of the key and spread its bits (Java mixes the high bits into the low bits).
  2. Take the hash modulo the table size (a power of two, so a bit mask) to pick a bucket.
  3. In that bucket, compare keys with equals and update, or append a new entry.
  4. When the number of entries exceeds capacity ร— load factor (default 16 and 0.75), the table doubles and entries are redistributed (rehashing).

Since Java 8, a bucket with many collisions (8 or more entries, in a table of at least 64) converts its linked list into a balanced tree, so the worst case drops from O(n) to O(log n) when keys are comparable. Average get and put are O(1).

JS Stand-in: a tiny HashMap with buckets and resizing

Press Run (or Ctrl + Enter) to see the console output here.

No output.

What is real and what is simplified: the structure (array of buckets, chains, doubling at the load factor) matches Java. The hash function and details such as treeification and null-key handling do not.

Follow-up questions to expect:

  • Why is the capacity a power of two? The bucket index becomes hash & (n - 1), which is faster than a modulo.
  • What if you mutate a key after inserting it? Its hash changes and the entry becomes unreachable. Use immutable keys.
  • Can HashMap hold null? One null key and any number of null values. ConcurrentHashMap and Hashtable allow neither.
  • Ordering? None guaranteed. LinkedHashMap keeps insertion order and TreeMap keeps sorted order.

Fail-fast iterators

Q: Why do you get ConcurrentModificationException? Most non-concurrent collections keep a modCount that increments on every structural change (add, remove). An iterator remembers the value it saw when it was created, and on every next() it checks that nothing changed. If the collection was modified by anything except the iterator itself, it throws. The check is best-effort, not a guarantee, so never write code that relies on catching it.

Java
List<Integer> numbers = new ArrayList<>(List.of(1, 2, 3, 4));
for (Integer n : numbers) {
    if (n == 2) numbers.remove(n);      // ConcurrentModificationException
}
numbers.removeIf(n -> n % 2 == 0);      // correct: let the collection do it
JS Stand-in: modCount and a fail-fast iterator

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Real alternatives: Iterator.remove(), removeIf, or a copy-on-write structure. CopyOnWriteArrayList iterators work on a snapshot and never throw, at the price of copying on each write.

ConcurrentHashMap

Q: How is ConcurrentHashMap different from Collections.synchronizedMap or Hashtable? Those wrap every method in one lock, so threads queue up. ConcurrentHashMap allows concurrent reads without locking and locks only the part being written (in modern Java, the head of a single bucket, plus compare-and-swap for empty buckets). Its iterators are weakly consistent: they never throw ConcurrentModificationException and may or may not show updates made after they were created.

It also has atomic compound operations. Check-then-act on a normal map is a race, even if each call is thread-safe:

Java
// Not atomic even on a ConcurrentHashMap: another thread can slip in between
if (!map.containsKey(key)) {
    map.put(key, compute(key));
}

// Atomic:
map.computeIfAbsent(key, k -> compute(k));
map.merge(word, 1, Integer::sum);       // thread-safe counter
JS Stand-in: why check-then-act loses an update

Press Run (or Ctrl + Enter) to see the console output here.

No output.

This is a model of the race, not of ConcurrentHashMap's internal locking.

Quick comparison table

Collection Ordered? Duplicates Thread-safe Typical cost
ArrayList insertion yes no get O(1), middle insert O(n)
LinkedList insertion yes no ends O(1), get O(n)
HashMap / HashSet none unique keys no O(1) average
LinkedHashMap insertion unique keys no O(1)
TreeMap / TreeSet sorted unique keys no O(log n)
ConcurrentHashMap none unique keys yes O(1) average

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. When does a HashMap resize?

    With the defaults (16 and 0.75), the table doubles after the 13th entry and entries are redistributed.
  2. 2. Why does removing from a list inside a for-each loop usually throw ConcurrentModificationException?

    Fail-fast iterators compare an expected modification count with the collection's current one on each next().
  3. 3. Which is a thread-safe way to count words in a shared ConcurrentHashMap<String, Integer>?

    merge performs the read-modify-write atomically. The others are check-then-act sequences that can lose updates.
  4. 4. For a list you mostly read by index, which is the better default?

    ArrayList is array-backed, giving constant-time indexed access and good cache locality.

Summary

  • ArrayList is the default list; LinkedList rarely wins, and ArrayDeque is the usual queue.
  • A HashMap hashes the key, picks a bucket, uses equals within it, and doubles its table past capacity ร— load factor; long buckets become trees.
  • Keys must be immutable and have a consistent equals and hashCode.
  • Fail-fast iterators use modCount and are best-effort; use removeIf or Iterator.remove.
  • ConcurrentHashMap locks finely, has weakly consistent iterators and atomic merge and computeIfAbsent.

Next: Java: JVM, Memory Model and Garbage Collection.