HashMap Internals & Locks Quiz
KOTLIN › 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 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) after 75% of capacity
- 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 loop body
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 removal until iteration completes; copy the map first
- 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
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.)
Which combination can hold a ReentrantReadWriteLock at the same moment?
- Several threads holding the read lock
- One reader plus one writer
- Two writers on different keys
- Anything, as long as all holders are reentrant
Answer: Several threads holding the read lock
Readers share: any number may hold the read lock concurrently. The write lock is exclusive against both readers and writers. That's the whole value: read-heavy structures stop serialising their readers.
A thread holding the READ lock of a ReentrantReadWriteLock tries to acquire the WRITE lock. What happens?
- It deadlocks: upgrading is not supported
- It succeeds because the lock is reentrant
- It succeeds if no other readers are active
- It throws IllegalMonitorStateException immediately
Answer: It deadlocks: upgrading is not supported
The write lock must wait for all readers to release, including the requesting thread itself, which is blocked waiting: a self-deadlock. Downgrading (acquire read while holding write, then release write) IS allowed. To "upgrade", release the read lock first and re-check state after acquiring write.
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 independent reads
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 before starting a 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 is a coroutine Mutex preferred over synchronized around code that calls suspend functions?
- A coroutine can resume on a different thread, breaking thread-owned monitors; Mutex suspends and is coroutine-owned
- synchronized is deprecated in Kotlin coroutines contexts
- Mutex is always faster than monitor locks
- synchronized cannot appear inside a suspend function at all
Answer: A coroutine can resume on a different thread, breaking thread-owned monitors; Mutex suspends and is coroutine-owned
Monitors are held by threads. Suspend inside the block and the coroutine may resume elsewhere while the original thread still owns (or has corrupted) the monitor. mutex.withLock suspends waiters without blocking threads and releases on the resuming context correctly.
In double-checked locking for a lazy singleton, why must the INSTANCE field be @Volatile?
- So a half-constructed object can't be published to other threads
- So the synchronized block can be entered recursively
- To make the null check atomic with the assignment
- To stop two singletons being garbage collected together
Answer: So a half-constructed object can't be published to other threads
Without volatile, the reference write can be reordered before the constructor finishes, so another thread's fast-path null check sees a non-null but uninitialised object. Volatile's ordering forbids that publication reorder. (Kotlin's lazy { } or an object declaration handles this for you.)