Map và Set — HashMap, TreeMap, HashSet

TL;DR: Interface Map không kế thừa từ Collection vì nó mô tả ánh xạ cặp key-value thay vì tập hợp phần tử đơn lẻ. HashMap dựa trên bảng băm mảng bucket kết hợp linked list và tự động chuyển đổi sang cây đỏ đen (Treeify - JEP 180) khi một bucket vượt quá 8 phần tử và dung lượng đạt tối thiểu 64, đảm bảo thời gian tra cứu $O(1)$ trung bình. Ngược lại, TreeMap duy trì cây nhị phân tự cân bằng với độ phức tạp $O(\log n)$, cho phép sắp xếp khóa tự nhiên và thực hiện truy vấn theo khoảng. Toàn bộ họ HashSet, LinkedHashSet, TreeSet trong JDK đều là các lớp vỏ bọc tái sử dụng logic của Map tương ứng với một giá trị dummy.

1. Vì sao Map không kế thừa từ interface Collection?

Trong kiến trúc Java Collections Framework, Map đứng ở một nhánh hoàn toàn độc lập với Collection:

• Collection quản lý các thực thể đơn lẻ (Single Elements) như danh sách ấn phẩm hoặc hàng đợi độc giả, với các thao tác cốt lõi: add(E e), contains(Object o).
• Map quản lý các cặp ánh xạ khóa - giá trị (Key-Value Pairs), ví dụ ánh xạ từ mã vạch (Barcode) sang thông tin chi tiết của ấn phẩm (LibraryItem), với các thao tác: put(K k, V v), get(Object k).

Nếu Map kế thừa Collection, các phương thức như add(E e) sẽ mơ hồ: ta đang thêm key, value, hay một entry? Do đó, Java tách biệt hai giao diện này và cung cấp ba góc nhìn tập hợp (Collection Views) khi cần duyệt: keySet(), values(), và entrySet().

2. HashMap xử lý băm, xung đột và Treeify (Java 8+) như thế nào?

Bên dưới HashMap, dữ liệu được tổ chức dưới dạng một mảng các nút (buckets):

public class HashMap<K, V> {
    Node<K, V>[] table;      // Internal bucket array
    int size;                // Number of key-value mappings
    int threshold;           // Capacity * loadFactor (triggers resize)
    float loadFactor;        // Default 0.75f

    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;     // Singly-linked list for collisions
    }
}

Cơ chế băm và tính toán chỉ số Bucket

Để phân bổ đều các khóa vào mảng và hạn chế xung đột, HashMap thực hiện hàm băm bổ trợ:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Phép dịch bit phải 16 vị trí và XOR (^) giúp các bit bậc cao tác động xuống các bit bậc thấp. Nhờ đó, khi tính chỉ số mảng bằng công thức index = (table.length - 1) & hash, các bucket không bị dồn cục bộ ngay cả khi hàm hashCode() gốc chỉ đổi ở bit cao.

Cơ chế giải quyết xung đột: Chaining và Treeify

Khi hai mã khóa khác nhau rơi vào cùng một chỉ số bucket (Hash Collision):

1. Chaining ban đầu: Các entry được móc nối thành danh sách liên kết đơn Node.next, so khớp bằng equals().
2. Chuyển đổi sang Cây đỏ đen (Treeify): Nếu số phần tử trong một bucket vượt quá ngưỡng 8 (TREEIFY_THRESHOLD = 8), và dung lượng toàn bảng đạt ít nhất 64 (MIN_TREEIFY_CAPACITY = 64), danh sách liên kết sẽ được chuyển hóa thành một Red-Black Tree (TreeNode).

Treeify (JEP 180) là cơ chế phòng thủ trọng yếu ngăn ngừa tấn công Hash Collision DoS (CVE-2011-4858), khi kẻ xấu gửi các chuỗi cùng hash code để kéo tụt tốc độ máy chủ từ $O(1)$ xuống $O(n)$. Nếu dung lượng bảng chưa đạt 64, HashMap sẽ gọi resize() nhân đôi số bucket để giãn phần tử ra thay vì tạo cây.

Khi số phần tử trong cây giảm xuống còn 6 (UNTREEIFY_THRESHOLD = 6), JVM tự động chuyển ngược cây về dạng danh sách liên kết để tiết kiệm bộ nhớ con trỏ.

3. Vì sao phải ghi đè đồng thời equals() và hashCode() khi làm khóa?

Như sơ đồ tra cứu minh họa, hai phương thức này đảm nhiệm hai giai đoạn tách biệt:

• hashCode(): Quyết định ngăn tủ (Bucket) nào chứa dữ liệu.
• equals(): Quyết định chính xác đối tượng (Key) nào khớp bên trong ngăn tủ đó.

Hãy xem điều gì xảy ra nếu quên ghi đè:

public class CatalogKey {
    private final String barcode;
    public CatalogKey(String barcode) { this.barcode = barcode; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof CatalogKey other)) return false;
        return Objects.equals(this.barcode, other.barcode);
    }
    // Missing hashCode() override!
}

Khi thực hiện tra cứu:

Map<CatalogKey, LibraryItem> catalog = new HashMap<>();
catalog.put(new CatalogKey("BC-101"), new PrintedBook("Clean Code", 0.6));

LibraryItem item = catalog.get(new CatalogKey("BC-101")); // Returns null!

Mặc dù equals() trả về true, hashCode() mặc định từ Object lại sinh ra hai giá trị ngẫu nhiên theo địa chỉ ô nhớ. get() sẽ tìm ở sai bucket và trả về null.

Quy tắc: Nếu a.equals(b) là true, bắt buộc a.hashCode() == b.hashCode(). Khóa nên là đối tượng bất biến (Immutable).

4. TreeMap cân bằng cây đỏ đen và phục vụ truy vấn khoảng ra sao?

Trong khi HashMap không bảo đảm bất kỳ thứ tự nào khi duyệt, TreeMap tổ chức dữ liệu theo cây tìm kiếm nhị phân tự cân bằng (Red-Black Tree), duy trì các khóa luôn sắp xếp:

public class TreeMap<K, V> {
    private transient Entry<K, V> root;
    private transient int size = 0;
    private final Comparator<? super K> comparator;
}

Tra cứu theo khoảng phân loại Dewey

Tại thư viện, ấn phẩm được phân loại theo mã thập phân Dewey. TreeMap hỗ trợ truy vấn dải danh mục hiệu quả:

NavigableMap<Double, LibraryItem> deweyCatalog = new TreeMap<>();
deweyCatalog.put(004.0, new PrintedBook("Computer Science", 1.0));
deweyCatalog.put(005.1, new PrintedBook("Programming Methods", 0.8));
deweyCatalog.put(510.0, new PrintedBook("Pure Mathematics", 1.2));

// Range query for computer science books:
SortedMap<Double, LibraryItem> csSection = deweyCatalog.subMap(004.0, 500.0);

// Find closest call number >= 005.0:
Double closestCode = deweyCatalog.ceilingKey(005.0); // 005.1

5. LinkedHashMap duy trì thứ tự và hỗ trợ xây dựng LRU Cache thế nào?

LinkedHashMap kế thừa từ HashMap và bổ sung danh sách liên kết đôi luồn qua toàn bộ các entry:

public class LinkedHashMap<K, V> extends HashMap<K, V> {
    transient LinkedHashMap.Entry<K, V> head;
    transient LinkedHashMap.Entry<K, V> tail;
    final boolean accessOrder;
}

Mặc định, LinkedHashMap bảo toàn thứ tự chèn (Insertion-order). Khi khởi tạo với cờ accessOrder = true, mỗi khi một entry được đọc (get) hoặc ghi (put), nó sẽ dời về cuối danh sách (Most Recently Used). Ghi đè removeEldestEntry() tạo ra LRU Cache tiện lợi:

public class LibraryLruCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxEntries;

    public LibraryLruCache(int maxEntries) {
        super(16, 0.75f, true); // accessOrder = true
        this.maxEntries = maxEntries;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxEntries; // Evict LRU head entry
    }
}

[!WARNING] LinkedHashMap không an toàn luồng. Khi accessOrder = true, ngay cả get() cũng thay đổi cấu trúc liên kết bên dưới. Cần bọc ngoài bằng Collections.synchronizedMap() hoặc dùng Caffeine Cache trong môi trường concurrent.

6. Các cấu trúc Set tái sử dụng mã nguồn của Map như thế nào?

JDK không viết lại thuật toán cho Set. Thay vào đó, toàn bộ họ Set chỉ là một lớp bọc mỏng xung quanh các đối tượng Map:

public class HashSet<E> implements Set<E> {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object(); // Shared dummy value

    public HashSet() { map = new HashMap<>(); }
    public boolean add(E e) { return map.put(e, PRESENT) == null; }
    public boolean contains(Object o) { return map.containsKey(o); }
}

Mỗi phần tử e trong HashSet được lưu làm Khóa (Key) trong HashMap nội bộ với giá trị chung PRESENT. Tương tự, LinkedHashSet bọc LinkedHashMap và TreeSet bọc TreeMap.

7. Đâu là những cạm bẫy thường gặp khi làm việc với Map và Set?

❌ Cạm bẫy 1: Không khởi tạo dung lượng ban đầu cho HashMap chứa số lượng lớn bản ghi Khi biết trước cần nạp 1.000.000 ấn phẩm:

// Anti-pattern: Triggers ~17 resizes and full rehashes
Map<String, LibraryItem> map = new HashMap<>();

// Recommended: expectedSize / loadFactor = 1_000_000 / 0.75
Map<String, LibraryItem> map = new HashMap<>(1_333_334);

❌ Cạm bẫy 2: Sửa đổi trường dữ liệu của khóa sau khi đã lưu vào Map/Set Nếu dùng một đối tượng có thể thay đổi (Mutable Object) làm khóa rồi cập nhật trường tính hash của nó, mã băm thay đổi nhưng vị trí lưu trong bucket vẫn ở chỗ cũ, biến entry thành "bóng ma" không thể tra cứu.

❌ Cạm bẫy 3: Xóa phần tử trong lúc lặp Map bằng foreach thông thường

// Bad: Throws ConcurrentModificationException
for (String key : map.keySet()) {
    if (key.startsWith("OLD_")) map.remove(key);
}

// Recommended: Use removeIf
map.keySet().removeIf(key -> key.startsWith("OLD_"));

8. Đọc thêm từ tài liệu Oracle và các liên kết liên quan

9. Tóm tắt các điểm mấu chốt

• HashMap đạt hiệu năng $O(1)$ nhờ mảng bucket và tự động chuyển sang Red-Black Tree khi có xung đột lớn ($\ge 8$ node và $\ge 64$ bucket).
• Khóa trong HashMap và phần tử trong HashSet bắt buộc phải ghi đè đồng bộ cả equals() và hashCode().
• TreeMap duy trì trật tự sắp xếp theo $O(\log n)$, thích hợp cho duyệt tuần tự hoặc truy vấn theo khoảng giá trị.
• LinkedHashMap kết hợp bảng băm với danh sách liên kết đôi, là nền tảng để thiết kế LRU Cache qua cơ chế accessOrder.
• Các lớp Set trong Java tái sử dụng 100% mã nguồn của các lớp Map tương ứng bằng cách dùng phần tử làm khóa và gán giá trị dummy chung.

10. Câu hỏi tự kiểm tra

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