HashMap Internals & Locks Flashcards
KOTLIN › Concurrency
- How does a HashMap find the entry for a key?
- It spreads the key's hashCode() and masks it into a bucket index ((n - 1) & hash). Within that bucket it walks the chain (or tree) comparing with equals(). So hashCode locates the bucket; equals picks the entry.
- What does HashMap's load factor control, and what happens on resize?
- At size > capacity x loadFactor (default 0.75) the table doubles and every entry is redistributed into new buckets. Resize is O(n) and is exactly where concurrent modification historically corrupted the map.
- What breaks if two equal objects have different hashCodes, or a key mutates after insertion?
- Lookup goes to the wrong bucket and misses the entry: the value is effectively lost while still occupying memory. That's why the contract requires equal objects to share a hashCode, and why map keys should be immutable.
- Name the three distinct failure modes of sharing a plain HashMap across threads.
- 1) Lost updates: two writers race and one write vanishes. 2) Visibility: a reader thread never sees another thread's write (no happens-before). 3) Structural corruption during concurrent resize (historically even infinite loops pre-Java 8).
- What does volatile (Kotlin @Volatile) guarantee, and what does it NOT guarantee?
- Guarantees: writes are visible to subsequent reads, with ordering (a happens-before edge from write to read). Not guaranteed: atomicity. count++ (read-modify-write) and if (x == null) x = ... (check-then-act) still race.
- Give three operations that create a happens-before edge.
- Unlocking a monitor then locking the same monitor; a volatile write then a volatile read of the same field; Thread.start() (everything before start is visible in the thread) and Thread.join() (everything in the thread is visible after join).
- Which map for which job: HashMap, LinkedHashMap, TreeMap, ConcurrentHashMap?
- HashMap: the O(1) unordered default for single-threaded use. LinkedHashMap: predictable iteration order, and with accessOrder=true plus removeEldestEntry() a ready-made LRU cache. TreeMap: keys kept sorted, O(log n), range queries. ConcurrentHashMap: the moment the map is shared across threads.
- When does ReentrantReadWriteLock beat plain synchronized, and what are its rules?
- Read-heavy, write-rare data: many threads may hold the read lock concurrently, one thread the write lock exclusively. It is reentrant; downgrading (write -> read) is allowed, upgrading (read -> write) deadlocks. Under write-heavy load it can be slower than a plain lock.
- Why use a coroutine Mutex instead of synchronized in suspend code?
- synchronized is thread-based and blocks; a coroutine may suspend inside the critical section and resume on a different thread, so a monitor can't protect across a suspension point. mutex.withLock { } suspends instead of blocking and is released correctly regardless of resume thread.