Map và Set — HashMap, TreeMap, HashSet bên dưới

Bài trước — List và Queue đi qua các implementation tuyến tính. Bài này phần còn lại của Collections framework: Map và Set — các implementation key-value và tập hợp không trùng.

Điểm thú vị: HashSet không có code logic riêng — nó chỉ là HashMap với value dummy. Cùng cách, LinkedHashSet = LinkedHashMap, TreeSet = TreeMap. Hiểu 3 Map (HashMap, TreeMap, LinkedHashMap) là hiểu luôn 3 Set.

Bài này đi sâu vào:

• HashMap — bucket array, hash function, chaining collision, treeify Java 8+.
• TreeMap — red-black tree balanced.
• LinkedHashMap — HashMap + linked list cho iteration order. Nền tảng LRU cache.
• HashSet/TreeSet/LinkedHashSet — wrap Map.

1. Map — không extends Collection

Cây interface ở đây phẳng: Map là gốc, SortedMap extends nó, NavigableMap extends SortedMap. HashMap và LinkedHashMap implement thẳng Map; TreeMap implement NavigableMap.

Map không extends Collection vì semantic khác: Map lưu cặp key-value, không phải tập element. Method signature cũng khác (put(k, v) thay vì add(e)).

3 implementation chính:

• HashMap: O(1) trung bình, không sắp xếp.
• TreeMap: O(log n), sorted theo key.
• LinkedHashMap: O(1) + giữ thứ tự insert (hoặc access).

2. HashMap — hash table với bucket + treeify

Cấu trúc bên dưới (Java 8+)

public class HashMap<K, V> {
    Node<K, V>[] table;      // Array cua bucket
    int size;
    int threshold;           // Size trigger resize
    float loadFactor;        // Mac dinh 0.75

    static class Node<K, V> {
        int hash;
        K key;
        V value;
        Node<K, V> next;      // Linked list cho collision
    }

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

Cơ chế hash → bucket

public V put(K key, V value) {
    int hash = hash(key);                     // Modify hashCode() de tranh cluster
    int index = (table.length - 1) & hash;    // Chi so bucket
    Node<K, V> bucket = table[index];
    // ... them vao bucket
}

static int hash(Object key) {
    int h = key.hashCode();
    return h ^ (h >>> 16);   // Mix high bit xuong low bit
}

3 bước:

1. Gọi key.hashCode() → int 32-bit.
2. Mix high bit xuống low bit (XOR với h >>> 16) — giảm clustering với bad hash.
3. & (table.length - 1) — nếu table.length là power of 2, tương đương hash % table.length nhưng nhanh hơn (bit-wise AND).

Kết quả là bucket index trong table array.

Đi hết một lượt tra cứu thì thấy hashCode() và equals() làm việc ở hai bước tách hẳn nhau:

hashCode() chỉ chọn ngăn; equals() mới chọn key bên trong ngăn đó. Đây là lý do override thiếu một trong hai thì hỏng theo hai kiểu khác nhau — hashCode() sai thì tra vào nhầm ngăn và không bao giờ tìm thấy, còn equals() sai thì vào đúng ngăn nhưng không nhận ra key.

Collision — chaining

2 key cùng bucket (hash collision) → lưu trong linked list của bucket:

table[5] -> Node(hash=5, "apple", 100) -> Node(hash=5, "banana", 200) -> null

Tra cứu: hash key → index → duyệt linked list trong bucket, compare bằng equals để tìm key đúng.

Treeify — Java 8 optimization

🎯 Điều kiện kép để chuyển sang Cây đỏ đen (Red-Black Tree)

Như bước cuối của sơ đồ trên: bucket đạt 8 phần tử chưa đủ. Java 8+ đòi cả TREEIFY_THRESHOLD = 8 (độ dài chain trong một bucket) lẫn MIN_TREEIFY_CAPACITY = 64 (tổng số bucket của table).

💡 Tại sao cần điều kiện MIN_TREEIFY_CAPACITY = 64?

Nếu tổng số lượng bucket của map còn quá nhỏ (dưới 64, ví dụ như default ban đầu là 16) nhưng đã có một bucket bị nghẽn vượt ngưỡng 8 phần tử, nguyên nhân cao là do phân phối hash chưa tốt hoặc kích thước mảng nhỏ làm gia tăng xung đột.

Lúc này, thay vì lập tức gánh chịu chi phí bộ nhớ đắt đỏ và thuật toán phức tạp để biến linked list thành cây đỏ đen, HashMap ưu tiên resize() (nhân đôi mảng bucket) — thêm bucket trống rồi rehash, giải toả áp lực collision một cách đồng đều và rẻ hơn nhiều.

Chỉ khi mảng bucket đã được mở rộng đủ lớn (tối thiểu là 64 bucket) mà tình trạng đụng độ cục bộ tại một bucket vẫn vượt quá ngưỡng 8, chứng tỏ việc resize không còn hiệu quả hoặc chi phí resize quá đắt, HashMap mới chính thức thực hiện chuyển đổi linked list nghẽn đó thành Cây đỏ đen (Red-Black Tree):

table[5] -> TreeNode (cấu trúc Red-Black Tree tự cân bằng)

Lookup trong cây đỏ đen có độ phức tạp là O(log n) thay vì O(n) của linked list nghẽn. Đây là tấm khiên phòng ngự vững chắc chống lại hash collision DoS attack (khi kẻ tấn công cố tình chèn hàng nghìn key được tính toán để đụng độ cùng một mã hash, kéo tụt hiệu năng tra cứu của server xuống O(n)).

Ghi chú lịch sử: Lỗ hổng bảo mật này được ghi nhận là JEP 180 và CVE-2011-4858 đối với các cấu trúc dạng Hashtable cũ.

Khi số lượng phần tử trong cây đỏ đen giảm xuống còn 6 phần tử (UNTREEIFY_THRESHOLD = 6), JVM sẽ chuyển đổi ngược cấu trúc cây thành linked list đơn giản để tối ưu hiệu năng bộ nhớ (tránh overhead quản lý cây). Khoảng cách giữa 8 và 6 (hysteresis) giúp ngăn hiện tượng đổi cấu trúc liên tục (thrashing) khi thêm/xoá liên tục quanh ngưỡng.

Load factor + resize

if (size > threshold) {   // threshold = capacity * loadFactor
    resize();
}

Load factor mặc định 0.75. Khi size / capacity > 0.75, resize:

1. Cấp table mới gấp đôi capacity (phải power of 2).
2. Rehash mọi entry sang bucket mới.

Java 8+ tối ưu: với table.length double, entry hoặc ở vị trí cũ hoặc ở vị trí cũ + oldCapacity — không cần tính lại hash, chỉ check 1 bit.

Resize O(n) — tốn. Biết trước size → init capacity đủ:

Map<String, Integer> m = new HashMap<>(1024);

get(key) — O(1) trung bình

public V get(Object key) {
    int hash = hash(key);
    int index = (table.length - 1) & hash;
    Node<K, V> bucket = table[index];
    if (bucket == null) return null;

    // Duyet linked list hoac tree
    for (Node<K, V> n = bucket; n != null; n = n.next) {
        if (n.hash == hash && (n.key == key || key.equals(n.key))) {
            return n.value;
        }
    }
    return null;
}

Với hash distribution tốt: ít collision → bucket nhỏ (~1-2 entry) → O(1). Collision nhiều: linked list → O(n). Treeify khi quá đông → O(log n).

Vai trò equals + hashCode

Vì hai bước đó tách nhau, class làm key phải override cả hai:

class Book {
    String title;
    // khong override
}

Map<Book, String> m = new HashMap<>();
m.put(new Book("Java"), "review 1");
m.get(new Book("Java"));   // null! 2 object khac nhau theo Object.equals default

Rule: override hashCode và equals cùng bộ field. Hàm hashCode phải nhất quán với equals — 2 object equal phải có cùng hashCode.

Null key — cho phép 1 null

HashMap cho 1 null key (đặt vào bucket 0). TreeMap không cho (vì cần compareTo).

3. TreeMap — red-black tree, sorted

Cấu trúc

Red-black tree — self-balancing binary search tree với màu node (red/black) đảm bảo height tối đa 2*log(n+1).

public class TreeMap<K, V> {
    Entry<K, V> root;
    int size;
    Comparator<? super K> comparator;

    static final class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> left;
        Entry<K, V> right;
        Entry<K, V> parent;
        boolean color;   // RED or BLACK
    }
}

Quy luật tự cân bằng của Cây đỏ đen (Red-Black Tree)

Đối với người học Java thực tế, thay vì phải ghi nhớ máy móc cả 5 quy tắc học thuật phức tạp của Red-Black Tree (các quy luật về màu sắc nút, gốc đen, lá đen, không có hai nút đỏ kề nhau và số lượng nút đen bằng nhau trên mọi đường đi), chúng ta chỉ cần hiểu trade-off (sự đánh đổi) thực tế cực kỳ rõ ràng của nó:

1. Ý nghĩa cốt lõi: Các quy tắc màu sắc và cân bằng này là công cụ giúp TreeMap luôn giữ cho chiều cao của cây nhị phân tăng trưởng theo hàm logarithmic so với số lượng phần tử (chiều cao cây H ≈ log N).
2. Cam kết tuyệt đối: Dù bạn có chèn dữ liệu theo thứ tự tăng dần/giảm dần (worst-case của cây nhị phân thông thường biến thành linked list), TreeMap nhờ các phép xoay cây (rotation) và đổi màu (recoloring) sẽ tự cân bằng lại, đảm bảo O(log N) tuyệt đối cho mọi thao tác chèn, xóa và tìm kiếm.

⚖️ Sự đánh đổi thực tế (Real-world Trade-off): Có đáng để sử dụng TreeMap?

Mặc dù cung cấp một cấu trúc tự sắp xếp hoàn hảo, TreeMap đi kèm với những cái giá rất đắt về bộ nhớ và tốc độ so với HashMap:

• Overhead bộ nhớ cực lớn: Với HashMap, mỗi entry chỉ cần giữ tham chiếu next đơn. Với TreeMap, mỗi node (Entry) phải gánh thêm tới 3 con trỏ tham chiếu (left, right, parent) cùng 1 biến boolean color. Điều này làm tăng dung lượng lưu trữ trên Heap lên gấp nhiều lần.
• Tốc độ chậm hơn HashMap từ 2 - 10 lần:
  • HashMap thực hiện tìm kiếm trực tiếp bằng chỉ số index của mảng thông qua phép toán hash (O(1)) vô cùng nhanh chóng.
  • TreeMap phải duyệt qua cấu trúc cây (pointer chasing). Việc nhảy từ địa chỉ node này sang node khác rải rác trên Heap gây ra hiện tượng CPU cache miss liên tục. Trong các thao tác lookup đơn giản trên thực tế, TreeMap chạy chậm hơn HashMap khoảng từ 2 đến 10 lần tùy kích thước.

Insert & Lookup — O(log n)

Mọi thao tác tìm kiếm (get) hay chèn (put) đều hoạt động bằng cách so sánh giá trị Key (compareTo hoặc thông qua Comparator) từ nút gốc (Root) rồi rẽ nhánh sang trái (nhỏ hơn) hoặc sang phải (lớn hơn) cho đến khi tìm thấy đích. Độ phức tạp là O(log N) tương ứng với độ sâu của cây đã được cân bằng.

Ưu điểm vượt trội của TreeMap

Mặc dù chậm hơn, TreeMap là sự lựa chọn duy nhất khi bạn cần:

• Sorted Iteration: Duyệt qua các Key luôn đảm bảo theo thứ tự tự nhiên (Natural Ordering) của Key hoặc Comparator tùy chỉnh.
• Range Queries (Truy vấn theo khoảng): Hỗ trợ cực tốt các hàm subMap(from, to), headMap(to), tailMap(from) với độ phức tạp chỉ O(log N + k) (k là số kết quả trả về).
• Navigation (Tìm kiếm lân cận): Dễ dàng tìm các phần tử gần nhất bằng ceilingKey(x) (≥ x), floorKey(x) (≤ x), higherKey, lowerKey chỉ trong O(log N).
• Worst-case ổn định: Hoàn toàn không sợ bị sụp đổ hiệu năng về O(n) khi gặp bad hash như HashMap.

Nhược điểm

• Tốc độ và bộ nhớ: Như đã phân tích ở trên (sử dụng nhiều con trỏ, cache miss, JIT khó optimize bằng HashMap).
• Key phải Comparable hoặc pass Comparator.
• Không cho null key (compareTo throw NPE).

Khi nào TreeMap

• Cần iterate theo thứ tự (sorted).
• Range query.
• Time-series data (lookup theo timestamp gần nhất).
• Pricing tier (lookup bậc giá theo số tiền).

Khi nào HashMap: lookup thuần, không quan tâm thứ tự — mặc định HashMap.

4. LinkedHashMap — HashMap + linked list

LinkedHashMap extend HashMap với thêm doubly-linked list kết nối entry theo thứ tự insert (hoặc access):

public class LinkedHashMap<K, V> extends HashMap<K, V> {
    // Them linked list kieu prev/next noi cac entry
    // Duyet theo linked list nay cho iteration order
}

Mỗi entry thêm 2 pointer prev/next → overhead memory nhưng bảo toàn thứ tự.

Insertion order (default)

LinkedHashMap<String, Integer> m = new LinkedHashMap<>();
m.put("c", 3);
m.put("a", 1);
m.put("b", 2);

m.forEach((k, v) -> System.out.println(k));
// Output: c, a, b  (thu tu insert)

Khác với HashMap (order tuỳ hash), LinkedHashMap đảm bảo iterate theo thứ tự insert.

Access order — LRU cache base

Constructor 3-arg của LinkedHashMap với tham số accessOrder = true cho phép mỗi lần gọi get() hoặc put(), entry được truy cập sẽ tự động di chuyển xuống cuối linked list (được xem là Most Recently Used - được truy cập gần đây nhất):

Map<String, Data> cache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Data> eldest) {
        return size() > 100; // Giới hạn kích thước cache là 100
    }
};

• accessOrder = true — mỗi lần truy cập phần tử sẽ cập nhật lại thứ tự.
• removeEldestEntry — một callback kích hoạt ngay sau mỗi lần gọi put(). Nếu trả về true, phần tử lâu đời nhất ở đầu linked list (Least Recently Used) sẽ bị loại bỏ khỏi map.

Đây chính là pattern xây dựng LRU Cache tinh gọn trong 5 dòng code.

⚠️ Cảnh báo cực kỳ quan trọng về Thread-Safety trong môi trường Concurrent

Một sai lầm kinh điển dẫn đến crash hệ thống trong production khi làm việc với LRU Cache tự chế này là bỏ qua tính an toàn luồng (Thread-Safety):

1. LinkedHashMap hoàn toàn không thread-safe: Khi sử dụng đa luồng (concurrent environment), ngay cả các thao tác đọc dữ liệu như get(key) cũng thay đổi cấu trúc bên dưới (di chuyển node trong linked list nội bộ để cập nhật vị trí LRU khi accessOrder = true).
2. Hậu quả thảm khốc: Nếu nhiều luồng đồng thời gọi get() hoặc put(), các liên kết con trỏ prev/next của linked list sẽ bị phá hỏng (pointers corruption). Hệ quả thường gặp là:
   • Treo CPU 100% do rơi vào vòng lặp vô hạn ngầm (infinite loop) khi duyệt danh sách liên kết bị lỗi vòng tròn.
   • Dữ liệu bị ghi đè, sai lệch hoặc ném lỗi ConcurrentModificationException.

🛠️ Giải pháp xử lý an toàn luồng:

• Phương án 1: Bọc đồng bộ bằng Collections.synchronizedMap

  Map<String, Data> syncCache = Collections.synchronizedMap(
      new LinkedHashMap<>(16, 0.75f, true) {
          @Override
          protected boolean removeEldestEntry(Map.Entry<String, Data> eldest) {
              return size() > 100;
          }
      }
  );
  

  Lưu ý: Việc bọc này sẽ khóa (lock) toàn bộ map trong mọi thao tác đọc/ghi. Trong môi trường chịu tải rất lớn, nó có thể tạo ra điểm nghẽn cổ chai (lock contention). Khi duyệt (iterate) qua map, ta vẫn phải đồng bộ thủ công:

  synchronized (syncCache) {
      for (var entry : syncCache.entrySet()) { ... }
  }
  

• Phương án 2: Sử dụng ReentrantLock độc lập Sử dụng một đối tượng ReentrantLock hoặc ReadWriteLock (tuy nhiên do get cũng thực hiện mutation nên write lock vẫn phải áp dụng cho cả get và put) để đồng bộ hóa quyền truy cập một cách tường minh.

• Phương án tốt nhất cho Production: Nếu hệ thống của bạn yêu cầu hiệu năng cao, concurrency cực lớn, đừng tự chế LRU Cache bằng LinkedHashMap. Hãy sử dụng các thư viện chuyên dụng như Caffeine Cache hoặc Guava Cache vốn được thiết kế tối ưu hóa cực tốt cho môi trường đa luồng mà không gây nghẽn cổ chai.

Pattern LRU cache này là nền tảng cho mini-challenge ở bài sau.

5. HashSet / LinkedHashSet / TreeSet — wrap Map

HashSet = HashMap với value dummy

public class HashSet<E> {
    private HashMap<E, Object> map;
    private static final Object PRESENT = new Object();

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }

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

Đơn giản là HashMap với value hằng số PRESENT. Tất cả đặc tính của HashSet (O(1), cần equals/hashCode) đều kế thừa từ HashMap.

LinkedHashSet = LinkedHashMap với value dummy

Giữ thứ tự insert. Dùng cho Set cần iterate deterministic.

TreeSet = TreeMap với value dummy

Sorted Set. Range query, navigation như TreeMap.

Bảng so sánh:

6. Immutable collection (Java 9+)

List<Integer> list = List.of(1, 2, 3);
Set<String> set = Set.of("a", "b", "c");
Map<String, Integer> map = Map.of("a", 1, "b", 2);

• Immutable — add/remove ném UnsupportedOperationException.
• Không cho phép null.
• Thread-safe (không đổi được).
• Implementation đặc biệt (ImmutableCollections.ListN, SetN, MapN) — tối ưu hơn ArrayList/HashMap cho size nhỏ.

List.copyOf, Set.copyOf, Map.copyOf — snapshot

List<Integer> mutable = new ArrayList<>(List.of(1, 2, 3));
List<Integer> snapshot = List.copyOf(mutable);

mutable.add(4);
// snapshot van la [1, 2, 3]

Pattern defensive copy — bảo vệ internal state khỏi mutation từ caller.

7. Bảng chọn

8. Pitfall tổng hợp

❌ Nhầm 1: Không override equals/hashCode cho class làm key HashMap / element HashSet.

class Book { String title; }
Set<Book> s = new HashSet<>();
s.add(new Book("Java"));
s.contains(new Book("Java"));   // false!

✅ Luôn override cả 2 với cùng bộ field.

❌ Nhầm 2: Không init capacity cho HashMap biết trước size.

Map<K, V> m = new HashMap<>();
for (int i = 0; i < 1_000_000; i++) m.put(keys[i], values[i]);   // resize ~17 lan

✅ new HashMap<>(1_500_000) — tránh resize, tăng speed 2-3x.

❌ Nhầm 3: ConcurrentModificationException khi modify trong loop.

for (var e : map.entrySet()) {
    if (bad(e.getKey())) map.remove(e.getKey());   // CME
}

✅ map.entrySet().removeIf(e -> bad(e.getKey()));

❌ Nhầm 4: Tưởng HashMap.keySet() iterate theo insert order.

Map<String, Integer> m = new HashMap<>();
m.put("a", 1); m.put("b", 2);
for (String k : m.keySet()) { ... }   // Thu tu KHONG xac dinh

✅ Cần order → LinkedHashMap.

❌ Nhầm 5: TreeMap với key null.

TreeMap<String, Integer> m = new TreeMap<>();
m.put(null, 1);   // NullPointerException

✅ HashMap cho null; TreeMap không cho.

9. 📚 Deep Dive Oracle

Liên kết khoá học khác

• Khoá Thuật toán — bài 01.1 Hash Function — hiểu uniform distribution và avalanche effect để biết tại sao hashCode tốt quan trọng.
• Khoá Java Internals — HashMap Internals — chaining vs treeify, load factor, resize internals của HashMap Java sâu hơn mức API.
• Khoá Thuật toán — bài 3.3 Open Addressing — phương án xử lý collision thay thế (linear/quadratic probing) để thấy rõ tradeoff với chaining.

10. Tóm tắt

• HashMap: bucket array + chaining, treeify collision vượt 8 (Java 8+). O(1) trung bình. Cần equals/hashCode cho key.
• TreeMap: red-black tree balanced, O(log n), sorted iterate + range query.
• LinkedHashMap: HashMap + linked list insertion/access order. accessOrder=true làm LRU cache.
• HashSet / LinkedHashSet / TreeSet = wrap Map tương ứng với value dummy PRESENT.
• HashMap cho 1 null key; TreeMap không cho.
• new HashMap<>(n) biết trước size → tránh resize multiple.
• Pattern removeEldestEntry + accessOrder=true → LRU cache builtin.
• Immutable Map.of, Set.of — thread-safe + optimized implementation.

11. Tự kiểm tra

Bài tiếp theo: Iterator, fail-fast và ConcurrentModificationException