Map và hợp đồng equals/hashCode

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

// --- Thêm / cập nhật ---
diem.put("An", 8);            // trả về null (khoá mới)
diem.put("Bình", 9);
Integer cu = diem.put("An", 10);  // trả về 8 — GIÁ TRỊ CŨ, và ghi đè
diem.putIfAbsent("An", 5);      // không làm gì vì "An" đã có

// --- Đọc ---
diem.get("An");                // 10
diem.get("Chi");               // null ⚠️ — không ném lỗi
diem.getOrDefault("Chi", 0);  // 0  ⭐ an toàn hơn nhiều

// ⚠️ Bẫy NullPointerException khi unboxing
// int d = diem.get("Chi");   // NPE — null không unbox thành int được
int d = diem.getOrDefault("Chi", 0);   // ✅

// --- Kiểm tra / xoá ---
diem.containsKey("An");         // true  — O(1) ⚡
diem.containsValue(10);        // true  — O(n) ⚠️ phải duyệt hết
diem.remove("An");             // trả về 10
diem.remove("Bình", 5);       // chỉ xoá nếu giá trị khớp — trả false
diem.size();
diem.isEmpty();
diem.clear();

// --- Map bất biến (Java 9+) ---
Map<String, Integer> batBien = Map.of("a", 1, "b", 2);   // tối đa 10 cặp
Map<String, Integer> nhieu = Map.ofEntries(
    Map.entry("a", 1), Map.entry("b", 2)     // không giới hạn
);

HashMap
│
└── Node[] table          // mảng "bucket", kích thước LUÔN là luỹ thừa của 2
     │
     ├── [0]  → null
     ├── [1]  → Node("An", 10) → null
     ├── [2]  → null
     ├── [3]  → Node("Bình", 9) → Node("Chi", 7) → null    // VA CHẠM: liên kết
     ├── ...
     └── [15] → Node("Dũng", 8) → null

// Mỗi Node lưu 4 thứ:
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;    // mã băm đã trộn — cache lại để không tính lại
    final K key;
    V value;
    Node<K,V> next;     // node kế trong cùng bucket (chuỗi va chạm)
}

// ---------- Bước trộn bit ----------
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// Vì sao XOR với 16 bit cao? Xem callout bên dưới.

// ---------- put ----------
public V put(K key, V value) {
    int h = hash(key);
    int i = h & (table.length - 1);       // ① tìm bucket

    for (Node<K,V> e = table[i]; e != null; e = e.next) {   // ② duyệt chuỗi
        if (e.hash == h && (e.key == key || key.equals(e.key))) {
            V cu = e.value;
            e.value = value;               // ③ khoá đã có → ghi đè
            return cu;
        }
    }
    table[i] = new Node<>(h, key, value, table[i]);   // ④ thêm vào đầu chuỗi
    if (++soLuong > nguong) resize();               // ⑤ đầy quá → nới rộng
    return null;
}

// ---------- get ----------
public V get(Object key) {
    int h = hash(key);
    for (Node<K,V> e = table[h & (table.length-1)]; e != null; e = e.next) {
        if (e.hash == h && (e.key == key || key.equals(e.key)))
            return e.value;
    }
    return null;
}

// Hai khoá khác nhau có thể cho cùng chỉ số bucket → VA CHẠM

// Trước Java 8: luôn dùng danh sách liên kết
[3] → Node(k1) → Node(k2) → Node(k3) → ... → Node(k100)
// Trường hợp xấu nhất: mọi khoá cùng bucket → get() thành O(n)
// → lỗ hổng "hash collision DoS": kẻ tấn công gửi các khoá cố ý trùng hash

// Từ Java 8: chuỗi dài quá 8 phần tử VÀ bảng ≥ 64 → chuyển thành CÂY ĐỎ ĐEN
[3] → TreeNode
         ╱      ╲
    TreeNode   TreeNode      // tra cứu O(log n) thay vì O(n)
      ╱  ╲       ╱  ╲

// Khi chuỗi rút xuống ≤ 6 phần tử (do xoá hoặc resize) → quay lại liên kết
// Hai ngưỡng 8 và 6 khác nhau để tránh chuyển đổi qua lại liên tục (hysteresis)

// Khi soLuong > capacity × loadFactor (mặc định 16 × 0.75 = 12):
//   1. Tạo bảng mới GẤP ĐÔI (16 → 32)
//   2. Phân bổ lại MỌI node vào bucket mới
//   → Thao tác này TỐN KÉM: O(n)

// ❌ Thêm 1 triệu phần tử vào map mặc định
Map<String, Integer> m = new HashMap<>();
// → khoảng 17 lần resize, mỗi lần phân bổ lại toàn bộ

// ✅ Biết trước số lượng thì đặt dung lượng ban đầu
Map<String, Integer> m2 = new HashMap<>(1_400_000);
// Công thức: soPhanTu / 0.75 + 1, làm tròn lên luỹ thừa của 2

// ✅ Java 19+: có hàm tiện ích làm sẵn việc đó
Map<String, Integer> m3 = HashMap.newHashMap(1_000_000);

// ❌ Chỉ override equals, QUÊN hashCode
class SanPham {
    String ma;
    SanPham(String ma) { this.ma = ma; }

    @Override
    public boolean equals(Object o) {
        return o instanceof SanPham s && ma.equals(s.ma);
    }
    // KHÔNG có hashCode() → dùng bản mặc định của Object (dựa trên địa chỉ)
}

Map<SanPham, Integer> kho = new HashMap<>();
kho.put(new SanPham("SP01"), 100);

System.out.println(kho.get(new SanPham("SP01")));   // null ⚠️⚠️
System.out.println(kho.containsKey(new SanPham("SP01")));  // false ⚠️

// Vì sao? Hai object có mã băm KHÁC NHAU (địa chỉ khác nhau)
// → rơi vào hai bucket khác nhau → equals() KHÔNG BAO GIỜ được gọi


// ✅ Override CẢ HAI
class SanPham {
    final String ma;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        return o instanceof SanPham s && Objects.equals(ma, s.ma);
    }

    @Override
    public int hashCode() {
        return Objects.hash(ma);      // ĐÚNG những trường như equals
    }
}

// ✅✅ Tốt nhất: dùng record — sinh sẵn cả hai đúng chuẩn
record SanPham(String ma) { }

Map<String, Integer> diem = Map.of("An", 8, "Bình", 9, "Chi", 7);

// ⭐ CÁCH TỐT NHẤT: entrySet() — một lần duyệt lấy cả khoá lẫn giá trị
for (Map.Entry<String, Integer> e : diem.entrySet()) {
    System.out.println(e.getKey() + " = " + e.getValue());
}
for (var e : diem.entrySet()) { ... }        // gọn hơn với var

// ❌ TỆ: keySet() rồi get() — mỗi vòng lặp là MỘT lần tra cứu thừa
for (String k : diem.keySet()) {
    System.out.println(k + " = " + diem.get(k));   // tra cứu lại — chậm gấp đôi
}

// ✅ Chỉ cần khoá / chỉ cần giá trị
for (String k : diem.keySet())   { ... }
for (Integer v : diem.values()) { ... }

// ⭐ forEach (Java 8+) — ngắn gọn nhất
diem.forEach((k, v) -> System.out.println(k + " = " + v));

// Duyệt theo thứ tự sắp xếp mà không đổi kiểu map
diem.entrySet().stream()
    .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
    .forEach(e -> System.out.println(e));

// ⚠️ Xoá khi đang duyệt — phải qua iterator hoặc removeIf
diem2.entrySet().removeIf(e -> e.getValue() < 5);   // ✅
diem2.values().removeIf(v -> v < 5);              // ✅ tương đương

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

// ---------- getOrDefault: tránh null ----------
int n = dem.getOrDefault("x", 0);

// ---------- ĐẾM TẦN SUẤT — ba cách ----------
String[] tu = {"java", "python", "java", "go", "java"};

// ❌ Cách cũ, dài dòng
for (String t : tu) {
    if (dem.containsKey(t)) dem.put(t, dem.get(t) + 1);
    else                     dem.put(t, 1);
}

// ✅ getOrDefault
for (String t : tu) dem.put(t, dem.getOrDefault(t, 0) + 1);

// ✅✅ merge — ngắn nhất và diễn đạt đúng ý nhất
for (String t : tu) dem.merge(t, 1, Integer::sum);
// Ý nghĩa: chưa có khoá → đặt 1; đã có → áp dụng Integer::sum(cũ, 1)
System.out.println(dem);   // {java=3, python=1, go=1}


// ---------- computeIfAbsent: nhóm phần tử ----------
Map<String, List<String>> nhom = new HashMap<>();

// ❌ Cách cũ
for (String t : tu) {
    String chuDau = t.substring(0, 1);
    if (!nhom.containsKey(chuDau)) nhom.put(chuDau, new ArrayList<>());
    nhom.get(chuDau).add(t);
}

// ✅ computeIfAbsent — một dòng
for (String t : tu) {
    nhom.computeIfAbsent(t.substring(0, 1), k -> new ArrayList<>()).add(t);
}
// {j=[java, java, java], p=[python], g=[go]}


// ---------- Toàn bộ họ compute* ----------
dem.computeIfAbsent("rust", k -> 0);           // chỉ khi CHƯA có khoá
dem.computeIfPresent("java", (k, v) -> v * 2);  // chỉ khi ĐÃ có
dem.compute("go", (k, v) -> v == null ? 1 : v + 1);   // cả hai trường hợp
// ⚠️ Hàm trả về null → XOÁ khoá khỏi map

dem.putIfAbsent("kotlin", 1);                 // khác computeIfAbsent: giá trị đã tính sẵn
dem.replaceAll((k, v) -> v * 10);              // đổi mọi giá trị
dem.replace("java", 100);                     // chỉ đổi nếu khoá tồn tại
dem.remove("go", 1);                          // chỉ xoá nếu giá trị khớp

// Chế độ mặc định: giữ thứ tự THÊM VÀO
Map<String, Integer> m = new LinkedHashMap<>();
m.put("c", 3); m.put("a", 1); m.put("b", 2);
System.out.println(m);   // {c=3, a=1, b=2} — đúng thứ tự thêm

// ⭐ Chế độ THỨ TỰ TRUY CẬP — tham số thứ ba = true
Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true);
lru.put("a", 1); lru.put("b", 2); lru.put("c", 3);
lru.get("a");                          // truy cập "a" → đưa nó xuống cuối
System.out.println(lru);              // {b=2, c=3, a=1}


// ⭐⭐ Bộ nhớ đệm LRU hoàn chỉnh — chỉ cần override MỘT method
class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int sucChua;

    LruCache(int sucChua) {
        super(sucChua, 0.75f, true);   // true = thứ tự truy cập
        this.sucChua = sucChua;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> cuNhat) {
        return size() > sucChua;      // đầy thì tự loại phần tử ít dùng nhất
    }
}

LruCache<String, String> cache = new LruCache<>(3);
cache.put("a", "1"); cache.put("b", "2"); cache.put("c", "3");
cache.get("a");                  // "a" thành mới nhất
cache.put("d", "4");            // đầy → loại "b" (ít dùng nhất)
System.out.println(cache);      // {c=3, a=1, d=4}

TreeMap<Integer, String> t = new TreeMap<>();
t.put(30, "ba mươi");
t.put(10, "mười");
t.put(20, "hai mươi");
System.out.println(t);   // {10=mười, 20=hai mươi, 30=ba mươi} — LUÔN sắp xếp

// --- Truy vấn hai đầu ---
t.firstKey();      // 10
t.lastKey();       // 30
t.firstEntry();    // 10=mười
t.pollFirstEntry(); // lấy VÀ xoá

// --- Truy vấn lân cận ---
t.floorKey(25);     // 20 — khoá lớn nhất ≤ 25
t.ceilingKey(25);   // 30 — khoá nhỏ nhất ≥ 25
t.lowerKey(20);     // 10 — nhỏ hơn hẳn
t.higherKey(20);    // 30 — lớn hơn hẳn

// --- Khung nhìn khoảng ---
t.headMap(20);              // {10=mười}          — nhỏ hơn 20
t.tailMap(20);              // {20=..., 30=...}   — từ 20 trở lên
t.subMap(10, true, 20, true); // [10, 20] — kiểm soát cả hai biên
t.descendingMap();          // đảo ngược thứ tự

// --- Sắp theo tiêu chí riêng ---
TreeMap<String, Integer> khongPhanBiet =
    new TreeMap<>(String.CASE_INSENSITIVE_ORDER);

// --- Ứng dụng thật: tra bảng theo khoảng ---
TreeMap<Integer, String> xepLoai = new TreeMap<>();
xepLoai.put(0,  "Yếu");
xepLoai.put(50, "Trung bình");
xepLoai.put(70, "Khá");
xepLoai.put(90, "Giỏi");

int diem = 75;
System.out.println(xepLoai.floorEntry(diem).getValue());   // "Khá"
// ⭐ Tra bảng theo khoảng chỉ với MỘT lời gọi — HashMap không làm được

// ---------- ① Đếm tần suất ----------
Map<String, Integer> tanSuat = new HashMap<>();
for (String t : danhSachTu) tanSuat.merge(t, 1, Integer::sum);

// Top 5 từ xuất hiện nhiều nhất
tanSuat.entrySet().stream()
    .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
    .limit(5)
    .forEach(e -> System.out.printf("%-15s %d%n", e.getKey(), e.getValue()));


// ---------- ② Nhóm theo tiêu chí ----------
Map<String, List<SinhVien>> theoLop = new HashMap<>();
for (SinhVien sv : danhSach) {
    theoLop.computeIfAbsent(sv.lop(), k -> new ArrayList<>()).add(sv);
}
// (Chương 10 sẽ làm việc này bằng Collectors.groupingBy — một dòng)


// ---------- ③ Chỉ mục tra cứu nhanh ----------
Map<String, SinhVien> chiMuc = new HashMap<>();
for (SinhVien sv : danhSach) chiMuc.put(sv.ma(), sv);
SinhVien tim = chiMuc.get("SV001");       // O(1) thay vì duyệt O(n)


// ---------- ④ Bộ nhớ đệm cho phép tính tốn kém ----------
private final Map<Integer, Long> cacheFib = new HashMap<>();

long fib(int n) {
    if (n <= 1) return n;
    return cacheFib.computeIfAbsent(n, k -> fib(k-1) + fib(k-2));
    // ⚠️ CẢNH BÁO: đệ quy trong computeIfAbsent gây ConcurrentModificationException
    //    từ Java 9. Xem callout bên dưới.
}


// ---------- ⑤ EnumMap: nhanh nhất khi khoá là enum ----------
enum Thu { HAI, BA, TU, NAM, SAU, BAY, CN }
Map<Thu, String> lich = new EnumMap<>(Thu.class);
lich.put(Thu.HAI, "Họp nhóm");
// Bên trong chỉ là một MẢNG đánh chỉ số theo ordinal() → nhanh hơn HashMap,
// tốn ít bộ nhớ hơn, và luôn duyệt theo thứ tự khai báo enum.