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

Bài trước (8.4) đi qua List và Queue. 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

flowchart TD
    Map[Map - khong extends Collection]
    Map --> SortedMap
    SortedMap --> NavigableMap

    Map -.-> HashMap
    Map -.-> LinkedHashMap
    NavigableMap -.-> TreeMap

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.

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

Khi bucket có trên 8 entry VÀ table size tối thiểu 64, Java 8+ chuyển linked list thành red-black tree:

table[5] -> TreeNode (red-black tree voi 20 entry)

Lookup trong tree: O(log n) thay vì O(n) linked list. Đây là defense chống hash collision DoS attack — kẻ tấn công craft nhiều key có cùng hash → bucket thành linked list dài → lookup worst-case O(n) → server slow xuống. Treeify biến thành O(log n).

CVE-2011-4858 (Java Hashtable) đã ghi nhận attack này. JEP 180 Java 8 fix qua treeify.

Khi tree shrink xuống dưới 6 entry, chuyển ngược về linked list (UNTREEIFY).

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

HashMap dùng hashCode để tìm bucket, equals để tìm key trong bucket. Class làm key phải override cả 2:

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
    }
}

Rule red-black tree

1. Mỗi node màu red hoặc black.
2. Root luôn black.
3. Leaf (null) là black.
4. Red node không có child red (2 red liên tiếp cấm).
5. Từ mỗi node, số black node trên đường đi xuống leaf bằng nhau.

5 rule đảm bảo tree balanced — height chỉ tăng log với n. Insert/remove giữ rule bằng rotation (left/right) và recoloring.

Insert — O(log n)

1. BST insert bình thường (so compareTo để đi left/right).
2. Color node mới red.
3. Fix-up: nếu vi phạm rule 4 (2 red liên tiếp), rotate + recolor.

Fix-up đi từ node mới lên root, mỗi bước O(1), tổng O(log n).

Lookup — O(log n)

BST lookup: compare key với root, đi left nếu nhỏ, right nếu lớn. Tree balanced → height log n.

Ưu điểm TreeMap

• Sorted iteration: for (key : map.keySet()) theo thứ tự compareTo.
• Range query: subMap(from, to), headMap(to), tailMap(from) — O(log n + k) với k = kết quả.
• Navigation: ceilingKey(x) (smallest key ≥ x), floorKey(x) (largest key ≤ x), higherKey, lowerKey — O(log n).
• Worst-case ổn định: luôn O(log n), không có worst-case O(n) như HashMap bad hash.

Nhược

• Chậm hơn HashMap cho lookup thuần: O(log n) vs O(1). Với n = 1M, log n = 20, chênh 20x.
• 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 với accessOrder = true — mỗi get di chuyển entry xuống cuối linked list (most-recently-used):

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

• accessOrder = true — access (get) update thứ tự.
• removeEldestEntry — callback sau mỗi put. Return true → remove eldest (đầu linked list = least recently used).

Pattern LRU cache trong 5 dòng. Mini-challenge bài sau xây LRU cache đầy đủ từ pattern này.

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

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

Map<String, Integer> m = new HashMap<>();
for (int i = 0; i < 1_000_000; i++) {
  m.put(keys[i], values[i]);
}

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

Map<String, Integer> m = new HashMap<>();
m.put("a", 1); m.put("b", 2); m.put("c", 3);
for (var e : m.entrySet()) {
  System.out.println(e.getKey() + "=" + e.getValue());
}

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

Bài tiếp theo: Mini-challenge: LRU Cache với LinkedHashMap