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
Phần 1 nói về array, linked list, stack, queue ở mức khái niệm; phần này là API mà code Java nào cũng dùng: Java Collections Framework. Đọc xong, bạn chọn đúng List/Set/Map/Queue, tránh các bẫy của ArrayList, HashSet, HashMap, và dùng được nhóm method Java 8 như merge, computeIfAbsent. Dữ liệu có thứ tự (TreeSet, TreeMap, Comparator) và Iterator nằm ở phần 3; cách ArrayList tăng kích thước và HashMap băm, resize nằm ở phần 4.
1. Java Collections Framework
Ý chính: Java có hai nhóm container: Collection chứa một tập phần tử, Map chứa cặp key/value. Chọn interface theo tính chất của dữ liệu: cần thứ tự, cần duy nhất, hay cần tra theo key.
- Collection: chứa một tập phần tử (
List,Set,Queue/Deque). - Map: chứa các cặp key/value.
Mapkhông kế thừaCollection.
flowchart TB
Iterable --> Collection
Collection --> List
Collection --> Set
Collection --> Queue
Queue --> Deque
List --> ArrayList
List --> LinkedList
List --> Vector --> Stack
Deque --> ArrayDeque
Deque --> LinkedList
Queue --> PriorityQueue
Set --> HashSet --> LinkedHashSet
Set --> SortedSet --> TreeSet
Map --> HashMap --> LinkedHashMap
Map --> SortedMap --> TreeMap
| Interface | Đặc điểm | Dùng khi | Ví dụ đời thực | Class hay dùng |
|---|---|---|---|---|
List |
Có thứ tự, có index, cho phép trùng | Cần giữ đúng thứ tự thêm vào hoặc truy cập theo vị trí | Danh sách học viên theo thứ tự đăng ký | ArrayList |
Set |
Không trùng (theo equals hoặc theo compareTo) |
Cần tính duy nhất, hỏi “đã có chưa” | Tập email đã đăng ký, mã nhân viên | HashSet, LinkedHashSet, TreeSet |
Map |
Cặp key/value, key không trùng | Cần tra cứu theo key | Danh bạ số điện thoại → tên, giỏ hàng mã sản phẩm → số lượng | HashMap, LinkedHashMap, TreeMap |
Queue/Deque |
Lấy ra theo thứ tự FIFO, LIFO hoặc theo độ ưu tiên | Xử lý lần lượt, hàng đợi việc | Hàng đợi gửi email, lịch sử “Back” | ArrayDeque, PriorityQueue |
Thói quen tốt: khai báo biến bằng interface (List<String> names = new ArrayList<>()), không bằng class cụ thể. Code phía sau chỉ phụ thuộc hợp đồng của List, nên đổi sang implementation khác (ví dụ CopyOnWriteArrayList) chỉ sửa một dòng.
1.1. Collection và List
Ý chính: Collection là interface gốc (add, remove, contains, size…); List thêm thứ tự, cho trùng và các method theo vị trí. Nhóm bulk operation (addAll, removeAll, retainAll…) làm phép tập hợp, nhưng sửa chính collection gọi nó.
Collection:add,remove,contains,size,isEmpty,iterator,stream…Listcó thêm:get(i),set(i, e),add(i, e),remove(i),indexOf,lastIndexOf,subList.
Bulk operation là method làm việc với cả một collection khác. Bốn method đầu trả boolean nghĩa là “collection này có bị thay đổi không”, không phải “thành công hay thất bại”:
| Method | Ý nghĩa | Tương đương tập hợp |
|---|---|---|
addAll(c) |
Thêm mọi phần tử của c |
Hợp (với Set) |
containsAll(c) |
Có chứa mọi phần tử của c không (chỉ đọc) |
Kiểm tra tập con |
removeAll(c) |
Xoá mọi phần tử có trong c |
Hiệu A \ B |
retainAll(c) |
Chỉ giữ lại phần tử có trong c |
Giao A ∩ B |
clear() |
Xoá hết | |
toArray() / toArray(T[]) |
Chép ra mảng | |
equals(o) |
So nội dung theo hợp đồng của interface con |
List<String> backend = new ArrayList<>(List.of("java", "sql", "git", "docker"));
List<String> frontend = List.of("js", "git", "docker", "css");
List<String> common = new ArrayList<>(backend);
common.retainAll(frontend); // true, common = [git, docker]
List<String> onlyBackend = new ArrayList<>(backend);
onlyBackend.removeAll(new HashSet<>(frontend)); // [java, sql]
backend.containsAll(List.of("java", "git")); // true
Object[] raw = backend.toArray(); // Object[], không ép kiểu sang String[] được
String[] typed = backend.toArray(new String[0]); // String[]
String[] typed11 = backend.toArray(String[]::new); // Java 11+, gọn hơn
new ArrayList<>(List.of(1, 2)).equals(new LinkedList<>(List.of(1, 2))); // true: List so theo thứ tự phần tử
List.of(1, 2).equals(List.of(2, 1)); // false
Muốn giữ bản gốc thì copy ra trước như ví dụ trên. Gọi retainAll trên List.of(...) (list bất biến, không sửa được) ném UnsupportedOperationException.
1.2. ArrayList
Ý chính: ArrayList là mảng động (mảng tự nới rộng khi đầy) implement List. Có bốn cách duyệt; muốn xoá trong lúc duyệt thì chỉ dùng iterator.remove() hoặc removeIf.
List<String> names = new ArrayList<>(List.of("An", "Binh", "Chi"));
for (int i = 0; i < names.size(); i++) { // 1. theo index
System.out.println(names.get(i));
}
for (String name : names) { // 2. for-each
System.out.println(name);
}
Iterator<String> it = names.iterator(); // 3. Iterator
while (it.hasNext()) {
String name = it.next();
if (name.startsWith("B")) it.remove(); // cách an toàn để xoá khi đang duyệt
}
names.forEach(System.out::println); // 4. forEach + lambda (Java 8+)
1.3. Lớp tiện ích Collections
Ý chính: java.util.Collections (có chữ s) là hộp đồ nghề static: sort, đảo, trộn, min/max, đếm, bọc thành list chỉ đọc hoặc đồng bộ.
List<Integer> nums = new ArrayList<>(List.of(5, 3, 8, 1, 3));
Collections.sort(nums); // [1, 3, 3, 5, 8]
Collections.reverse(nums); // [8, 5, 3, 3, 1]
Collections.shuffle(nums);
int max = Collections.max(nums); // 8
int freq = Collections.frequency(nums, 3); // 2
Collections.swap(nums, 0, 1);
List<Integer> readOnly = Collections.unmodifiableList(nums);
List<Integer> syncList = Collections.synchronizedList(new ArrayList<>());
List<String> fives = Collections.nCopies(5, "x");
Thêm method: reverseOrder, binarySearch, copy, fill, disjoint
List<Integer> nums = new ArrayList<>(List.of(5, 1, 4, 2, 3));
Collections.sort(nums, Collections.reverseOrder()); // [5, 4, 3, 2, 1], sort theo Comparator
int min = Collections.min(nums); // 1 (cũng có min/max nhận Comparator)
String shortest = Collections.min(List.of("pear", "fig", "banana"),
Comparator.comparing(String::length)); // "fig"
Collections.sort(nums); // [1, 2, 3, 4, 5]
int idx = Collections.binarySearch(nums, 4); // 3; list phải đã sort
int miss = Collections.binarySearch(nums, 9); // -6 = -(điểm chèn) - 1
List<Integer> dest = new ArrayList<>(Collections.nCopies(nums.size(), 0));
Collections.copy(dest, nums); // dest = [1, 2, 3, 4, 5]
Collections.fill(dest, -1); // [-1, -1, -1, -1, -1]
boolean noCommon = Collections.disjoint(List.of(1, 2), Set.of(3, 4)); // true: không có phần tử chung
Collections.sort(list, comparator)tương đươnglist.sort(comparator)(Java 8+ nên dùng cách sau). Bên trong là TimSort, ổn định (giữ thứ tự các phần tử bằng nhau), xem phần merge sort, quick sort.Collections.reverseOrder()trả về một Comparator đảo thứ tự tự nhiên;reverseOrder(cmp)đảo một comparator có sẵn. KhácCollections.reverse(list)là đảo vị trí phần tử.Collections.binarySearchchỉ đúng khi list đã sắp xếp theo cùng thứ tự; thuật toán ở tìm kiếm nhị phân.
1.4. Stack class và Queue
Ý chính: java.util.Stack (push, pop, peek, empty, search) là class cũ từ Java 1.0, kế thừa Vector. Queue là interface; implementation hay dùng là ArrayDeque, LinkedList, PriorityQueue.
Stack<Integer> st = new Stack<>();
st.push(1); st.push(2); st.push(3); // đỉnh là 3
st.search(3); // 1 (đỉnh cách đỉnh 1 bước, đếm từ 1)
st.search(1); // 3 (đáy)
st.search(9); // -1 (không có)
st.empty(); // false, tên cũ có từ Java 1.0
st.isEmpty(); // false, thừa hưởng từ Vector, cùng nghĩa
Queue:ArrayDeque,LinkedList,PriorityQueue(lấy ra theo độ ưu tiên, không theo FIFO), và cácBlockingQueuecho đa luồng.
1.5. Set và HashSet
Ý chính: Set không bao giờ chứa hai phần tử e1.equals(e2). HashSet dùng hashCode để chọn bucket (ô trong bảng băm) và equals để quyết định trùng, nên class phải override cả hai.
// record tự sinh equals/hashCode theo tất cả field
record Email(String value) {}
Set<Email> emails = new HashSet<>();
emails.add(new Email("a@x.com"));
emails.add(new Email("a@x.com"));
System.out.println(emails.size()); // 1
set.add(x) diễn ra thế nào. HashSet thực chất là một HashMap chỉ dùng key, nên add đi qua bốn bước của HashMap.put:
- Gọi
x.hashCode()lấy một số nguyên. - Từ số đó tính ra bucket. Bucket trống thì đặt
xvào, xong. - Bucket đã có phần tử (va chạm, collision) thì duyệt các phần tử trong đó.
- Gọi
equalsvới từng phần tử. Có phần tử bằngxthì không thêm (addtrảfalse); không có thì thêmx.
Một số tài liệu nhập môn nói thiếu hashCode thì “mọi phần tử dồn vào một bucket”. Không đúng: hashCode mặc định của Object dựa trên danh tính object nên phân tán rất đều. Lỗi thật là hai object bằng nhau theo equals nhận hai hash khác nhau, rơi vào hai bucket, và set giữ cả hai. Chi tiết bảng băm (trộn bit, treeify, resize) ở phần 4.
HashSet |
LinkedHashSet |
TreeSet |
|
|---|---|---|---|
| Bên trong | Bảng băm | Bảng băm + danh sách liên kết đôi | Cây đỏ-đen |
| Thứ tự duyệt | Không đảm bảo | Thứ tự thêm vào | Tăng dần theo compareTo/Comparator |
| Xác định trùng bằng | hashCode + equals |
hashCode + equals |
compareTo/compare |
Phần tử null |
Một | Một | Không (natural ordering ném NullPointerException) |
add/contains/remove |
O(1) trung bình | O(1) trung bình | O(log n) |
Mặc định dùng HashSet; cần output ổn định theo thứ tự thêm thì LinkedHashSet; cần sắp xếp hoặc hỏi “phần tử nhỏ nhất lớn hơn x” thì TreeSet (xem phần 3).
1.6. Map và HashMap
Ý chính: Map lưu cặp key/value với key duy nhất, tra value theo key rất nhanh; HashMap là implementation dùng nhiều nhất. Từ Java 8, getOrDefault, putIfAbsent, merge, compute, computeIfAbsent bỏ được kiểu code “get, kiểm tra null, rồi put”.
Method chính: put, get, getOrDefault, containsKey, remove, keySet, values, entrySet, putIfAbsent, merge, computeIfAbsent. Cách HashMap hoạt động bên trong (bucket, hash, treeify, resize) ở phần 4.
Map<String, Integer> stock = new HashMap<>();
stock.getOrDefault("apple", 0); // 0; KHÔNG ghi gì vào map
stock.putIfAbsent("apple", 10); // chỉ put khi key chưa có (hoặc đang map tới null)
stock.merge("apple", 5, Integer::sum); // có rồi thì cộng dồn: apple=15
stock.merge("pear", 3, Integer::sum); // chưa có thì put 3
stock.compute("apple", (k, v) -> v == null ? 1 : v * 2); // tính lại từ giá trị cũ
// Nhóm theo key (multimap) mà không cần if
Map<String, List<String>> byDept = new HashMap<>();
byDept.computeIfAbsent("dev", k -> new ArrayList<>()).add("An");
byDept.computeIfAbsent("dev", k -> new ArrayList<>()).add("Bình"); // {dev=[An, Bình]}
// Duyệt: entrySet lấy cả key lẫn value trong một lần, không phải tra lại bằng get
for (Map.Entry<String, Integer> e : stock.entrySet()) {
System.out.println(e.getKey() + " = " + e.getValue());
}
stock.entrySet().removeIf(e -> e.getValue() == 0); // xoá an toàn trong lúc duyệt
Ba chi tiết ít người để ý:
- Hàm trong
merge/compute/computeIfPresenttrảnullnghĩa là xoá entry:merge("pear", -3, (a, b) -> a + b == 0 ? null : a + b)xoápearkhi về 0. - Duyệt
keySet()rồi gọiget(key)là tra hash hai lần mỗi phần tử; vớiTreeMaplà thêm một lần O(log n). DùngentrySet()hoặcforEach((k, v) -> ...). - Hàm của
computeIfAbsentkhông được sửa chính map đó. Memo hoá Fibonacci đệ quy bằngmemo.computeIfAbsent(n, k -> fib(k - 1) + fib(k - 2))némConcurrentModificationExceptiontrênHashMaptừ Java 9 (vớiConcurrentHashMapcó thể treo hoặc némIllegalStateException). Tính giá trị trước rồi mớiput.
Bài tập
Bài 1: Dùng ArrayList để quản lý một dãy số
Đề: chương trình cho phép thêm, sửa, xoá và xem một tập các số.
Lời giải bài 1
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class NumberManager {
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<>();
Scanner in = new Scanner(System.in);
while (true) {
System.out.print("1-Add 2-Update 3-Delete 4-Show 0-Exit: ");
int choice = in.nextInt();
switch (choice) {
case 1 -> {
System.out.print("Value: ");
numbers.add(in.nextInt());
}
case 2 -> {
System.out.print("Index and new value: ");
int idx = in.nextInt(), val = in.nextInt();
if (idx >= 0 && idx < numbers.size()) numbers.set(idx, val);
else System.out.println("Invalid index");
}
case 3 -> {
System.out.print("Value to delete: ");
// ép sang Integer để gọi remove(Object), không phải remove(int index)
boolean removed = numbers.remove(Integer.valueOf(in.nextInt()));
System.out.println(removed ? "Deleted" : "Not found");
}
case 4 -> System.out.println(numbers);
case 0 -> { return; }
default -> System.out.println("Unknown option");
}
}
}
}
Bài 2: Dùng HashMap đếm số lần xuất hiện của từ
Đề: nhập một đoạn văn, đếm mỗi từ xuất hiện bao nhiêu lần và in kết quả.
Lời giải bài 2
static Map<String, Integer> countWords(String text) {
Map<String, Integer> counts = new TreeMap<>(); // TreeMap để in theo thứ tự chữ cái
for (String word : text.toLowerCase().split("[^\\p{L}\\p{N}]+")) {
if (word.isEmpty()) continue;
counts.merge(word, 1, Integer::sum); // chưa có -> 1, có rồi -> cộng 1
}
return counts;
}
// "Java is fun. Java, is it? fun fun" -> {fun=3, is=2, it=1, java=2}
- Chuẩn hoá chữ hoa/thường; tách theo ký tự không phải chữ/số (
\p{L}khớp cả chữ tiếng Việt có dấu). - Dùng
mergethay cặpcontainsKey+put. - Chỉ cần đếm, không cần thứ tự thì
HashMapnhanh hơn. Stream API cũng làm được:Collectors.groupingBy(w -> w, Collectors.counting()).
Bài 3: Dùng HashSet đếm số phân biệt
Đề: đếm có bao nhiêu giá trị khác nhau trong một dãy số, ví dụ 1, 2, 2, 3, 4, 5, 4 có 5 số khác nhau.
Lời giải bài 3
static int countDistinct(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int n : nums) seen.add(n); // add trùng sẽ bị bỏ qua
return seen.size();
}
// hoặc: Arrays.stream(nums).distinct().count()
O(n) thời gian, O(n) bộ nhớ. Không được dùng thêm bộ nhớ thì sort rồi đếm số lần giá trị thay đổi: O(n log n).
Bài 4: ArrayList<Student> theo index và HashSet<Product> theo id
Đề (diễn đạt lại), hai bài nhỏ của tài liệu Hỏi Dân IT:
- (a) Record
Student(name, age)in ra dạngName: <name>, Age: <age>. Thêm ba sinh viên vàoArrayList, in; chèn một sinh viên vào index 1, in; xoá sinh viên ở index 0, in. - (b) Class
Product(id, name, price)có getter/setter, overridetoString,equals,hashCode. Thêm vàoHashSetnăm sản phẩm, trong đó một sản phẩm trùng id nhưng khác tên/giá và một sản phẩm trùng hoàn toàn; in set; rồi xoá sản phẩm có id 3.
Lời giải bài 4
import java.util.*;
public class StudentProduct {
record Student(String name, int age) {
@Override
public String toString() { return "Name: " + name + ", Age: " + age; }
}
// Định danh nghiệp vụ là id: hai Product cùng id là "cùng một sản phẩm"
static final class Product {
private final int id;
private String name;
private double price;
Product(int id, String name, double price) {
this.id = id;
this.name = name;
this.price = price;
}
int getId() { return id; }
String getName() { return name; }
double getPrice() { return price; }
void setName(String name) { this.name = name; } // không tham gia equals/hashCode
void setPrice(double price) { this.price = price; } // nên sửa được mà không phá HashSet
@Override
public boolean equals(Object o) {
return this == o || (o instanceof Product p && p.id == id);
}
@Override
public int hashCode() { return Integer.hashCode(id); }
@Override
public String toString() { return "Product{id=" + id + ", name=" + name + ", price=" + price + "}"; }
}
static void print(String title, List<Student> students) {
System.out.println(title);
students.forEach(s -> System.out.println(" " + s));
}
public static void main(String[] args) {
List<Student> students = new ArrayList<>();
students.add(new Student("Alice", 20));
students.add(new Student("Bob", 22));
students.add(new Student("Charlie", 21));
print("Initial:", students);
students.add(1, new Student("David", 23)); // chèn: dịch Bob, Charlie sang phải
print("After add at index 1:", students); // Alice, David, Bob, Charlie
students.remove(0); // remove(int): theo vị trí
print("After remove index 0:", students); // David, Bob, Charlie
Set<Product> products = new HashSet<>();
products.add(new Product(1, "Laptop", 1500.0)); // true
products.add(new Product(2, "Mouse", 20.0)); // true
products.add(new Product(3, "Keyboard", 45.0)); // true
products.add(new Product(1, "Laptop Pro", 2000.0)); // false: trùng id
products.add(new Product(1, "Laptop", 1500.0)); // false: trùng hoàn toàn
products.forEach(System.out::println); // 3 sản phẩm, "Laptop" bản đầu được giữ
products.removeIf(p -> p.getId() == 3); // hoặc products.remove(new Product(3, "", 0))
System.out.println("After removing id 3: " + products.size() + " products"); // 2
}
}
Giải thích:
add(1, x)vàremove(0)trênArrayListđều dịch các phần tử phía sau, O(n). Ba phần tử thì không thấy, nhưng xoá đầu list lớn trong vòng lặp là O(n²); khi đó dùngArrayDequehoặc duyệt ngược.- “Trùng” là quyết định nghiệp vụ: ở đây hai sản phẩm cùng id là một, nên
equals/hashCodechỉ dùngid. Nếu dùng recordProduct(id, name, price)thì record so mọi field, và"Laptop Pro"cùng id 1 được thêm như một sản phẩm khác. Không có đáp án đúng chung; phải chọn có chủ đích. addtrùng không ghi đè: set giữ object cũ ("Laptop", 1500.0). Muốn “cập nhật nếu đã có” thì dùngMap<Integer, Product>vớiput.- Field tham gia
hashCode(id) làfinal;name,pricesửa được vì không ảnh hưởng bucket. Cho sửaidsau khi đã bỏ vào set là cách chắc chắn làm “mất” phần tử.
Mình đã chạy chương trình với JDK 21, output khớp các comment ở trên.
Ghi nhớ
- Chọn được
List,Set,MaphayQueuecho một yêu cầu, và giải thích vì sao khai báo bằng interface. - Giải thích được bốn bước của
HashSet.addvà vì sao thiếuhashCodethì set chứa trùng. - Biết cách xoá an toàn khi đang duyệt, và
remove(1)trênList<Integer>xoá gì. - Biết khi nào dùng
getOrDefault,putIfAbsent,computeIfAbsent,merge, và hàm trảnulllàm gì. - Biết vì sao
removeAll/retainAllcó thể O(n·m) và sửa thế nào.
Câu hỏi phỏng vấn
Junior
Vì sao khi override equals thì phải override hashCode?
Vì contract bắt hai object equals nhau phải có cùng hashCode, và HashMap/HashSet dựa vào hashCode để chọn bucket trước khi so equals.
Nếu chỉ override equals, hai object “bằng nhau” có thể nằm ở hai bucket khác nhau, nên set chứa trùng và map không get lại được.
HashSet, LinkedHashSet và TreeSet khác nhau thế nào? Chọn cái nào?
Mặc định HashSet; cần thứ tự thêm thì LinkedHashSet; cần sắp xếp hoặc truy vấn khoảng thì TreeSet.
HashSet: bảng băm, thêm/tìm/xoá O(1) trung bình, không đảm bảo thứ tự, trùng xác định bằnghashCode+equals, cho mộtnull.LinkedHashSet: như trên, thêm danh sách liên kết để duyệt theo thứ tự thêm vào.TreeSet: cây đỏ-đen, O(log n), luôn duyệt tăng dần, trùng xác định bằngcompareTo/Comparator, không nhậnnullvới natural ordering, cófloor/ceiling/headSet.
Với List<Integer> list, list.remove(1) xoá gì?
Xoá phần tử ở index 1, không phải giá trị 1.
Overload remove(int index) khớp chính xác với đối số int nên được chọn trước remove(Object) (vốn cần boxing). Muốn xoá giá trị 1 thì viết list.remove(Integer.valueOf(1)). Bẫy hay gặp trong code đọc số từ input rồi xoá theo giá trị.
Mid
ConcurrentModificationException xảy ra khi nào? Xử lý ra sao?
Khi collection bị thêm/xoá phần tử trong lúc đang duyệt bằng iterator, kể cả trong cùng một luồng; sửa bằng iterator.remove() hoặc removeIf.
Ví dụ list.remove(x) bên trong for-each. Iterator so modCount với giá trị mong đợi và ném exception (fail-fast). Cách khác: duyệt trên bản copy, hoặc dùng collection concurrent.
getOrDefault, putIfAbsent, computeIfAbsent và merge khác nhau thế nào?
getOrDefault chỉ đọc; putIfAbsent ghi giá trị tạo sẵn; computeIfAbsent chỉ tạo giá trị khi thiếu key; merge đặt hoặc gộp.
getOrDefault(k, d): trảdkhi thiếu key và không ghi gì vào map.putIfAbsent(k, v): ghivkhi key chưa có (hoặc đang map tớinull);vluôn được tạo sẵn kể cả khi không dùng.computeIfAbsent(k, fn): chỉ gọifnkhi thiếu key, hợp với giá trị tốn công tạo hoặc multimap (computeIfAbsent(k, x -> new ArrayList<>()).add(v)).merge(k, v, fn): đặtvkhi chưa có, có rồi thì gộp bằngfn, hợp với đếm và cộng dồn.- Hàm trả về
nulltrongcompute/mergenghĩa là xoá entry.
Bỏ Product vào HashSet: equals/hashCode nên dùng field nào? add một bản trùng có ghi đè bản cũ không?
Dùng đúng các field tạo nên định danh nghiệp vụ (thường là id, nên final); add bản trùng không ghi đè mà trả false.
Field sửa được (giá, tên) không nên tham gia, nếu không đổi giá sau khi add sẽ làm phần tử “mất tích” trong set. Record so mọi field, nên với record hai sản phẩm cùng id khác giá là hai phần tử khác nhau. Set giữ object cũ; muốn cập nhật theo id thì dùng Map<Id, Product> và put.
Lấy phần giao và phần hiệu của hai danh sách thế nào? Có bẫy hiệu năng nào?
Copy danh sách gốc rồi gọi retainAll(other) để lấy giao, removeAll(other) để lấy hiệu; bọc other bằng HashSet để tránh O(n·m).
Cả hai sửa chính collection gọi nó và trả true nếu nó thay đổi. Bên trong chúng gọi other.contains(x) cho từng phần tử, nên nếu other là ArrayList thì độ phức tạp là O(n·m); với new HashSet<>(other) còn O(n + m). Gọi trên list bất biến (List.of) ném UnsupportedOperationException.
Từ vựng tiếng Anh
| Term | Phát âm | Nghĩa | Ví dụ câu trong phỏng vấn |
|---|---|---|---|
| fail-fast | /feɪl fæst/ | phát hiện lỗi sớm | “ArrayList iterators are fail-fast, not thread-safe.” |
| immutable | /ɪˈmjuːtəbəl/ | bất biến | “Map keys should be immutable.” |
| key-value pair | /kiː ˈvæljuː pɛər/ | cặp khoá/giá trị | “A map stores key-value pairs, and keys are unique.” |
| duplicate | /ˈduːplɪkət/ | phần tử trùng | “The set rejects duplicates, so add returns false.” |
| hash code | /hæʃ koʊd/ | mã băm | “The hash code picks the bucket; equals settles the tie.” |
| bucket | /ˈbʌkɪt/ | ô chứa trong bảng băm | “Two equal objects must land in the same bucket.” |
| program to an interface | /ˈproʊɡræm/ | khai báo theo interface | “I program to the List interface so the implementation can change.” |
| intersection / difference | /ˌɪntərˈsɛkʃən/ /ˈdɪfrəns/ | phần giao / phần hiệu | “retainAll gives me the intersection, removeAll gives me the difference.” |
| business identity | /ˈbɪznəs aɪˈdɛntəti/ | định danh nghiệp vụ | “Equals should be based on the business identity, usually the id.” |
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.