Hash table, linked order, red-black tree và binary heap

1. HashMap fields và invariants

transient Node<K,V>[] table;
transient int size;
int threshold;
final float loadFactor;

• table là mảng buckets; capacity luôn được chọn theo power of two trong implementation hiện đại.
• size là số mappings, không phải số buckets.
• threshold ≈ capacity × loadFactor; mặc định load factor 0.75.
• Mỗi bucket rỗng, linked nodes hoặc tree bin khi collision đủ dày và table đủ lớn.

Đối chiếu nguồn: [M1] [M2]

2. put(key,value) từng bước

1. Tính hash đã spread: implementation trộn high bits vào low bits để low-bit mask dùng thêm entropy.
2. Nếu table chưa được khởi tạo, allocate theo initial/default capacity.
3. Tính index bằng (n - 1) & hash; power-of-two capacity làm phép mask tương đương modulo trong miền phù hợp.
4. Bucket rỗng: đặt node mới.
5. Bucket có entry: so hash, sau đó key identity hoặc equals. Cùng key thì replace value.
6. Nếu khác key: đi qua list hoặc tree bin; append/insert và treeify khi điều kiện đạt.
7. Nếu thêm mapping mới làm size vượt threshold, resize.

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

int index = (table.length - 1) & hash;

Đối chiếu nguồn: [M1] [M2]

3. get(key)

Tính cùng spread hash và bucket index; kiểm tra first node rồi traverse list/tree, so hash trước và equality sau. Vì vậy mutable key đổi field tham gia hashCode/equals sau insert có thể nằm ở bucket cũ nhưng được tìm bằng hash mới, khiến get trả null.

Đối chiếu nguồn: [M1] [M2]

4. Collision, treeification và complexity

Collision là bình thường. Java 8+ có thể chuyển bucket dài thành red-black tree khi bin đạt threshold (thường 8) và table có capacity tối thiểu (thường 64); nếu table còn nhỏ, resize được ưu tiên. Tree bin có lookup O(log n) trong điều kiện phù hợp; average map operation vẫn O(1). Các con số này là OpenJDK implementation detail, không phải Map contract.

Đối chiếu nguồn: [M2]

5. Resize không đơn giản là “rehash tất cả”

Khi capacity gấp đôi, một entry hoặc giữ index cũ hoặc chuyển tới oldIndex + oldCapacity tùy bit hash & oldCapacity. OpenJDK split bucket thành low/high lists, tránh gọi lại user hashCode. Resize vẫn O(n), allocation lớn và có latency/memory spike; initial capacity hợp lý giúp workload lớn.

Đối chiếu nguồn: [M1] [M2]

6. equals/hashCode contract

• Nếu a.equals(b) thì bắt buộc cùng hash code.
• Cùng hash code không bắt buộc equal.
• Keys nên immutable theo các fields tham gia equality/hash.
• Hash distribution kém tạo collision và giảm performance.
• Một null key được hỗ trợ; null hash được xử lý đặc biệt.

record AccountKey(String bankCode, String accountNumber) {}

Map<AccountKey, Account> accounts = new HashMap<>();
// Record phù hợp vì equality/hashCode theo immutable components.

Đối chiếu nguồn: [M1] [M9]

7. HashSet thực chất lưu gì?

HashSet<E> dùng một HashMap<E,Object> bên dưới. Element trở thành map key; value là cùng một sentinel object dùng chung. add(e) tương đương put key và trả true khi trước đó chưa có mapping. Vì thế uniqueness, null support, collision và mutable-element risk theo HashMap key semantics.

Đối chiếu nguồn: [M5]

8. LinkedHashMap và LRU

Ngoài hash table, entries tham gia doubly linked order. Insertion-order giữ thứ tự thêm; access-order di chuyển entry được access về cuối. Override removeEldestEntry tạo bounded in-process LRU đơn giản.

Map<K,V> lru = new LinkedHashMap<>(capacity, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > capacity;
    }
};

Nó không thread-safe, không có TTL/weight/distributed consistency và eviction chạy khi insert. Production cache thường cần Caffeine/Redis tùy boundary.

Đối chiếu nguồn: [M6]

9. TreeMap/TreeSet: red-black tree

TreeMap là self-balancing binary search tree. Search/put/remove O(log n); rotation/recolor giữ tree height bounded. Key ordering đến từ natural ordering hoặc Comparator. Nếu comparison trả 0, map coi keys là cùng vị trí dù equals false; comparator nên consistent with equals nếu muốn Map/Set behavior trực giác.

• floor/ceiling/lower/higher tận dụng ordered tree.
• subMap/headMap/tailMap là range views, thường backed bởi map.
• TreeSet được backed bởi navigable map với elements làm keys.

Đối chiếu nguồn: [M3] [M7]

10. PriorityQueue: binary heap

PriorityQueue giữ heap trong array. Với min-heap, parent không lớn hơn children; không yêu cầu toàn array sorted. offer đặt cuối rồi siftUp; poll lấy root, đưa phần tử cuối lên root rồi siftDown.

parent(i) = (i - 1) / 2
left(i)   = 2 * i + 1
right(i)  = 2 * i + 2

• peek O(1), offer/poll O(log n).
• Remove arbitrary object/search O(n).
• Iterator chỉ đi theo heap array, không sorted order.
• Top-K thường giữ min-heap kích thước K, O(n log K), thay vì sort toàn bộ O(n log n).

Đối chiếu nguồn: [M4] [M8]

11. Interview answer: HashMap internals trong 60 giây

Đối chiếu nguồn: [M1] [M2]

12. Mini-labs: tự kiểm chứng implementation và contract

Bổ sung thực hành · Hai chương trình độc lập, không có thư viện ngoài. Java 21; lưu đúng tên file hiển thị. Assertion dùng kiểm tra tường minh, không phụ thuộc cờ -ea.

Lab C1 · Collision và ranh giới treeification

Failure-first: thay phỏng đoán “8 node chắc chắn là tree” bằng trace trên HashMap initial capacity 64, mọi key cùng hash. Các key vẫn có equality và ordering phân biệt được nhau.

TreeifyLab.java

import java.lang.reflect.Field;
import java.util.HashMap;

public class TreeifyLab {
    record Key(int id) implements Comparable<Key> {
        @Override public int hashCode() { return 42; }
        @Override public int compareTo(Key other) {
            return Integer.compare(id, other.id);
        }
    }

    public static void main(String[] args) throws Exception {
        var map = new HashMap<Key, Integer>(64);
        Field field = HashMap.class.getDeclaredField("table");
        field.setAccessible(true); // Lab-only: requires --add-opens.
        for (int i = 1; i <= 9; i++) {
            map.put(new Key(i), i);
            if (i == 8 || i == 9) {
                Object[] buckets = (Object[]) field.get(map);
                int hash = 42 ^ (42 >>> 16);
                Object bin = buckets[(buckets.length - 1) & hash];
                String kind = bin.getClass().getSimpleName();
                System.out.printf("size=%d capacity=%d bin=%s%n",
                    map.size(), buckets.length, kind);
                String expected = i == 8 ? "Node" : "TreeNode";
                if (buckets.length != 64 || !kind.equals(expected)) {
                    throw new AssertionError("Different implementation: " + kind);
                }
            }
        }
        for (int i = 1; i <= 9; i++) {
            if (!Integer.valueOf(i).equals(map.get(new Key(i)))) {
                throw new AssertionError("Missing key " + i);
            }
        }
        System.out.println("PASS: treeification and equality lookup");
    }
}

javac --release 21 TreeifyLab.java
java --add-opens java.base/java.util=ALL-UNNAMED TreeifyLab

Quan sát trên OpenJDK 21: sau 8 mappings: capacity=64, bin=Node; sau mapping thứ 9: bin=TreeNode. Lookup bằng key mới nhưng equal vẫn đúng. Thử capacity 16 và trace từng lần put để thấy resize được ưu tiên trước khi treeify.

Acceptance: trace khớp nhánh source putVal/treeifyBin trên bản JDK đã ghi nhận và không mất mapping. Nộp: java -version, stdout, initial capacity và giải thích vì sao hằng số 8 không đồng nghĩa tree xuất hiện ở lần insert thứ 8.

Lab C2 · Equality, comparator, LRU và heap

Failure-first: dự đoán sai rằng hai instances là hai keys, case-insensitive tree giữ cả hai cách viết, get không ảnh hưởng LRU, hoặc iterator heap luôn sorted. Chạy các checks để phân biệt từng invariant.

MapHeapLab.java

import java.util.*;

public class MapHeapLab {
    record AccountKey(String bankCode, String accountNumber) {}

    static void check(boolean ok, String message) {
        if (!ok) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        var first = new AccountKey("BK", "001");
        var equal = new AccountKey("BK", "001");
        var accounts = new HashMap<AccountKey, Integer>();
        accounts.put(first, 10);
        check(accounts.put(equal, 20) == 10, "put must return old value");
        check(accounts.size() == 1, "equal keys must share one mapping");
        check(new HashSet<>(List.of(first, equal)).size() == 1,
            "set uniqueness");

        var tree = new TreeMap<String, Integer>(
            String.CASE_INSENSITIVE_ORDER);
        tree.put("java", 1);
        tree.put("JAVA", 2);
        check(!"java".equals("JAVA") && tree.size() == 1,
            "comparator identity differs from equals");

        final int capacity = 2;
        Map<String, Integer> lru =
            new LinkedHashMap<>(capacity, 0.75f, true) {
                @Override
                protected boolean removeEldestEntry(
                        Map.Entry<String, Integer> eldest) {
                    return size() > capacity;
                }
            };
        lru.put("A", 1);
        lru.put("B", 2);
        lru.get("A");
        lru.put("C", 3);
        check(new ArrayList<>(lru.keySet()).equals(List.of("A", "C")),
            "B must be evicted after accessing A");

        var heap = new PriorityQueue<>(List.of(9, 1, 8, 2, 7));
        System.out.println("Iterator (not a sorted-order contract): " + heap);
        var ordered = new ArrayList<Integer>();
        while (!heap.isEmpty()) ordered.add(heap.poll());
        check(ordered.equals(List.of(1, 2, 7, 8, 9)), "poll order");
        System.out.println("PASS: equality, set, comparator, LRU, heap");
    }
}

javac --release 21 MapHeapLab.java
java MapHeapLab

Acceptance: một mapping cho hai equal keys; comparator gộp hai cách viết; B bị eviction; poll trả thứ tự 1, 2, 7, 8, 9. Không assert chuỗi iterator: có thể tình cờ sorted ở một input. Nộp: stdout và giải thích cái nào là contract, cái nào là policy/comparator do test chọn.

13. Selection guide và review có bằng chứng

Bổ sung · Chọn theo query pattern và ownership; Big-O chỉ là bước đầu.