Cụm bài Cấu trúc dữ liệu: 1. Array, Linked List, Stack, Queue · 2. List, Set, Map · 3. TreeMap, Comparator, Iterator · 4. Bên trong ArrayList, HashMap
Dùng ArrayList và HashMap thì ai cũng biết; phỏng vấn senior hỏi tiếp chúng chạy thế nào bên trong JDK. Đọc xong, bạn giải thích được add tốn bao nhiêu khi mảng đầy, vì sao LinkedList và Stack hiếm khi đúng, HashMap xử lý trùng bucket ra sao, và tự viết lại được ArrayList, LinkedList. Nên đọc trước phần 1 (array, linked list, stack, queue ở mức khái niệm), phần 2 (API của List, Set, Map) và phần 3 (TreeMap, Comparator, Iterator).
1. Bên trong JDK (phần senior hay bị hỏi)
Ý chính: mỗi collection là một cấu trúc dữ liệu cụ thể (mảng, mảng vòng, danh sách liên kết, bảng băm). Biết cấu trúc đó là suy ra được chi phí của từng thao tác và các bẫy của nó.
1.1. ArrayList tăng kích thước thế nào
Ý chính: ArrayList là một mảng; đầy thì tạo mảng mới lớn hơn ~1.5 lần và copy sang. Vì tăng theo cấp số nhân, thêm vào cuối là O(1) amortized.
new ArrayList<>()chưa cấp phát 10 ô ngay. Nó trỏ tới một mảng rỗng dùng chung; lầnaddđầu tiên mới tạo mảng capacity 10. Slide nói “mặc định là 10” là đúng con số, nhưng việc cấp phát là lười.- Khi đầy: capacity mới =
old + (old >> 1)(≈ 1.5 lần), rồiArrays.copyOfsang mảng mới. - Amortized (khấu hao) nghĩa là chi phí trung bình trên cả chuỗi thao tác. Tổng chi phí copy cho n lần
addvẫn là O(n), nên trung bình mỗi lần O(1). Riêng lầnaddgặp resize tốn O(n): với hệ thống nhạy latency, đó là một cú “spike”. - Biết trước kích thước thì khai báo luôn:
new ArrayList<>(expectedSize)hoặcensureCapacity(n), để tránh resize nhiều lần. ArrayListkhông thread-safe. Cần đa luồng thì cân nhắcCollections.synchronizedList,CopyOnWriteArrayList(đọc rất nhiều, ghi rất ít), hoặc thiết kế để không chia sẻ list.
ArrayList: trimToSize, remove và cơ chế fail-fast modCount
trimToSize()thu mảng về đúngsizeđể giảm bộ nhớ.remove(index)dùngSystem.arraycopyđể dịch các phần tử sau sang trái, rồi gán ô cuối bằngnullđể GC thu hồi được object. Quên bước gánnullnày là một kiểu memory leak kinh điển khi tự viết cấu trúc dữ liệu.ArrayListcó biếnmodCountđếm số lần bị sửa cấu trúc. Iterator kiểm tra nó để phát hiện list bị sửa trong lúc duyệt, rồi némConcurrentModificationException. Đây là cơ chế fail-fast (báo lỗi sớm để lộ bug), không phải cơ chế đồng bộ: đừng dựa vào nó cho tính đúng đắn đa luồng.- Với
intsố lượng lớn,ArrayList<Integer>tốn hơnint[]nhiều lần do boxing (bọc giá trị primitive thành object; mỗiInteger~16 byte). Code xử lý số liệu lớn nên dùng mảng primitive hoặcIntStream.
1.2. LinkedList trong JDK
Ý chính: LinkedList là danh sách liên kết đôi; truy cập theo index vẫn O(n) và mỗi phần tử tốn thêm một object node. Ưu điểm thật sự chỉ là chèn/xoá O(1) qua ListIterator đang đứng sẵn ở vị trí đó.
- Là doubly linked list (mỗi node trỏ cả node trước và node sau), implement cả
ListlẫnDeque. get(i)đi từ đầu gần hơn:i < size/2thì đi từfirst, ngược lại từlast. Vẫn là O(n).- Mỗi phần tử là một object
Node(item, next, prev): khoảng 24 byte mỗi node với compressed oops (JVM nén tham chiếu 64-bit xuống 4 byte), chưa tính object phần tử.ArrayListchỉ tốn 4 byte tham chiếu mỗi phần tử. Nhiều object nhỏ cũng làm GC vất vả hơn. - Node nằm rải rác trong heap nên CPU cache kém hiệu quả; mảng của
ArrayListnằm liền nhau (cache locality tốt). Làm queue/stack thìArrayDequetốt hơn.
1.3. Đừng dùng Stack, hãy dùng ArrayDeque
Ý chính: Stack là class cũ, khoá không cần thiết và lộ thao tác theo index. ArrayDeque làm stack và queue đều O(1) amortized, không lock, không tạo node.
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // addFirst
stack.pop(); // removeFirst
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); // addLast
queue.poll(); // pollFirst
Cho đa luồng có các queue riêng. Backpressure (áp lực ngược) nghĩa là khi consumer chậm, producer bị buộc chậm lại thay vì đổ dồn việc vào bộ nhớ.
1.4. HashMap hoạt động thế nào
Ý chính: HashMap là mảng bucket; hash của key chọn bucket, key trùng bucket được nối thành list (dài thì thành cây). Quá 75% đầy thì gấp đôi mảng.
flowchart LR
K["key.hashCode()"] --> M["h ^ (h >>> 16)"]
M --> I["index = hash & (n - 1)"]
I --> T["table[index]"]
T --> B1["Node(k1,v1)"] --> B2["Node(k2,v2)"]
T -. "bucket >= 8 node và table >= 64" .-> RB["Red-black tree"]
- Mảng
tablecác bucket (ô chứa). Capacity mặc định 16, luôn là lũy thừa của 2, nên index tính bằng phép ANDhash & (n - 1)thay vì%. - Collision (hai key trùng bucket) được nối thành linked list. Từ Java 8, bucket có từ 8 node trở lên và table ≥ 64 ô thì chuyển thành cây đỏ-đen (treeify): worst case từ O(n) xuống O(log n). Table còn nhỏ hơn 64 thì HashMap resize thay vì treeify.
- Load factor mặc định 0.75: khi
size > capacity * 0.75, table gấp đôi và entry được chia lại. get/puttrung bình O(1) nếuhashCodephân bố tốt.hashCode()trả hằng số thì mọi key dồn vào một bucket.- Không thread-safe: nhiều luồng cùng
putcó thể mất dữ liệu. DùngConcurrentHashMap. - Đừng dùng object mutable làm key: đổi field tham gia
hashCodesau khiputthì không bao giờgetlại được nữa. Record vàStringlà key tốt vì immutable. LinkedHashMapgiữ thứ tự chèn; dựng vớiaccessOrder = truevà overrideremoveEldestEntrylà thành LRU cache đơn giản.TreeMaplà cây đỏ-đen, O(log n), cófloorKey,ceilingKey,subMap.
Chi tiết HashMap: trộn hash, chia lại khi resize, key null, HashSet
- Hash được “trộn” bằng
h ^ (h >>> 16)để các bit cao cũng ảnh hưởng tới index (vì& (n - 1)chỉ lấy các bit thấp). - Khi resize gấp đôi, mỗi entry hoặc giữ nguyên index, hoặc dịch thêm đúng
oldCapacity. Không cần tính lại hash đầy đủ. - Cây trong bucket giảm còn 6 node thì về lại linked list.
- Cho phép một key
null(nằm ở bucket 0) và nhiều valuenull. - Trước Java 8, nhiều luồng cùng resize còn có thể tạo vòng lặp vô hạn trong bucket.
HashSetthực chất là mộtHashMapvới value là một object dummy.
1.5. Java 21: Sequenced Collections
Ý chính: từ Java 21, List, Deque, LinkedHashSet có chung getFirst(), getLast(), reversed()… nên không phải viết list.get(list.size() - 1) nữa.
1.6. Bảng Big-O tổng hợp
Ý chính: mảng mạnh ở truy cập index, ArrayDeque ở hai đầu, HashMap ở tìm theo key, TreeMap khi cần thứ tự. LinkedList chỉ rẻ khi đã đứng sẵn ở vị trí cần sửa.
| Cấu trúc | Truy cập index | Tìm theo giá trị | Thêm đầu | Thêm cuối | Thêm/xoá giữa | Xoá đầu | Xoá cuối |
|---|---|---|---|---|---|---|---|
int[] |
O(1) | O(n) | không | không | không | không | không |
ArrayList |
O(1) | O(n) | O(n) | O(1)* | O(n) | O(n) | O(1) |
LinkedList |
O(n) | O(n) | O(1) | O(1) | O(n) tìm + O(1) nối | O(1) | O(1) |
ArrayDeque |
không | O(n) | O(1)* | O(1)* | không | O(1) | O(1) |
PriorityQueue |
không | O(n) | offer O(log n) |
poll O(log n) |
|||
HashMap/HashSet |
không | O(1) trung bình, O(log n) worst (Java 8+) | put O(1) TB |
remove O(1) TB |
|||
TreeMap/TreeSet |
không | O(log n) | put O(log n) |
remove O(log n) |
* amortized.
Bài tập
Bài 1: Tự viết ArrayList và bổ sung method
Đề: từ class ArrayList tự viết trong bài, thêm clear, contains, get, indexOf, lastIndexOf, set, trimToSize, addFirst, addLast, removeFirst, removeLast, getFirst, getLast.
Lời giải Bài 1: hệ số tăng capacity và MyArrayList generic (đã chạy test)
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Objects;
public class MyArrayList<E> {
private static final int DEFAULT_CAPACITY = 10;
private Object[] data;
private int size;
public MyArrayList() { this(DEFAULT_CAPACITY); }
public MyArrayList(int initialCapacity) {
if (initialCapacity < 0) throw new IllegalArgumentException("capacity < 0");
data = new Object[initialCapacity];
}
public int size() { return size; }
public boolean isEmpty() { return size == 0; }
private void growIfFull() {
if (size == data.length) {
// tăng ~1.5 lần giống JDK; max(...) để xử lý capacity 0 hoặc 1
int newCap = Math.max(DEFAULT_CAPACITY, data.length + (data.length >> 1));
data = Arrays.copyOf(data, newCap);
}
}
private void checkIndex(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
}
public void add(E e) { add(size, e); }
public void add(int index, E e) {
if (index < 0 || index > size) // index == size nghĩa là thêm vào cuối
throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
growIfFull();
System.arraycopy(data, index, data, index + 1, size - index);
data[index] = e;
size++;
}
@SuppressWarnings("unchecked")
public E get(int index) {
checkIndex(index);
return (E) data[index];
}
public E set(int index, E e) {
E old = get(index);
data[index] = e;
return old;
}
public E remove(int index) {
E old = get(index);
System.arraycopy(data, index + 1, data, index, size - index - 1);
data[--size] = null; // không giữ tham chiếu thừa -> tránh leak
return old;
}
public int indexOf(Object o) {
for (int i = 0; i < size; i++)
if (Objects.equals(o, data[i])) return i; // xử lý được cả null
return -1;
}
public int lastIndexOf(Object o) {
for (int i = size - 1; i >= 0; i--)
if (Objects.equals(o, data[i])) return i;
return -1;
}
public boolean contains(Object o) { return indexOf(o) >= 0; }
public void clear() {
data = new Object[DEFAULT_CAPACITY]; // đề yêu cầu trả về kích thước mặc định
size = 0;
}
public void trimToSize() {
if (data.length > size) data = Arrays.copyOf(data, size);
}
public void addFirst(E e) { add(0, e); } // O(n)
public void addLast(E e) { add(size, e); } // O(1) amortized
public E removeFirst() { requireNotEmpty(); return remove(0); }
public E removeLast() { requireNotEmpty(); return remove(size - 1); }
public E getFirst() { requireNotEmpty(); return get(0); }
public E getLast() { requireNotEmpty(); return get(size - 1); }
private void requireNotEmpty() {
if (size == 0) throw new NoSuchElementException("list is empty");
}
@Override
public String toString() { // slide 1.3 "show()": [a, b, c]
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size; i++) {
if (i > 0) sb.append(", "); // dấu phẩy chỉ đặt GIỮA hai phần tử
sb.append(data[i]);
}
return sb.append(']').toString();
}
}
Giải thích nhanh:
System.arraycopyxử lý đúng cả khi vùng nguồn và đích chồng nhau, nên dùng nó để dịch phải (khi chèn) và dịch trái (khi xoá), thay cho vòngforthủ công.getFirsttrên list rỗng némNoSuchElementException, giốngArrayList.getFirst()trong Java 21.Objects.equalsgiúpindexOf(null)hoạt động đúng.toString()thay choshow()của slide (in dạng[a, b, c]): dấu phẩy đặt trước mọi phần tử trừ phần tử đầu, nên không thừa dấu phẩy cuối. List rỗng in ra[]. OverridetoStringtốt hơn method tự in raSystem.out, vì chuỗi dùng được cho log, test và debugger.
Bài 2: Tự viết LinkedList và bổ sung method
Đề: từ class LinkedList (singly, có head, tail, size) trong bài, thêm clear, contains, indexOf, lastIndexOf, set, getFirst, getLast.
Lời giải Bài 2: các lỗi của code mẫu slide và MyLinkedList
Các lỗi nhỏ hơn nhưng vẫn nên biết: tên method removeFist bị gõ sai; get(n) với n ngoài phạm vi lặng lẽ trả null thay vì ném exception; add(i, e) với i > size lặng lẽ thêm vào cuối thay vì báo lỗi; remove(i) với i >= size làm hỏng danh sách. Lời giải dưới kiểm tra index và ném IndexOutOfBoundsException cho tất cả các trường hợp này.
import java.util.NoSuchElementException;
import java.util.Objects;
public class MyLinkedList<E> {
private static final class Node<E> {
E data;
Node<E> next;
Node(E data) { this.data = data; }
}
private Node<E> head;
private Node<E> tail;
private int size;
public int size() { return size; }
private Node<E> node(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
Node<E> cur = head;
for (int i = 0; i < index; i++) cur = cur.next;
return cur;
}
public void addFirst(E e) {
Node<E> n = new Node<>(e);
n.next = head;
head = n;
if (tail == null) tail = n; // list đang rỗng
size++;
}
public void addLast(E e) { // O(1) nhờ có tail
Node<E> n = new Node<>(e);
if (tail == null) {
head = tail = n;
} else {
tail.next = n;
tail = n;
}
size++;
}
public void add(int index, E e) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
if (index == 0) { addFirst(e); return; }
if (index == size) { addLast(e); return; }
Node<E> prev = node(index - 1);
Node<E> n = new Node<>(e);
n.next = prev.next; // nối node mới vào phần sau TRƯỚC
prev.next = n; // rồi mới đổi con trỏ của prev
size++;
}
public E removeFirst() {
if (head == null) throw new NoSuchElementException();
E val = head.data;
head = head.next;
if (head == null) tail = null; // vừa xoá phần tử cuối cùng
size--;
return val;
}
public E removeLast() { // vẫn O(n): singly list phải tìm node áp chót
if (size <= 1) return removeFirst();
Node<E> prev = node(size - 2);
E val = tail.data;
prev.next = null;
tail = prev;
size--;
return val;
}
public E remove(int index) {
if (index == 0) return removeFirst();
Node<E> prev = node(index - 1);
Node<E> target = prev.next;
if (target == null) throw new IndexOutOfBoundsException("index=" + index);
prev.next = target.next;
if (target == tail) tail = prev;
size--;
return target.data;
}
public E get(int index) { return node(index).data; }
public E set(int index, E e) {
Node<E> n = node(index);
E old = n.data;
n.data = e;
return old;
}
public int indexOf(Object o) {
int i = 0;
for (Node<E> cur = head; cur != null; cur = cur.next, i++)
if (Objects.equals(o, cur.data)) return i;
return -1;
}
public int lastIndexOf(Object o) { // singly list không đi lùi được: duyệt một lượt, nhớ lần khớp cuối
int i = 0, last = -1;
for (Node<E> cur = head; cur != null; cur = cur.next, i++)
if (Objects.equals(o, cur.data)) last = i;
return last;
}
public boolean contains(Object o) { return indexOf(o) >= 0; }
public void clear() {
head = tail = null; // các node không còn ai tham chiếu, GC sẽ dọn
size = 0;
}
public E getFirst() {
if (head == null) throw new NoSuchElementException();
return head.data;
}
public E getLast() {
if (tail == null) throw new NoSuchElementException();
return tail.data;
}
@Override
public String toString() { // O(n), đi theo next thay vì gọi get(i)
StringBuilder sb = new StringBuilder("[");
for (Node<E> cur = head; cur != null; cur = cur.next) {
sb.append(cur.data);
if (cur.next != null) sb.append(" -> ");
}
return sb.append("]").toString();
}
}
Đề có ghi clear() “đặt về kích thước mặc định”, nhưng linked list không có capacity, nên ở đây chỉ cần bỏ hết tham chiếu.
Ghi nhớ
- Giải thích được vì sao
addcủaArrayListlà O(1) amortized dù có lần tốn O(n), và vì sao tăng+10mỗi lần lại thành O(n²). - Biết khi nào
LinkedListthật sự tốt hơnArrayList, và nêu được hai lý do nó thường thua (cache locality, ~24 byte mỗi node). - Nói được ba lý do bỏ
Stackđể dùngArrayDeque, và vì saoArrayDequekhông nhậnnull. - Vẽ lại được đường đi
hashCode→ trộn hash →hash & (n - 1)→ bucket → list/cây, với các ngưỡng 8, 64, 0.75. - Biết vì sao key mutable làm hỏng
HashMapvà vì sao queue production phải có giới hạn.
Câu hỏi phỏng vấn
Mid
ArrayList tăng kích thước như thế nào và vì sao add là O(1) amortized?
Đầy thì tạo mảng mới ~1.5 lần và copy sang; vì tăng theo cấp số nhân, tổng chi phí copy qua n lần add chỉ là O(n).
Constructor mặc định dùng mảng rỗng; lần add đầu cấp 10 ô. Tổng copy bị chặn bởi một hằng số nhân n, nên trung bình mỗi lần add là O(1), dù một lần riêng lẻ có thể là O(n).
Khi nào LinkedList thực sự tốt hơn ArrayList?
Hiếm khi: chủ yếu khi chèn/xoá nhiều ở giữa qua một ListIterator đang đứng sẵn ở vị trí đó.
Hoặc khi cần thêm/xoá ở đầu mà không muốn dùng ArrayDeque. Trong đa số benchmark, ArrayList thắng nhờ cache locality và ít object hơn; LinkedList tốn ~24 byte overhead mỗi node và làm GC vất vả hơn.
Vì sao nên dùng ArrayDeque thay cho Stack?
Stack kế thừa Vector nên khoá không cần thiết và phá vỡ LIFO; ArrayDeque là mảng vòng, push/pop O(1) amortized, không lock.
Mọi method của Stack đều synchronized, và nó lộ các method truy cập theo index. ArrayDeque không tạo node. Javadoc khuyến nghị dùng Deque.
Senior
Mô tả cách HashMap hoạt động trong Java 8+.
Mảng bucket kích thước lũy thừa 2; hash chọn bucket, collision nối thành list, list dài thành cây đỏ-đen, quá load factor thì gấp đôi table.
Mặc định 16 bucket. Hash được trộn bằng h ^ (h >>> 16), index = hash & (n-1). Bucket từ 8 node trở lên và table ≥ 64 thì treeify (worst case O(log n)), giảm còn 6 thì về lại list. Vượt capacity * 0.75 thì gấp đôi table và chia lại entry. Không thread-safe; cho phép một key null.
Dùng object mutable làm key của HashMap có vấn đề gì?
Đổi field tham gia hashCode sau khi put thì get tính ra bucket khác, nên không bao giờ tìm thấy entry nữa.
Entry vẫn nằm ở bucket cũ, thành “rác” không lấy lại được, gây memory leak. Dùng key immutable (String, record, Long).
Chọn queue nào cho producer/consumer trong production? Vì sao bounded?
ArrayBlockingQueue hoặc LinkedBlockingQueue có capacity, vì queue không giới hạn che giấu consumer chậm cho tới khi heap đầy.
Queue không giới hạn kết thúc bằng OutOfMemoryError. Queue có giới hạn tạo backpressure: producer bị chặn hoặc nhận false từ offer, từ đó có thể từ chối request, đổ ra chỗ khác hoặc scale consumer. ThreadPoolExecutor mặc định của Executors.newFixedThreadPool dùng LinkedBlockingQueue không giới hạn; đây là một cái bẫy hay gặp.
Thiết kế LRU cache bằng Java Collections như thế nào?
Dùng LinkedHashMap(capacity, 0.75f, true) và override removeEldestEntry trả về size() > capacity; get/put O(1).
accessOrder = true để mỗi lần get đẩy entry về cuối. Tự làm thì kết hợp HashMap (key → node) với doubly linked list. Đa luồng thì cần lock, hoặc dùng thư viện như Caffeine.
Từ vựng tiếng Anh
| Term | Phát âm | Nghĩa | Ví dụ câu trong phỏng vấn |
|---|---|---|---|
| amortized | /ˈæmərtaɪzd/ | chi phí trung bình (khấu hao) | “Appending to an ArrayList is amortized O(1).” |
| capacity | /kəˈpæsəti/ | sức chứa | “Capacity is the length of the backing array, size is how many elements it holds.” |
| resize / grow | /riːˈsaɪz/ | tăng kích thước | “When the array is full, it grows by about fifty percent.” |
| collision | /kəˈlɪʒən/ | va chạm (trùng bucket) | “Collisions are chained in a bucket and treeified when they get long.” |
| load factor | /loʊd ˈfæktər/ | hệ số tải | “The default load factor of 0.75 trades memory for fewer collisions.” |
| bucket | /ˈbʌkɪt/ | ô chứa trong bảng băm | “The key’s hash decides which bucket it lands in.” |
| thread-safe | /θrɛd seɪf/ | an toàn đa luồng | “HashMap isn’t thread-safe; use ConcurrentHashMap instead.” |
| backpressure | /ˈbækˌprɛʃər/ | áp lực ngược | “A bounded queue gives us backpressure when consumers fall behind.” |
| boxing | /ˈbɑːksɪŋ/ | đóng gói primitive thành object | “A List of Integer has boxing overhead compared with an int array.” |
Ghi chép dựa trên khoá Fundamentals of Backend (Ronin Engineer) và tài liệu Java Core của Hỏi Dân IT, cộng thêm kiến thức tự tìm hiểu, viết lại theo cách hiểu của mình.