HashMap Internals & Collection Choice Quiz
KOTLIN › JVM Concurrency
Two threads each run this 1000 times on a shared HashMap. Why can the final count be less than 2000?
- get-then-put is a check-then-act race, so increments are lost
- HashMap caps concurrent writes at one per bucket
- Integer boxing makes the values compare unequal
- The map resizes partway through and drops the newest entries by design
Answer: get-then-put is a check-then-act race, so increments are lost
Both threads can read the same old value, both add 1, and both write the same result: one increment vanishes. Atomicity of the whole read-modify-write is needed, not just safe individual calls.
Which is the correct minimal fix for that lost-update race?
- ConcurrentHashMap with merge() or compute()
- Mark the HashMap reference @Volatile
- Wrap only the read in a synchronized block
- Replace HashMap with Collections.unmodifiableMap
Answer: ConcurrentHashMap with merge() or compute()
merge/compute make the read-modify-write one atomic operation per key. @Volatile only fixes visibility of the reference, and synchronizing just the read still lets writes interleave.
A key type overrides equals() but not hashCode(). What is the observable symptom when it is used in a HashMap?
- Lookups miss entries that are equal to the stored key
- put() throws IllegalArgumentException
- All entries land in one bucket and lookups get slower
- The map silently deduplicates unequal keys
Answer: Lookups miss entries that are equal to the stored key
Two equal instances get different default (identity) hashCodes, so get() searches the wrong bucket and returns null even though an equal key is in the map. Equal objects must share a hashCode.
What does a HashMap's load factor of 0.75 mean?
- The table doubles once size exceeds 75% of capacity
- At most 75% of entries may share one bucket
- Lookups degrade to O(n) once 75% of the table capacity is used
- 25% of the table is reserved for treeified bins
Answer: The table doubles once size exceeds 75% of capacity
capacity x loadFactor is the resize threshold: a 16-bucket map resizes when the 13th entry arrives, rehashing every entry into a doubled table. Sizing an expected-large map up front avoids repeated O(n) resizes.
A worker loop is stopped via a plain Boolean flag set from another thread, and sometimes never stops. Why does @Volatile fix it?
- It guarantees the write becomes visible to the reading thread
- It makes the Boolean assignment atomic
- It moves the flag into synchronized memory
- It prevents the compiler from inlining the body of the worker loop
Answer: It guarantees the write becomes visible to the reading thread
Without a happens-before edge the worker may keep reading a cached value forever. Volatile creates that edge (write then read), so the loop observes the change. Plain Boolean writes were already atomic; visibility was the bug.
counter is declared @Volatile but counter++ from many threads still loses updates. What is the right fix?
- Use AtomicInteger.incrementAndGet()
- Also mark the incrementing function @Synchronized ... on every reader
- Declare the counter as Long instead of Int
- Add a second volatile field as a write barrier
Answer: Use AtomicInteger.incrementAndGet()
Volatile gives visibility, not atomicity: ++ is read, add, write, and two threads can interleave. AtomicInteger does the whole thing as one CAS loop. (A single lock guarding all access also works but is heavier.)
On a SINGLE thread, you remove entries from a HashMap inside a for-in loop and it throws ConcurrentModificationException. Why, and what is the fix?
- The iterator is fail-fast against any structural change but its own; use iterator.remove() or removeIf()
- HashMap forbids any removal at all until iteration completes, so copy the map first and then iterate over that copy
- The hash order changed mid-loop; switch to LinkedHashMap
- A background GC compacted the table during the loop
Answer: The iterator is fail-fast against any structural change but its own; use iterator.remove() or removeIf()
Fail-fast iterators track a modCount; any structural modification not made through the iterator invalidates it, threads or not. Mutate through the iterator, use removeIf, or collect keys first and remove after the loop.
What is the classic minimal LRU cache built directly on a JDK map?
- LinkedHashMap with accessOrder=true, overriding removeEldestEntry()
- HashMap plus a timestamp field scanned on every put
- TreeMap keyed by last-access time
- WeakHashMap, since stale entries are collected automatically over time
Answer: LinkedHashMap with accessOrder=true, overriding removeEldestEntry()
accessOrder=true makes iteration order follow access recency, and removeEldestEntry() is consulted on each insert: return true when size exceeds capacity and the least-recently-used entry is evicted. (Single-threaded; wrap or replace it when shared.)
What pair of guarantees does a synchronized block on a shared monitor give?
- Mutual exclusion plus a happens-before edge between successive holders
- Mutual exclusion only; visibility still needs volatile fields
- Visibility only; exclusion needs an additional lock
- Atomicity for the block, plus reordering of the independent reads inside it
Answer: Mutual exclusion plus a happens-before edge between successive holders
Unlock followed by lock of the same monitor is a happens-before edge, so the next holder sees everything the previous holder wrote (any fields, not just those touched in the block). That's why consistent locking on one monitor needs no volatile.
Which of these establishes a happens-before edge?
- Thread.join(): the joined thread's writes are visible after join returns
- Thread.sleep() on the writing thread
- Assigning a plain, non-volatile field just before starting the worker loop
- Calling Thread.yield() between the write and the read
Answer: Thread.join(): the joined thread's writes are visible after join returns
start() and join() are the thread-lifecycle edges: writes before start() are visible inside the thread, and all its writes are visible to whoever joins it. sleep/yield are scheduling hints with no memory semantics.
Why does ArrayList usually outperform LinkedList even for mid-list insertion?
- Contiguous memory avoids the cache miss per node that pointer chasing incurs
- Its insertion is O(1), whereas LinkedList insertion is O(n) in the list length
- It synchronises internally, avoiding lock contention
- It stores elements off-heap, reducing garbage collection
Answer: Contiguous memory avoids the cache miss per node that pointer chasing incurs
The asymptotics favour LinkedList for insertion, but a node per element scattered across the heap means a cache miss per traversal step, while the array copy is one fast bulk operation.
What makes CopyOnWriteArrayList suitable for a listener list?
- Reads take no lock and iterators hold a snapshot, so a listener can unregister itself mid-notification
- Writes are cheap, so registration is fast
- It preserves the exact registration order, which a plain ArrayList does not do at all reliably
- It deduplicates listeners automatically
Answer: Reads take no lock and iterators hold a snapshot, so a listener can unregister itself mid-notification
The full-array copy on every write is expensive, which is fine when writes are rare. The snapshot iterator is what turns self-removal during iteration from a crash into a non-event.
What remains unsafe when using Collections.synchronizedMap?
- Iteration and any compound operation, since the wrapper only makes individual calls atomic
- Nothing at all: every single operation, including iteration, is covered by the wrapper lock
- Reads, which bypass the wrapper lock entirely
- Writes from more than two threads at once
Answer: Iteration and any compound operation, since the wrapper only makes individual calls atomic
A loop is a sequence of calls, so you must synchronize on the map yourself or get a ConcurrentModificationException. Check-then-act has the same hole, which is why ConcurrentHashMap offers compound operations.
When does SparseArray beat HashMap<Integer, V>?
- Small maps with int keys, since it avoids boxing and per-entry node allocation
- Large maps, since binary search over the sorted keys scales better than hashing does
- Concurrent access, since it is internally synchronised
- Whenever insertion order must be preserved
Answer: Small maps with int keys, since it avoids boxing and per-entry node allocation
Parallel int and value arrays remove two allocations per entry, at the cost of O(log n) lookup. That trade pays off in the hundreds of entries and reverses as the map grows.
What iteration order does Kotlin mapOf() guarantee?
- Insertion order, since it returns a LinkedHashMap
- No order at all, since mapOf returns a plain HashMap under the hood
- Sorted key order
- Reverse insertion order
Answer: Insertion order, since it returns a LinkedHashMap
Kotlin map and set literals are LinkedHashMap and LinkedHashSet backed, so insertion order is a real guarantee, which is why Kotlin code hits ordering bugs less often than the Java equivalent.
A test relying on HashMap iteration order passes locally and fails in CI. Why?
- HashMap order is unspecified and changes with capacity, hashing, and JVM
- HashMap iterates in reverse on some platforms by design
- CI runs the test with a different Comparator configured
- The map was mutated concurrently only in the continuous integration environment
Answer: HashMap order is unspecified and changes with capacity, hashing, and JVM
A small map often looks stable, so code accidentally depends on it, and the order changes the day the map resizes or runs on a different JVM. Use LinkedHashMap when order matters.