Khép lại chặng Collections bằng câu hỏi ngược: nếu bạn cần một List mà JDK không có sẵn thì viết thế nào?

Câu trả lời ngắn hơn bạn nghĩ — hai phương thức.

Một danh sách không lưu phần tử nào

Giả sử cần một danh sách chứa dãy số học: bắt đầu từ 10, bước 5, sáu phần tử. Cách hiển nhiên là dựng một ArrayList rồi đổ số vào. Nhưng dãy đó có thể tính ra được, nên chẳng cần lưu gì:

static class Day extends AbstractList<Integer> {
    private final int dau, buoc, soLuong;

    @Override public Integer get(int i) {
        Objects.checkIndex(i, soLuong);
        return dau + i * buoc;
    }
    @Override public int size() { return soLuong; }
}

Chỉ vậy. Và đây là những gì bạn nhận được:

  toString  : [10, 15, 20, 25, 30, 35]
  contains  : true / false
  indexOf   : 3
  subList   : [15, 20, 25]
  stream    : [10, 20, 30]
  for-each  : 10  15  20  25  30  35
  equals với ArrayList cùng nội dung: true
  hashCode bằng nhau                : true

AbstractList cài sẵn toàn bộ phần còn lại dựa trên hai phương thức bạn viết. contains gọi indexOf, indexOf duyệt bằng iterator, iterator gọi get. stream đi qua spliterator, cũng dựa trên get và size.

Kể cả equals và hashCode — và chúng tương thích với ArrayList, vì hợp đồng của List quy định rõ cách tính: hai List bằng nhau khi cùng kích thước và các phần tử tương ứng bằng nhau, còn mã băm tính theo công thức cố định.

Đối tượng này chiếm ba số nguyên trong bộ nhớ, dù nó là một danh sách sáu phần tử. Với dãy một triệu phần tử thì vẫn ba số nguyên.

Mặc định là chỉ đọc

  add -> UnsupportedOperationException
  set -> UnsupportedOperationException

AbstractList cài add và set bằng cách ném UnsupportedOperationException. Muốn cho sửa thì ghi đè thêm:

@Override public String set(int i, String x) {
    var cu = mang[i]; mang[i] = x; return cu;
}

Và ngay lập tức mọi API dựa trên set cũng hoạt động:

  sau Collections.sort : [a, b, c]
  sau replaceAll       : [A, B, C]

Collections.sort và replaceAll chỉ cần get và set. Bạn không viết dòng nào cho hai việc đó.

Muốn thêm/xoá được nữa thì ghi đè add(int, E) và remove(int).

Các lớp trừu tượng có sẵn

Lớp Phải cài Cho danh sách/tập kiểu gì
AbstractList get(int), size() truy cập ngẫu nhiên
AbstractSequentialList listIterator(), size() truy cập tuần tự, như danh sách liên kết
AbstractSet iterator(), size() tập hợp
AbstractMap entrySet() map
AbstractCollection iterator(), size() collection chung

Chọn AbstractList hay AbstractSequentialList tuỳ vào việc get(i) của bạn có rẻ không. Rẻ thì chọn cái đầu — như dãy số trên, get là một phép nhân. Đắt thì chọn cái sau, để các thuật toán không gọi get trong vòng lặp.

Bốn hợp đồng phải giữ

Đây là phần dễ sai nhất, vì trình biên dịch không kiểm tra được.

size() phải nói thật. Mọi thứ khác dựa vào nó. Xem chuyện gì xảy ra khi nó nói dối:

new AbstractList<String>() {
    @Override public String get(int i) { return "x"; }
    @Override public int size() { return 3; }
}

  size() = 3 nhưng get() luôn trả 'x': [x, x, x]
  indexOf("x") = 0
  equals(List.of("x","x","x")) = true

Ở đây "danh sách" này thực ra vô hạn, nhưng vì size() nói 3 nên mọi thứ hành xử như thể nó có ba phần tử. Không có gì sai — nhưng nếu size() trả về một số không khớp với những gì get cho ra, bạn sẽ có IndexOutOfBoundsException ở những chỗ rất bất ngờ.

get(i) phải ném IndexOutOfBoundsException khi chỉ số ngoài biên. Objects.checkIndex(i, size) làm đúng việc đó trong một dòng.

equals và hashCode phải theo hợp đồng của giao diện. May là AbstractList đã cài đúng — đừng ghi đè trừ khi bạn biết chính xác mình đang làm gì.

modCount phải tăng khi cấu trúc thay đổi, nếu danh sách sửa được. AbstractList có sẵn trường này; iterator của nó dùng để phát hiện sửa-trong-lúc-duyệt như bài về ConcurrentModificationException. Quên tăng thì iterator im lặng cho kết quả sai; tăng nhầm thì ném ngoại lệ vô cớ.

Khi nào đáng tự viết

Thành thật thì hiếm. Nhưng có vài trường hợp rõ ràng:

Khung nhìn lên dữ liệu có sẵn — bọc một mảng, một ByteBuffer, một vùng nhớ, để mã khác dùng được như List mà không phải sao chép. Đây là công dụng phổ biến nhất.

Danh sách tính toán được — dãy số, kết quả của một hàm theo chỉ số. Tiết kiệm bộ nhớ đáng kể khi n lớn.

Danh sách lười — chỉ nạp dữ liệu khi có ai hỏi tới. Cẩn thận: toString hay một lần equals sẽ kéo toàn bộ.

Thêm ràng buộc — danh sách không cho null, hoặc có giới hạn kích thước. Nhưng cân nhắc dùng thành phần thay vì kế thừa, đúng bài học ở bài kế thừa.

Còn nếu chỉ cần "danh sách có thêm một phương thức tiện ích", đừng kế thừa — viết một hàm tĩnh nhận List làm tham số.

Iterator tự viết

Với AbstractCollection bạn phải cài iterator(). Mẫu tối thiểu:

@Override public Iterator<T> iterator() {
    return new Iterator<>() {
        private int viTri = 0;
        @Override public boolean hasNext() { return viTri < size(); }
        @Override public T next() {
            if (!hasNext()) throw new NoSuchElementException();
            return layPhanTu(viTri++);
        }
    };
}

Hai điều bắt buộc: next() phải ném NoSuchElementException khi hết, và hasNext() không được có tác dụng phụ — gọi nó mười lần liên tiếp phải cho cùng kết quả.

Nếu cho phép xoá thì cài thêm remove(), và nhớ rằng nó xoá phần tử vừa trả về bởi next(), không phải phần tử kế tiếp.

Hết chặng Collections

Mười bốn bài vừa qua: bản đồ tổng quan, ArrayList và LinkedList, bên trong HashMap, LinkedHashMap với LRU, TreeMap, ba loại Set, Deque và PriorityQueue, iterator, bất biến, generics, PECS, xoá kiểu, chọn cấu trúc theo độ phức tạp, và hôm nay là tự viết.

Ba điều tôi mong đọng lại:

Chọn cấu trúc theo cách bạn truy cập dữ liệu, không theo thói quen. Một dòng đổi List thành Set cho nhanh hơn 31 lần, như bài hôm qua đã đo.

Đọc tài liệu về hợp đồng, không chỉ về phương thức. equals của Set, compareTo của TreeSet, hashCode của khoá HashMap — phá vỡ chúng thì dữ liệu biến mất trong im lặng.

Đo, đừng đoán. Big-O cho biết xu hướng; cục bộ bộ nhớ quyết định con số thật.

Từ ngày mai ta sang chặng lập trình hàm và Stream — mười hai bài, bắt đầu từ lambda và kết thúc ở việc viết mã hàm mà vẫn đọc được.

Thử ba mươi giây

Viết một AbstractList<Integer> trả về bình phương của chỉ số, size() trả về 10.

Rồi gọi contains(49), indexOf(49), stream().sum(), và so sánh nó với một List.of(...) tương ứng bằng equals. Tất cả đều hoạt động, và bạn chỉ viết hai phương thức.