Set Interface

Mục tiêu bài học

Sau bài này, bạn sẽ:

• Hiểu Set interface - collection không chứa duplicates, mô phỏng tập hợp toán học
• So sánh HashSet (O(1), unordered), LinkedHashSet (insertion-ordered), TreeSet (sorted, O(log n))
• Nắm vững equals() và hashCode() contract - phải override cả hai cho custom objects
• Thực hiện các set operations: union, intersection, difference, symmetric difference
• Áp dụng Set để remove duplicates, membership testing, và unique element problems

Bài trước: List Interface — Đã học về List với ArrayList và LinkedList. Bài này sẽ tìm hiểu Set - collection không chứa phần tử trùng lặp.

Set Interface là gì?

Set là một interface trong Collections Framework đại diện cho một tập hợp không chứa phần tử trùng lặp (no duplicates), mô phỏng theo khái niệm tập hợp trong toán học.

Đặc điểm chính

• No duplicates: Mỗi phần tử chỉ xuất hiện tối đa một lần
• Unordered (phụ thuộc implementation): Không đảm bảo thứ tự
• At most one null: Chỉ chứa tối đa một phần tử null (HashSet, LinkedHashSet)
• Fast lookup: Kiểm tra sự tồn tại nhanh chóng

public interface Set<E> extends Collection<E> {
    // Không có method mới ngoài Collection
    // Nhưng hành vi khác: không cho phép duplicates

    boolean add(E e);        // Trả về false nếu đã tồn tại
    boolean contains(Object o);
    boolean remove(Object o);
    int size();
    // ...
}

HashSet - Hash Table Implementation

HashSet là implementation phổ biến nhất của Set, sử dụng hash table (thực chất là HashMap bên trong).

HashSet IS a HashMap Internally!

Một sự thật ít người biết: HashSet chỉ là wrapper của HashMap:

// Simplified HashSet source code
public class HashSet<E> {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object();  // Dummy value

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
        // Phần tử là KEY, value luôn là PRESENT
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }
}

Cơ chế:

• HashSet lưu elements làm keys của HashMap
• Mọi key đều map to cùng một dummy object PRESENT
• HashSet operations = HashMap key operations

Set<String> set = new HashSet<>();
set.add("Apple");   // Thực chất: map.put("Apple", PRESENT)
set.contains("Apple");  // Thực chất: map.containsKey("Apple")
set.remove("Apple");    // Thực chất: map.remove("Apple")

💡 Cách nhớ: HashSet = "HashMap vứt bỏ values"

HashSet giống như HashMap chỉ quan tâm keys, vứt bỏ values. Mọi value đều là một dummy object vô nghĩa (PRESENT). HashSet = HashMap<E, IGNORED_DUMMY_VALUE>

Đặc điểm

• Unordered: Không đảm bảo thứ tự
• Fast operations: O(1) cho add, remove, contains (average case)
• Allows one null: Chấp nhận một phần tử null
• Not thread-safe
• Dựa vào equals() và hashCode(): Rất quan trọng!

import java.util.*;

public class HashSetDemo {
    public static void main(String[] args) {
        Set<String> fruits = new HashSet<>();

        // Thêm phần tử
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Cherry");
        fruits.add("Apple");    // Duplicate - không thêm được
        System.out.println("Size: " + fruits.size());  // 3, không phải 4

        // Thứ tự không được đảm bảo
        System.out.println(fruits);  // Có thể là [Banana, Apple, Cherry]

        // Kiểm tra tồn tại - rất nhanh O(1)
        boolean hasApple = fruits.contains("Apple");  // true

        // Xóa phần tử
        fruits.remove("Banana");

        // Null được chấp nhận
        fruits.add(null);
        System.out.println(fruits);  // [null, Apple, Cherry]

        // Iteration
        for (String fruit : fruits) {
            System.out.println(fruit);
        }
    }
}

Performance của HashSet

Operation	Time Complexity	Note
add(element)	O(1) average	Có thể O(n) khi resize
remove(element)	O(1) average	Hash collision có thể làm chậm
contains(element)	O(1) average	Rất nhanh
size()	O(1)
Iteration	O(n)

Capacity và Load Factor

HashSet có 2 tham số quan trọng:

• Initial capacity: Kích thước ban đầu (mặc định 16)
• Load factor: Tỷ lệ đầy (mặc định 0.75)

Khi size > capacity * loadFactor, HashSet sẽ resize (tăng gấp đôi capacity).

// Mặc định: capacity=16, loadFactor=0.75
Set<String> set1 = new HashSet<>();

// Custom capacity
Set<String> set2 = new HashSet<>(100);

// Custom capacity và loadFactor
Set<String> set3 = new HashSet<>(100, 0.8f);

LinkedHashSet - Ordered Hash Table

LinkedHashSet extends HashSet và duy trì insertion order (thứ tự thêm vào).

Đặc điểm

• Insertion-ordered: Duy trì thứ tự thêm vào
• Performance tương tự HashSet: O(1) cho add, remove, contains
• Tốn bộ nhớ hơn HashSet: Cần thêm doubly-linked list
• Allows one null

import java.util.*;

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        Set<String> fruits = new LinkedHashSet<>();

        fruits.add("Banana");
        fruits.add("Apple");
        fruits.add("Cherry");
        fruits.add("Banana");  // Duplicate - không thêm được

        // Thứ tự được duy trì theo insertion order
        System.out.println(fruits);  // [Banana, Apple, Cherry]

        // Iteration theo thứ tự thêm vào
        for (String fruit : fruits) {
            System.out.println(fruit);
        }
        // Output:
        // Banana
        // Apple
        // Cherry
    }
}

TreeSet - Sorted Set

TreeSet là implementation dựa trên Red-Black Tree (self-balancing binary search tree), tự động sắp xếp các phần tử.

Đặc điểm

• Sorted: Tự động sắp xếp (natural order hoặc Comparator)
• No null: KHÔNG chấp nhận null (sẽ throw NullPointerException)
• Slower than HashSet: O(log n) cho add, remove, contains
• NavigableSet: Hỗ trợ navigation methods (higher, lower, ceiling, floor)

import java.util.*;

public class TreeSetDemo {
    public static void main(String[] args) {
        // Natural order (alphabetical)
        Set<String> fruits = new TreeSet<>();
        fruits.add("Banana");
        fruits.add("Apple");
        fruits.add("Cherry");
        fruits.add("Avocado");

        System.out.println(fruits);  // [Apple, Avocado, Banana, Cherry] - sorted!

        // Numbers - sorted ascending
        Set<Integer> numbers = new TreeSet<>();
        numbers.add(5);
        numbers.add(2);
        numbers.add(8);
        numbers.add(1);
        System.out.println(numbers);  // [1, 2, 5, 8]

        // Custom comparator - descending order
        Set<Integer> descNumbers = new TreeSet<>(Comparator.reverseOrder());
        descNumbers.add(5);
        descNumbers.add(2);
        descNumbers.add(8);
        descNumbers.add(1);
        System.out.println(descNumbers);  // [8, 5, 2, 1]

        // NavigableSet methods
        NavigableSet<Integer> navSet = new TreeSet<>(Arrays.asList(1, 3, 5, 7, 9));
        System.out.println(navSet.lower(5));    // 3 (strictly less than 5)
        System.out.println(navSet.floor(5));    // 5 (less than or equal)
        System.out.println(navSet.ceiling(6));  // 7 (greater than or equal)
        System.out.println(navSet.higher(5));   // 7 (strictly greater than 5)

        // Range views
        System.out.println(navSet.headSet(5));     // [1, 3] (< 5)
        System.out.println(navSet.tailSet(5));     // [5, 7, 9] (>= 5)
        System.out.println(navSet.subSet(3, 8));   // [3, 5, 7] (>= 3, < 8)
    }
}

TreeSet Comparator Contract Gotcha

TreeSet sử dụng Comparator (hoặc Comparable) để xác định equality, KHÔNG dùng equals()!

Rule: comparator.compare(a, b) == 0 → TreeSet coi a và b là "equal" (duplicate), dù a.equals(b) có thể false!

class Person {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Person)) return false;
        Person p = (Person) o;
        return age == p.age && Objects.equals(name, p.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public String toString() {
        return name + "(" + age + ")";
    }
}

// TreeSet với Comparator chỉ compare theo age
Set<Person> people = new TreeSet<>(Comparator.comparingInt(p -> p.age));

people.add(new Person("Alice", 25));
people.add(new Person("Bob", 30));
people.add(new Person("Charlie", 25));  // Cùng age với Alice!

System.out.println(people);
// Output: [Alice(25), Bob(30)]
// Charlie KHÔNG được thêm vào vì comparator.compare(Charlie, Alice) == 0
// TreeSet coi Charlie == Alice dù !charlie.equals(alice)!

// Kiểm tra contains cũng dùng Comparator
System.out.println(people.contains(new Person("David", 25)));  // true!
// Vì comparator.compare(David(25), Alice(25)) == 0

🔥 Bẫy OCP: TreeSet "mất" elements

Set<Person> people = new TreeSet<>(Comparator.comparing(Person::getName));

people.add(new Person("Alice", 25));
people.add(new Person("Alice", 30));  // Cùng name, khác age

System.out.println(people.size());  // Output: 1 (not 2!)
// Person("Alice", 30) không được add vì comparator coi nó bằng Person("Alice", 25)

// Đây là bug nếu bạn muốn lưu cả hai!

Fix: Comparator phải compare tất cả distinguishing fields:

Set<Person> people = new TreeSet<>(
    Comparator.comparing(Person::getName)
              .thenComparingInt(Person::getAge)
);

people.add(new Person("Alice", 25));
people.add(new Person("Alice", 30));

System.out.println(people.size());  // Output: 2 - correct!

💡 Cách nhớ: TreeSet dùng Comparator làm "luật so sánh"

TreeSet giống như người bảo vệ cổng chỉ nhận diện người bằng một đặc điểm (Comparator). Nếu Comparator chỉ so sánh tuổi, hai người cùng tuổi sẽ bị coi là cùng một người, dù tên khác nhau!

NavigableSet Methods - Chi tiết

NavigableSet (implemented by TreeSet) cung cấp các navigation methods để tìm phần tử gần nhất:

NavigableSet<Integer> set = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50));
//                                                        ↑
//                                         Assume target = 35 (không tồn tại trong set)

// lower(e): Phần tử lớn nhất < e (strictly less)
System.out.println(set.lower(35));    // 30 (< 35)
System.out.println(set.lower(30));    // 20 (< 30, không bằng 30)
System.out.println(set.lower(10));    // null (không có phần tử < 10)

// floor(e): Phần tử lớn nhất <= e (less than or equal)
System.out.println(set.floor(35));    // 30 (<= 35)
System.out.println(set.floor(30));    // 30 (= 30)
System.out.println(set.floor(5));     // null (không có phần tử <= 5)

// ceiling(e): Phần tử nhỏ nhất >= e (greater than or equal)
System.out.println(set.ceiling(35));  // 40 (>= 35)
System.out.println(set.ceiling(40));  // 40 (= 40)
System.out.println(set.ceiling(60));  // null (không có phần tử >= 60)

// higher(e): Phần tử nhỏ nhất > e (strictly greater)
System.out.println(set.higher(35));   // 40 (> 35)
System.out.println(set.higher(40));   // 50 (> 40, không bằng 40)
System.out.println(set.higher(50));   // null (không có phần tử > 50)

// Comparison table
//             lower(35)  floor(35)  ceiling(35)  higher(35)
// Set: [10, 20, 30, 40, 50]
//              ↑30        ↑30         ↑40          ↑40
//              <          <=          >=           >

Mnemonic:

• lower/floor → tìm bên trái (smaller)
• ceiling/higher → tìm bên phải (larger)
• lower/higher → strictly (nhỏ hơn, lớn hơn)
• floor/ceiling → inclusive (nhỏ hơn hoặc bằng, lớn hơn hoặc bằng)

// pollFirst() và pollLast() - lấy và xóa
NavigableSet<Integer> set = new TreeSet<>(Arrays.asList(10, 20, 30));
System.out.println(set.pollFirst());  // 10 - remove và return smallest
System.out.println(set.pollLast());   // 30 - remove và return largest
System.out.println(set);              // [20]

// descendingSet() - reversed view
NavigableSet<Integer> desc = set.descendingSet();
System.out.println(desc);  // [20] - reversed (nhưng chỉ có 1 element)

// subSet, headSet, tailSet với inclusive/exclusive control
set = new TreeSet<>(Arrays.asList(10, 20, 30, 40, 50));
System.out.println(set.subSet(20, false, 40, true));  // (20, 40] = [30, 40]
System.out.println(set.headSet(30, true));            // [10, 20, 30]
System.out.println(set.tailSet(30, false));           // (30, ∞) = [40, 50]

### Performance của TreeSet

| Operation | Time Complexity | Note |
|-----------|----------------|------|
| `add(element)` | O(log n) | Binary search tree |
| `remove(element)` | O(log n) | |
| `contains(element)` | O(log n) | Chậm hơn HashSet |
| `first()`, `last()` | O(log n) | |
| Iteration | O(n) | Sorted iteration |

## HashMap Bucket Structure Diagram

Sơ đồ minh họa internal structure của HashMap (và HashSet vì HashSet = HashMap bên trong):

```mermaid
graph TD
    A["HashMap/HashSet Array"] --> B0["Bucket 0: null"]
    A --> B1["Bucket 1: LinkedList"]
    A --> B2["Bucket 2: Red-Black Tree"]
    A --> B3["Bucket 3: Single Node"]
    A --> B4["Bucket 4-15: ..."]

    B1 --> N1["Node: hash=17, key='Alice', next→"]
    N1 --> N2["Node: hash=49, key='Bob', next→"]
    N2 --> N3["Node: hash=81, key='Charlie', next=null"]

    B2 --> T["TreeNode: root (hash=5)"]
    T --> TL["TreeNode: left (hash=2)"]
    T --> TR["TreeNode: right (hash=8)"]
    TL --> TLL["TreeNode: ..."]
    TR --> TRR["TreeNode: ..."]

    B3 --> S["Node: hash=99, key='David', next=null"]

    style B1 fill:#ccffcc
    style B2 fill:#ffcccc
    style B3 fill:#ccccff
    style B0 fill:#eeeeee

Chú thích:

• Bucket 0 (null): Không có phần tử nào hash về bucket này
• Bucket 1 (LinkedList): 3 phần tử collision, stored as linked list (≤8 elements)
• Bucket 2 (Red-Black Tree): >8 phần tử collision, converted to tree for O(log n)
• Bucket 3 (Single Node): Chỉ có 1 phần tử, không có collision

Process:

1. hashCode() của key → hash value
2. hash & (n-1) → bucket index (n = array length)
3. Tìm trong bucket: LinkedList (O(n)) hoặc Tree (O(log n))
4. So sánh equals() để tìm exact match

So sánh 3 Implementations

Đặc điểm	HashSet	LinkedHashSet	TreeSet
Cấu trúc	Hash table	Hash table + Linked list	Red-Black Tree
Ordering	Unordered	Insertion order	Sorted (natural/custom)
Null	1 null OK	1 null OK	NO null
Performance	O(1) add/remove/contains	O(1) add/remove/contains	O(log n) add/remove/contains
Memory	Ít nhất	Trung bình	Nhiều nhất
Use case	General purpose, nhanh nhất	Cần duy trì insertion order	Cần sắp xếp tự động
Thread-safe	No	No	No

Khi nào dùng implementation nào?

// HashSet - Default choice, nhanh nhất
Set<String> uniqueIds = new HashSet<>();  // ✅ Chỉ cần unique, không quan tâm thứ tự

// LinkedHashSet - Cần duy trì thứ tự thêm vào
Set<String> visitedPages = new LinkedHashSet<>();  // ✅ Track navigation history

// TreeSet - Cần tự động sắp xếp
Set<Integer> sortedScores = new TreeSet<>();  // ✅ Luôn muốn scores theo thứ tự

equals() và hashCode() Contract - RẤT QUAN TRỌNG!

Đây là một trong những khái niệm quan trọng nhất khi làm việc với HashSet (và HashMap).

The Contract - 3 Rules

Rule 1: Nếu a.equals(b) = true, thì a.hashCode() PHẢI bằng b.hashCode() Rule 2: Nếu a.hashCode() != b.hashCode(), thì a.equals(b) PHẢI là false Rule 3: Nếu a.hashCode() == b.hashCode(), a.equals(b) có thể true HOẶC false (hash collision OK)

equals() = true  →  hashCode() PHẢI giống nhau
hashCode() khác  →  equals() PHẢI false
hashCode() giống →  equals() có thể true/false (collision)

equals/hashCode Contract Flowchart

Giải thích:

• equals true → hashCode equal: MANDATORY (nếu vi phạm, HashSet break!)
• hashCode khác → equals false: MANDATORY
• hashCode giống → equals có thể true/false: Hash collision là OK

Nếu vi phạm contract này, HashSet sẽ hoạt động không đúng!

// ❌ SAI: Vi phạm equals/hashCode contract
class Person {
    String name;
    int age;

    // Chỉ override equals
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Person)) return false;
        Person person = (Person) o;
        return age == person.age && name.equals(person.name);
    }

    // KHÔNG override hashCode - BUG!
}

// Test
Set<Person> people = new HashSet<>();
Person p1 = new Person("Alice", 25);
Person p2 = new Person("Alice", 25);

people.add(p1);
people.add(p2);  // Sẽ thêm vào dù p1.equals(p2) = true!
System.out.println(people.size());  // 2 - WRONG!

Cách đúng: Override cả equals() và hashCode()

// ✅ ĐÚNG: Override cả equals() và hashCode()
class Person {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Person)) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);  // Java 7+
    }

    @Override
    public String toString() {
        return name + "(" + age + ")";
    }
}

// Test
Set<Person> people = new HashSet<>();
Person p1 = new Person("Alice", 25);
Person p2 = new Person("Alice", 25);

people.add(p1);
people.add(p2);  // Không thêm vào vì p1.equals(p2) và hashCode giống nhau
System.out.println(people.size());  // 1 - CORRECT!
System.out.println(people.contains(new Person("Alice", 25)));  // true

Quy tắc vàng

Luôn luôn override cả equals() và hashCode() cùng nhau!

IDE hiện đại (IntelliJ, Eclipse) có thể tự generate cho bạn. Hoặc dùng Lombok @EqualsAndHashCode.

equals/hashCode Contract Deep Dive

Case 1: Override equals nhưng KHÔNG override hashCode - BUG!

class Person {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // Chỉ override equals
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Person)) return false;
        Person p = (Person) o;
        return age == p.age && Objects.equals(name, p.name);
    }

    // KHÔNG override hashCode - VÀ PHẠM CONTRACT!
    // hashCode() sử dụng default implementation (memory address)
}

// Test
Set<Person> people = new HashSet<>();
Person p1 = new Person("Alice", 25);
Person p2 = new Person("Alice", 25);

System.out.println("p1.equals(p2): " + p1.equals(p2));  // Output: true
System.out.println("p1.hashCode(): " + p1.hashCode());  // Output: 123456 (random)
System.out.println("p2.hashCode(): " + p2.hashCode());  // Output: 789012 (random, KHÁC nhau!)

people.add(p1);
people.add(p2);  // Sẽ add cả hai dù equals() = true!
System.out.println(people.size());  // Output: 2 - WRONG! (Should be 1)

// Tìm kiếm cũng fail
System.out.println(people.contains(new Person("Alice", 25)));  // Output: false - WRONG!

Giải thích: HashSet dùng hashCode() để xác định bucket, rồi mới dùng equals(). Vì p1.hashCode() != p2.hashCode(), HashSet nghĩ chúng khác nhau trước khi gọi equals().

Case 2: Mutable Key Danger - Lost in HashSet!

class MutablePerson {
    String name;
    int age;

    public MutablePerson(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof MutablePerson)) return false;
        MutablePerson p = (MutablePerson) o;
        return age == p.age && Objects.equals(name, p.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    // Setters cho phép mutation
    public void setAge(int age) {
        this.age = age;
    }
}

// Test
Set<MutablePerson> people = new HashSet<>();
MutablePerson alice = new MutablePerson("Alice", 25);

people.add(alice);
System.out.println("Contains Alice(25): " + people.contains(alice));  // Output: true

// Thay đổi age → hashCode thay đổi!
int oldHash = alice.hashCode();
alice.setAge(26);
int newHash = alice.hashCode();
System.out.println("HashCode changed: " + oldHash + " → " + newHash);

// Object bị "lost" trong HashSet!
System.out.println("Contains Alice(26): " + people.contains(alice));  // Output: false - LOST!
System.out.println("Contains new Person('Alice', 26): " +
    people.contains(new MutablePerson("Alice", 26)));  // Output: false

// HashSet nghĩ alice vẫn ở bucket cũ (oldHash), nhưng alice.hashCode() đã thay đổi!
// → Tìm ở bucket sai → không tìm thấy

🔥 Bẫy OCP: Mutable objects trong HashSet

class Student {
    String name;
    double gpa;

    // equals/hashCode dựa trên name và gpa

    public void setGpa(double gpa) {
        this.gpa = gpa;
    }
}

Set<Student> students = new HashSet<>();
Student alice = new Student("Alice", 3.5);
students.add(alice);

alice.setGpa(3.8);  // Mutation → hashCode changed!

// Alice bị "lost" trong HashSet
students.contains(alice);  // false - can't find anymore!
students.remove(alice);    // false - can't remove!

// HashSet bị "leak" - object tồn tại nhưng không access được!
System.out.println(students.size());  // 1 - vẫn có element
System.out.println(students.contains(alice));  // false - nhưng không tìm được!

Giải thích: Khi add alice vào HashSet với gpa=3.5, alice được lưu ở bucket tương ứng với hashCode(name="Alice", gpa=3.5). Khi change gpa→3.8, hashCode() thay đổi nhưng alice vẫn ở bucket cũ. HashSet tìm ở bucket mới (với gpa=3.8) → không thấy!

Mutable Key Danger Diagram

Kết quả: Object bị "lost" - tồn tại trong HashSet nhưng không thể tìm thấy hoặc xóa được!

💡 Cách nhớ: Mutable key = "Thay chìa khóa nhà"

Mutable object trong HashSet giống như thay chìa khóa nhà sau khi cất vào két. Khi bạn muốn lấy ra, bạn dùng chìa khóa mới (hashCode mới), nhưng két vẫn khóa bằng chìa cũ (hashCode cũ) → mở không được!

Rule of thumb: Objects trong HashSet/HashMap key nên immutable (final fields, no setters).

Hash Collision Handling - Chaining → Red-Black Tree (Java 8+)

Khi nhiều objects có cùng hashCode (hash collision), HashMap/HashSet xử lý như sau:

Phase 1: Chaining với LinkedList

• Ban đầu, colliding elements được lưu trong LinkedList ở cùng bucket
• Tìm kiếm: O(n) trong chain (n = số phần tử trong bucket)

Phase 2: Treeify - Chuyển sang Red-Black Tree (Java 8+)

• Khi một bucket có > 8 elements VÀ total capacity >= 64, chain được convert thành Red-Black Tree
• Tìm kiếm cải thiện: O(log n) thay vì O(n)

// Simplified internal structure
class HashMap<K, V> {
    static class Node<K,V> {  // LinkedList node
        final int hash;
        final K key;
        V value;
        Node<K,V> next;  // Pointer to next node in chain
    }

    static class TreeNode<K,V> extends Node<K,V> {  // Red-Black Tree node
        TreeNode<K,V> parent;
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        boolean red;  // Red-Black Tree color
    }

    static final int TREEIFY_THRESHOLD = 8;
    static final int MIN_TREEIFY_CAPACITY = 64;
}

Visualization:

Demo hash collision:

// Tạo objects với cùng hashCode (deliberately bad hash function)
class BadHash {
    int value;

    public BadHash(int value) {
        this.value = value;
    }

    @Override
    public int hashCode() {
        return 1;  // ❌ Tất cả objects có cùng hashCode!
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof BadHash)) return false;
        return this.value == ((BadHash) o).value;
    }
}

Set<BadHash> set = new HashSet<>();
for (int i = 0; i < 100; i++) {
    set.add(new BadHash(i));
}

// Tất cả 100 objects nằm trong 1 bucket!
// Ban đầu: LinkedList với 8 elements
// Sau đó: Convert thành Red-Black Tree khi > 8
// Performance: O(1) average → O(log 100) ≈ O(7) lookups

📖 Theo Oracle Docs: Treeify Improvement

Từ Java 8, HashMap cải thiện worst-case performance từ O(n) xuống O(log n) khi có hash collision nhiều. Đây là improvement quan trọng để tránh DoS attacks (Denial of Service) bằng cách cố tình tạo hash collisions.

hashCode() Best Practices

class Student {
    private int id;
    private String name;
    private double gpa;

    // ✅ Cách 1: Dùng Objects.hash() (Java 7+, recommended)
    @Override
    public int hashCode() {
        return Objects.hash(id, name, gpa);
    }

    // ✅ Cách 2: Manual với prime number (old style)
    @Override
    public int hashCode() {
        int result = 17;
        result = 31 * result + id;
        result = 31 * result + (name != null ? name.hashCode() : 0);
        long gpaLong = Double.doubleToLongBits(gpa);
        result = 31 * result + (int)(gpaLong ^ (gpaLong >>> 32));
        return result;
    }

    // ❌ KHÔNG BAO GIỜ: Return constant
    @Override
    public int hashCode() {
        return 42;  // Legal nhưng performance cực kém!
        // Tất cả objects có cùng hashCode → mọi elements vào 1 bucket
        // → LinkedList/Tree operations, không còn O(1)!
    }
}

Set.of() - Immutable Set (Java 9+)

Set.of() tạo truly immutable Set, không cho phép modification VÀ forbids null:

// Tạo immutable set
Set<String> set = Set.of("A", "B", "C");

// Không thể modify
// set.add("D");        // UnsupportedOperationException
// set.remove("A");     // UnsupportedOperationException
// set.clear();         // UnsupportedOperationException

// ❌ NULL KHÔNG ĐƯỢC PHÉP!
try {
    Set<String> withNull = Set.of("A", null, "C");
} catch (NullPointerException e) {
    System.out.println("Set.of() forbids null: " + e.getClass().getSimpleName());
    // Output: Set.of() forbids null: NullPointerException
}

// ❌ DUPLICATES KHÔNG ĐƯỢC PHÉP!
try {
    Set<String> withDup = Set.of("A", "B", "A");  // Duplicate "A"
} catch (IllegalArgumentException e) {
    System.out.println("Set.of() forbids duplicates: " + e.getClass().getSimpleName());
    // Output: Set.of() forbids duplicates: IllegalArgumentException
}

Set.of() vs HashSet:

Feature	Set.of()	HashSet
Mutability	Immutable	Mutable
Null	❌ NullPointerException	✅ Allows 1 null
Duplicates	❌ IllegalArgumentException	✅ Silently ignores
Thread-safe	✅ Yes (immutable)	❌ No
Use case	Constants, config	General purpose

// HashSet allows null và duplicates
Set<String> hashSet = new HashSet<>();
hashSet.add("A");
hashSet.add(null);   // OK
hashSet.add("A");    // OK, silently ignored (size stays 2)
System.out.println(hashSet);  // Output: [null, A]

// Set.of() không cho phép null hoặc duplicates
Set<String> immutable = Set.of("A", "B", "C");  // OK
// Set<String> bad1 = Set.of("A", null);  // NullPointerException
// Set<String> bad2 = Set.of("A", "A");   // IllegalArgumentException

OCP Traps - Bẫy thường gặp trong kỳ thi

🔥 Bẫy 1: HashSet.contains() dùng hashCode() trước, equals() sau

class Person {
    String name;

    @Override
    public boolean equals(Object o) {
        return o instanceof Person && ((Person) o).name.equals(this.name);
    }

    // KHÔNG override hashCode() → default implementation (memory address)
}

Set<Person> people = new HashSet<>();
Person alice1 = new Person("Alice");
people.add(alice1);

Person alice2 = new Person("Alice");
System.out.println(people.contains(alice2));  // false - WRONG!

// Giải thích:
// 1. HashSet gọi alice2.hashCode() → bucket X
// 2. alice1 ở bucket Y (vì hashCode khác)
// 3. HashSet tìm ở bucket X → không thấy alice1
// 4. Return false (không bao giờ gọi equals()!)

🔥 Bẫy 2: TreeSet without Comparable/Comparator

class Person {
    String name;
    // KHÔNG implement Comparable
}

Set<Person> people = new TreeSet<>();
people.add(new Person("Alice"));  // ❌ ClassCastException!

// Exception: Person cannot be cast to java.lang.Comparable
// Fix: implements Comparable hoặc provide Comparator
Set<Person> people = new TreeSet<>(Comparator.comparing(p -> p.name));

🔥 Bẫy 3: Mutable elements in HashSet

class MutablePerson {
    String name;
    public void setName(String name) { this.name = name; }
    // equals/hashCode dựa trên name
}

Set<MutablePerson> people = new HashSet<>();
MutablePerson alice = new MutablePerson("Alice");
people.add(alice);

alice.setName("Bob");  // Mutation!

// Alice bị "lost" trong HashSet
System.out.println(people.contains(alice));  // false - can't find!
System.out.println(people.size());           // 1 - still there but lost!

🔥 Bẫy 4: TreeSet null element

Set<String> treeSet = new TreeSet<>();
treeSet.add("A");
treeSet.add(null);  // ❌ NullPointerException!

// TreeSet cần compare elements → null.compareTo(...) → NPE
// HashSet allows null vì không cần compare
Set<String> hashSet = new HashSet<>();
hashSet.add(null);  // ✅ OK

Set Operations - Phép toán tập hợp

Set hỗ trợ các phép toán tập hợp toán học:

1. Union (Hợp) - A ∪ B

Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4));
Set<Integer> set2 = new HashSet<>(Arrays.asList(3, 4, 5, 6));

Set<Integer> union = new HashSet<>(set1);
union.addAll(set2);
System.out.println(union);  // [1, 2, 3, 4, 5, 6]

2. Intersection (Giao) - A ∩ B

Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4));
Set<Integer> set2 = new HashSet<>(Arrays.asList(3, 4, 5, 6));

Set<Integer> intersection = new HashSet<>(set1);
intersection.retainAll(set2);
System.out.println(intersection);  // [3, 4]

3. Difference (Hiệu) - A \ B

Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4));
Set<Integer> set2 = new HashSet<>(Arrays.asList(3, 4, 5, 6));

Set<Integer> difference = new HashSet<>(set1);
difference.removeAll(set2);
System.out.println(difference);  // [1, 2]

4. Symmetric Difference (Hiệu đối xứng) - (A \ B) ∪ (B \ A)

Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4));
Set<Integer> set2 = new HashSet<>(Arrays.asList(3, 4, 5, 6));

Set<Integer> symmetricDiff = new HashSet<>(set1);
symmetricDiff.addAll(set2);  // Union
Set<Integer> tmp = new HashSet<>(set1);
tmp.retainAll(set2);  // Intersection
symmetricDiff.removeAll(tmp);  // Union - Intersection
System.out.println(symmetricDiff);  // [1, 2, 5, 6]

Ví dụ thực hành

Ví dụ 1: Loại bỏ duplicates từ List

public class RemoveDuplicates {
    public static void main(String[] args) {
        List<String> listWithDuplicates = Arrays.asList(
            "Apple", "Banana", "Apple", "Cherry", "Banana", "Date"
        );

        // Cách 1: Dùng HashSet (không giữ thứ tự)
        Set<String> uniqueSet = new HashSet<>(listWithDuplicates);
        System.out.println(uniqueSet);  // Unordered

        // Cách 2: Dùng LinkedHashSet (giữ thứ tự)
        Set<String> orderedSet = new LinkedHashSet<>(listWithDuplicates);
        System.out.println(orderedSet);  // [Apple, Banana, Cherry, Date]

        // Chuyển về List
        List<String> uniqueList = new ArrayList<>(orderedSet);
    }
}

Ví dụ 2: Tìm unique và duplicate elements

public class FindDuplicates {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 2, 3, 2, 4, 5, 1, 6, 3);

        Set<Integer> unique = new HashSet<>();
        Set<Integer> duplicates = new HashSet<>();

        for (Integer num : numbers) {
            if (!unique.add(num)) {  // add() returns false if already exists
                duplicates.add(num);
            }
        }

        System.out.println("Unique: " + unique);        // [1, 2, 3, 4, 5, 6]
        System.out.println("Duplicates: " + duplicates);  // [1, 2, 3]
    }
}

Ví dụ 3: Word Frequency với Set operations

public class WordAnalysis {
    public static void main(String[] args) {
        String text1 = "the quick brown fox jumps over the lazy dog";
        String text2 = "the lazy dog sleeps under the warm sun";

        Set<String> words1 = new HashSet<>(Arrays.asList(text1.split(" ")));
        Set<String> words2 = new HashSet<>(Arrays.asList(text2.split(" ")));

        // Common words (intersection)
        Set<String> commonWords = new HashSet<>(words1);
        commonWords.retainAll(words2);
        System.out.println("Common words: " + commonWords);
        // [the, lazy, dog]

        // Unique to text1
        Set<String> uniqueToText1 = new HashSet<>(words1);
        uniqueToText1.removeAll(words2);
        System.out.println("Unique to text1: " + uniqueToText1);
        // [quick, brown, fox, jumps, over]

        // All unique words (union)
        Set<String> allWords = new HashSet<>(words1);
        allWords.addAll(words2);
        System.out.println("All unique words: " + allWords);
    }
}

Ví dụ 4: Custom Object trong Set

class Student {
    private int id;
    private String name;
    private double gpa;

    public Student(int id, String name, double gpa) {
        this.id = id;
        this.name = name;
        this.gpa = gpa;
    }

    // PHẢI override equals() và hashCode()
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Student)) return false;
        Student student = (Student) o;
        return id == student.id;  // Chỉ so sánh theo ID
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

    @Override
    public String toString() {
        return name + "(ID:" + id + ", GPA:" + gpa + ")";
    }
}

public class StudentSetDemo {
    public static void main(String[] args) {
        Set<Student> students = new HashSet<>();

        students.add(new Student(1, "Alice", 3.8));
        students.add(new Student(2, "Bob", 3.5));
        students.add(new Student(1, "Alice Smith", 3.9));  // Same ID, không thêm vào

        System.out.println("Students: " + students.size());  // 2

        // TreeSet với custom Comparator
        Set<Student> sortedByGpa = new TreeSet<>(
            Comparator.comparingDouble(s -> s.gpa)
        );
        sortedByGpa.addAll(students);
        System.out.println("Sorted by GPA: " + sortedByGpa);
    }
}

Bài tập thực hành

Bài 1: Unique Characters

Viết method boolean hasAllUniqueChars(String str) kiểm tra một String có toàn ký tự unique hay không.

Bài 2: First Non-Repeating Character

Viết method char firstNonRepeating(String str) tìm ký tự đầu tiên không lặp lại trong String.

Bài 3: Two Sum với Set

Viết method boolean hasPairWithSum(int[] arr, int sum) kiểm tra có cặp số nào trong mảng có tổng bằng sum không. Sử dụng Set để giải quyết trong O(n).

Bài 4: Longest Consecutive Sequence

Viết method int longestConsecutive(int[] nums) tìm độ dài của dãy số liên tiếp dài nhất trong mảng. Ví dụ: [100, 4, 200, 1, 3, 2] → return 4 (dãy 1,2,3,4)

Tổng kết

Trong bài này, bạn đã học:

• Set: Collection không chứa duplicates, mô phỏng tập hợp toán học
• HashSet: Implementation nhanh nhất (O(1)), unordered, cho phép 1 null
• LinkedHashSet: Giống HashSet nhưng duy trì insertion order
• TreeSet: Tự động sắp xếp (sorted), O(log n), KHÔNG cho phép null
• equals() và hashCode() contract: PHẢI override cả hai cho custom objects
• Set operations: Union, Intersection, Difference, Symmetric Difference
• Use cases: Remove duplicates, find unique elements, membership testing

Quy tắc vàng:

1. Khi không chắc → Dùng HashSet
2. Cần thứ tự insertion → Dùng LinkedHashSet
3. Cần tự động sắp xếp → Dùng TreeSet
4. Luôn override cả equals() VÀ hashCode() cho custom objects!

Đọc thêm

• Set Interface - Oracle
• HashSet API - Oracle
• TreeSet API - Oracle