Cả bài trong một trang: ý chính, sơ đồ, điểm phỏng vấn.
Java Collections: List, Set và Map
1Collection và Map
Java có hai nhóm container: Collection chứa tập phần tử, Map chứa cặp key/value (không kế thừa Collection). Chọn theo dữ liệu: cần thứ tự, cần duy nhất hay tra theo key.
Interface
Đặc điểm
Class hay dùng
List
Có thứ tự, cho trùng
ArrayList
Set
Không trùng
HashSet, TreeSet
Map
Key/value, key duy nhất
HashMap
Queue/Deque
FIFO, LIFO, ưu tiên
ArrayDeque, PriorityQueue
2ArrayList và cách xoá an toàn
ArrayList là mảng động. Khai báo bằng interface để đổi implementation chỉ sửa một dòng. Xoá lúc duyệt thì dùng removeIf hoặc iterator.remove().
List<Integer> list = new ArrayList<>();
for (Integer x : list) list.remove(x); // CME
list.removeIf(x -> x < 0); // đúng
list.remove(1); // xoá index 1
list.remove(Integer.valueOf(1)); // xoá giá trị 1
3HashSet tìm trùng thế nào
HashSet là HashMap chỉ dùng key: hashCode chọn bucket (ô bảng băm), equals quyết định trùng. Class phải override cả hai.
flowchart TD
A["add(e)"] --> B["hashCode chọn bucket"]
B --> C{"Bucket có phần tử equals e?"}
C -->|có| D["Không thêm, trả false"]
C -->|không| E["Thêm vào bucket, trả true"]
4Chọn loại Set
Mặc định HashSet; cần thứ tự thêm vào thì LinkedHashSet; cần sắp xếp hoặc truy vấn khoảng thì TreeSet (cây đỏ-đen).
Set
Thứ tự duyệt
Chi phí
HashSet
Không đảm bảo
O(1) trung bình
LinkedHashSet
Thứ tự thêm
O(1) trung bình
TreeSet
Tăng dần
O(log n)
5Map gọn từ Java 8
Bỏ kiểu "get, kiểm null, put" bằng các method mới. Hàm trong merge/compute trả null nghĩa là xoá entry.
getOrDefault(k, 0): chỉ đọc
merge(word, 1, Integer::sum): đếm số lần
computeIfAbsent(k, x -> new ArrayList<>()): tạo khi thiếu
Nhiều thread dùng chung: ConcurrentHashMap
💡 Ghi nhớ
Map không kế thừa Collection.
Override equals thì phải override hashCode.
Xoá lúc duyệt: removeIf hoặc iterator.remove().
Bọc tham số removeAll bằng HashSet để tránh O(n·m).
⭐ Điểm phỏng vấn
Tự trả lời trước, rồi bấm từng câu để xem đáp án.
Vì sao override cả hashCode?
Bằng nhau phải cùng hash, bucket chọn trước.
HashSet, LinkedHashSet, TreeSet?
Mặc định Hash; giữ thứ tự Linked; sắp xếp Tree.
ConcurrentHashMap khác synchronizedMap?
Đọc không khoá, ghi chỉ khoá bucket.
Xong phần tự kiểm tra, bài này đã được đánh dấu đã học ✓
⚠️ Lỗi thường gặp
Quên hashCode, HashSet chứa hai object "bằng nhau".
list.remove(1) trên List<Integer> xoá index chứ không phải giá trị.
Collections.copy vào list rỗng: cần size đủ, capacity không tính.
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ừa Collection.
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ó.
List có 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")); // trueObject[] raw = backend.toArray(); // Object[], không ép kiểu sang String[] đượcString[] typed = backend.toArray(new String[0]); // String[]String[] typed11 = backend.toArray(String[]::new); // Java 11+, gọn hơnnew 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. Iteratorwhile (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, 1, 4, 2, 3));Collections.sort(nums, Collections.reverseOrder()); // [5, 4, 3, 2, 1], sort theo Comparatorint 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 đã sortint miss = Collections.binarySearch(nums, 9); // -6 = -(điểm chèn) - 1List<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 đương list.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ác Collections.reverse(list) là đảo vị trí phần tử.
Collections.binarySearch chỉ đú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à 3st.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.0st.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ác BlockingQueue cho đ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ả fieldrecord 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 x vào, xong.
Bucket đã có phần tử (va chạm, collision) thì duyệt các phần tử trong đó.
Gọi equals với từng phần tử. Có phần tử bằng x thì không thêm (add trả false); không có thì thêm x.
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 mapstock.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=15stock.merge("pear", 3, Integer::sum); // chưa có thì put 3stock.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 ifMap<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 getfor (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/computeIfPresent trả null nghĩa là xoá entry: merge("pear", -3, (a, b) -> a + b == 0 ? null : a + b) xoá pear khi về 0.
Duyệt keySet() rồi gọi get(key) là tra hash hai lần mỗi phần tử; với TreeMap là thêm một lần O(log n). Dùng entrySet() hoặc forEach((k, v) -> ...).
Hàm của computeIfAbsent không được sửa chính map đó. Memo hoá Fibonacci đệ quy bằng memo.computeIfAbsent(n, k -> fib(k - 1) + fib(k - 2)) ném ConcurrentModificationException trên HashMap từ Java 9 (với ConcurrentHashMap có thể treo hoặc ném IllegalStateException). Tính giá trị trước rồi mới put.
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 merge thay cặp containsKey + put.
Chỉ cần đếm, không cần thứ tự thì HashMap nhanh hơn. Stream API cũng làm được: Collectors.groupingBy(w -> w, Collectors.counting()). Collectors, toMap gặp key trùng và các bẫy khác của stream có ở bài Lambda và Stream API.
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ạng Name: <name>, Age: <age>. Thêm ba sinh viên vào ArrayList, 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, override toString, equals, hashCode. Thêm vào HashSet nă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ên ArrayList đề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ùng ArrayDeque hoặ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/hashCode chỉ dùng id. Nếu dùng record Product(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.
add trùng không ghi đè: set giữ object cũ ("Laptop", 1500.0). Muốn “cập nhật nếu đã có” thì dùng Map<Integer, Product> với put.
Field tham gia hashCode (id) là final; name, price sửa được vì không ảnh hưởng bucket. Cho sửa id sau 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, Map hay Queue cho 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.add và vì sao thiếu hashCode thì set chứa trùng.
Biết cách xoá an toàn khi đang duyệt, và remove(1) trên List<Integer> xoá gì.
Biết khi nào dùng getOrDefault, putIfAbsent, computeIfAbsent, merge, và hàm trả null làm gì.
Biết vì sao removeAll/retainAll có 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ằng hashCode + equals, cho một null.
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ằng compareTo/Comparator, không nhận null vớ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ả d khi thiếu key và không ghi gì vào map.
putIfAbsent(k, v): ghi v khi key chưa có (hoặc đang map tới null); v luôn được tạo sẵn kể cả khi không dùng.
computeIfAbsent(k, fn): chỉ gọi fn khi 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): đặt v khi chưa có, có rồi thì gộp bằng fn, hợp với đếm và cộng dồn.
Hàm trả về null trong compute/merge nghĩ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.
HashMap, Hashtable, Collections.synchronizedMap và ConcurrentHashMap khác nhau thế nào?
HashMap không thread-safe; Hashtable và synchronizedMap khoá cả map cho mọi thao tác; ConcurrentHashMap đọc không khoá và chỉ khoá từng bucket khi ghi, nên là lựa chọn mặc định khi nhiều thread dùng chung.
HashMap
Hashtable
synchronizedMap(m)
ConcurrentHashMap
Thread-safe
không
có, một lock cho cả map
có, một lock cho cả map
có, CAS + lock theo bucket
null key/value
1 key null, nhiều value null
không
theo map bên trong
không
Duyệt khi map đổi
fail-fast
fail-fast (Enumeration thì không)
phải tự synchronized (map) khi duyệt
weakly consistent, không ném CME
Thao tác ghép (kiểm rồi ghi)
không an toàn
không an toàn
không an toàn
putIfAbsent, computeIfAbsent, merge nguyên tử
Hashtable là class cũ từ Java 1.0, chỉ còn vì tương thích; code mới không dùng. Bẫy hay gặp với cả hai loại khoá toàn map: if (!map.containsKey(k)) map.put(k, v) vẫn là race vì hai lời gọi là hai lần khoá riêng. ConcurrentHashMap cấm null để get trả null chỉ có một nghĩa (“không có”); với HashMap thì không phân biệt được “không có key” và “value là null” khi nhiều thread cùng đọc ghi.
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.