Module 2 — Tổng kết: cheat sheet cấu trúc tuyến tính
Cheat sheet Big-O, memory footprint, glossary 13 thuật ngữ, 5 pitfall tổng hợp, self-assessment 4 outcome, và lộ trình tiếp theo.
TL;DR
Bạn vừa đi qua 8 bài về cấu trúc dữ liệu tuyến tính — từ array nguyên thuỷ 40 MB đến ring buffer SPSC lock-free không alloc trong steady state. Tổng kết này gom lại cheat sheet, glossary, pitfall hay mắc, và self-assessment để bạn kiểm tra xem mình đã thực sự nắm hay chưa.
Đã đi qua
| Bài | Chủ đề | Điểm cốt lõi |
|---|---|---|
| 01 | Array vs ArrayList | Boxing overhead: 40 MB vs 234 MB cho 10M số nguyên |
| 02 | Linked list | Cache miss 25x dù cùng O(n); Node overhead 32 byte |
| 03 | Stack | LIFO — call stack, undo, balanced brackets, DFS iterative |
| 04 | Queue & Deque | FIFO — BFS, sliding window max với monotonic deque |
| 05 | Circular buffer | Ring + modulo trick; SPSC lock-free chỉ cần volatile |
| 06 | Priority queue | Min-heap intro — O(log n) insert/poll, O(1) peek |
| 07 | Mini-challenge LRU | HashMap + DoublyLinkedList — O(1) get & put |
| 08 | Case study Disruptor | Pre-alloc + padding 7 long — 25M+ ops/s, zero GC |
Cheat sheet
Big-O theo thao tác
| Cấu trúc | Truy cập index | Tìm kiếm | Chèn đầu | Chèn cuối | Xoá đầu | Xoá cuối |
|---|---|---|---|---|---|---|
| Array nguyên thuỷ | O(1) | O(n) | O(n) shift | O(n) shift | O(n) shift | O(1) |
| ArrayList (mảng động) | O(1) | O(n) | O(n) shift | Amortized O(1) | O(n) shift | O(1) |
| Singly linked list | O(n) | O(n) | O(1) | O(n) hoặc O(1) nếu giữ tail | O(1) | O(n) |
| Doubly linked list | O(n) | O(n) | O(1) | O(1) nếu giữ tail | O(1) | O(1) |
| Stack (trên array) | — | — | — | O(1) push | — | O(1) pop |
| Queue (trên array) | — | — | O(1) enqueue | — | O(1) dequeue | — |
| Deque (ArrayDeque) | O(1) đầu/cuối | O(n) | O(1) | O(1) | O(1) | O(1) |
| Circular buffer | O(1) | O(n) | O(1) overwrite | O(1) | O(1) | O(1) |
| Priority queue (heap) | O(1) peek min | O(n) | O(log n) | O(log n) | O(log n) poll | — |
Memory footprint cho 10 triệu phần tử
| Cấu trúc | RAM ước tính | Ghi chú |
|---|---|---|
int[] nguyên thuỷ | ~40 MB | 4 byte/phần tử, không boxing |
Integer[] boxed | ~200 MB | 16 byte object + 4 byte ref = 20 byte/slot |
ArrayList<Integer> | ~234 MB | Boxed array + capacity slack ~17% |
LinkedList<Integer> | ~400 MB | Node overhead 24 byte/phần tử |
ArrayDeque<Integer> | ~234 MB | Circular array boxed, ít overhead hơn LinkedList |
Khi nào chọn cái nào
Biết trước kích thước + cần tốc độ tối đa (hot loop)?
-> array nguyên thuỷ int[], long[], double[]
Cần grow linh hoạt + truy cập ngẫu nhiên?
-> ArrayList (mặc định cho hầu hết trường hợp)
Cần insert/delete đầu thường xuyên + không cần random access?
-> ArrayDeque (không phải LinkedList)
Cần LIFO (undo, call stack, DFS)?
-> Stack bằng ArrayDeque (Deque.push/pop)
Cần FIFO (BFS, task queue)?
-> Queue bằng ArrayDeque (Deque.offer/poll)
Cần giữ N phần tử gần nhất, O(1) enqueue, tự evict oldest?
-> Circular buffer (ring buffer)
Cần luôn lấy min/max nhanh nhất?
-> Priority queue (min-heap)
Cần O(1) get + O(1) put + evict LRU?
-> HashMap + DoublyLinkedList (hoặc LinkedHashMap)
Cần producer-consumer lock-free throughput cao nhất?
-> Ring buffer SPSC (Disruptor pattern hoặc JCTools)
Glossary
| Thuật ngữ | Định nghĩa ngắn |
|---|---|
| Array nguyên thuỷ | Mảng lưu giá trị trực tiếp (int[]) — không boxing, cache-friendly, kích thước cố định |
| Boxing | Wrap primitive thành object wrapper (int → Integer) — tốn thêm object header 12 byte |
| Cache locality | Dữ liệu liền kề trong bộ nhớ được CPU prefetch cùng lúc — array thắng linked list nhờ đây |
| False sharing | Hai biến không liên quan nằm cùng cache line 64 byte — write một biến invalidate cache của biến kia |
| Amortized O(1) | Chi phí trung bình theo chuỗi thao tác — ArrayList grow 1.5x: mỗi grow tốn O(n) nhưng trải đều thành O(1)/thao tác |
| Circular buffer | Array kích thước cố định với head/tail chạy vòng theo modulo — O(1) enqueue/dequeue, không alloc |
| SPSC | Single Producer Single Consumer — lock-free pattern chỉ cần volatile vì producer và consumer write hai biến khác nhau |
| Capacity slack | Phần backing array dự phòng chưa dùng trong mảng động — lý do ArrayList dùng nhiều RAM hơn số phần tử thực |
| modCount | Bộ đếm structural modification trong ArrayList — fail-fast iterator dùng để detect concurrent modification |
| Sentinel node | Node giả (dummy) ở đầu/cuối doubly linked list — đơn giản hoá code insert/delete, tránh null check |
| Priority queue | Hàng đợi trả về phần tử có độ ưu tiên cao nhất (min hoặc max) — thường implement bằng binary heap |
| Heapify | Xây heap từ array có sẵn trong O(n) — nhanh hơn insert từng phần tử O(n log n) |
| Sequence barrier | Cơ chế Disruptor gating consumer chờ producer publish đủ sequence — không lock, không blocking queue |
Pitfall tổng hợp
Pitfall 1 — Dùng LinkedList vì tưởng O(1) insert nhanh hơn ArrayList:
LinkedList.add(0, x) là O(1) pointer update, nhưng ArrayList.add(0, x) tuy O(n) shift lại nhanh hơn trên thực tế khi n nhỏ hơn vài nghìn, vì array shift dùng System.arraycopy — JVM intrinsic — trong khi linked list gây cache miss liên tục khi traverse. Đo JMH trước khi switch.
Pitfall 2 — Nhầm capacity với size trong ArrayList:
new ArrayList<>(100) tạo backing array kích thước 100 nhưng size = 0. Gọi get(50) ném IndexOutOfBoundsException. Capacity chỉ kiểm soát khi nào grow xảy ra — không tạo sẵn phần tử.
Pitfall 3 — Iterator fail-fast bị bỏ qua trong multi-threaded context:
ConcurrentModificationException từ fail-fast là "best-effort" — trong môi trường multi-threaded không có happens-before, modCount có thể không visible và lỗi không trigger, khiến iterator trả về kết quả sai thầm lặng. Dùng CopyOnWriteArrayList hoặc explicit synchronization cho concurrent access.
Pitfall 4 — Ring buffer kích thước không phải lũy thừa 2:
Circular buffer dùng head & (N-1) thay modulo chỉ đúng khi N là lũy thừa 2. Kích thước N = 100 với head & 99 cho kết quả sai. Luôn dùng power-of-2 hoặc modulo % thông thường nếu không chắc.
Pitfall 5 — Disruptor ProducerType.SINGLE với nhiều publisher thread:
Single-producer mode không dùng CAS — nhanh hơn nhưng silent corruption nếu nhiều thread cùng gọi ring.next(). Lỗi không có exception, chỉ thấy data sai ở consumer, thường chỉ xuất hiện dưới production load. Luôn dùng ProducerType.MULTI khi có nhiều publisher thread.
Mermaid tổng quan
graph TD
Q["Truy cập<br/>ngẫu nhiên?"]
YES_ACCESS["array / ArrayList"]
NO_ACCESS["Cần LIFO/FIFO?"]
LIFO["Stack<br/>(ArrayDeque)"]
FIFO["Queue/Deque<br/>(ArrayDeque)"]
NO_QUEUE["Kích thước cố định?"]
RING["Circular buffer"]
PRIORITY["Priority queue<br/>(heap)"]
COMBINED["Cấu trúc kết hợp<br/>(LRU, Disruptor)"]
Q -->|"Có"| YES_ACCESS
Q -->|"Không"| NO_ACCESS
NO_ACCESS -->|"LIFO"| LIFO
NO_ACCESS -->|"FIFO"| FIFO
NO_ACCESS -->|"Không"| NO_QUEUE
NO_QUEUE -->|"Có"| RING
NO_QUEUE -->|"Ưu tiên"| PRIORITY
NO_QUEUE -->|"Phức tạp"| COMBINED✅ Self-assessment
Bạn đã đạt module này nếu trả lời được:
- So sánh được mảng tĩnh, mảng động và danh sách liên kết theo truy cập / chèn / xoá và bộ nhớ (Nếu chưa: đọc lại bài 01 và 02)
- Implement được stack, queue, deque, circular buffer và hàng đợi ưu tiên bằng pseudocode (Nếu chưa: đọc lại bài 03, 04, 05, 06)
- Giải thích được vì sao cache locality khiến mảng nhanh hơn danh sách liên kết dù cùng O(n) (Nếu chưa: đọc lại bài 02 section "Cơ chế bên dưới")
- Thiết kế được cấu trúc kết hợp LRU cache và ring buffer SPSC (Nếu chưa: đọc lại bài 07 và 08)
🚀 What's next
Module này kết thúc khoá Thuật toán Căn bản (tier 1). Bạn đã nắm các cấu trúc dữ liệu tuyến tính cùng cơ chế bộ nhớ bên dưới — nền tảng để hiểu tại sao các thuật toán hoạt động với complexity như vậy.
Khoá tiếp theo — Thuật toán Cốt lõi (tier 2) — bắt đầu với Module Tìm kiếm nhanh: hash function, binary search, trie, và bloom filter. Mỗi cấu trúc trong module này đều xây trên nền kiến thức bạn vừa học.
Thuật toán Cốt lõi — Tìm kiếm nhanh
📚 Tài liệu mở rộng
- OpenJDK 21 — ArrayList.java — source code
grow(),modCount,elementData. Đọc cùng cheat sheet để thấy implementation thực tế. - LMAX Disruptor paper (2011) — paper gốc mô tả ring buffer, sequence barrier, false sharing avoidance. Benchmark methodology trong Table 1.
- JCTools — Lock-free collections — SPSC, MPSC, SPMC, MPMC queue nhẹ hơn Disruptor cho use case đơn giản.
- Effective Java, Item 28 — Prefer lists to arrays — Bloch giải thích covariance vs invariance, và khi nào array nguyên thuỷ là lựa chọn đúng.
- Aleksey Shipilev — JVM performance blog — false sharing, boxing overhead,
@Contended, JMH benchmark methodology.
Bài tiếp theo: Thuật toán Cốt lõi — Module Tìm kiếm: tổng quan
Bài này có giúp bạn hiểu bản chất không?
Hỏi đáp về bài này
Chưa có câu hỏi
Có gì chưa rõ trong bài? Đặt câu hỏi đầu tiên — câu trả lời từ cộng đồng giúp bạn (và người sau).
Đặt câu hỏi đầu tiên