[Advanced Java] Set trong Java: HashSet, LinkedHashSet và TreeSet

List trả lời câu hỏi "cái gì nằm ở index 3". Map trả lời "cái gì được lưu dưới key này". Set chỉ trả lời đúng một câu hỏi — element này đã có trong đây chưa — và mọi khác biệt giữa ba implementation của JDK đều sinh ra từ cách mỗi cái trả lời câu hỏi đó.

Bản thân interface hứa đúng một điều và không hứa gì thêm: không có duplicate. Ordering, sorted, khả năng chứa null và chi phí của contains đều thuộc về implementation, và mỗi cái chọn một đánh đổi khác nhau. Bài này đi qua từng đánh đổi đó, và dành phần lớn dung lượng cho chỗ khiến nhiều người bất ngờ: HashSet và TreeSet thậm chí không thống nhất với nhau về việc thế nào là một duplicate.

Mọi listing, dump javap, exception và con số đếm bên dưới đều được compile và chạy trên OpenJDK 21.0.6 (arm64). Chi phí luôn được diễn đạt bằng số lần gọi hashCode(), equals() và compareTo() được đếm bằng instrument, không bao giờ bằng thời gian chạy — một bộ đếm cho ra cùng một con số trên mọi máy, còn đồng hồ bấm giờ thì không. Quy tắc hashCode/equals ở đây được coi là đã biết; đó là chủ đề của bài HashMap trong series Java Basics.

Set đảm bảo gì và không đảm bảo gì

Set<E> extends Collection<E> và không khai báo thêm method nào của riêng nó. Cái nó thêm vào là một cách hiểu chặt hơn cho những method đã có sẵn: add trả về false thay vì lưu bản sao thứ hai, và size() đếm số element phân biệt.

Chi tiết mà nhiều người bỏ qua là chuyện gì xảy ra với chính object khi add bị từ chối. Set giữ lại cái nó đã có và vứt cái mới của bạn đi:

import java.util.HashSet;
import java.util.Set;

class Id {
    final String v;
    final int serial;

    Id(String v, int serial) { this.v = v; this.serial = serial; }

    @Override public boolean equals(Object o) { return o instanceof Id i && v.equals(i.v); }
    @Override public int hashCode() { return v.hashCode(); }
    @Override public String toString() { return v + "#" + serial; }
}

public class KeepsFirst {
    public static void main(String[] args) {
        Id first = new Id("a", 1);
        Id second = new Id("a", 2);

        Set<Id> s = new HashSet<>();
        System.out.println("add first  = " + s.add(first));
        System.out.println("add second = " + s.add(second));
        System.out.println("set        = " + s);
        System.out.println("kept is the first object = " + (s.iterator().next() == first));
    }
}

add first  = true
add second = false
set        = [a#1]
kept is the first object = true

add không phải put. Hai object có thể equal nhau mà vẫn mang dữ liệu khác nhau — serial khác, timestamp khác, một field cache khác — và Set lặng lẽ giữ lại cái nào đến trước. Nếu bạn cần last-write-wins thì phải remove rồi add, hoặc dùng Map.

Đây là danh sách đầy đủ những gì bạn được và không được đảm bảo:

Ba implementation, ba thứ tự iteration

Cùng năm element, cùng thứ tự add, ba kết quả khác nhau:

import java.util.*;

public class Ordering {
    public static void main(String[] args) {
        List<String> input = List.of("delta", "alpha", "charlie", "bravo", "echo");

        Set<String> hash = new HashSet<>(input);
        Set<String> linked = new LinkedHashSet<>(input);
        Set<String> tree = new TreeSet<>(input);

        System.out.println("inserted      = " + input);
        System.out.println("HashSet       = " + hash);
        System.out.println("LinkedHashSet = " + linked);
        System.out.println("TreeSet       = " + tree);
    }
}

inserted      = [delta, alpha, charlie, bravo, echo]
HashSet       = [bravo, alpha, delta, echo, charlie]
LinkedHashSet = [delta, alpha, charlie, bravo, echo]
TreeSet       = [alpha, bravo, charlie, delta, echo]

LinkedHashSet và TreeSet đang đưa ra một lời hứa ở đó. HashSet thì không.

Vì sao thứ tự của HashSet trông ổn định mà vẫn không được dựa vào

Dòng HashSet đó là output chạy thật, và nó ra y hệt ở mọi lần chạy trên JDK này. Nó thậm chí không phụ thuộc vào thứ tự các element được đưa vào:

import java.util.*;

public class OrderIndep {
    public static void main(String[] args) {
        String[] a = {"delta", "alpha", "charlie", "bravo", "echo"};
        String[] b = {"echo", "bravo", "charlie", "alpha", "delta"};
        System.out.println("inserted A = " + new HashSet<>(Arrays.asList(a)));
        System.out.println("inserted B = " + new HashSet<>(Arrays.asList(b)));
    }
}

inserted A = [bravo, alpha, delta, echo, charlie]
inserted B = [bravo, alpha, delta, echo, charlie]

Hai dòng giống hệt nhau vì vị trí của một String trong table là hàm của hashCode() và kích thước table, mà cả hai thứ đó đều không biết gì về thứ tự add. Chính tính xác định này làm cái bẫy trở nên nguy hiểm: thứ tự ổn định đủ để qua mọi test bạn viết, nhưng nó không phải là một đảm bảo. Thêm một element làm table resize, chạy trên JDK khác, hoặc đổi sang một kiểu element có hashCode không ổn định giữa các JVM, là nó đổi.

Set.of cho thấy điều đó rõ đến mức không thể chối. Nó được salt một cách có chủ đích, nên thứ tự iteration đổi giữa các lần chạy JVM của cùng một chương trình:

import java.util.Set;

public class Immutable {
    public static void main(String[] args) {
        Set<String> s = Set.of("delta", "alpha", "charlie", "bravo", "echo");
        System.out.println("Set.of = " + s);
    }
}

Set.of = [echo, charlie, delta, bravo, alpha]
Set.of = [echo, alpha, bravo, delta, charlie]
Set.of = [alpha, echo, charlie, delta, bravo]
Set.of = [alpha, bravo, delta, charlie, echo]

Bốn lần chạy cùng một file class, bốn thứ tự, không sửa một dòng code nào. Đó là JDK chủ động bảo vệ chữ "không quy định" trong specification. Nếu bạn cần một thứ tự, hãy nói ra: LinkedHashSet cho insertion order, TreeSet cho sorted order.

Thêm hai điều đáng biết về Set.of, vì nó là cách ngắn nhất để dựng một set: nó từ chối duplicate ngay lúc khởi tạo chứ không gộp lại, và nó từ chối null.

add  -> java.lang.UnsupportedOperationException
dup  -> java.lang.IllegalArgumentException: duplicate element: a
null -> java.lang.NullPointerException

Ngược lại, Set.copyOf thì gộp duplicate — Set.copyOf(List.of("a", "b", "a")) cho ra một set hai element.

HashSet chính là HashMap bị vứt bỏ phần value

Đây không phải cách nói ẩn dụ. Đó là implementation thật, và biết điều này giải thích được toàn bộ chi phí của HashSet chỉ trong một nhát. javap -p in ra các thành phần private của bất kỳ class nào nằm trên class path của chính JDK:

javap -p java.util.HashSet

Compiled from "HashSet.java"
public class java.util.HashSet<E> extends java.util.AbstractSet<E> implements java.util.Set<E>, java.lang.Cloneable, java.io.Serializable {
  static final long serialVersionUID;
  transient java.util.HashMap<E, java.lang.Object> map;
  static final java.lang.Object PRESENT;
  public java.util.HashSet();
  ...
}

Hai field, và đó là toàn bộ trạng thái: một HashMap có value kiểu Object, và một static final Object duy nhất tên PRESENT. Disassemble các method ra thì thấy chúng được dùng thế nào:

javap -p -c java.util.HashSet

  public boolean add(E);
    Code:
       0: aload_0
       1: getfield      #10                 // Field map:Ljava/util/HashMap;
       4: aload_1
       5: getstatic     #64                 // Field PRESENT:Ljava/lang/Object;
       8: invokevirtual #68                 // Method java/util/HashMap.put:(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;
      11: ifnonnull     18
      14: iconst_1
      15: goto          19
      18: iconst_0
      19: ireturn

  public boolean contains(java.lang.Object);
    Code:
       0: aload_0
       1: getfield      #10                 // Field map:Ljava/util/HashMap;
       4: aload_1
       5: invokevirtual #60                 // Method java/util/HashMap.containsKey:(Ljava/lang/Object;)Z
       8: ireturn

  static {};
    Code:
       0: new           #80                 // class java/lang/Object
       3: dup
       4: invokespecial #225                // Method java/lang/Object."<init>":()V
       7: putstatic     #64                 // Field PRESENT:Ljava/lang/Object;
      10: return

Đọc thẳng từ bytecode: add(e) chính là map.put(e, PRESENT) và trả về true đúng khi put trả về null, tức là cách map nói rằng key này mới. contains(o) chính là map.containsKey(o). Static initializer cấp phát đúng một Object trần cho cả class — một instance duy nhất cho mọi HashSet trong JVM, mãi mãi.

Kiểm chứng lại bằng reflection

Bytecode đã là bằng chứng, nhưng nhìn bức tranh lúc runtime vẫn đáng. Trên Java 21, module system chặn cách làm hiển nhiên:

Field f = HashSet.class.getDeclaredField("map");
f.setAccessible(true);

Exception in thread "main" java.lang.reflect.InaccessibleObjectException: Unable to make field transient java.util.HashMap java.util.HashSet.map accessible: module java.base does not "opens java.util" to unnamed module @15db9742
	at java.base/java.lang.reflect.AccessibleObject.throwInaccessibleObjectException(AccessibleObject.java:391)
	at java.base/java.lang.reflect.Field.setAccessible(Field.java:177)
	at Reflect.main(Reflect.java:8)

Chạy lại bằng java --add-opens java.base/java.util=ALL-UNNAMED Reflect thì được:

HashSet.map class = java.util.HashMap
HashSet.map       = {a=java.lang.Object@3af49f1c, b=java.lang.Object@3af49f1c}
PRESENT class     = java.lang.Object
all values same object = true
value == PRESENT       = true
LinkedHashSet.map class = java.util.LinkedHashMap

Cả hai entry in ra cùng một identity hash vì cả hai value đúng là một object duy nhất. (Mấy chữ số hex đổi giữa các lần chạy; điều quan trọng là hai cái trùng nhau.) Mọi thứ bạn đã biết về HashMap chuyển sang đây không cần sửa gì:

Dòng cuối mới là dòng cắn người. Iteration đi qua toàn bộ table, kể cả các slot rỗng, nên một HashSet từng chứa một triệu element và giờ chỉ còn ba vẫn phải đi hết một triệu slot để duyệt — table không co lại khi remove.

LinkedHashSet: cái linked list thêm vào mua được gì

LinkedHashSet extends HashSet và không thêm instance field nào của riêng nó:

Compiled from "LinkedHashSet.java"
public class java.util.LinkedHashSet<E> extends java.util.HashSet<E> implements java.util.SequencedSet<E>, java.lang.Cloneable, java.io.Serializable {
  private static final long serialVersionUID;
  public java.util.LinkedHashSet(int, float);
  ...
  java.util.LinkedHashMap<E, java.lang.Object> map();
  public void addFirst(E);
  public void addLast(E);
  public E getFirst();
  public E getLast();
  public E removeFirst();
  public E removeLast();
  public java.util.SequencedSet<E> reversed();
}

Nó kế thừa field map của HashSet rồi nhét vào đó một LinkedHashMap — đúng như dump reflection ở trên đã cho thấy. Vậy nên cái giá của đảm bảo ordering chính xác bằng chênh lệch giữa một entry của LinkedHashMap và một entry của HashMap, và javap báo giá:

class java.util.LinkedHashMap$Entry<K, V> extends java.util.HashMap$Node<K, V> {
  java.util.LinkedHashMap$Entry<K, V> before;
  java.util.LinkedHashMap$Entry<K, V> after;
}

Hai reference thêm cho mỗi element, cộng lên bốn field mà HashMap$Node đã có. Đổi lại, iteration đi theo linked list chứ không đi theo table, nên nó là O(size) thay vì O(capacity + size) — một LinkedHashSet hoàn toàn có thể duyệt nhanh hơn một HashSet cùng nội dung khi table thưa.

Add lại một element không dời nó; remove rồi add mới dời

Câu hỏi hiển nhiên về insertion order là chuyện gì xảy ra khi add lại. Đừng đoán — chạy thử:

import java.util.*;

public class Reinsert {
    public static void main(String[] args) {
        LinkedHashSet<String> s = new LinkedHashSet<>(List.of("a", "b", "c", "d"));
        System.out.println("start          = " + s);

        System.out.println("add(\"b\") again = " + s.add("b"));
        System.out.println("after re-add   = " + s);

        s.remove("b");
        System.out.println("after remove b = " + s);
        s.add("b");
        System.out.println("after re-insert= " + s);

        LinkedHashSet<String> t = new LinkedHashSet<>(List.of("a", "b", "c"));
        t.addFirst("z");
        System.out.println("addFirst z     = " + t);
        t.addLast("a");
        System.out.println("addLast a      = " + t);
        System.out.println("reversed       = " + t.reversed());
    }
}

start          = [a, b, c, d]
add("b") again = false
after re-add   = [a, b, c, d]
after remove b = [a, c, d]
after re-insert= [a, c, d, b]
addFirst z     = [z, a, b, c]
addLast a      = [z, b, c, a]
reversed       = [a, c, b, z]

Có ba hành vi khác nhau trong output đó, và rất dễ nhầm chúng thành một:

• add trên element đã có thì không làm gì cả. Nó trả về false và vị trí giữ nguyên. "Insertion order" nghĩa là thứ tự lần add đầu tiên.
• remove rồi add sẽ dời element xuống cuối. Với linked list thì đây là một element hoàn toàn mới.
• addLast trên element đã có thì có dời nó. Nhìn dòng áp chót: t đang là [z, a, b, c], addLast("a") cho ra [z, b, c, a]. addFirst và addLast đến cùng SequencedCollection ở Java 21 và được document rõ là sẽ đặt lại vị trí của element đã có, khiến chúng thành ngoại lệ so với add.

Sự bất đối xứng cuối cùng đó là nguồn bug thật trong code trộn hai API này trên cùng một set.

TreeSet và các method của NavigableSet

TreeSet vứt hẳn hash table đi. javap -p java.util.TreeSet cho thấy đúng một instance field, private transient java.util.NavigableMap<E, java.lang.Object> m, bên cạnh vẫn là chiêu PRESENT; cái map đó là TreeMap, tức một red-black tree. Element được giữ theo sorted order — theo compareTo nếu chúng là Comparable, hoặc theo một Comparator truyền vào constructor.

Nhưng sorted order không phải lý do để chọn TreeSet. Bạn có thể sort một HashSet ra list bất cứ lúc nào. Lý do là NavigableSet: tree trả lời được các câu hỏi về element lân cận, thứ mà hash table không trả lời được chút nào.

Các method điều hướng

import java.util.*;

public class Navigate {
    public static void main(String[] args) {
        TreeSet<Integer> t = new TreeSet<>(List.of(10, 20, 30, 40, 50));
        System.out.println("set          = " + t);
        System.out.println("first        = " + t.first());
        System.out.println("last         = " + t.last());
        System.out.println("floor(35)    = " + t.floor(35));
        System.out.println("floor(30)    = " + t.floor(30));
        System.out.println("ceiling(35)  = " + t.ceiling(35));
        System.out.println("ceiling(30)  = " + t.ceiling(30));
        System.out.println("lower(30)    = " + t.lower(30));
        System.out.println("higher(30)   = " + t.higher(30));
        System.out.println("floor(5)     = " + t.floor(5));
        System.out.println("ceiling(99)  = " + t.ceiling(99));
        System.out.println("headSet(30)  = " + t.headSet(30));
        System.out.println("headSet(30,t)= " + t.headSet(30, true));
        System.out.println("tailSet(30)  = " + t.tailSet(30));
        System.out.println("subSet(20,50)= " + t.subSet(20, 50));
        System.out.println("subSet incl  = " + t.subSet(20, true, 50, true));
        System.out.println("descendingSet= " + t.descendingSet());
    }
}

set          = [10, 20, 30, 40, 50]
first        = 10
last         = 50
floor(35)    = 30
floor(30)    = 30
ceiling(35)  = 40
ceiling(30)  = 30
lower(30)    = 20
higher(30)   = 40
floor(5)     = null
ceiling(99)  = null
headSet(30)  = [10, 20]
headSet(30,t)= [10, 20, 30]
tailSet(30)  = [30, 40, 50]
subSet(20,50)= [20, 30, 40]
subSet incl  = [20, 30, 40, 50]
descendingSet= [50, 40, 30, 20, 10]

Cả nhóm rút gọn về hai lựa chọn độc lập — đi hướng nào, và có tính trường hợp trùng khớp hay không:

Cả bốn trả về null khi không có gì thỏa mãn, đó là lý do floor(5) và ceiling(99) ra null ở trên. Các dạng mặc định của headSet/tailSet/subSet theo quy ước quen thuộc của Java là cận dưới inclusive và cận trên exclusive; các overload ba và bốn tham số cho phép bạn nói khác đi.

Mỗi lời gọi như vậy là một lần đi xuống theo tree, không phải quét. Một Comparator có bộ đếm cho thấy đường đi đó ngắn thế nào:

contains(30) comparisons = 3
contains(35) comparisons = 3
floor(35)    comparisons = 3
first()      comparisons = 0

Ba lần so sánh trong một set năm element, và first() không tốn lần nào — nó chỉ đi theo con trỏ trái tới hết. Đó là hình dạng của cả class này: O(log n) cho mọi thứ dựa trên giá trị, O(1) cho hai đầu.

Range view là view sống

headSet, tailSet, subSet và descendingSet không copy. Chúng trả về một view nằm trên cùng cái tree, và nó hoạt động theo cả hai chiều:

NavigableSet<Integer> view = t.tailSet(30, true);
t.add(45);
System.out.println("view is live = " + view);
view.remove(45);
System.out.println("backing set  = " + t);

System.out.println("pollFirst    = " + t.pollFirst() + " -> " + t);
System.out.println("pollLast     = " + t.pollLast() + " -> " + t);

view is live = [30, 40, 45, 50]
backing set  = [10, 20, 30, 40, 50]
pollFirst    = 10 -> [20, 30, 40, 50]
pollLast     = 50 -> [20, 30, 40]

Thêm 45 vào set gốc làm nó xuất hiện trong một view được tạo từ trước khi nó tồn tại, và xóa nó qua view thì nó biến khỏi set gốc. Thường thì đó đúng là thứ bạn muốn, thỉnh thoảng thì là một bất ngờ khó chịu: giữ một subSet sống là giữ luôn cả set gốc sống. Bọc lại bằng new TreeSet<>(view) khi bạn muốn một bản chụp.

pollFirst và pollLast xóa và trả về hai đầu, khiến TreeSet dùng được như một hàng đợi có sắp xếp khi bạn còn cần cả contains lẫn khả năng loại duplicate.

Hai quy tắc khác nhau để quyết định duplicate

Đây là phần quan trọng nhất. HashSet và TreeSet không dùng cùng một định nghĩa cho "đã có sẵn", và không compiler lẫn runtime nào báo cho bạn biết khi hai định nghĩa đó mâu thuẫn.

Instrument một element class để đếm mọi lời gọi nó nhận được, rồi add cùng bảy giá trị vào từng implementation:

import java.util.*;

class Probe implements Comparable<Probe> {
    static int hash = 0, eq = 0, cmp = 0;
    static void reset() { hash = eq = cmp = 0; }
    static String counts() { return "hashCode=" + hash + "  equals=" + eq + "  compareTo=" + cmp; }

    final int id;
    Probe(int id) { this.id = id; }

    @Override public int hashCode() { hash++; return Integer.hashCode(id); }
    @Override public boolean equals(Object o) { eq++; return o instanceof Probe p && id == p.id; }
    @Override public int compareTo(Probe o) { cmp++; return Integer.compare(id, o.id); }
}

public class WhoIsCalled {
    public static void main(String[] args) {
        int[] ids = {5, 3, 8, 1, 9, 3, 8};

        Probe.reset();
        Set<Probe> h = new HashSet<>();
        for (int i : ids) h.add(new Probe(i));
        System.out.println("HashSet  after 7 adds -> size " + h.size() + "   " + Probe.counts());

        Probe.reset();
        Set<Probe> t = new TreeSet<>();
        for (int i : ids) t.add(new Probe(i));
        System.out.println("TreeSet  after 7 adds -> size " + t.size() + "   " + Probe.counts());

        Probe.reset();
        h.contains(new Probe(9));
        System.out.println("HashSet  contains(#9)             " + Probe.counts());

        Probe.reset();
        t.contains(new Probe(9));
        System.out.println("TreeSet  contains(#9)             " + Probe.counts());
    }
}

HashSet  after 7 adds -> size 5   hashCode=7  equals=2  compareTo=0
TreeSet  after 7 adds -> size 5   hashCode=0  equals=0  compareTo=11
HashSet  contains(#9)             hashCode=1  equals=1  compareTo=0
TreeSet  contains(#9)             hashCode=0  equals=0  compareTo=3

Cả hai set đều kết thúc với năm element, và chúng đến đó bằng cách hỏi những method hoàn toàn rời nhau. TreeSet gọi equals() không lần nào. Không phải "hiếm khi" — là không bao giờ. Khái niệm duplicate của nó là compare(a, b) == 0, hết, và hashCode() cũng vô nghĩa với nó y như vậy.

Cũng để ý hai lần gọi equals ở phía HashSet: đúng bằng hai id bị lặp. equals chỉ được hỏi tới khi một hash collision đẩy hai element vào cùng một bucket, và đó là lý do một hashCode tốt đáng để viết.

Khi compareTo mâu thuẫn với equals

Document của Comparable gọi một phép so sánh là "consistent with equals" khi a.compareTo(b) == 0 khớp với a.equals(b), và nói thẳng rằng đây là điều rất khuyến nghị chứ không bắt buộc. Sorted collection chính là chỗ "không bắt buộc" biến thành mất dữ liệu.

Đây là một số phiên bản mà compareTo cố tình bỏ qua phần build:

import java.util.*;

class Version implements Comparable<Version> {
    final int major, minor;
    final String build;

    Version(int major, int minor, String build) {
        this.major = major; this.minor = minor; this.build = build;
    }

    @Override public boolean equals(Object o) {
        return o instanceof Version v && major == v.major && minor == v.minor && build.equals(v.build);
    }

    @Override public int hashCode() { return Objects.hash(major, minor, build); }

    // ignores build, so this is NOT consistent with equals
    @Override public int compareTo(Version o) {
        int c = Integer.compare(major, o.major);
        return c != 0 ? c : Integer.compare(minor, o.minor);
    }

    @Override public String toString() { return major + "." + minor + "+" + build; }
}

public class Conflict {
    public static void main(String[] args) {
        List<Version> versions = List.of(
                new Version(2, 1, "a1b2"),
                new Version(2, 1, "c3d4"),
                new Version(3, 0, "e5f6"));

        Set<Version> hash = new HashSet<>(versions);
        Set<Version> tree = new TreeSet<>(versions);

        System.out.println("added         = " + versions);
        System.out.println("HashSet size  = " + hash.size() + "  " + hash);
        System.out.println("TreeSet size  = " + tree.size() + "  " + tree);

        Version probe = new Version(2, 1, "zzzz");
        System.out.println("equals any?   = " + versions.stream().anyMatch(v -> v.equals(probe)));
        System.out.println("hash.contains = " + hash.contains(probe));
        System.out.println("tree.contains = " + tree.contains(probe));
    }
}

added         = [2.1+a1b2, 2.1+c3d4, 3.0+e5f6]
HashSet size  = 3  [2.1+a1b2, 3.0+e5f6, 2.1+c3d4]
TreeSet size  = 2  [2.1+a1b2, 3.0+e5f6]
equals any?   = false
hash.contains = false
tree.contains = true

Cùng ba object, add vào hai set trong cùng một chương trình: một cái giữ ba, cái kia giữ hai. Không có gì throw, không có cảnh báo nào, và 2.1+c3d4 đơn giản là biến mất khỏi TreeSet.

Ba dòng cuối còn tệ hơn. probe không equal với bất cứ thứ gì trong collection — kiểm tra bằng stream nói vậy, và HashSet đồng ý. TreeSet lại báo rằng nó có chứa probe, vì 2.1+zzzz so sánh bằng với 2.1+a1b2. Một TreeSet sẵn sàng nói với bạn rằng nó chứa một element mà theo mọi định nghĩa equality trong class của bạn thì nó không hề chứa.

Mâu thuẫn này còn chạy theo chiều ngược lại. Cho một class có equals rộng hơn compareTo thì đúng hai object mà HashSet gộp lại sẽ nằm tách nhau trong TreeSet:

class Coord implements Comparable<Coord> {
    final int x, y;
    Coord(int x, int y) { this.x = x; this.y = y; }

    @Override public boolean equals(Object o) { return o instanceof Coord c && x == c.x; }   // x only
    @Override public int hashCode() { return Integer.hashCode(x); }
    @Override public int compareTo(Coord o) {                                                // x then y
        int c = Integer.compare(x, o.x);
        return c != 0 ? c : Integer.compare(y, o.y);
    }
    @Override public String toString() { return "(" + x + "," + y + ")"; }
}

a.equals(b)     = true
a.compareTo(b)  = -1
HashSet         = [(1,1)]  size 1
TreeSet         = [(1,1), (1,2)]  size 2

Hai object tự nhận là equal nhau, nằm trong một set chứa cả hai. Quy tắc rút ra rất ngắn: nếu một class implement Comparable và có khả năng gặp sorted collection, hãy làm cho compareTo trả về 0 đúng với những cặp mà equals trả về true. Khi không làm được, đừng bỏ nó vào TreeSet.

Comparator khiến "duplicate" mang nghĩa gì tùy nó

Quy tắc trên áp dụng y nguyên cho Comparator truyền vào constructor, và chỗ này còn dễ vấp hơn vì comparator thường được viết để sort chứ không phải để định danh:

Set<String> ci = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
ci.addAll(List.of("Java", "java", "JAVA", "Kotlin"));

Set<String> byLength = new TreeSet<>(Comparator.comparingInt(String::length));
byLength.addAll(List.of("aa", "bb", "ccc"));

input                    = [Java, java, JAVA, Kotlin]
TreeSet natural          = [JAVA, Java, Kotlin, java]
TreeSet CASE_INSENSITIVE = [Java, Kotlin]
ci.contains("jAvA")      = true
plain.contains("jAvA")   = false
TreeSet by length        = [aa, ccc]   size 2

Set case-insensitive thì còn biện hộ được: ba cách viết của một từ gộp thành một entry thường đúng là mục đích, và đó là lý do người ta dựng lookup không phân biệt hoa thường theo kiểu này. Comparator theo độ dài thì là thảm họa — "bb" biến mất vì nó dài bằng "aa". Một comparator dùng với sorted set không phải là một thứ tự sắp xếp, nó là một hàm định danh, và bất kỳ comparator nào trả về 0 cho hai giá trị thật sự khác nhau đều sẽ lặng lẽ xóa dữ liệu.

⚠️ Comparator.comparing(...) trên một field không duy nhất là cách phổ biến nhất để mất element trong TreeSet. Hãy nối thêm một tiêu chí phụ bằng thenComparing trên thứ gì đó duy nhất.

Element bị sửa sau khi đã add

Cả hai implementation đều đặt element dựa trên hình dạng của nó tại thời điểm add. Sửa nó sau đó là nó nằm sai chỗ — nhưng hai kiểu hỏng trông khác nhau.

class Tag implements Comparable<Tag> {
    String name;   // mutable on purpose
    Tag(String name) { this.name = name; }

    @Override public boolean equals(Object o) { return o instanceof Tag t && name.equals(t.name); }
    @Override public int hashCode() { return name.hashCode(); }
    @Override public int compareTo(Tag o) { return name.compareTo(o.name); }
    @Override public String toString() { return name; }
}

Add aaa vào mỗi set cùng vài element hàng xóm, rồi đổi tên nó thành zzz khi nó đang nằm bên trong:

HashSet  = [zzz, ccc, bbb, ddd]
  size            = 4
  contains(same)  = false
  remove(same)    = false
  size after      = 4
TreeSet  = [zzz, bbb, ccc, ddd, eee, fff, ggg]
  size            = 7
  contains(same)  = false
  remove(same)    = false
  size after      = 7
  first()         = zzz
  iteration sees it = true

Trong HashSet, element được xếp theo hashCode cũ, nên một lần lookup sẽ hash "zzz", đi tới một bucket khác và không thấy gì. contains nói không, remove nói không, size nói bốn và toString vẫn in nó ra. Element đó không truy cập được và cũng không xóa được, chỉ còn iteration là nhìn thấy nó.

Trong TreeSet, nó cũng không truy cập được vì cùng lý do nhưng theo một cơ chế khác: lệnh tìm so sánh "zzz" với root rồi đi sang phải, trong khi node đang nằm bên trái, ở chỗ mà "aaa" từng thuộc về. Cái tree giờ đã sai về mặt cấu trúc — nhìn kết quả first() mà xem. Nó trả về zzz, vì first() không so sánh gì cả, nó chỉ đi theo con trỏ trái, và node ngoài cùng bên trái chính là node đã hỏng. Một TreeSet có element bị sửa không chỉ mất một element; bất biến về ordering của nó đã vỡ và những lần insert sau đó có thể rơi vào bất cứ đâu.

Element mutable không thuộc về set nào trong hai cái. Nếu một field tham gia vào equals, hashCode hay compareTo, hãy để nó final.

TreeSet từ chối cái gì: kiểu không Comparable và null

ClassCastException, và chính xác lúc nào nó nổ

Một TreeSet không có Comparator yêu cầu element của nó phải là Comparable, và compiler không kiểm tra điều đó — new TreeSet<Point>() compile ngon lành cho một Point không implement gì cả. Lỗi xảy ra lúc runtime:

class Point {
    final int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }
}

Set<Point> s = new TreeSet<>();
System.out.println("add first  = " + s.add(new Point(1, 1)));

Exception in thread "main" java.lang.ClassCastException: class Point cannot be cast to class java.lang.Comparable (Point is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
	at java.base/java.util.TreeMap.compare(TreeMap.java:1604)
	at java.base/java.util.TreeMap.addEntryToEmptyMap(TreeMap.java:811)
	at java.base/java.util.TreeMap.put(TreeMap.java:820)
	at java.base/java.util.TreeSet.add(TreeSet.java:259)
	at NoCompare.main(NoCompare.java:12)

Để ý nó đến từ đâu. Lệnh println chưa hề chạy, và frame là addEntryToEmptyMap — trên JDK này chính lần add đầu tiên đã throw, vì việc chèn vào một tree rỗng gọi compare(key, key) thuần túy như một phép kiểm tra kiểu. Nhiều tài liệu cũ nói exception đến ở lần add thứ hai, với lý do lần chèn đầu không có gì để so sánh; điều đó đúng với các JDK cũ hơn nhiều và không đúng ở đây. Hãy đọc tên frame trước khi tin bên nào.

Vẫn có một trường hợp hỏng ở lần add thứ hai, và nó là một bug khác. Khi từng element đều là Comparable nhưng không so sánh được với nhau, lần chèn đầu qua được kiểm tra kiểu và lần thứ hai nổ ngay bên trong compareTo của chính bạn:

add "a"  = true
size     = 1
now adding an Integer to a TreeSet that already holds a String
Exception in thread "main" java.lang.ClassCastException: class java.lang.String cannot be cast to class java.lang.Integer (java.lang.String and java.lang.Integer are in module java.base of loader 'bootstrap')
	at java.base/java.lang.Integer.compareTo(Integer.java:73)
	at java.base/java.util.TreeMap.put(TreeMap.java:849)
	at java.base/java.util.TreeSet.add(TreeSet.java:259)
	at MixedType.main(MixedType.java:9)

Stack frame là Integer.compareTo, không phải TreeMap.compare. Một TreeSet kiểu raw hoặc kiểu Object là con đường quen thuộc dẫn tới đây.

null

HashSet và LinkedHashSet chấp nhận đúng một null; TreeSet không chấp nhận cái nào.

HashSet add(null)   = true
HashSet add(null)#2 = false
HashSet             = [null]  size=1
HashSet contains    = true
LinkedHashSet       = [a, null, b]
TreeSet empty add(null) -> java.lang.NullPointerException: Cannot invoke "java.lang.Comparable.compareTo(Object)" because "k1" is null
TreeSet non-empty add(null) -> java.lang.NullPointerException
TreeSet contains(null) -> java.lang.NullPointerException
TreeSet w/ nullsFirst comparator = [null, a, b]

null là một element hợp lệ trong set dựa trên hash — nó được xử lý đặc biệt để rơi vào bucket 0 — và một null thứ hai bị từ chối như một duplicate bình thường.

Mấy dòng TreeSet trả lời một câu hỏi đáng hỏi: set rỗng hay không có ảnh hưởng gì không? Kết quả thì không — cả hai đều throw — nhưng exception thì có, và khác biệt đó cho biết bạn đã rơi vào nhánh code nào:

Message hữu ích ở set rỗng là một helpful-NullPointerException sinh ra từ bytecode; ở set không rỗng thì lệnh kiểm tra null tường minh nổ trước và bạn không nhận được gì. contains(null) cũng throw, khiến TreeSet khá vướng trong mọi nhánh code có thể chứa null một cách hợp lệ.

Dòng cuối là lối thoát: việc từ chối null đến từ natural ordering chứ không phải từ bản thân TreeSet. Đưa cho nó Comparator.nullsFirst(Comparator.naturalOrder()) là null trở thành một element bình thường.

EnumSet: Set đúng đắn cho element là enum

Khi kiểu element là enum thì không cái nào trong ba cái trên là câu trả lời đúng. EnumSet là một abstract class không có public constructor, chỉ có một loạt factory, và nó lưu trạng thái thành viên bằng bit thay vì bằng object:

enum Perm { READ, WRITE, EXECUTE, DELETE }

EnumSet<Perm> e = EnumSet.noneOf(Perm.class);
e.add(Perm.DELETE); e.add(Perm.READ); e.add(Perm.EXECUTE);

EnumSet inserted DELETE,READ,EXECUTE -> [READ, EXECUTE, DELETE]
class          = java.util.RegularEnumSet
complementOf   = [WRITE]
range(R,E)     = [READ, WRITE, EXECUTE]
HashSet same   = [READ, DELETE, EXECUTE]
add(null)      -> java.lang.NullPointerException: Cannot invoke "Object.getClass()" because "e" is null
f retain e     = [READ]

Ba thứ trong output đó là lý do để dùng nó. Iteration theo thứ tự khai báo bất kể thứ tự add, và đây là một đảm bảo thật chứ không phải may mắn — so với dòng HashSet dựng từ đúng ba constant đó mà xem. complementOf và range là những operation chỉ có nghĩa khi tập vũ trụ của các element được biết trước. Và null bị từ chối thẳng, vì không có vị trí bit nào cho một constant không có ordinal.

Bạn nhận được implementation nào là tùy vào enum khai báo bao nhiêu constant, và ranh giới rất chính xác:

63 constants -> java.util.RegularEnumSet
64 constants -> java.util.RegularEnumSet
65 constants -> java.util.JumboEnumSet

RegularEnumSet giữ toàn bộ set trong một long, mỗi constant một bit, nên 64 là kích thước cuối cùng còn vừa; tới 65 thì factory chuyển sang JumboEnumSet và một mảng long. Vậy một Set gồm 64 enum constant tốn tám byte dữ liệu, chỗ mà một HashSet sẽ tốn một table cộng 64 node object.

Đại số tập hợp: union, intersection và difference

Ba method bulk trên Collection chính là đại số tập hợp dưới tên khác, và cả ba đều sửa trực tiếp đối tượng gọi:

Set<String> a = new LinkedHashSet<>(List.of("red", "green", "blue", "cyan"));
Set<String> b = new LinkedHashSet<>(List.of("blue", "cyan", "magenta"));

Set<String> union = new LinkedHashSet<>(a);        union.addAll(b);
Set<String> intersection = new LinkedHashSet<>(a); intersection.retainAll(b);
Set<String> difference = new LinkedHashSet<>(a);   difference.removeAll(b);

A                    = [red, green, blue, cyan]
B                    = [blue, cyan, magenta]
A union B            = [red, green, blue, cyan, magenta]
A intersect B        = [blue, cyan]
A minus B            = [red, green]
symmetric difference = [red, green, magenta]
A unchanged          = [red, green, blue, cyan]
containsAll(subset)  = true

Hãy copy trước, như ở trên. Mỗi method này đều ghi thẳng vào set bạn gọi nó, và một removeAll nhầm đối tượng là bug mất dữ liệu nhưng đọc lên thì giống một câu truy vấn.

Vì sao removeAll có thể thành quadratic

AbstractSet.removeAll chọn giữa hai thuật toán hoàn toàn khác nhau dựa trên collection nào lớn hơn. Bytecode nói rõ điều đó:

  public boolean removeAll(java.util.Collection<?>);
    Code:
       7: aload_0
       8: invokevirtual #15                 // Method size:()I
      11: aload_1
      12: invokeinterface #11,  1           // InterfaceMethod java/util/Collection.size:()I
      17: if_icmple     59
      ...
      48: invokevirtual #52                 // Method remove:(Ljava/lang/Object;)Z
      ...
      80: invokeinterface #56,  2           // InterfaceMethod java/util/Collection.contains:(Ljava/lang/Object;)Z

this.size() so với c.size(), rồi rẽ nhánh. Nếu set lớn hơn, nó duyệt tham số và gọi remove của chính nó — mỗi lần là một lần hash lookup. Nếu set không lớn hơn, nó duyệt chính nó và gọi c.contains trên từng element. Khi c là một List, đó là một lần quét tuyến tính cho mỗi element.

Instrument element class vào là khác biệt không hề tinh tế. Mỗi dòng là một lời gọi removeAll, đếm số lần equals() được gọi:

set 1000, arg ArrayList 2000  (set <= arg)     set=1000  arg=2000  equals calls=500500
set 1000, arg HashSet   2000  (set <= arg)     set=1000  arg=2000  equals calls=1000
set 3000, arg ArrayList 2000  (set >  arg)     set=3000  arg=2000  equals calls=2000
set 2000, arg ArrayList 2000  (set == arg)     set=2000  arg=2000  equals calls=2001000
set 2001, arg ArrayList 2000  (set >  arg by 1) set=2001  arg=2000  equals calls=2000

Đọc hai dòng cuối cùng lúc. Cùng tham số, cùng dữ liệu, set nhiều hơn đúng một element — 2.001.000 lần gọi equals so với 2.000. Khối lượng công việc đổi gấp nghìn lần chỉ vì thêm một element, bởi element đó lật size() > c.size() từ false thành true và đổi luôn thuật toán.

Dòng thứ hai là cách sửa: truyền một HashSet thay vì ArrayList làm tham số biến c.contains thành lời gọi hằng số thời gian và con số rơi từ 500.500 xuống 1.000 — một equals cho mỗi element, tức là mức sàn.

Quy tắc gói trong một dòng: removeAll và retainAll gọi contains trên tham số của chúng, nên tham số nên là một collection dựa trên hash. set.removeAll(someList) là hình dạng cần soi khi review code.

Chọn implementation nào

Mặc định hãy dùng HashSet. Chuyển sang LinkedHashSet khi thứ tự output có ý nghĩa hoặc cần tái lập được, mà chuyện này xảy ra nhiều hơn người ta tưởng — log ổn định và test fixture ổn định đều cần nó, và nó rẻ. Chỉ chuyển sang TreeSet khi bạn cần sorted iteration ở mọi lần đọc, hoặc cần các truy vấn lân cận của NavigableSet. Dùng EnumSet bất cứ khi nào element là enum constant.

FAQ

HashSet, LinkedHashSet và TreeSet trong Java khác nhau ở đâu?

Cả ba đều loại duplicate; khác nhau ở ordering và chi phí. HashSet không đảm bảo ordering và cho operation O(1) trung bình. LinkedHashSet thêm một doubly-linked list xuyên qua các entry để có insertion order, đổi lấy hai reference cho mỗi element. TreeSet giữ element sorted trong một red-black tree với operation O(log n), và là cái duy nhất hỗ trợ truy vấn lân cận và truy vấn khoảng.

HashSet có giữ thứ tự không?

Không. Thứ tự iteration không được quy định và có thể đổi khi table resize, khi đổi JDK, hoặc với kiểu element khác. Nó thường trông ổn định qua các lần chạy của một chương trình trên một JDK, và đó chính là thứ khiến việc dựa vào nó nguy hiểm. Set.of cố tình đổi thứ tự giữa các lần chạy JVM để chặn thói quen đó hình thành.

Vì sao TreeSet của tôi làm mất element dù chúng không equal nhau?

Vì TreeSet quyết định duplicate bằng compareTo hoặc một Comparator, và không bao giờ gọi equals. Hai element bất kỳ mà phép so sánh trả về 0 là một element đối với TreeSet, dù equals nói chúng khác nhau đến đâu. Nguyên nhân hay gặp nhất là Comparator.comparing trên một field không duy nhất; hãy thêm một thenComparing trên thứ gì đó duy nhất.

TreeSet có chứa được null không?

Không, với natural ordering — add(null) throw NullPointerException, và contains(null) cũng vậy. Nó chạy được nếu bạn cấp một comparator chịu được null như Comparator.nullsFirst(Comparator.naturalOrder()). HashSet và LinkedHashSet chấp nhận đúng một element null mà không cần cấu hình gì.

Vì sao TreeSet throw ClassCastException?

Vì kiểu element không implement Comparable và cũng không có Comparator nào được cấp. Trên OpenJDK 21, nó throw ngay ở lần add đầu tiên, trong TreeMap.addEntryToEmptyMap, chỗ gọi compare(key, key) như một phép kiểm tra kiểu. Một ClassCastException khác ở lần add thứ hai nghĩa là các element đều Comparable nhưng không so sánh được với nhau, chẳng hạn một String và một Integer trong cùng một set.

Nên dùng Set nào cho giá trị enum?

EnumSet. Nó iterate theo thứ tự khai báo, lưu trạng thái thành viên bằng bit — một long cho tới 64 constant, một mảng long từ 65 trở lên — và cung cấp complementOf, range, allOf và noneOf, những thứ mà một set đa dụng không làm được. Nó từ chối null.

Làm union hoặc intersection của hai set trong Java thế nào?

Copy một set rồi gọi method bulk trên bản copy: addAll cho union, retainAll cho intersection, removeAll cho difference. Không có method cho symmetric difference; hãy addAll rồi removeAll phần intersection. Hãy để tham số là một HashSet chứ đừng là List, vì removeAll và retainAll gọi contains trên nó.

HashSet có thread-safe không?

Không, LinkedHashSet và TreeSet cũng không. Bọc lại bằng Collections.synchronizedSet(...), cái này cho ra một java.util.Collections$SynchronizedSet, hoặc dùng ConcurrentHashMap.newKeySet(), cái này trả về một ConcurrentHashMap$KeySetView và là set concurrent mà JDK thực sự muốn bạn dùng.

Kết luận

Set đảm bảo đúng một điều — không duplicate — và mọi khác biệt giữa các implementation đều là một câu trả lời khác cho "cái gì được tính là duplicate, và tôi nhận được thứ tự nào". HashSet là một HashMap với đúng một object giả dùng chung ở mọi slot, điều mà bytecode của add phơi ra trong năm lệnh và giải thích trọn vẹn chi phí của nó. LinkedHashSet mua insertion order bằng hai reference cho mỗi element. TreeSet là một red-black tree, và nó đáng giá O(log n) không phải vì sorted iteration mà vì floor, ceiling, headSet cùng phần còn lại của NavigableSet.

Thứ đáng mang theo nhất là chỗ rẽ đôi trong quy tắc equality. HashSet hỏi hashCode và equals; TreeSet hỏi compareTo và không gọi equals lần nào — con số đếm được là 0, không phải nhỏ. Một compareTo mâu thuẫn với equals cho ra hai kích thước set khác nhau từ cùng ba object, một cách lặng lẽ. Thêm vào đó là kỷ luật về mutation: một element bị sửa sau khi add là không truy cập được trong HashSet và làm một TreeSet sai cấu trúc.

Bài tiếp theo vẫn ở trong collections framework và chuyển sang các map: TreeMap, LinkedHashMap, Hashtable cũ kỹ và ConcurrentHashMap — bao gồm cả việc TreeMap cho bạn đúng những method điều hướng bạn vừa gặp ở TreeSet, và vì sao ConcurrentHashMap không đơn giản là một HashMap được synchronized.