HashMap Internals & Collection Choice Explained
KOTLIN › JVM 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
}
Before the map menu, the list menu, because the same interviewer usually asks both.
**ArrayList versus LinkedList** has a textbook answer and a real one. The textbook answer: array-backed random access is O(1) and insertion in the middle is O(n); linked-node insertion is O(1) once you are at the position and access is O(n).
The real answer is that **ArrayList wins almost always anyway**, because a LinkedList allocates a node object per element and scatters them across the heap, so every traversal is a cache miss, while an ArrayList walks one contiguous block. The O(n) memory copy on insertion is a single System.arraycopy, which is fast enough that it usually beats the pointer chasing. Being able to say "the constant factors dominate the asymptotics here" is a better answer than reciting the table.
Use ArrayDeque rather than LinkedList when you need a queue or stack: same operations, array-backed, no per-element allocation.
**CopyOnWriteArrayList** is the one worth knowing for concurrency. Every mutation copies the entire backing array, so writes are O(n) and expensive, but reads take no lock at all and iterators never throw ConcurrentModificationException because each one holds an immutable snapshot.
// The canonical use: a listener list, read constantly, written rarely
private val listeners = CopyOnWriteArrayList<Listener>()
fun notifyAll(event: Event) {
listeners.forEach { it.onEvent(event) } // safe even if a listener unregisters itself
}
That last point is the reason it exists: a listener removing itself during iteration is exactly the case that breaks a normal list, and the snapshot makes it harmless.
Two ways to get a thread-safe map look equivalent and are not.
val a = Collections.synchronizedMap(HashMap<String, User>())
val b = ConcurrentHashMap<String, User>()
**Collections.synchronizedMap** is a wrapper that puts every method inside a synchronized block on one lock. That makes each individual call safe and serialises **everything**: one reader at a time, across the whole map.
**ConcurrentHashMap** locks per bin and never locks reads at all, so throughput under concurrent access is not comparable.
There is a correctness difference too, and it is the sharper one. Iterating a synchronized map is **not** covered by the wrapper, so you have to lock manually:
synchronized(a) { // required, and easy to forget
for ((k, v) in a) { ... }
}
// Without it: ConcurrentModificationException
A ConcurrentHashMap iterator is weakly consistent and never throws.
The same trap exists for Vector and Hashtable, the original synchronized collections, which are effectively deprecated for exactly these reasons: they serialise everything and still leave compound operations unsafe.
The rule: **synchronized wrappers make each call atomic; they do not make sequences of calls atomic.** That is the same lesson as check-then-act on any thread-safe collection, and it is why ConcurrentHashMap provides putIfAbsent, compute and merge. If you are reaching for a synchronized wrapper on Android, there is almost always a better answer: ConcurrentHashMap, or confining the plain map to one dispatcher.
Android ships its own map implementations, and knowing when they beat HashMap is a distinctly Android answer.
val sparse = SparseArray<User>() // int keys, no boxing
val sparseBool = SparseBooleanArray()
val arrayMap = ArrayMap<String, User>() // object keys, compact
A HashMap<Integer, User> allocates a HashMap.Node per entry **and** boxes every key into an Integer. SparseArray avoids both: it stores two parallel arrays, one of int keys and one of values, and finds an entry by binary search over the sorted key array.
The trade is asymptotic. Lookup is O(log n) rather than O(1), and insertion in the middle shifts the array. So the guidance is **hundreds of entries, not thousands**, where the constant-factor and allocation savings dominate and the log n is small.
ArrayMap applies the same idea to object keys: two arrays, binary search over cached hashes, no per-entry node objects. It is what the framework itself uses for small collections, and it is the backing type of a Bundle.
The honest interview answer has both halves:
- **Yes**, they reduce allocation and memory noticeably for small maps, which matters because allocation drives garbage collection and GC pauses drive jank. - **But** measure before converting. Google's own guidance has softened over the years, the difference is small for genuinely small maps, and HashMap is faster once the collection grows. Converting every map in a codebase on principle is cargo cult; converting a per-frame map in a RecyclerView adapter is a real optimisation.
Mentioning the second half unprompted is what makes the answer credible.
Iteration order is a small topic that produces a disproportionate number of bugs, because the guarantees differ per implementation and none of them is what people assume.
| Type | Iteration order | |---|---| | HashMap | **unspecified**, and it changes on resize | | LinkedHashMap | insertion order, or access order with the constructor flag | | TreeMap | sorted by key, via Comparable or a Comparator | | ConcurrentHashMap | unspecified, and weakly consistent under concurrent writes | | ArrayMap / SparseArray | sorted by key hash / by int key |
The trap is that a small HashMap often **looks** stable across runs, so code accidentally depends on the order, and it changes the day the map grows past a resize threshold or the app runs on a different JVM. A test that passes locally and fails in CI is the usual first sign.
// Bug: relies on unspecified order
val firstUser = usersById.values.first()
// Correct: state the order you actually want
val firstUser = usersById.values.minByOrNull { it.createdAt }
Kotlin's own literals are a useful default here: mapOf() and setOf() return **LinkedHashMap** and **LinkedHashSet** implementations, so they preserve insertion order. That is a genuine guarantee you can rely on, and it is why Kotlin code has fewer of these bugs than the equivalent Java.
The rule to state: **if the order matters, use a type that guarantees it.** Relying on a HashMap that happens to be ordered today is a latent bug, not a shortcut.
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.