Một Set là "tập hợp không có phần tử trùng lặp". Định nghĩa đó nghe rõ ràng cho tới khi bạn hỏi: trùng lặp nghĩa là gì?

Ba bản cài đặt của Java trả lời ba kiểu, và khác biệt đó không nằm ở hiệu năng mà nằm ở kết quả.

Cùng dữ liệu, hai kích thước

record Nguoi(String ten, int tuoi) {}

var ds = List.of(new Nguoi("Minh", 30), new Nguoi("Lan", 30), new Nguoi("Hải", 25));

Set<Nguoi> bam = new HashSet<>(ds);
Set<Nguoi> cay = new TreeSet<>(Comparator.comparingInt(Nguoi::tuoi));
cay.addAll(ds);

  HashSet (dùng equals)           : 3 phần tử
  TreeSet theo tuổi (dùng compare): 2 phần tử  <- MẤT một người!
  còn lại: [Nguoi[ten=Hải, tuoi=25], Nguoi[ten=Minh, tuoi=30]]

Lan biến mất.

TreeSet không dùng equals. Nó dùng comparator, và comparator của tôi chỉ so tuổi — nên Minh và Lan cùng 30 tuổi là "bằng nhau", và cái thứ hai bị bỏ.

Đây không phải lỗi. Tài liệu của SortedSet nói rõ: nó dùng compareTo (hoặc comparator) thay cho equals để xác định trùng lặp. Nhưng nó rất dễ gây mất dữ liệu nếu bạn viết comparator chỉ để sắp xếp mà quên rằng nó cũng đang định nghĩa "bằng nhau".

Hệ quả còn rõ hơn ở contains:

  cay.contains(Nguoi("AiCungDuoc", 30)) = true
  bam.contains(Nguoi("AiCungDuoc", 30)) = false

Một người hoàn toàn khác, chỉ trùng tuổi, và TreeSet bảo "có rồi".

Comparator dùng cho TreeSet phải phân biệt được mọi phần tử khác nhau. Nếu bạn muốn sắp theo tuổi, hãy thêm tiêu chí phụ để phá thế hoà: Comparator.comparingInt(Nguoi::tuoi).thenComparing(Nguoi::ten). Đây cũng chính là khuyến nghị "compareTo nên nhất quán với equals" ở bài Comparable — giờ bạn thấy hậu quả khi bỏ qua.

Ba loại, ba đặc tính

  HashSet       : [a, b, c, d]
  LinkedHashSet : [b, a, c, d]
  Stream distinct: [b, a, c, d]

Đầu vào là b, a, c, a, b, d.

HashSet — không hứa thứ tự nào. Ở đây tình cờ ra bảng chữ cái, và đó chính là cái bẫy: kết quả ổn định với cùng dữ liệu nên bạn dễ tưởng nó có thứ tự. Đổi dữ liệu là đổi thứ tự.

LinkedHashSet — thứ tự lần xuất hiện đầu tiên. Đây là thứ bạn cần trong hầu hết trường hợp "bỏ trùng lặp" thực tế, vì nó bảo toàn ý định của người nhập.

Stream.distinct() cũng giữ thứ tự gặp — nó tương đương LinkedHashSet về mặt kết quả.

TreeSet — theo thứ tự sắp xếp, và dùng compareTo để xác định trùng lặp như vừa nói.

Giá của thứ tự sắp xếp

Đo contains trên tập 100.000 phần tử:

TapHop.contains_HashSet        avgt   3.341 ± 0.071  ns/op
TapHop.contains_LinkedHashSet  avgt   3.433 ± 0.373  ns/op
TapHop.contains_TreeSet        avgt  46.976 ± 2.733  ns/op

Hai điều rút ra:

LinkedHashSet gần như không đắt hơn HashSet — chênh 3%, nằm trong sai số. Cấu trúc tra cứu y hệt; danh sách liên kết chỉ thêm vào lúc chèn và lúc duyệt. Nên nếu bạn phân vân giữa hai cái vì lo hiệu năng, đừng lo: cứ chọn LinkedHashSet khi cần thứ tự.

TreeSet chậm hơn 14 lần. Đây là chi phí của O(log n) so với O(1): khoảng 17 phép so sánh cho 100.000 phần tử, mỗi phép gọi compareTo. Với Integer thì rẻ; với chuỗi dài hoặc comparator nhiều tầng thì đắt hơn nhiều.

Đổi lại TreeSet cho bạn thứ tự và các phép truy vấn theo khoảng:

  floor(35)   : 30  ceiling(35): 40
  headSet(30) : [10, 20]  tailSet(30): [30, 40, 50]
  descending  : [50, 40, 30, 20, 10]

Giống hệt TreeMap của bài hôm qua, chỉ bỏ phần giá trị.

Phép toán tập hợp

Java không có toán tử hợp/giao/hiệu, nhưng có ba phương thức tương đương:

var hop  = new LinkedHashSet<>(a); hop.addAll(b);      // hợp
var giao = new LinkedHashSet<>(a); giao.retainAll(b);  // giao
var hieu = new LinkedHashSet<>(a); hieu.removeAll(b);  // hiệu

  hợp   : [1, 2, 3, 4, 5, 6, 7]
  giao  : [4, 5]
  hiệu  : [1, 2, 3]

Chú ý phải sao chép trước, vì cả ba phương thức đều sửa tại chỗ. Quên bước đó là bạn vừa phá mất tập a gốc — một lỗi rất dễ mắc khi viết vội.

Một chi tiết hiệu năng ít người biết: a.removeAll(b) có hai chiến lược tuỳ kích thước. Nếu a lớn hơn b, nó duyệt b và xoá từng cái khỏi a. Ngược lại nó duyệt a và hỏi b.contains. Nên danhSachLon.removeAll(listNho) nhanh, còn setNho.removeAll(danhSachLon) có thể chậm bất ngờ nếu danhSachLon là một List — vì contains trên List là O(n). Chuyển sang Set trước khi làm phép toán tập hợp.

Khi nào dùng cái nào

Cần Dùng
Bỏ trùng lặp, không quan tâm thứ tự HashSet
Bỏ trùng lặp, giữ thứ tự xuất hiện LinkedHashSet
Cần sắp xếp, hoặc truy vấn theo khoảng TreeSet
Tập cố định, chỉ đọc Set.of(...)
Tập hợp trên enum EnumSet

EnumSet đáng nhắc riêng: nó dùng một mảng bit bên trong, nên nhanh hơn HashSet rất nhiều và tốn ít bộ nhớ hơn hẳn. Nếu phần tử là enum thì gần như luôn nên dùng nó.

EnumSet<TrangThai> dangHoatDong = EnumSet.of(TrangThai.MOI, TrangThai.DANG_XU_LY);

Vài chỗ hay sai

HashSet bên trong chính là một HashMap. Mọi phần tử làm khoá, giá trị là một đối tượng dùng chung. Nên mọi thứ đã học ở bài HashMap — hệ số tải, va chạm, cây đỏ đen — đều áp dụng nguyên xi. Và lời khuyên khai sẵn dung lượng cũng vậy.

Phần tử của Set phải bất biến ở những trường tham gia equals/hashCode. Sửa một phần tử sau khi đã thêm vào set thì nó thành "vô hình" — đúng cái bẫy khoá HashMap của bài equals.

Set.of(...) không nhận null và không nhận phần tử trùng. Set.of("a", "a") ném IllegalArgumentException ngay lúc tạo, chứ không âm thầm bỏ bớt như HashSet. Đây là chủ ý: nếu dữ liệu của bạn có trùng lặp thì đó là lỗi cần biết.

Đừng dùng Set khi cần đếm số lần xuất hiện. Đó là việc của Map<T, Integer> — hoặc Collectors.groupingBy(x -> x, Collectors.counting()) ở chặng Stream.

Thử ba mươi giây

Tạo một TreeSet với comparator chỉ so một trường của đối tượng, thêm hai đối tượng khác nhau nhưng trùng trường đó, rồi in size().

Kết quả là 1. Không ngoại lệ, không cảnh báo — chỉ là dữ liệu biến mất. Nếu đoạn mã đó nằm trong một quy trình nhập liệu, bạn vừa tạo ra một lỗi mà log không ghi lại gì.

Ngày mai: Deque, Queue và PriorityQueue — vì sao Stack nên bị bỏ hẳn, và tại sao in một PriorityQueue ra lại không thấy nó sắp xếp.