Đến nội dung chính
notes.vinhnq.com

Tìm kiếm

Cấu trúc dữ liệu & Thuật toánJunior20 phút đọc

Java Collections: List, Set và Map

Ôn 13 thẻ
Trong bài này

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. Map khô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ó.

  • Collection: add, remove, contains, size, isEmpty, iterator, stream…
  • 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"));        // 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 đươ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à 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á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ả 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:

  1. Gọi x.hashCode() lấy một số nguyên.
  2. Từ số đó tính ra bucket. Bucket trống thì đặt x vào, xong.
  3. Bucket đã có phần tử (va chạm, collision) thì duyệt các phần tử trong đó.
  4. 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 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/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()).

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.

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.