Collections: contract ở trên, data structure ở dưới
Interface quyết định semantics client được dựa vào; implementation quyết định memory, locality, complexity và concurrency. Internal detail giúp reasoning nhưng không được nhầm thành API guarantee.
Bốn lớp cần tách
| Lớp | Câu hỏi | Ví dụ |
|---|---|---|
| Interface contract | Operation và semantics nào được bảo đảm? | List có order/index; Set unique; Map key→value. |
| Abstract skeletal implementation | Behavior mặc định nào được chia sẻ? | AbstractList, AbstractMap, AbstractSet. |
| Concrete data structure | Array, linked nodes, hash table, tree hay heap? | ArrayList, HashMap, TreeMap, PriorityQueue. |
| Runtime/use context | Mutation, contention, ordering, memory và workload? | Read-heavy listener list khác shared counter map. |
API contract Không suy từ tên interface ra layout hay thread-safety. Một biến List<E> có thể trỏ tới array-based list, linked list, list không cho sửa, hoặc một view. “Có method” cũng không có nghĩa mọi implementation đều hỗ trợ mutation; hãy đọc các optional operations. [A-R1]
List và Deque cùng nằm dưới SequencedCollection, có encounter order và API hai đầu; reversed() trả reverse-ordered view chứ không mặc định tạo bản sao. Có chung API không làm operation cost của array và linked nodes trở nên giống nhau. [A-R2]Object graph và cost model
Big-O không phản ánh toàn bộ performance. Contiguous arrays có cache locality tốt và ít allocation; linked structures tạo object/node, pointer chasing và GC pressure. Resize O(n) có thể vẫn cho append amortized O(1). Comparator/hash quality và input distribution ảnh hưởng constant factors lẫn worst case.
Đọc object graph thay vì chỉ nhìn tên class
Với array-based collections, các reference slots ở liền nhau; không suy ra toàn bộ object được trỏ tới cũng nằm liên tiếp. Với linked list, ngoài item còn có node và các đường liên kết. Suy luận locality cần gắn với cách duyệt và loại payload, không biến thành lời hứa về tốc độ trên mọi JVM. [A-R3] [A-R4]
| Trục phân tích | Câu hỏi cần trả lời | Bằng chứng nên giữ |
|---|---|---|
| Algorithmic work | Đang tìm vị trí, dịch suffix, sửa liên kết, hay sao chép khi grow? | Trace các bước và số phần tử/reference bị đụng tới. |
| Allocation và lifetime | Tạo node/array nào? View hoặc iterator còn giữ dữ liệu cũ không? | Allocation profile và đường giữ reference trong heap. |
| Latency so với throughput | Append thông thường hay đúng lần resize? Có yêu cầu tail latency không? | Kết quả tách steady state, resize boundary và workload tổng thể. |
| Workload thực tế | Read/write ratio, list size, comparator/hash cost, phân bố index/key? | Thông số benchmark, raw results và môi trường chạy. |
Đây là khung suy luận và kế hoạch đo bổ sung, không phải một benchmark đã chạy. Big-O thường giả định phép so sánh/hash có chi phí hằng; nếu chúng đắt, phải tính cả phần đó.
Bản đồ chuyên đề
List & Deque
ArrayList growth/shift, LinkedList nodes, ArrayDeque circular array, CopyOnWrite snapshot.
Map, Set & Heap
HashMap put/get/resize/treeify, HashSet backing, LinkedHashMap, TreeMap và PriorityQueue.
Concurrent collections & views
ConcurrentHashMap atomic APIs, blocking/non-blocking queues, fail-fast/snapshot/weak consistency.
Scenarios & practice
Mutable key, LRU, top-K, backpressure, compound race và benchmark evidence.
Theo thứ tự: List/Deque → Map/Set/Heap → Concurrent/Views → Scenarios. Các đường dẫn giữ nguyên tên canonical trong gói đầu vào; bài này không thay thế các chuyên đề liền kề.
Complexity cheat sheet
| Implementation | Lookup/get | Add/put | Remove | Đặc tính chi phối |
|---|---|---|---|---|
| ArrayList | Index O(1), search O(n) | Append amortized O(1), middle O(n) | Middle O(n) | Contiguous array, shift elements. |
| LinkedList | O(n) | Ends O(1), at known node O(1) | At known node O(1) | Traversal + node allocations. |
| HashMap/HashSet | Average O(1) | Average O(1) | Average O(1) | Hash quality, load, collision, resize. |
| TreeMap/TreeSet | O(log n) | O(log n) | O(log n) | Red-black tree + comparator. |
| PriorityQueue | Head O(1), arbitrary O(n) | O(log n) | Head O(log n) | Binary heap; iteration không sorted. |
| ArrayDeque | Ends O(1) | Ends amortized O(1) | Ends O(1) | Circular array, no null. |
Điều kiện đi cùng bảng
ArrayList: “append amortized O(1)” nói về chi phí phân bổ trên một chuỗi thao tác; một lần grow riêng vẫn có thể O(n). Remove cuối khác remove giữa vì không cần dịch suffix. LinkedList: “lookup O(n)” là truy cập theo index bất kỳ; hai đầu không cần quét. “Known node” là vị trí đã có, chẳng hạn qua ListIterator, không phải public API đưa node tùy ý vào list. [A-R3] [A-R4]
HashMap/HashSet: average O(1) dựa trên hash phân bố phù hợp; collision và resize làm chi phí thực tế thay đổi. Không nâng nhận xét này thành worst-case O(1), cũng không suy mọi tình huống collision đều tự trở thành O(log n). TreeMap/TreeSet: cộng thêm chi phí comparator và giữ comparator nhất quán. PriorityQueue: lấy head khác tìm/xóa item bất kỳ; iterator không phải sorted traversal. O(log n) trong bảng mô tả đường sửa heap; array growth riêng có thể cần copy tuyến tính. [A-R5] [A-R6] [A-R7]
ArrayDeque: bảng nói về thao tác ở hai đầu. Tìm một giá trị hay remove occurrence phải tìm vị trí, không được suy là O(1). Việc resize không biến mỗi append thành O(n), nhưng có thể tạo một lần allocation/copy đáng kể. [A-R8]
Quy tắc đọc source OpenJDK
- Đọc public method để thấy validation và delegation.
- Theo helper như
putVal,getNode,grow,siftUp. - Ghi invariant của fields trước khi đọc branch.
- Vẽ state trước/sau operation và test boundary: empty, threshold, collision, resize.
- Đối chiếu Javadoc để tách guarantee khỏi implementation detail.
Một phiếu đọc source có thể kiểm tra lại
Ví dụ với append: ghi rõ jdk-21-ga, class ArrayList, entry point add(E), helper grow; invariant 0 ≤ size ≤ elementData.length. Vẽ hai state: còn chỗ và array đầy. Xác định phần nào là public guarantee (amortized constant-time append), phần nào là implementation detail (field, default storage, growth policy). [A-R3]
Boundary cần đối chiếu: empty; index đầu/cuối; thêm đúng tại size; resize; remove phần tử cuối; input gây collision đối với hash structures. Hãy ghi cả expected state lẫn kết quả quan sát, không chỉ ghi “test pass”.
jdk-21-ga là snapshot để đọc implementation, không phải tuyên bố mọi bản Java 21 update, vendor build hoặc JDK đời sau có cùng từng dòng code. Nếu dùng behavior Java 8+ để giải thích treeification, vẫn phải ghi rõ version/phạm vi và kiểm tra lại source tương ứng.Chọn implementation và yêu cầu bằng chứng
Bổ sung · Decision guide, không phải universal ranking
| Workload | Ứng viên ban đầu | Điều phải xác minh |
|---|---|---|
| List đọc theo index; append phổ biến | ArrayList | Size/capacity, resize spikes, tỷ lệ insert/remove giữa. |
| Mutation cục bộ tại vị trí iterator đã tìm được | LinkedList | Tính cả chi phí tìm vị trí; đo node allocation, không chỉ unlink. |
| Stack/queue trong một owner, không cần null | ArrayDeque | Hai đầu, wrap-around, burst size; không dùng như queue concurrent. |
| Listener/config list nhỏ; iteration vượt xa writes | CopyOnWriteArrayList | Chấp nhận snapshot cũ; đo write/copy cost và lifetime của iterator. |
| Shared producer/consumer hoặc compound invariant | Xác định protocol đồng bộ trước | Atomic boundary, queue bound, blocking/non-blocking và semantics traversal; học tiếp bài Concurrent/Views. |
Các ứng viên trên dựa vào semantics và mô hình chi phí, không phải số đo trên máy của người học. [A-R3] [A-R4] [A-R8] [A-R9]