Watch a HashMap come apart

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

/**
 * Warm-up: race a HashMap on purpose, and survive every way it can end.
 *
 * Eight threads each write five thousand DISJOINT keys. No key is written
 * twice, so a correct map must end with forty thousand entries. A HashMap will
 * not.
 *
 * Note how this is written. Racing a HashMap is undefined behaviour, and it
 * fails in three different ways — entries lost, an exception thrown, or a
 * thread that never terminates because a concurrent resize left a cycle in a
 * bin. The threads are daemons with a bounded join so the third one cannot
 * hang this program. That defensive shape is the lesson as much as the output.
 */
public class Starter {

    static final int THREADS = 8;
    static final int WRITES_PER_THREAD = 5_000;
    static final long PATIENCE_MS = 10_000;

    /** Returns { threads that threw, threads still running }. */
    static int[] fill(Map<Integer, Integer> map) throws Exception {
        AtomicInteger failed = new AtomicInteger();
        Thread[] threads = new Thread[THREADS];
        CountDownLatch start = new CountDownLatch(1);

        for (int i = 0; i < THREADS; i++) {
            final int id = i;
            Thread t = new Thread(() -> {
                try {
                    start.await();
                    int from = id * WRITES_PER_THREAD;
                    for (int k = from; k < from + WRITES_PER_THREAD; k++) map.put(k, k);
                } catch (Throwable x) {
                    failed.incrementAndGet();
                }
            });
            t.setDaemon(true);
            t.start();
            threads[i] = t;
        }
        start.countDown();

        long deadline = System.currentTimeMillis() + PATIENCE_MS;
        for (Thread t : threads) t.join(Math.max(1, deadline - System.currentTimeMillis()));

        int running = 0;
        for (Thread t : threads) if (t.isAlive()) running++;
        return new int[] { failed.get(), running };
    }

    static void report(String label, Map<Integer, Integer> map, int[] outcome) {
        int expected = THREADS * WRITES_PER_THREAD;
        System.out.printf("  %-18s %d of %d, lost? %s, threw: %d, still running: %d%n",
            label, map.size(), expected, map.size() < expected ? "yes" : "no",
            outcome[0], outcome[1]);
    }

    public static void main(String[] args) throws Exception {
        // TODO 1: predict the HashMap number before running. Then run it five
        // times. Write down the three different failure modes you see —
        // you will not see all of them on the first run.
        Map<Integer, Integer> plain = new HashMap<>();
        report("HashMap", plain, fill(plain));

        // TODO 2: swap in ConcurrentHashMap and run it five more times. The
        // count is exact every time.

        // TODO 3: the keys are disjoint — no two threads ever write the same
        // key. So why does the HashMap lose entries at all? Answer in terms of
        // what a resize does to the table.

        // TODO 4: explain the daemon threads and the bounded join. What would
        // this program do without them, on the run where a thread gets stuck?

        // TODO 5: for the ConcurrentHashMap version, say exactly where the
        // lock is taken on a write — and name the case where no lock is taken
        // at all.

        // TODO 6: replace the map with Collections.synchronizedMap(new
        // HashMap<>()). The count is exact too. Say what you gave up, and what
        // extra rule you must follow if you ever iterate it.
    }
}