Array, linked nodes và circular buffer

Lab 01 · Dynamic array: thấy được slot và grow

Goal. Tự viết một dynamic array nhỏ có add/get/remove/grow, giữ đúng thứ tự, bounds và không giữ reference thừa ở phần ngoài size.

Việc phải làm. Dùng Object[] và size; public methods kiểm tra index trước khi sửa state. Chọn và ghi rõ growth policy của riêng lab, kể cả capacity bằng 0; kiểm tra overflow khi tính capacity mới thay vì để phép cộng int wrap âm. Khi remove, lưu item trả về, shift phần suffix, giảm size và xóa reference ở slot cuối cũ.

// Pseudocode cho remove(index), KHONG la toan bo class:
check 0 <= index < size
removed = elements[index]
copy [index + 1, size) sang [index, size - 1)
size = size - 1
elements[size] = null
return removed

Failure-first. Bắt đầu bằng test cố tình làm lộ lỗi: capacity = 0 rồi add; grow qua nhiều boundary; remove phần tử đầu, giữa, cuối; get(-1), get(size); remove trên empty. Tạm bỏ câu null slot để thấy test retention fail, sau đó khôi phục.

Acceptance. Sau mỗi operation, 0 ≤ size ≤ capacity; contents khớp model ArrayList; các slot từ size đến capacity đều null sau remove. Test ít nhất một grow giữ đủ thứ tự và object identity. Dùng accessor package-private trong class tự viết để assert storage; không cần reflection vào JDK, không dùng “GC chạy ngay” làm assertion.

Artifact. Source class + self-test, log boundary cases, một bảng state trước/sau grow và remove, giải thích vì sao xóa reference không đồng nghĩa object lập tức biến mất. Với self-test tên MiniArrayTest, chạy:

javac --release 21 MiniArray.java MiniArrayTest.java
java -ea MiniArrayTest

Hai file trên do người học triển khai; yêu cầu lab không nhúng sẵn một đáp án hoàn chỉnh. Expected result là toàn bộ assertions qua, không phải một thời gian chạy cố định.

Lab 02 · JMH: traversal, append và middle insert

Goal. So ArrayList/LinkedList bằng workload được định nghĩa, có warmup và chống dead-code elimination. Không dùng một lần nanoTime() để kết luận class nào luôn nhanh hơn.

Setup. Ví dụ dùng JDK 21 và JMH 1.37 như một baseline tái lập, không tuyên bố đây là phiên bản mới nhất. JMH/Maven chỉ là công cụ người học cài để chạy lab; hai trang HTML không tải chúng. Tạo project benchmark theo hướng dẫn chính thức, rồi đặt class bên dưới tại src/main/java/org/example/ListDequeBench.java. [B-R10]

mvn archetype:generate -B -DarchetypeGroupId=org.openjdk.jmh -DarchetypeArtifactId=jmh-java-benchmark-archetype -DarchetypeVersion=1.37 -DgroupId=org.example -DartifactId=collections-bench -Dversion=1.0 -Dpackage=org.example
cd collections-bench
mvn clean package
java -jar target/benchmarks.jar "org.example.ListDequeBench.*" -prof gc -rf json -rff results.json

Đặt class vào project trước lệnh build. Mỗi command là một dòng, dùng được trong terminal Windows hoặc POSIX có Java/Maven đúng PATH. Ghi version JDK, JMH và môi trường trong báo cáo.

package org.example;

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

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Warmup(iterations = 3, time = 1)
@Measurement(iterations = 5, time = 1)
@Fork(2)
public class ListDequeBench {
    @State(Scope.Thread)
    public static class Data {
        @Param({"array", "linked"})
        public String implementation;

        @Param({"100", "10000"})
        public int size;

        public Integer[] seed;
        public List<Integer> values;
        public Integer token;

        public List<Integer> fresh() {
            if ("array".equals(implementation)) return new ArrayList<>();
            if ("linked".equals(implementation)) return new LinkedList<>();
            throw new IllegalArgumentException(implementation);
        }

        @Setup(Level.Trial)
        public void setup() {
            seed = new Integer[size];
            for (int i = 0; i < size; i++) seed[i] = i;
            values = fresh();
            Collections.addAll(values, seed);
            token = -1;
        }
    }

    @Benchmark
    public long traverse(Data data) {
        long sum = 0;
        for (Integer value : data.values) sum += value;
        return sum;
    }

    @Benchmark
    public List<Integer> appendBatch(Data data) {
        List<Integer> result = data.fresh();
        for (Integer value : data.seed) result.add(value);
        return result;
    }

    @Benchmark
    public Integer middleInsertRemovePair(Data data) {
        int middle = data.size / 2;
        data.values.add(middle, data.token);
        return data.values.remove(middle);
    }
}

Giới hạn phép đo. Một operation của traverse là duyệt cả list; appendBatch gồm tạo list và append cả batch, có allocation nhưng tái dùng Integer payload đã chuẩn bị. middleInsertRemovePair đo cả insert lẫn remove để khôi phục kích thước; không gắn nhãn kết quả là “pure insert latency”. LinkedList ở benchmark này còn phải tìm index. Returned result giúp JMH giữ lại công việc thay vì loại bỏ như dead code. [B-R11]

Failure-first và biến thể. Viết một bản cố tình bỏ consume/return để nhận diện benchmark sai, nhưng không nộp số đó như kết luận. Thêm case ArrayList pre-sized, so index traversal với iterator traversal, và tách case LinkedList mutation qua iterator đã định vị. Nếu đo pure insert bằng @Setup(Level.Invocation), ghi chi phí setup/timer/GC và tác động đến đo thao tác ngắn; không mặc định cho rằng setup ngoài vùng timing thì hoàn toàn không ảnh hưởng. [B-R12]

Acceptance. Có kết quả cho cả hai implementations, hai sizes và ba workloads; warmup, measurement, forks rõ; không để list tăng vô hạn qua nhiều invocation. Báo score/error/unit và allocation với đúng đơn vị “mỗi traversal”, “mỗi batch” hoặc “mỗi pair”. Không trừ máy móc hai score để bịa latency riêng của insert.

Artifact. Benchmark source, nguyên lệnh chạy, raw JSON, version/CPU/heap/JVM flags, nhận xét về variance và phạm vi kết luận. Không có threshold “ArrayList phải nhanh hơn X lần”; nếu kết quả trái dự đoán, điều tra workload, allocation và measurement trước.

Lab 03 · Circular deque: wrap-around rồi grow

Goal. Implement deque có hai đầu; không làm mất, lặp hoặc đảo thứ tự khi head lớn hơn tail và array phải grow.

Thiết kế lab. Chọn mô hình spare slot: capacity tối thiểu 2, null không được chấp nhận, head == tail là empty, size ≤ capacity - 1. Khi sắp hết chỗ, grow trước lần ghi tiếp theo; đây là thiết kế học tập, không sao chép nguyên thứ tự lệnh của OpenJDK.

// Pseudocode: grow giu nguyen logical order
oldSize = size
newCapacity = growCapacitySafely(oldCapacity)
newElements = array(newCapacity)
for k in [0, oldSize):
    newElements[k] = elements[(head + k) mod oldCapacity]
elements = newElements
head = 0
tail = oldSize
// Them tiep o tail; cac slot chua dung phai la null.

Failure-first trace. Bắt đầu với array length 7. OfferLast A…F; pollFirst bốn lần để còn E,F. OfferLast G,H,I,J: lúc này head = 4, tail = 3, size = 6. OfferLast K phải grow; sau grow, pollFirst đến empty phải cho E,F,G,H,I,J,K. Một bản copy theo physical array order thay vì logical order sẽ fail ở đây.

Acceptance. Test empty/singleton, poll/peek không làm sai size, hai đầu xen kẽ, null rejection, wrap nhiều vòng và grow khi head > tail. Sau mỗi bước kiểm tra head/tail hợp lệ, size không âm, unused slots null. Chạy thêm tối thiểu 10.000 operation ngẫu nhiên với seed được ghi lại, so contents với ArrayDeque làm model; so qua list contents, không dùng deque.equals như một content-equality contract.

Artifact. Implementation, self-test, trace các index/state của ca trên và seed/log của differential test. Chạy javac --release 21 MiniDeque.java MiniDequeTest.java rồi java -ea MiniDequeTest sau khi triển khai. Không dùng bit-mask nếu thiết kế không bảo đảm power-of-two capacity.

Lab 04 · CopyOnWrite: chứng minh snapshot cũ

Goal. Tạo iterator, mutate list rồi chỉ ra iterator và list hiện tại đang quan sát hai cấu trúc khác nhau; đồng thời chứng minh snapshot không freeze mutable object.

Steps. Khởi tạo list [A,B], tạo iterator cũ; remove A và add C qua list; collect iterator cũ và tạo traversal mới. Tiếp theo gọi iterator.remove để thấy operation không được hỗ trợ. Cuối cùng lặp thí nghiệm với một mutable element, đổi field sau khi tạo iterator trong cùng thread.

Expected observations. Iterator cũ thấy [A,B]; list hiện tại là [B,C]; iterator.remove ném UnsupportedOperationException. Snapshot mutable element vẫn thấy field vừa đổi vì reference trỏ cùng object. Thử nghiệm cùng thread có chủ đích để không đánh đồng visibility/race với shallow-copy semantics. [B-R6] [B-R7]

Acceptance và artifact. Nộp assertions cho cả bốn quan sát, output thực tế, một object graph chứa array cũ/array mới và giải thích memory lifetime. Không dùng sleep để “chứng minh atomicity”, không suy từ test snapshot rằng compound workflow là atomic. Code kiểm chứng bên dưới có thể dùng làm điểm xuất phát cho lab này.

Code kiểm chứng chung · Java 21

Lưu đoạn này thành CollectionsChecks.java. Đây là harness bổ sung cho các ví dụ và lab 04, không thay thế implementation phải tự viết ở lab 01/03 hay thí nghiệm đo ở lab 02. CME case chỉ là kiểm tra chẩn đoán trên implementation đang chạy.

import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;

public final class CollectionsChecks {
    static void check(boolean condition, String label) {
        if (!condition) throw new AssertionError(label);
    }
    static void expect(Class<? extends Throwable> type, Runnable action) {
        try {
            action.run();
        } catch (Throwable error) {
            if (type.isInstance(error)) return;
            throw new AssertionError("Expected " + type.getSimpleName(), error);
        }
        throw new AssertionError("Missing " + type.getSimpleName());
    }
    public static void main(String[] args) {
        ArrayList<String> names = new ArrayList<>();
        names.add("An");
        names.add(0, "Binh");
        names.ensureCapacity(64);
        check(names.size() == 2, "capacity is not size");
        check(names.remove(0).equals("Binh"), "remove shifts suffix");
        check(names.equals(List.of("An")), "remaining element");
        expect(IndexOutOfBoundsException.class, () -> names.get(1));
        System.out.println("PASS ArrayList: order, capacity, bounds");

        LinkedList<String> tasks =
                new LinkedList<>(List.of("A", "B", "C"));
        ListIterator<String> cursor = tasks.listIterator(1);
        cursor.add("X");
        check(cursor.next().equals("B"), "cursor position");
        cursor.remove();
        check(tasks.equals(List.of("A", "X", "C")), "local mutation");
        System.out.println("PASS LinkedList: positioned ListIterator");

        Deque<String> queue = new ArrayDeque<>();
        queue.offer("A");
        queue.offer("B");
        check(queue.poll().equals("A"), "FIFO");
        queue.push("X");
        check(queue.pop().equals("X"), "LIFO at first");
        check(queue.poll().equals("B"), "remaining FIFO item");
        check(queue.poll() == null, "empty poll");
        expect(NoSuchElementException.class, queue::pop);
        expect(NullPointerException.class, () -> queue.offer(null));
        System.out.println("PASS ArrayDeque: ends, empty, null");

        List<String> parent =
                new ArrayList<>(List.of("A", "B", "C", "D"));
        List<String> view = parent.subList(1, 3);
        view.set(0, "X");
        check(parent.equals(List.of("A", "X", "C", "D")), "backed view");
        List<String> detached = new ArrayList<>(view);
        view.clear();
        check(parent.equals(List.of("A", "D")), "clear range");
        parent.add("E"); // Do not use view after this structural change.
        check(detached.equals(List.of("X", "C")), "detached structure");
        List<String> readOnly = List.copyOf(detached);
        expect(UnsupportedOperationException.class, () -> readOnly.add("Y"));
        expect(NullPointerException.class,
                () -> List.copyOf(Arrays.asList("X", null)));
        System.out.println("PASS subList: write-through and shallow copy");

        CopyOnWriteArrayList<String> listeners =
                new CopyOnWriteArrayList<>(List.of("A", "B"));
        Iterator<String> old = listeners.iterator();
        listeners.remove("A");
        listeners.add("C");
        List<String> observed = new ArrayList<>();
        old.forEachRemaining(observed::add);
        check(observed.equals(List.of("A", "B")), "old snapshot");
        check(listeners.equals(List.of("B", "C")), "current list");
        expect(UnsupportedOperationException.class, old::remove);
        check(!listeners.addIfAbsent("C"), "absent check is one operation");

        int[] box = {1};
        CopyOnWriteArrayList<int[]> boxes = new CopyOnWriteArrayList<>();
        boxes.add(box);
        Iterator<int[]> snapshot = boxes.iterator();
        box[0] = 2; // Same thread: deterministic shallow-snapshot observation.
        check(snapshot.next()[0] == 2, "snapshot does not freeze object");
        System.out.println("PASS CopyOnWrite: snapshot, UOE, mutable element");

        ArrayList<String> safe = new ArrayList<>(List.of("A", "B"));
        Iterator<String> valid = safe.iterator();
        check(valid.next().equals("A"), "first iterator element");
        valid.remove();
        check(safe.equals(List.of("B")), "iterator-owned remove");
        Iterator<String> stale = safe.iterator();
        safe.add("C");
        // Diagnostic example for the tested OpenJDK 21 implementation only.
        expect(ConcurrentModificationException.class, stale::next);
        System.out.println("PASS iterator: legal remove; diagnostic CME");
    }
}

javac --release 21 CollectionsChecks.java
java -ea CollectionsChecks

Expected output: sáu dòng PASS bên dưới; nếu có assertion fail, giữ nguyên stack trace và kiểm tra assumptions/version thay vì sửa expected value để che lỗi.

PASS ArrayList: order, capacity, bounds
PASS LinkedList: positioned ListIterator
PASS ArrayDeque: ends, empty, null
PASS subList: write-through and shallow copy
PASS CopyOnWrite: snapshot, UOE, mutable element
PASS iterator: legal remove; diagnostic CME