Từ câu hỏi internals tới quyết định production

Setup và quan sát có kiểm soát

Chọn JDK 21, ghi đầy đủ java -version, vendor và build. Attach source JDK tương ứng trong IDE; đặt breakpoint ở putVal, resize và treeifyBin. Đoạn bên dưới không dùng reflection hoặc mở module: bucket array và loại node được xem trong debugger, không phải public API.

import java.util.*;

public class HashMapFlowLab {
    record Key(int id, int rawHash) {
        @Override public int hashCode() { return rawHash; }
    }
    record StableKey(String id) {}

    static final class MutableKey {
        int id;
        MutableKey(int id) { this.id = id; }
        @Override public int hashCode() { return id; }
        @Override public boolean equals(Object other) {
            return other instanceof MutableKey k && id == k.id;
        }
    }

    static int spread(int raw) { return raw ^ (raw >>> 16); }

    public static void main(String[] args) {
        // Case 1: unique hashes; observe the insertion at size 13.
        var unique = new HashMap<Key, Integer>(16);
        for (int i = 0; i < 13; i++) unique.put(new Key(i, i), i);
        for (int i = 0; i < 13; i++)
            assert unique.get(new Key(i, i)) == i;

        // Case 2: raw hashes 1 and 17 have equal low four bits.
        var split = new HashMap<Key, Integer>(16);
        split.put(new Key(1, 1), 1);
        split.put(new Key(17, 17), 17);
        for (int i = 2; i <= 12; i++) split.put(new Key(i, i), i);
        assert split.size() == 13;
        for (var entry : split.entrySet())
            assert Objects.equals(split.get(entry.getKey()), entry.getValue());

        for (int raw : new int[]{1, 17, 33, 65_536, -1}) {
            int h = spread(raw);
            int oldIndex = h & (16 - 1);
            int newIndex = h & (32 - 1);
            assert newIndex == oldIndex + ((h & 16) == 0 ? 0 : 16);
            System.out.printf("raw=%d spread=%d old=%d new=%d%n",
                raw, h, oldIndex, newIndex);
        }

        // Case 3: distinct keys, identical hash; inspect treeifyBin.
        var collision = new HashMap<Key, Integer>(64);
        for (int i = 0; i < 9; i++) collision.put(new Key(i, 0), i);
        assert collision.size() == 9;
        for (int i = 0; i < 9; i++)
            assert collision.get(new Key(i, 0)) == i;

        // Controlled OpenJDK experiment, NOT a portable mutable-key contract.
        var broken = new HashMap<MutableKey, String>(16);
        var key = new MutableKey(1);
        broken.put(key, "value");
        key.id = 2;
        assert broken.get(key) == null;
        assert broken.remove(key) == null;
        assert broken.size() == 1; // entry still exists
        key.id = 1;
        assert "value".equals(broken.get(key));

        var fixed = new HashMap<StableKey, String>();
        fixed.put(new StableKey("1"), "value");
        assert "value".equals(fixed.get(new StableKey("1")));
        System.out.println("PASS HashMapFlowLab");
    }
}

java -version
javac --release 21 HashMapFlowLab.java
java -ea HashMapFlowLab

Expected observations. Với hai map khởi tạo capacity 16 và load factor mặc định trong ví dụ, kiểm tra lần thêm mapping thứ 13 đi qua resize. Với map capacity 64 và constant hash, theo dõi bin trước/sau lần put thứ 9. Bổ sung counters cho hashCode/equals theo dataset; ghi số operation đã thực hiện, không biến số đếm quan sát trên một build thành guarantee chung.

Acceptance gate. Cả 13 mapping ở nhóm unique và nhóm split đều lookup được; 9 key constant-hash không bị gộp. Bảng index khớp quy tắc split. Case mutable key vẫn có size 1 nhưng get/remove với hash đã đổi thất bại trong thí nghiệm này; bản StableKey lookup bằng một key equal thành công. Đây là thí nghiệm ngoài contract mutable-key, không phải lời hứa mọi mutation đều cho cùng kết quả. [3]

Artifact cần nộp. Source test; JDK/build; bảng key/raw hash/spread hash/old index/new index; ảnh debugger tại ba breakpoint; số operation/so sánh và assertion log chứng minh không mất mapping ở các case key ổn định.

Thiết kế benchmark trước khi chạy

Workload definition. Ví dụ JMH sau dùng cùng size, cùng chuỗi chỉ số random và state riêng mỗi thread. Return value được JMH consume. Hai benchmark ghi có bước undo để giữ size ổn định; phải báo cáo cả cặp thao tác, không đặt tên kết quả là latency của một lần add. [21]

package org.example;

import java.util.*;
import java.util.concurrent.TimeUnit;
import org.openjdk.jmh.annotations.*;

@State(Scope.Thread)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Warmup(iterations = 3)
@Measurement(iterations = 5)
@Fork(2)
public class CollectionsBench {
    @Param({"array", "linked"}) public String kind;
    @Param({"1000", "10000"}) public int n;
    private List<Integer> list;
    private ListIterator<Integer> middle;
    private final int[] indices = new int[1024];
    private int cursor;
    private final Integer marker = Integer.MIN_VALUE;

    @Setup(Level.Trial)
    public void setup() {
        // ArrayList gets one spare slot: this is NOT a resize benchmark.
        list = kind.equals("array")
            ? new ArrayList<>(n + 1) : new LinkedList<>();
        for (int i = 0; i < n; i++) list.add(i);
        middle = list.listIterator(n / 2); // locating cost excluded
        var random = new Random(7);
        for (int i = 0; i < indices.length; i++)
            indices[i] = random.nextInt(n);
    }

    @Benchmark public long traversal() {
        long total = 0;
        for (int value : list) total += value;
        return total; // JMH consumes the returned result
    }

    @Benchmark public int randomGet() {
        return list.get(indices[cursor++ & (indices.length - 1)]);
    }

    @Benchmark public Integer appendAndUndo() {
        list.add(marker);
        return list.remove(n); // restore size; measures an operation pair
    }

    @Benchmark public Integer iteratorInsertAndUndo() {
        middle.add(marker);
        Integer value = middle.previous();
        middle.remove(); // restores the original cursor position and size
        return value;    // measures add + previous + remove, not add alone
    }
}

Chạy bằng project JMH riêng. Cần JDK và Maven/JMH trong môi trường lab; đây không phải dependency của trang HTML. Tạo project, lưu class ở src/main/java/org/example/CollectionsBench.java, rồi build và chạy. Ghi lại version JMH thực tế được resolve và cấu hình build; không mặc định một version là mới nhất. [21]

mvn archetype:generate -DinteractiveMode=false -DarchetypeGroupId=org.openjdk.jmh -DarchetypeArtifactId=jmh-java-benchmark-archetype -DgroupId=org.example -DartifactId=collections-bench -Dversion=1.0
cd collections-bench
# Save CollectionsBench.java in src/main/java/org/example/
mvn clean verify
java -jar target/benchmarks.jar "org.example.CollectionsBench.*" -wi 3 -i 5 -f 2 -prof gc -rf json -rff results.json

Failure injection. Chạy thêm indexed traversal get(i) trên LinkedList để thấy việc “duyệt” có thể vô tình thành nhiều lần tìm node. So với iterator traversal; không gộp hai workload dưới cùng nhãn. Thử size vượt vùng cache thuận lợi, nhưng không dự đoán trước bên nào thắng ở mọi size.

Acceptance gate. Báo cáo đủ bốn nhóm với size, operation unit, warmup, measurement, forks, JDK, JMH, CPU và GC settings. Đưa score/error hoặc phân bố qua các fork, allocation/op, GC metrics và profiler evidence khi khả dụng. -prof gc cho biết allocation, không tự chứng minh cache misses; không so số microsecond của cả lượt traversal với một get như thể cùng đơn vị công việc. [23]

Artifact cần nộp. Source benchmark và các biến thể; build/version manifest; command line; raw results; GC/profiler report; nhận xét về locality/allocation và giới hạn áp dụng. Không chốt “ArrayList/LinkedList luôn nhanh hơn” từ một số milliseconds.

Heap invariant trước, hiệu năng sau

Setup. Cài min-heap trên int[] theo parent (i - 1) / 2, children 2i + 1/2i + 2. Ví dụ dùng capacity cố định để làm rõ full/empty policy; nó không nhằm thay thế toàn bộ API của PriorityQueue. Đối chiếu mỗi poll với PriorityQueue, không dùng thứ tự iterator của PriorityQueue làm oracle. [10]

import java.util.*;

public class MinHeapLab {
    // Educational bounded heap. Capacity is an explicit contract.
    static final class MinHeap {
        private final int[] data;
        private int size;

        MinHeap(int capacity) {
            if (capacity < 1) throw new IllegalArgumentException("capacity > 0");
            data = new int[capacity];
        }

        void offer(int value) {
            if (size == data.length) throw new IllegalStateException("full");
            int child = size++;
            while (child > 0) {
                int parent = (child - 1) / 2;
                if (data[parent] <= value) break;
                data[child] = data[parent];
                child = parent;
            }
            data[child] = value;
        }

        int poll() {
            if (size == 0) throw new NoSuchElementException("empty");
            int root = data[0];
            int last = data[--size];
            int parent = 0;
            while (2 * parent + 1 < size) {
                int child = 2 * parent + 1;
                if (child + 1 < size && data[child + 1] < data[child])
                    child++;
                if (last <= data[child]) break;
                data[parent] = data[child];
                parent = child;
            }
            if (size > 0) data[parent] = last;
            return root;
        }

        boolean valid() {
            for (int i = 1; i < size; i++)
                if (data[(i - 1) / 2] > data[i]) return false;
            return true;
        }
    }

    public static void main(String[] args) {
        var heap = new MinHeap(1_024);
        var oracle = new PriorityQueue<Integer>();
        var random = new Random(7);
        for (int i = 0; i < 1_000; i++) {
            if (oracle.isEmpty() || random.nextBoolean()) {
                int value = random.nextInt();
                heap.offer(value);
                oracle.offer(value);
            } else {
                int actual = heap.poll();
                int expected = oracle.remove();
                assert actual == expected;
            }
            assert heap.valid();
        }
        while (!oracle.isEmpty()) {
            int actual = heap.poll();
            int expected = oracle.remove();
            assert actual == expected;
            assert heap.valid();
        }
        boolean emptyRejected = false;
        try { heap.poll(); }
        catch (NoSuchElementException expected) { emptyRejected = true; }
        assert emptyRejected;

        var range = new TreeMap<Integer, String>();
        range.put(10, "A"); range.put(20, "B"); range.put(30, "C");
        assert range.floorKey(25) == 20;
        assert range.ceilingKey(25) == 30;
        assert range.subMap(10, true, 30, false).keySet()
            .equals(Set.of(10, 20));

        Comparator<String> byLength = Comparator.comparingInt(String::length);
        var wrong = new TreeMap<String, Integer>(byLength);
        wrong.put("aa", 1); wrong.put("bb", 2);
        assert !"aa".equals("bb");
        assert wrong.size() == 1 && wrong.get("aa") == 2;
        var fixed = new TreeMap<String, Integer>(
            byLength.thenComparing(Comparator.naturalOrder()));
        fixed.put("aa", 1); fixed.put("bb", 2);
        assert fixed.size() == 2;
        System.out.println("PASS MinHeapLab: heap + range + comparator");
    }
}

javac --release 21 MinHeapLab.java TopKDemo.java
java -ea MinHeapLab
java -ea TopKDemo

Failure injection. Bổ sung dataset toàn phần tử bằng nhau, tăng dần, giảm dần, số âm và Integer.MIN_VALUE/MAX_VALUE. Kiểm tra queue rỗng, queue đầy; cố ý đổi một dấu so sánh trong sift-up/down để xác nhận invariant test thực sự bắt được lỗi. Với top-K, đưa score trùng và kiểm tra tie-breaker thống nhất với full-sort oracle.

Expected observations. Sau mỗi thao tác, mọi parent không lớn hơn child; poll liên tiếp cho dãy không giảm. Comparator chỉ so độ dài làm “aa” và “bb” dùng chung một key slot ở TreeMap; tie-breaker khôi phục hai mapping nếu đó là semantics cần có. Range [10, 30) chứa 10 và 20; floor/ceiling của 25 là 20/30. Submap là backed view, không phải bản sao độc lập. [9]

Acceptance gate. Heap khớp oracle qua seed cố định và các edge case; top-K khớp full sort với cùng comparator ở tập nhỏ. Báo cáo O(log n) cho sift path của heap n phần tử, O(n log k) cho input top-K với k ≥ 2 và O(k) bộ nhớ phụ; giải thích cả chi phí sort phần output. Chạy bài 100 triệu record bằng input streaming, không bắt buộc nạp toàn bộ để chứng minh kết quả.

Artifact cần nộp. Heap implementation, tests/seed, trace của một sift-up và một sift-down, đối chiếu top-K/full-sort, log comparator-overwrite và range/floor/ceiling. Nếu đo hiệu năng, lưu số liệu thực tế thay vì gán trước một tỉ lệ nhanh hơn.

Tái hiện race bằng phối hợp thread, không bằng may rủi

Setup. Hai barrier bảo đảm hai thread cùng quan sát trạng thái cũ trước khi ghi; start barrier đơn lẻ chỉ giúp bắt đầu cùng lúc, chưa ép được interleaving cần kiểm tra. Chương trình tách redundant construction khỏi lost update, rồi sửa counter bằng computeIfAbsent + LongAdder. Mọi wait đều có timeout để lỗi lab không treo vô hạn.

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

public class CompoundRaceLab {
    static void await(CyclicBarrier barrier) throws Exception {
        barrier.await(5, TimeUnit.SECONDS);
    }

    static void runTwo(Callable<Void> task) throws Exception {
        ExecutorService pool = Executors.newFixedThreadPool(2);
        try {
            Future<Void> first = pool.submit(task);
            Future<Void> second = pool.submit(task);
            first.get(10, TimeUnit.SECONDS);
            second.get(10, TimeUnit.SECONDS);
        } finally {
            pool.shutdownNow();
            if (!pool.awaitTermination(5, TimeUnit.SECONDS))
                throw new IllegalStateException("workers did not terminate");
        }
    }

    public static void main(String[] args) throws Exception {
        var start1 = new CyclicBarrier(2);
        var afterCheck = new CyclicBarrier(2);
        var bad = new ConcurrentHashMap<String, Object>();
        var builds = new AtomicInteger();
        runTwo(() -> {
            await(start1);
            boolean missing = !bad.containsKey("key");
            await(afterCheck); // both checks finish before either put
            if (missing) {
                builds.incrementAndGet();
                bad.put("key", new Object());
            }
            return null;
        });
        assert bad.size() == 1 && builds.get() == 2;

        var start2 = new CyclicBarrier(2);
        var afterRead = new CyclicBarrier(2);
        var count = new ConcurrentHashMap<String, Integer>();
        count.put("key", 0);
        runTwo(() -> {
            await(start2);
            int old = count.get("key");
            await(afterRead); // both threads read 0
            count.put("key", old + 1);
            return null;
        });
        assert count.get("key") == 1; // intended total is 2

        var start3 = new CyclicBarrier(2);
        var fixed = new ConcurrentHashMap<String, LongAdder>();
        var fixedBuilds = new AtomicInteger();
        runTwo(() -> {
            await(start3);
            for (int i = 0; i < 10_000; i++) {
                fixed.computeIfAbsent("key", k -> {
                    fixedBuilds.incrementAndGet();
                    return new LongAdder();
                }).increment();
            }
            return null;
        });
        // Both futures completed; no remove/reset/clear occurs in this test.
        assert fixedBuilds.get() == 1;
        assert fixed.get("key").sum() == 20_000;

        var ordinary = new ArrayList<>(List.of(1, 2));
        Iterator<Integer> failFast = ordinary.iterator();
        ordinary.add(3);
        boolean detected = false;
        try { failFast.next(); }
        catch (ConcurrentModificationException expected) { detected = true; }
        assert detected; // controlled single-thread OpenJDK illustration

        var cow = new CopyOnWriteArrayList<>(List.of(1, 2));
        Iterator<Integer> snapshot = cow.iterator();
        cow.add(3);
        var snapshotSeen = new ArrayList<Integer>();
        snapshot.forEachRemaining(snapshotSeen::add);
        assert snapshotSeen.equals(List.of(1, 2));

        var concurrent = new ConcurrentHashMap<Integer, String>();
        concurrent.put(1, "A"); concurrent.put(2, "B");
        Iterator<Integer> weak = concurrent.keySet().iterator();
        concurrent.put(3, "C");
        var weakSeen = new HashSet<Integer>();
        while (weak.hasNext()) {
            int key = weak.next();
            assert Set.of(1, 2, 3).contains(key);
            boolean newKey = weakSeen.add(key);
            assert newKey; // each stable key at most once
        }
        assert weakSeen.containsAll(Set.of(1, 2));
        // Do not demand that 3 is present, absent, or in any fixed order.
        System.out.println("PASS CompoundRaceLab: reproduced races; fixed=20000");
    }
}

javac --release 21 CompoundRaceLab.java
java -ea CompoundRaceLab

Thí nghiệm callback chậm bắt buộc

Trong một biến thể riêng, đặt sleep hoặc remote-call giả có timeout vào callback; dùng latch báo “callback đã vào”, rồi từ controller gửi thêm request cùng key và key khác. Ghi thời gian chờ theo operation và chụp thread dump/JFR khi có contention. Một số update có thể phải đợi callback; không suy ra mọi read đều khóa hay mọi key khác đều độc lập. [14]

Chuyển I/O ra ngoài atomic map operation và đo lại. putIfAbsent chỉ quyết định value thắng; nó không tự ngăn nhiều request cùng tải dữ liệu trước khi put. Nếu cần một load đang chạy cho mỗi key, thiết kế publication của future ngắn gọn, chỉ owner thực hiện I/O ngoài callback, kèm cleanup/retry/cancellation khi lỗi. Không đặt barrier chờ hai callback cùng-key cùng đi vào bên trong compute: thread thứ hai có thể đang bị chặn bởi chính atomic operation.

Oracle cho iteration

Nguồn cho các oracle: ArrayList, CopyOnWriteArrayList và java.util.concurrent. [6] [19] [20]

Acceptance gate. Bản lỗi tái hiện được cả construction dư và lost update; bản sửa cho tổng đúng sau khi join, kể cả nhiều lần chạy và hot-key contention. Giữ rõ precondition: không có remove/reset/clear trong lúc increment. Nếu thêm eviction, phải thiết kế lại để không increment một LongAdder đã bị tách khỏi map. Mapping lifecycle đúng không tự chứng minh business side effect chỉ xảy ra một lần.

Artifact cần nộp. Source/barrier schedule, construction/update counts, repeated-run assertion logs, callback latency cùng thread dump/JFR, before/after I/O placement và bảng assertion cho cả ba iterator semantics. Phân biệt lỗi thuật toán với một lần chạy chưa kích hoạt được race.