Study Library
23 min read
JVM & Data•4,915 words

Data Structures in Java & Kotlin

What this is: not a leetcode refresher. This is the data-structures knowledge a Staff+ engineer is actually tested on — choosing the right structure for an access pattern, knowing what the JDK/Kotlin collections do underneath, reasoning about memory, cache, and contention, and talking about it in a way that sounds senior. Every example is JVM-real (Java + Kotlin, Spring Boot where natural) and something you could whiteboard in an interview.

The mental model (the one idea everything derives from)#

A data structure is a materialized trade-off between an access pattern and its costs — time, space, contention, and cache behavior. At Staff+, interviews test selection and reasoning under constraints, not reimplementation.

Nobody senior is going to ask you to hand-roll a red-black tree. They will ask: "You get 50k lookups/sec by ID, occasional range scans, mostly reads, updated by 200 threads — what do you reach for and why?" The junior answer names a structure. The senior answer starts from the access pattern and derives the structure, then names the concrete JVM type, its backing representation, the complexity you're buying, and the cost you're accepting.

Everything below is organized so you can run that derivation out loud. The four questions that pick a structure:

  1. How do you access it? By key, by index, by order, by priority, by prefix, by membership, by range?
  2. What's the read/write mix and cardinality? Read-mostly vs write-heavy; 50 elements vs 50 million.
  3. What are the ordering guarantees you need? None, insertion order, sorted, priority?
  4. Who touches it concurrently, and what's your latency/memory budget? Single-threaded, read-mostly shared, high-contention? Tight heap? p99-sensitive?

If you can answer those four and then say "…so I'd use X, which is backed by Y, giving O(...) for the op I care about, at the cost of Z" — you sound like staff.

1. Complexity in practice: Big-O is necessary but not sufficient#

Big-O is the interview lingua franca, but the thing that separates a senior answer is knowing where Big-O lies to you.

Time and space, average and amortized and worst#

Always quote both time and space, and be precise about which time:

  • Amortized — ArrayList.add is amortized O(1): most adds are O(1), but occasionally the backing array doubles (copies all n elements). Averaged over many adds, O(1). A single add is O(n) worst-case. HashMap.put is the same story (resize).
  • Worst-case vs average — HashMap get/put is O(1) average, O(log n) worst-case since Java 8 (treeified bins — see §3), was O(n) before. Quicksort is O(n log n) average, O(n²) worst.
  • Space — a List<Long> of 10M elements isn't 80MB; it's ~240MB+ once you count boxing and object headers (see below). The long[] is 80MB. This difference decides real designs.

The three things Big-O hides that Staff+ engineers talk about#

1. Constant factors and small-n reality. For n < ~50–100, a linear scan over a contiguous ArrayList/array beats a HashMap — no hashing, no pointer chasing, perfect cache behavior. "It's O(n) so it's bad" is a mid-level reflex. "n is bounded at ~30 here, so a flat array scan is faster and simpler than a hash map" is a senior one.

2. Cache locality / mechanical sympathy. This is the single highest-leverage thing you can say. Modern CPUs read memory in ~64-byte cache lines and prefetch sequential addresses. A long[] or ArrayList is contiguous → sequential iteration is a stream of cache hits. A LinkedList scatters nodes across the heap → each .next is a potential cache miss (~100+ cycles). This is why LinkedList is almost always slower than ArrayList even for operations where it's theoretically better. A "O(n) array shift" of a few thousand contiguous longs often beats an "O(1) linked-list insert" because the shift is one tight memmove-like loop and the linked traversal is death by cache miss.

3. Allocation and GC pressure. Every Integer, every Node, every intermediate collection is an allocation the garbage collector must eventually trace and free. Structures that allocate per-element (LinkedList, HashMap nodes, boxed primitives) create GC work that shows up as p99 latency, not average throughput. Lazy pipelines (Kotlin Sequence, Java Stream) and primitive arrays exist largely to not allocate.

Memory layout on the JVM (know these numbers)#

  • Object header: ~12 bytes (compressed oops, the default under ~32GB heap), 16 bytes uncompressed. Every object pays this.
  • Integer/Long boxing: an Integer is ~16 bytes (12 header + 4 int + padding) plus the 4–8 byte reference to it. So List<Integer> of one int ≈ 20 bytes vs 4 bytes for an int[] slot. ~5× blowup.
  • Integer cache: Integer.valueOf(-128..127) returns cached instances — this is why Integer a = 127; a == 127 is true but Integer a = 128; a == 128 (reference compare) is false. Classic trap. Always compare boxed with .equals/== in Kotlin (which compiles to .equals for Integer), never reference == in Java.
  • Practical rule: hot numeric paths and large numeric collections use primitive arrays (int[], long[], Kotlin IntArray) or a primitive-collection library (Eclipse Collections, fastutil, HPPC) — not List<Integer>.

Interview line: "Big-O picks the algorithm class; cache locality, boxing, and allocation pick the winner within that class. For small or hot paths I'll reason about bytes and cache lines, not just asymptotics."

2. The equals/hashCode/Comparable contract — the bug factory#

Half of all "my HashMap lost my entry" and "my TreeSet ate a duplicate" bugs come from violating these contracts. This is prime Staff+ material because it's about invariants, not syntax.

The equals/hashCode contract#

  1. If a.equals(b) is true, then a.hashCode() == b.hashCode() must be true.
  2. The reverse need not hold — unequal objects may share a hashCode (a "collision"), but for performance they should spread.
  3. hashCode must be consistent — same object, same value, as long as the fields used in equals don't change.
  4. Override them together, from the same fields. Overriding one without the other is a latent bug.

Why the hash map cares: it locates an entry by hashCode (which bucket) then confirms with equals (which node in the bucket). Break rule 1 and the map looks in the wrong bucket and cannot find a key it contains.

The "mutable key" catastrophe#

If a field used in hashCode/equals changes after the object is used as a key, the entry becomes unreachable — it's in the bucket for its old hash, but every lookup computes the new hash. Keys must be effectively immutable.

java
// Java — the bug class OrderId { int value; /* ...uses value in equals/hashCode... */ } var map = new HashMap<OrderId, String>(); var k = new OrderId(1); map.put(k, "created"); k.value = 2; // mutated a field used by hashCode map.get(k); // => null. The entry is orphaned in bucket-for-1.
kotlin
// Kotlin — use a data class for value-keys; make it immutable (val) data class OrderId(val value: Int) // equals/hashCode/copy generated from val props val map = HashMap<OrderId, String>() val k = OrderId(1) map[k] = "created" // OrderId is immutable — you literally cannot mutate value; no orphan possible.

Kotlin data class auto-generates equals/hashCode/toString/copy from the properties in the primary constructor — and if you declare them val, immutability is enforced by the compiler. This is the single best reason data classes are the default for keys and DTOs. (Watch out: properties declared in the body, not the primary constructor, are not included in generated equals/hashCode.)

Comparable/Comparator must be consistent with equals — and total#

TreeMap/TreeSet (and sorted operations) decide equality by compareTo(...) == 0, not by equals. If your comparator says two distinct objects compare equal, a TreeSet treats them as duplicates and silently drops one.

java
// Java — comparator inconsistent with equals: TreeSet "swallows" people record Person(String name, int age) {} var byAge = new TreeSet<>(Comparator.comparingInt(Person::age)); byAge.add(new Person("Ann", 30)); byAge.add(new Person("Bob", 30)); // compareTo == 0 => treated as duplicate, NOT added System.out.println(byAge.size()); // 1 (!!)
kotlin
// Kotlin — make the ordering total by adding a tie-breaker consistent with identity data class Person(val name: String, val age: Int) val byAge = sortedSetOf(compareBy(Person::age).thenBy(Person::name)) byAge += Person("Ann", 30) byAge += Person("Bob", 30) // distinct by (age, name) => both kept println(byAge.size) // 2

Interview line: "Keys and sorted-set elements must be immutable and their ordering total and consistent with equals; a TreeSet uses compareTo==0 as its notion of equality, which is a classic silent-data-loss trap."

3. The JVM collections framework, by shape#

The java.util hierarchy is Collection → {List, Set, Queue/Deque} and, separately, Map (not a Collection). Know the interface you're programming to and the concrete class you're constructing — seniors specify both and never leak the concrete type further than necessary.

3.1 Lists — indexed sequences#

TypeBackingget(i)add(end)insert/remove(mid)Use it when
ArrayListresizable arrayO(1)amortized O(1)O(n) (shift)The default. 95% of lists.
LinkedListdoubly-linked nodesO(n)O(1)O(1) if you hold the nodeAlmost never — see below

ArrayList internals worth knowing: starts as an empty shared array; on first add it allocates capacity 10; grows by ~1.5× (newCap = oldCap + (oldCap >> 1)). Growth copies the whole array — so if you know the size, pre-size it (new ArrayList<>(expectedSize)) to avoid repeated resizes. get/set are true O(1) index math.

Why LinkedList is a trap: its O(1) insert requires you to already be positioned at the node (via a ListIterator); add(index, e) still walks O(n) to find the spot, then does its O(1) splice — and every node is a separate heap allocation with two pointers (~24 bytes overhead/node) scattered across memory. In practice ArrayList wins on almost everything including queue-like use. LinkedList's only defensible use is as a Deque, and even there ArrayDeque beats it.

kotlin
// Kotlin: mutableListOf() -> ArrayList under the hood. Pre-size when you know n. val ids = ArrayList<Long>(10_000) // pre-sized, avoids resizes val readOnly: List<String> = listOf("a", "b", "c") // read-only *view* (see §6)
java
// Java: pre-size, and prefer List.of for small immutable lists List<Long> ids = new ArrayList<>(10_000); List<String> readOnly = List.of("a", "b", "c"); // truly immutable, throws on mutation

3.2 Maps — the workhorse (and the most-asked internals)#

TypeBackingget/putOrderNullsUse it when
HashMaparray of bins (list→tree)O(1) avg, O(log n) worstnone1 null key, many null valsDefault keyed lookup
LinkedHashMapHashMap + doubly-linked listO(1)insertion or accesssamePredictable iteration; LRU cache
TreeMapred-black treeO(log n)sortedno null keyRange/sorted queries (NavigableMap)

HashMap internals — the single most-asked "explain what happens inside" question. Rehearse this narrative:

  • Backing is an array of bins (Node[] table), length always a power of 2 (default 16). Index = (n - 1) & hash — a fast bitmask instead of modulo, which is why capacity is a power of two.
  • The stored hash is spread: h = key.hashCode(); h ^ (h >>> 16) — XORs the high 16 bits into the low 16 so that keys whose hashes differ only in high bits don't all collide into the same low-bit bucket.
  • A bin starts as a singly-linked list of nodes. When a bin would exceed 8 nodes (TREEIFY_THRESHOLD — precisely, the check fires as the 9th node is appended to a bin already holding 8) and the table capacity is ≥ 64 (MIN_TREEIFY_CAPACITY), that bin converts to a red-black tree, making its worst case O(log n) instead of O(n). If capacity < 64, it resizes instead of treeifying. On shrink, a tree bin falls back to a list at 6 nodes (UNTREEIFY_THRESHOLD) — the 8/6 gap is hysteresis to avoid flapping.
  • Load factor 0.75 (default): when size > capacity × 0.75, the table doubles and every entry is rehashed to a new bucket. This is the amortized-O(1) cost and a source of latency spikes for big maps — pre-size with new HashMap<>(expectedEntries / 0.75f + 1) if you know the count.
  • Treeification since Java 8 is why a maliciously-crafted collision attack degrades to O(log n), not O(n) — a real security-relevant fact.
java
// Java — pre-sizing a HashMap you'll fill with ~10k entries avoids ~9 resizes Map<String, User> byId = new HashMap<>((int) (10_000 / 0.75f) + 1);

LinkedHashMap → a real LRU cache in ~5 lines (a genuinely great thing to whiteboard):

java
// Java — bounded LRU via access-order LinkedHashMap class LruCache<K, V> extends LinkedHashMap<K, V> { private final int cap; LruCache(int cap) { super(16, 0.75f, /* accessOrder = */ true); this.cap = cap; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> e) { return size() > cap; } }
kotlin
// Kotlin — same idea; object expression over LinkedHashMap fun <K, V> lruCache(cap: Int): MutableMap<K, V> = object : LinkedHashMap<K, V>(16, 0.75f, /* accessOrder = */ true) { override fun removeEldestEntry(eldest: Map.Entry<K, V>) = size > cap }

accessOrder = true moves an entry to the tail on every get, so the eldest (head) is the least-recently-used — removeEldestEntry evicts it. Say out loud in an interview: "this is O(1) get/put with O(1) eviction, single-threaded; for production concurrency I'd reach for Caffeine (Window-TinyLFU), not roll my own."

TreeMap/NavigableMap — the range-query structure. When you need "all orders between two timestamps," "the next key ≥ x," "floor/ceiling," or sorted iteration, TreeMap is the answer and HashMap is not:

kotlin
// Kotlin — NavigableMap for range + nearest-key queries (O(log n) each) val prices = java.util.TreeMap<Int, String>() prices[10] = "a"; prices[20] = "b"; prices[30] = "c" prices.ceilingKey(15) // 20 (smallest key >= 15) prices.floorKey(25) // 20 (largest key <= 25) prices.subMap(10, true, 25, true).keys // [10, 20] range scan

3.3 Sets — membership and uniqueness#

HashSet is a HashMap with a dummy value (same internals, same load factor/treeify story). LinkedHashSet adds insertion-order iteration. TreeSet is a TreeMap (sorted, NavigableSet). The single most common performance bug in real code is using a List.contains in a loop (O(n) each → O(n²) overall) where a HashSet gives O(1):

kotlin
// Kotlin — de-dup / membership: Set, not List.contains in a loop val seen = HashSet<String>() val firstOccurrences = events.filter { seen.add(it.id) } // add returns false if already present

3.4 Queues, deques, stacks, and heaps#

NeedUseNotWhy
Stack (LIFO)ArrayDequejava.util.StackStack extends Vector, synchronized, legacy-slow
Queue (FIFO)ArrayDequeLinkedListarray-backed, cache-friendly, no per-node alloc
Priority / top-kPriorityQueuesorting repeatedlybinary heap: O(log n) push/pop, O(1) peek
  • ArrayDeque is a resizable circular array — the correct default for both stacks and queues. Faster than LinkedList (no node allocation, cache-friendly) and than Stack/Vector (no synchronization). Doesn't allow null (it uses null internally as "empty slot").
  • PriorityQueue is a binary min-heap in an array. offer/poll are O(log n), peek is O(1). Iteration is not sorted — only poll order is. It's unbounded (grows), which is an OOM footgun for streaming top-k (see §7). Use a Comparator for max-heap or custom priority.
java
// Java — classic "top K largest" with a bounded MIN-heap of size k (O(n log k), O(k) space) static List<Integer> topK(int[] nums, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(k); // min-heap for (int x : nums) { heap.offer(x); if (heap.size() > k) heap.poll(); // evict the smallest -> keeps k largest } return new ArrayList<>(heap); }
kotlin
// Kotlin — same shape; PriorityQueue with a comparator. Note: kotlin stdlib has no heap, // you use java.util.PriorityQueue directly (a fair thing to say in an interview). fun topK(nums: IntArray, k: Int): List<Int> { val heap = java.util.PriorityQueue<Int>(k) // min-heap for (x in nums) { heap.offer(x) if (heap.size > k) heap.poll() } return heap.toList() }

Interview line: "Default stack and queue are both ArrayDeque, not Stack or LinkedList — array-backed, cache-friendly, unsynchronized. PriorityQueue is an array heap: great for streaming top-k if I bound it, an OOM risk if I don't."

4. Concurrent collections — the Staff+ differentiator#

Most engineers can name ArrayList and HashMap. Fewer can reason about what happens when 200 threads hit them. This section is where senior candidates pull ahead. A plain HashMap under concurrent writes is not just racy — pre-Java-8 it could spin into an infinite loop during resize; post-8 you get lost updates and corrupted state. Never share a mutable java.util collection across threads without a concurrent replacement or external synchronization.

The wrong fix vs the right fix#

Collections.synchronizedMap(new HashMap<>()) wraps every method in one mutex. It's correct but: (a) it serializes all access (one lock, no concurrency), and (b) compound actions are still racy — if (!map.containsKey(k)) map.put(k, v) is two synchronized calls with a gap between them. And you must manually synchronize iteration or risk a ConcurrentModificationException. It's a legacy answer.

The right answer is the java.util.concurrent collections:

TypeMechanismUse it for
ConcurrentHashMapCAS + per-bin synchronized; lock-free readsThe default concurrent map. Shared caches, registries, counters
CopyOnWriteArrayListevery write copies the whole array; reads are snapshotsRead-heavy, rarely-mutated small lists (listeners, config)
ConcurrentLinkedQueuelock-free (Michael–Scott)Unbounded non-blocking producer/consumer
ArrayBlockingQueue / LinkedBlockingQueuebounded, blocking put/takeBack-pressured producer/consumer, thread-pool queues
ConcurrentSkipListMap / …Setlock-free skip listConcurrent sorted map/set (the concurrent TreeMap)

ConcurrentHashMap — know these facts:

  • Since Java 8 it dropped the segment/Segment[] design; it now locks at individual bin granularity (synchronizes on the first node of a bin) and uses CAS for empty-bin inserts. Reads are generally lock-free. Far higher write concurrency than the old segmented version or synchronizedMap.
  • Does not allow null keys or values — deliberately. In a concurrent map get(k) == null is ambiguous ("absent" vs "present with null value") and you can't re-check atomically the way you can single-threaded. Memorize this; it's a frequent gotcha.
  • Its atomic methods are the whole point — use them instead of check-then-act:
java
// Java — atomic "insert if absent", atomic counter increment, atomic accumulate. // These are single lock-free/locked-per-bin operations, not racy compound ops. ConcurrentHashMap<String, List<Order>> byCustomer = new ConcurrentHashMap<>(); byCustomer.computeIfAbsent(custId, k -> new CopyOnWriteArrayList<>()).add(order); ConcurrentHashMap<String, LongAdder> counts = new ConcurrentHashMap<>(); counts.computeIfAbsent(key, k -> new LongAdder()).increment(); // hot counter: LongAdder > AtomicLong ConcurrentHashMap<String, Integer> totals = new ConcurrentHashMap<>(); totals.merge(key, amount, Integer::sum); // atomic read-modify-write
kotlin
// Kotlin — identical semantics; getOrPut is NOT atomic on a ConcurrentHashMap, // so use computeIfAbsent for atomicity. (Common Kotlin trap.) val byCustomer = ConcurrentHashMap<String, MutableList<Order>>() byCustomer.computeIfAbsent(custId) { CopyOnWriteArrayList() }.add(order) // atomic // getOrPut { } does a separate get first and may run the lambda more than once — not atomic. // Prefer computeIfAbsent for atomicity + single evaluation.

Kotlin trap worth stating: ConcurrentHashMap.getOrPut { } is not atomic. Kotlin does resolve a ConcurrentMap-specific overload that finishes with putIfAbsent (so it won't clobber a concurrent write), but it still does a separate get first and the lambda can execute more than once under contention. For real atomicity and single evaluation, use Java's computeIfAbsent. Naming this precisely in an interview is a strong signal.

CopyOnWriteArrayList — writes are O(n) (copy the array) and see-through: an iterator holds a snapshot and never throws ConcurrentModificationException, but also never sees writes made after it was created. Perfect for a listener list you write once and read constantly; terrible for a write-heavy collection.

BlockingQueue is the backbone of producer/consumer and every ThreadPoolExecutor (the pool's work queue is a BlockingQueue). Bound it (ArrayBlockingQueue(capacity) or a bounded LinkedBlockingQueue) so a fast producer applies back-pressure instead of OOMing. SynchronousQueue (zero capacity, direct hand-off) is what a cached thread pool uses.

kotlin
// Kotlin — bounded blocking queue = built-in back-pressure between producer and consumer val queue: BlockingQueue<Task> = ArrayBlockingQueue(1_000) // producer: blocks when full instead of exhausting the heap queue.put(task) // consumer: blocks when empty val next = queue.take()

Spring Boot reality check: a @Service/@Component singleton is shared across all request threads. Any mutable collection field in it must be a concurrent type (or externally synchronized). An in-memory registry, rate-limiter state, or local cache in a bean is a ConcurrentHashMap, never a HashMap:

kotlin
@Service class IdempotencyRegistry { // shared across all request threads — MUST be concurrent private val processed = ConcurrentHashMap.newKeySet<String>() // concurrent Set fun firstTime(key: String): Boolean = processed.add(key) // atomic, returns false if seen }

Interview line: "For shared mutable state I reach for java.util.concurrent, not synchronized wrappers, and I use the map's atomic methods (computeIfAbsent, merge) rather than check-then-act. ConcurrentHashMap forbids nulls by design, locks per-bin, and reads lock-free."

5. Foundational structures behind system-design answers#

At Staff+ these show up not as "implement a trie" but as the right building block for a design prompt. Know the one-liner, the JVM realization, and the design problem each one solves.

  • Heap / PriorityQueue → scheduling, Dijkstra/A*, streaming top-k, and the two-heaps running median (a max-heap of the low half + min-heap of the high half, balanced so the medians sit at the tops). Reach for it whenever you need "the current best/worst k without sorting everything."
  • Trie (prefix tree) → autocomplete, typeahead, longest-prefix routing, dictionary/spell-check. O(L) lookup in the key length L, independent of how many keys are stored. The answer to "design autocomplete."
  • Union-Find / Disjoint Set (DSU) → connectivity, grouping, "are these in the same cluster," cycle detection in undirected graphs, Kruskal's MST. With path compression + union by rank, near-O(1) amortized (inverse-Ackermann α(n)). The answer to "count connected components / detect friend circles."
  • Bloom filter → probabilistic set membership with no false negatives, tunable false positives, tiny memory. "Have I definitely not seen this?" Used for cache-admission, dedup at scale, "is this URL/key possibly present before I hit the expensive store." Guava ships BloomFilter; Cassandra/HBase use them per-SSTable.
  • LRU/LFU cache → LinkedHashMap (access-order) for a hand-rolled LRU; Caffeine (Window-TinyLFU) for production — near-optimal hit rates, O(1), concurrent. Name Caffeine and you sound like you've shipped this.
  • Ring buffer (circular array) → bounded queues, fixed-window rate limiting, the LMAX Disruptor (mechanical-sympathy poster child). O(1) push/pop, zero per-element allocation.
  • Skip list → probabilistic ordered structure; ConcurrentSkipListMap is the concurrent sorted map, and it's what Redis sorted sets use for large leaderboards (a skip list ordered by score plus a hash of member→score; small ZSETs use a compact listpack instead). The answer to "concurrent sorted access / leaderboard."
  • Graph representations → adjacency list (Map<V, List<V>>) for sparse graphs (most real graphs), adjacency matrix (boolean[][]) for dense graphs or O(1) edge existence. State which and why.
  • Inverted index (Map<Term, PostingList>) → full-text search (Lucene/Elasticsearch). The answer to "design search."
kotlin
// Kotlin — a trie for autocomplete: O(L) insert & prefix walk, then collect the subtree class Trie { private class Node { val children = HashMap<Char, Node>() var isWord = false } private val root = Node() fun insert(word: String) { var n = root for (c in word) n = n.children.getOrPut(c) { Node() } n.isWord = true } fun withPrefix(prefix: String): List<String> { var n = root for (c in prefix) n = n.children[c] ?: return emptyList() val out = ArrayList<String>() fun dfs(node: Node, path: StringBuilder) { if (node.isWord) out += path.toString() for ((c, child) in node.children) { path.append(c); dfs(child, path); path.deleteCharAt(path.length - 1) } } dfs(n, StringBuilder(prefix)) return out } }
java
// Java — Union-Find with path compression + union by rank (near-O(1) amortized) class UnionFind { private final int[] parent, rank; UnionFind(int n) { parent = new int[n]; rank = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; } int find(int x) { // path compression while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; } boolean union(int a, int b) { // union by rank; false if already connected int ra = find(a), rb = find(b); if (ra == rb) return false; if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; } parent[rb] = ra; if (rank[ra] == rank[rb]) rank[ra]++; return true; } }

Interview line: "Autocomplete → trie; leaderboard / concurrent sorted → skip list (ConcurrentSkipListMap, like Redis ZSET); 'possibly seen' at scale → Bloom filter; connectivity/clustering → union-find; production cache → Caffeine. I pick the structure from the access pattern and name the concrete library."

6. Kotlin collections — the idioms and the traps#

Kotlin's collections are the JDK collections at runtime — listOf is backed by java collections, mutableMapOf is a LinkedHashMap. What Kotlin adds is a type-system distinction and a rich functional API. Both are Staff+ talking points because both have sharp edges.

Read-only ≠ immutable (the #1 Kotlin data-structure trap)#

Kotlin splits List/MutableList, Set/MutableSet, Map/MutableMap. List is a read-only view, not an immutable collection. The object behind a List reference may still be mutable, and can be aliased by a MutableList reference that can change it:

kotlin
val mutable = mutableListOf(1, 2, 3) val readOnly: List<Int> = mutable // read-only VIEW of the same object mutable.add(4) println(readOnly) // [1, 2, 3, 4] — it changed under you!
  • listOf() returns a read-only reference, but that's a compile-time guarantee about the reference, not a runtime immutability guarantee about the object. Under the hood it can even be a java.util.Arrays$ArrayList whose size is fixed but which is not deeply immutable.
  • For a true defensive boundary, copy (.toList(), .toMap()) so callers can't mutate your internals, or use kotlinx.collections.immutable (persistentListOf, PersistentMap) which gives genuinely immutable, structurally-shared collections. Java's List.of / Map.of are the truly-immutable equivalents (throw on mutation).
kotlin
// Defensive: return a snapshot copy so callers can't mutate internal state class Basket { private val items = mutableListOf<Item>() fun items(): List<Item> = items.toList() // copy — caller can't reach the backing list }

Runtime defaults to know: mutableListOf → ArrayList; mutableSetOf → LinkedHashSet; mutableMapOf → LinkedHashMap (insertion-ordered — chosen for predictable iteration). If you want the plain hash versions, use hashSetOf / hashMapOf. If you want sorted, sortedMapOf / sortedSetOf (TreeMap/TreeSet).

Sequences vs eager collections — lazy or you allocate on every step#

Eager operators (map, filter, …) each build a new intermediate list. Chain five of them over a million elements and you allocate five million-element lists. A Sequence (asSequence()) is lazy: elements flow through the whole chain one at a time, no intermediates, and terminal operations can short-circuit (first, find, take).

kotlin
// Eager: allocates an intermediate List after map AND after filter (2 big lists) val r1 = bigList.map { it * 2 }.filter { it > 10 }.take(5) // Lazy: no intermediates, stops after finding 5 — often orders of magnitude less work val r2 = bigList.asSequence().map { it * 2 }.filter { it > 10 }.take(5).toList()

But a Sequence has per-element overhead, so for small collections eager is faster and clearer. Rule: lazy for large data, long chains, or short-circuiting; eager for small collections. (This mirrors Java Stream, which is lazy like a sequence — the map/filter are intermediate ops that don't run until a terminal op.)

Boxing still bites — use primitive arrays on hot paths#

List<Int> is List<Integer> — boxed. For numeric hot loops or large numeric data use IntArray/LongArray/DoubleArray, which are real primitive int[]/long[]/double[] with no boxing:

kotlin
val scores = IntArray(1_000_000) // primitive int[], ~4MB — NOT List<Int> (~20MB boxed) var sum = 0L for (s in scores) sum += s // no boxing, cache-friendly sequential scan

The functional API that replaces loops (know these cold)#

kotlin
val orders: List<Order> = load() val byStatus: Map<Status, List<Order>> = orders.groupBy { it.status } // bucket val byId: Map<Long, Order> = orders.associateBy { it.id } // index by key val (paid, unpaid) = orders.partition { it.isPaid } // split in two val total: Long = orders.sumOf { it.amountCents } // no boxing (sumOf) val topItems: List<Item> = orders.flatMap { it.items } // flatten val page: List<Order> = orders.asSequence().drop(20).take(10).toList() // buildList/buildMap (1.6+): construct a read-only result with a mutable builder, no leak val result: List<String> = buildList { add("header"); addAll(orders.map { it.id.toString() }) }

associateBy (index-by-key → Map) and groupBy (bucket-by-key → Map<K, List<V>>) are the two most-reached-for; knowing which is which and that both are eager is the practical bit.

Interview line: "In Kotlin List is a read-only view, not immutable — I copy or use kotlinx.immutable at trust boundaries. I use Sequence for large or short-circuiting pipelines to avoid intermediate allocation, eager operators for small ones, and primitive arrays for numeric hot paths to dodge boxing."

7. Problems & how to solve them#

The Staff+ tell is diagnosing why the obvious code is wrong and naming the precise fix. Problem → Root cause → Fix.

1. ConcurrentModificationException while iterating. Root cause: structurally modifying a collection (add/remove) through the collection while a fail-fast iterator is walking it — the iterator detects the modCount change and throws. Happens even single-threaded (for (x in list) if (bad(x)) list.remove(x)). Fix: remove through the iterator (Iterator.remove()), or removeIf { } (Java/Kotlin removeAll/removeIf), or collect-then-remove, or iterate a copy, or use a concurrent/CopyOnWrite collection whose iterators are weakly-consistent and don't throw.

2. HashMap "lost" my entry (orphaned key). Root cause: a field used in hashCode/equals was mutated after insertion — the entry sits in the old bucket, lookups hash to the new one. Fix: immutable keys. Kotlin data class with vals; Java records. Never mutate a key.

3. O(n²) blow-up from List.contains in a loop. Root cause: membership test against an ArrayList is O(n); inside a loop it's O(n²). Fix: put the lookup side in a HashSet (O(1) contains). One of the most common real-world perf wins.

4. OutOfMemoryError from an unbounded queue/heap. Root cause: PriorityQueue, LinkedBlockingQueue (default), and ConcurrentLinkedQueue are unbounded; a producer faster than the consumer grows them until OOM. Streaming "top-k" with an ever-growing heap is the same bug. Fix: bound it — ArrayBlockingQueue(cap) or a capacity-bounded LinkedBlockingQueue for back-pressure; for top-k keep a fixed-size k-heap and evict (as in §3.4).

5. Memory blow-up / GC pressure from boxing. Root cause: List<Integer>/List<Long> of millions — each element a boxed object with a header plus a reference (~5× the primitive). Fix: primitive arrays (int[], Kotlin IntArray) or a primitive-collection library (Eclipse Collections, fastutil, HPPC). Use sumOf/IntStream to avoid boxing in aggregation.

6. TreeSet/TreeMap silently drops distinct elements. Root cause: the comparator isn't total / not consistent with equals — two distinct objects compare == 0, so the sorted structure treats them as duplicates. Fix: make the ordering total with a tie-breaker (thenComparing), consistent with equals.

7. Corrupted/mysterious HashMap behavior under threads. Root cause: a plain HashMap shared across threads — lost updates, and historically an infinite loop during concurrent resize. Fix: ConcurrentHashMap and its atomic methods; never a bare HashMap for shared mutable state.

8. Check-then-act race even with a concurrent map. Root cause: if (!map.containsKey(k)) map.put(k, compute()) is two operations; two threads both pass the check. Fix: computeIfAbsent(k) { compute() } / putIfAbsent / merge — a single atomic operation. In Kotlin, avoid getOrPut on a ConcurrentHashMap (not atomic).

9. Repeated resizing on a collection you could have pre-sized. Root cause: filling a default-capacity ArrayList/HashMap with a known-large count triggers multiple grow-and-copy/rehash cycles (latency spikes for big maps). Fix: pre-size — new ArrayList<>(n), new HashMap<>((int)(n / 0.75f) + 1), HashMap(expected).

10. Kotlin read-only list mutated under a caller. Root cause: returning a List reference that aliases your internal MutableList — the caller (or a later cast) mutates your state. Fix: return .toList() copy, Collections.unmodifiableList, or a PersistentList.

Interview line: "Most collection bugs are one of: fail-fast iteration, a mutated key, a List-where-a-Set-belonged, an unbounded queue, or shared-mutable-without-concurrency. I can spot and name the fix for each on sight."

8. Interview framing — how to sound Staff+#

The content above is table stakes; how you deploy it is the signal. Concretely:

  1. Derive, don't recall. Start every structure choice from the access pattern and constraints (reads/writes, cardinality, ordering, concurrency, memory/latency budget). "What's the read/write mix and do we need ordering?" before "use a HashMap."
  2. Name three layers: the interface (Map), the concrete type (ConcurrentHashMap), and the backing representation (bin array with per-bin locking). Then the complexity and the cost.
  3. Show mechanical sympathy. Mention cache lines, boxing, allocation, and resize/GC pauses. This is the clearest mid-vs-senior separator — most candidates stop at Big-O.
  4. Talk about the tail, not the average. "Average O(1), but the resize is O(n) and shows up as a p99 spike, so I pre-size / bound it." Reasoning about worst-case and tail latency reads as production experience.
  5. Reason about concurrency explicitly, even when unprompted. State whether the structure is shared, and pick the concurrent type and atomic operation deliberately.
  6. Know when not to optimize. "n is 30 and bounded — a flat array scan is faster and simpler than a map." Right-sizing the solution is a senior move; over-engineering is not.
  7. Reach for the right production library and say so: Caffeine (caching), Guava (Bloom filter, immutable collections), Eclipse Collections/fastutil (primitive collections), kotlinx.collections.immutable (persistent). Knowing the ecosystem beats reinventing it.
  8. Flag version- and language-specific facts ("treeified bins since Java 8," "ConcurrentHashMap dropped segments in 8," "Kotlin read-only ≠ immutable") — precision signals depth.

Common wrong answers that cost points: "LinkedList is better for inserts" (usually false — cache misses); "use synchronizedMap for thread safety" (legacy, serial, compound ops still racy); "Vector/Stack" (legacy synchronized); "Kotlin listOf is immutable" (it's read-only, not immutable); reference-comparing boxed Integers in Java; iterating-and-removing on the collection; leaving PriorityQueue/LinkedBlockingQueue unbounded.

9. Cheat-sheet#

Need / access patternReach forBackingKey complexityWatch out
Indexed list, defaultArrayList / mutableListOfresizable arrayget O(1), add amortized O(1), mid-insert O(n)pre-size if n known
List with cheap ends onlyArrayDequecircular arrayoffer/poll ends O(1)no null; not thread-safe
Keyed lookup, defaultHashMap / mutableMapOf*bin array (list→RB-tree)O(1) avg, O(log n) worstpre-size; *mutableMapOf is LinkedHashMap
Keyed + insertion/access order, LRULinkedHashMapHashMap + linked listO(1)accessOrder=true + removeEldestEntry = LRU
Keyed + sorted / range / nearestTreeMap (NavigableMap)red-black treeO(log n)comparator total & consistent w/ equals; no null key
Membership / de-dupHashSet / mutableSetOfHashMapO(1)replaces O(n) List.contains
Sorted unique / rangeTreeSet (NavigableSet)TreeMapO(log n)drops elements if compareTo==0
Stack (LIFO) or Queue (FIFO)ArrayDequecircular arrayO(1) endsnot Stack, not LinkedList
Priority / streaming top-kPriorityQueuebinary heap (array)push/pop O(log n), peek O(1)unbounded → bound it; iteration not sorted
Concurrent mapConcurrentHashMapper-bin lock + CASO(1) avg, lock-free readsno null k/v; use computeIfAbsent/merge
Concurrent sorted mapConcurrentSkipListMapskip listO(log n)the concurrent TreeMap; Redis-ZSET-like
Read-heavy shared listCopyOnWriteArrayListcopy-on-write arrayread O(1), write O(n)snapshot iterator; write-heavy = bad
Back-pressured producer/consumerArrayBlockingQueuebounded array + locksput/take O(1)bound capacity for back-pressure
Prefix / autocompleteTrienode map per charO(L) in key lengthmemory per node; use library at scale
Connectivity / clusteringUnion-Find (DSU)parent/rank arrays~O(α(n)) amortizedpath compression + union by rank
"Possibly seen" at scaleBloom filterbit array + k hashesO(k)false positives, no false negatives
Production cacheCaffeineW-TinyLFUO(1)don't hand-roll concurrent LRU
Numeric hot path / big numeric dataint[]/IntArray, fastutilprimitive arrayO(1) indexavoids boxing (~5× memory)

* Kotlin runtime defaults: mutableListOf→ArrayList, mutableSetOf→LinkedHashSet, mutableMapOf→LinkedHashMap; hashMapOf/hashSetOf for plain hash; sortedMapOf/sortedSetOf for tree.

10. Self-test (say the answers out loud)#

  1. A colleague swears LinkedList is faster than ArrayList because inserts are O(1). When is that actually true, and why is it usually false in practice?
  2. Walk me through exactly what happens inside HashMap.put — hashing, bucket index, collision, treeification, resize. What are the magic numbers (16, 0.75, 8, 6, 64) and what does each do?
  3. Why does ConcurrentHashMap forbid null keys and values when HashMap allows them?
  4. You must return "top 1000 events by score" from a stream of 50M. What structure, what complexity, what's the memory footprint, and what's the bug if you get it wrong?
  5. In Kotlin, is listOf(1, 2, 3) immutable? Explain read-only vs immutable and how you'd create a genuinely immutable list.
  6. When do you choose a Sequence over eager map/filter in Kotlin, and when is eager actually better?
  7. A TreeSet<Person> sorted by age silently loses people. What's the invariant you violated, and how do you fix it?
  8. Show two ways to atomically "increment a per-key counter" in a ConcurrentHashMap and say why getOrPut/containsKey-then-put is wrong.
  9. List<Long> of 10M vs long[] of 10M — what's the memory difference and where does it come from?
  10. You're getting ConcurrentModificationException in a single-threaded loop. Give three correct fixes.
  11. Which structure for: autocomplete, a leaderboard with concurrent updates, deduplicating a billion URLs with a tight memory budget, and connected-components? One line each.
  12. A HashMap in a Spring @Service singleton "randomly" loses data under load. Diagnose and fix.
  13. Why is capacity a power of two in HashMap, and what does h ^ (h >>> 16) accomplish?
  14. When is an O(n) linear scan the right answer over an O(1) hash lookup?

Lineage / sources#

JDK behavior described is OpenJDK 8–21 java.util / java.util.concurrent (HashMap treeification, ConcurrentHashMap's post-8 per-bin design, ArrayList 1.5× growth). Kotlin behavior is stdlib 1.9/2.0 (read-only vs mutable interfaces, Sequence, data class generation, runtime collection defaults). Production libraries referenced: Caffeine (W-TinyLFU caching), Guava (BloomFilter, immutable collections), Eclipse Collections / fastutil / HPPC (primitive collections), kotlinx.collections.immutable (persistent collections). Verify exact thresholds against the JDK version you target — they're implementation details, not spec guarantees.