HashMap Internals & Locks Explained
KOTLIN › Concurrency
The classic live-coding trap in Android interviews is "build a thread-safe cache." It sounds like a syntax problem, add a lock somewhere, but interviewers use it to probe something deeper: do you actually understand how a HashMap stores data, and what specifically breaks when two threads touch it at once.
Candidates lose more points here on the WHY than the WHAT. Knowing that ConcurrentHashMap exists is not enough; you need to explain memory visibility, happens-before, and the difference between a race that corrupts data and one that merely loses an update. This lesson builds that understanding from the ground up: first how a plain HashMap actually works, then exactly how sharing one across threads goes wrong, then the tools, volatile, atomics, locks, and the right map for the job, that fix each failure specifically.
A plain HashMap's lookup is a two-step process, and everything else in this lesson follows from it. A key's hashCode() gets spread and masked into a bucket index, that's where the entry lives. Within that bucket, equals() walks the chain, or in Java 8+, a small red-black tree once a bucket gets long, to find the exact match. So hashCode locates the bucket, equals picks the entry inside it.
val m = HashMap<String, Int>()
m["ada"] = 1 // hashCode("ada") -> bucket index, entry appended there
The table also tracks a load factor, default 0.75. Once size exceeds capacity times load factor, the table doubles and every entry gets rehashed into the new table, an O(n) pass. A 16-bucket map resizes the moment its 13th entry arrives. And when a single bucket's chain grows past 8 nodes in a table of at least 64 buckets, Java 8+ treeifies that one bucket into a small tree, turning a worst-case O(n) bucket scan into O(log n); below that size threshold it just resizes the whole table instead.
This is why the hashCode-or-equals contract matters so much: equal objects must produce equal hashCodes. Break that, and lookups silently fail.
class Point(val x: Int, val y: Int) // equals overridden, hashCode left as identity
val m = HashMap<Point, String>()
m[Point(1, 2)] = "a"
m[Point(1, 2)] // null, different identity hashCode -> wrong bucket
A Kotlin data class generates both together, which is exactly why it's the safe default for map keys. There's a second, sneakier version of this bug: mutating a key after insertion. The entry stays physically in the bucket its old hashCode pointed to, so a lookup with the new hashCode goes to the wrong bucket and the entry is effectively lost while still consuming memory. Map keys should be immutable.
There's a HashMap gotcha that trips people up even on a single thread, and it shows up constantly in code review: removing entries while iterating. HashMap's iterators are fail-fast: they track an internal modification count, and any structural change, an add or a remove, made any way other than through the iterator itself invalidates it immediately, throwing ConcurrentModificationException on the next step. This has nothing to do with threads; a single thread mutating the map mid-loop triggers it just as reliably as two threads would.
for ((key, value) in map) {
if (value.isExpired()) map.remove(key) // throws ConcurrentModificationException
}
The fix is to mutate through the iterator, or to use a method built for exactly this: removeIf on the entry set, or iterator.remove() inside a manual while loop.
map.entries.removeIf { it.value.isExpired() } // safe
Now share that same HashMap across threads with no protection, and three distinct things go wrong, worth naming separately in an interview:
1. Lost updates: two threads do get-then-put on the same key, both read the old value, both write the same new value, one increment vanishes 2. Stale reads, a visibility problem: a reader thread never sees another thread's write at all, because there's no happens-before edge forcing the write to publish 3. Structural corruption during a concurrent resize: two threads triggering a resize together can corrupt the bucket chains, pre-Java 8 this could even spin a bucket into an infinite loop
These are different bugs with different fixes, which is exactly why interviewers ask you to name all three instead of just saying "it's not thread-safe."
The visibility half of that story is volatile territory, and it's worth being precise here because it's a common trip-up: volatile, Kotlin's @Volatile, guarantees visibility and ordering, and nothing else. A volatile write happens-before a later volatile read of that field, so a stale-flag bug is a genuine volatile fix: a worker loop reading a plain, non-volatile Boolean set from another thread can spin forever because it keeps reading a cached value; marking that Boolean @Volatile gives the write a guaranteed path to the reader.
But volatile gives you zero atomicity. count++ is read-add-write; two threads can each see the visible-but-not-yet-updated value and both write the same result. Check-then-act has the identical shape.
@Volatile var cache: String? = null
// two threads race:
fun load() {
if (cache == null) cache = expensiveCompute()
}
Both threads can see cache as null before either assigns, so expensiveCompute() can run twice. Volatile alone cannot fix either case; the sequence itself needs to become one indivisible step.
Once you've spotted a lost-update race, check-then-act or read-modify-write, the fix is to make the whole sequence indivisible, not to sprinkle in more volatile. A few tools do this directly, and each covers a distinct shape of problem.
For a single mutable counter, swap the field for AtomicInteger and call incrementAndGet(); it performs the read-add-write as one CAS-based operation instead of three separate steps a second thread could interleave with.
val counter = AtomicInteger(0)
fun bump() = counter.incrementAndGet() // atomic, no lost updates
For a shared map, ConcurrentHashMap gives you the same idea per key. merge() and compute() run the read-modify-write for one key atomically, so two threads bumping the same key never race:
val map = ConcurrentHashMap<String, Int>()
fun bump() = map.merge("count", 1, Int::plus) // atomic per key
A related shape is "compute this value only once, even if several threads ask for the same missing key at the same moment." computeIfAbsent() runs the mapping function atomically per key, so concurrent callers never race to compute the same value twice:
val cache = ConcurrentHashMap<String, Bitmap>()
fun getOrLoad(key: String) = cache.computeIfAbsent(key) { loadExpensive(it) }
Marking a reference @Volatile fixes none of these; it only makes the reference itself visible, the race lives in the multi-step operation on what it points to.
Every fix so far has relied on the same underlying idea: a happens-before edge, a guarantee that one thread's write is visible to another thread's read, in a specific order. It's worth naming the edges directly, because interviewers ask for them by name:
- Unlocking a monitor, then another thread locking that same monitor: the next holder sees everything the previous holder wrote, not just fields touched inside the synchronized block. - A volatile write, then a volatile read of that same field. - Thread.start(): everything written before start() is visible inside the new thread. - Thread.join(): everything the joined thread wrote is visible to whoever joins it, once join() returns.
That first edge is why consistent locking on one monitor needs no volatile fields at all, the lock itself does the publishing. It also explains a classic bug: lazy singleton initialization without @Volatile on the instance field. A thread can see a non-null but not-yet-fully-constructed object, because without that edge the compiler or CPU is free to reorder the reference write before the constructor finishes running.
@Volatile private var INSTANCE: Repo? = null
fun get(): Repo = INSTANCE ?: synchronized(this) {
INSTANCE ?: Repo().also { INSTANCE = it }
}
Volatile here isn't about visibility of a simple flag, it's stopping that reordering so no thread ever observes a half-built object.
Once you've named the failure mode, picking the map is a menu, not a mystery:
- HashMap: fine as the default, single-threaded, unordered, O(1) - LinkedHashMap: predictable iteration order; pass accessOrder = true and override removeEldestEntry() for a ready-made LRU cache - TreeMap: keys stay sorted, O(log n), supports range queries - ConcurrentHashMap: the moment the map is actually shared across threads, its own deep topic, but the short version is it bakes in the happens-before edges, CAS plus per-bin locking, so you don't hand-roll them
val lru = object : LinkedHashMap<String, Bitmap>(16, 0.75f, true) {
override fun removeEldestEntry(e: MutableMap.MutableEntry<String, Bitmap>) = size > 50
}
For the locking half of the toolkit: synchronized, or Kotlin's coroutine Mutex, is the default for simple mutual exclusion. ReentrantReadWriteLock beats it for read-heavy, write-rare data, since it lets any number of readers hold the read lock concurrently, while the write lock is exclusive against everyone.
val lock = ReentrantReadWriteLock()
fun read() = lock.readLock().withLock { cache[key] }
fun write(v: String) = lock.writeLock().withLock { cache[key] = v }
One trap: it's reentrant and supports downgrading, acquire read while already holding write, then release write, but upgrading a held read lock straight to a write lock deadlocks, the write lock waits for all readers including yourself. And inside suspend functions, prefer a coroutine Mutex over synchronized: a coroutine can suspend and resume on a different thread, and a thread-owned monitor can't protect across that gap the way a coroutine-aware Mutex, with mutex.withLock { }, can.
Put it all together and the whole topic collapses into one interview answer: a plain HashMap is fast because it trades safety for it, no synchronization anywhere in its lookup or resize path. Sharing one across threads without protection risks lost updates, stale reads, and structural corruption during a resize, three distinct failures with three distinct causes. volatile buys you visibility and ordering, never atomicity, so read-modify-write and check-then-act sequences still need an atomic operation or a lock. Every one of those fixes ultimately rests on a happens-before edge, whether that's a monitor, a volatile field, or a thread's start and join.
When you're asked to build that thread-safe cache live, say the plan out loud before you type: name which map you'd reach for, ConcurrentHashMap the moment threads share it, LinkedHashMap or TreeMap when they don't, then name the specific race you're protecting against and the smallest tool that closes it, an atomic method, a lock, or a coroutine Mutex if you're inside suspend code. That's the difference between reciting "use ConcurrentHashMap" and actually demonstrating you understand why.