equals, hashCode và HashMap: bỏ Order vào HashSet rồi không tìm lại được

Đây là bug kinh điển: class Order chưa override equals và hashCode. Ta đi từ bug tới cách HashMap chạy bên trong.

1. Bài toán: lọc đơn trùng khi đồng bộ từ cổng thanh toán

public class Order {
    private final String id;
    private final String customerId;
    private BigDecimal total;
    // constructor, getter... KHÔNG có equals/hashCode
}

Set<Order> processed = new HashSet<>();
processed.add(new Order("ORD-1", "C001", new BigDecimal("500000")));

// webhook gửi lại cùng đơn, parse thành object mới
Order dup = new Order("ORD-1", "C001", new BigDecimal("500000"));
processed.contains(dup);   // false ❌ → đơn bị xử lý 2 lần, trừ kho 2 lần

2. Vấn đề

• Không override thì dùng Object.equals (so ==) và Object.hashCode (thường dựa trên identity). Hai object khác nhau → khác nhau, dù cùng dữ liệu.
• Nếu chỉ override equals mà quên hashCode: hai đơn "bằng nhau" nhưng hash khác → rơi vào hai bucket khác nhau → HashSet không bao giờ gọi tới equals. Vẫn false.

3. Giải pháp: equals/hashCode contract

1. Reflexive: a.equals(a) luôn true.
2. Symmetric: a.equals(b) ⇔ b.equals(a).
3. Transitive: a=b, b=c ⇒ a=c.
4. Consistent: gọi nhiều lần cho cùng kết quả nếu object không đổi.
5. a.equals(null) luôn false.
6. Quan trọng nhất: a.equals(b) ⇒ a.hashCode() == b.hashCode(). Ngược lại không bắt buộc (cùng hash chưa chắc equals: đó là collision).

4. Code từng bước

Bước 1: Chọn "danh tính" của Order: đơn hàng được xác định bởi id, không phải total (total có thể đổi khi áp voucher).

Bước 2: Override cả hai, dùng cùng tập field

public class Order {
    private final String id;
    private final String customerId;
    private BigDecimal total;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Order other)) return false;    // pattern matching Java 16
        return id.equals(other.id);
    }

    @Override
    public int hashCode() {
        return id.hashCode();                              // cùng field với equals
    }
}

Bước 3: Value object thì dùng record: record tự sinh equals/hashCode/toString theo mọi component, và field là final.

public record OrderLineKey(String orderId, String productId) {}

Map<OrderLineKey, Integer> qty = new HashMap<>();
qty.put(new OrderLineKey("ORD-1", "P01"), 2);
qty.get(new OrderLineKey("ORD-1", "P01"));   // 2 ✅

Bước 4: Viết test

@Test
void sameIdMeansSameOrder() {
    var a = new Order("ORD-1", "C001", new BigDecimal("500000"));
    var b = new Order("ORD-1", "C001", new BigDecimal("450000"));
    assertEquals(a, b);
    assertEquals(a.hashCode(), b.hashCode());
    assertTrue(new HashSet<>(List.of(a)).contains(b));
}

5. Cách hoạt động: HashMap bên trong

map.put(key, value):
 1. h = key.hashCode()
 2. hash spreading: h ^ (h >>> 16)    ← trộn 16 bit cao xuống thấp
 3. index = hash & (n - 1)             ← n = số bucket, luôn là lũy thừa 2
 4. bucket rỗng → đặt Node mới
    bucket có Node → duyệt: hash bằng nhau && equals → ghi đè value
                           không có → nối Node vào cuối (collision chaining)

table (n = 16)
 [0]  null
 [1]  Node(ORD-1) → Node(ORD-17) → null      ← collision: cùng index
 [2]  null
 ...
 [5]  TreeNode (red-black tree)              ← chain ≥ 8 và table ≥ 64 → treeify
 ...
 [15] Node(ORD-9)

• Hash spreading: vì index chỉ lấy vài bit thấp, nếu hashCode chỉ khác ở bit cao thì sẽ dồn vào cùng bucket. XOR với 16 bit cao giúp phân tán đều hơn.
• Treeify (Java 8): một bucket có ≥ 8 node (và table ≥ 64, nếu chưa đủ thì resize trước) đổi linked list thành red-black tree: tìm kiếm trong bucket từ O(n) xuống O(log n). Giảm còn ≤ 6 thì đổi lại list.
• Load factor 0.75: khi size > capacity × 0.75 (16 × 0.75 = 12) thì resize gấp đôi, phân bổ lại các node. Nhờ n là lũy thừa 2, mỗi node chỉ ở lại index cũ hoặc chuyển sang index + oldCap.
• Cho phép một key null (luôn ở bucket 0) và nhiều value null.

6. So sánh

7. Khi nào nên dùng / không nên

• Class sẽ nằm trong HashSet, làm key HashMap, hoặc so sánh trong test → override cả hai, hoặc dùng record.
• JPA entity: so theo id nghiệp vụ hoặc id DB có xử lý null cẩn thận; tránh dùng mọi field (lazy collection, id null trước khi persist). Lombok @Data trên entity là cái bẫy.
• Không đưa field có thể thay đổi vào hashCode nếu object làm key.

Đúng chỗ nguy hiểm. Entry vẫn nằm trong map nhưng bị "mất tích":

Map<Order, Invoice> invoices = new HashMap<>();
order.setStatus(NEW);
invoices.put(order, invoice);        // hash tính theo NEW → bucket 3

order.setStatus(PAID);               // hashCode giờ khác → trỏ tới bucket 11
invoices.get(order);                 // null ❌ (tìm ở bucket 11)
invoices.containsKey(order);         // false
invoices.size();                     // 1  — entry vẫn còn, nằm ở bucket 3
invoices.put(order, invoice2);       // thêm entry thứ 2 → size 2, memory leak

bucket 3:  [Order(NEW→PAID), invoice]   ← vẫn ở đây, hash cũ lưu trong Node
bucket 11: (trống)                       ← get() tìm ở đây

HashMap lưu hash vào Node lúc put và không tính lại. Cách tránh:

• Key immutable (String, Long, record, enum).
• Hoặc hashCode chỉ dùng field không đổi (id final).
• Bắt buộc đổi field trong key: remove → đổi → put lại.

Gần đúng, chỉ chỉnh một điểm: tham số là capacity (số bucket), không phải số phần tử. Map resize khi size vượt capacity × 0.75.

new HashMap<>(10_000)
  → làm tròn lên lũy thừa 2: 16384 bucket
  → ngưỡng = 16384 × 0.75 = 12288 > 10000 → lần này may mắn không resize

new HashMap<>(12_000)  → 16384, ngưỡng 12288: OK
new HashMap<>(13_000)  → 16384, nhưng 13000 > 12288 → vẫn resize 1 lần

Cách đúng là tính theo số phần tử mong đợi. Java 19+ có sẵn:

Map<String, BigDecimal> prices = HashMap.newHashMap(10_000);   // tự tính capacity
// Java 17: new HashMap<>((int) (expected / 0.75f) + 1)

Mỗi lần resize phải duyệt và phân bổ lại tất cả node, nên với map lớn build một lần thì đặt sẵn capacity giúp tránh vài lần copy. Với map nhỏ thì không cần bận tâm.

Không. Contract chỉ đi một chiều: equals ⇒ cùng hashCode. Cùng hashCode chưa chắc equals, vì hashCode chỉ có 2³² giá trị còn số object có thể là vô hạn.

"Aa".hashCode();   // 2112
"BB".hashCode();   // 2112
"Aa".equals("BB"); // false  → collision thật, HashMap xử lý bằng chaining + equals

Đó là lý do HashMap luôn kiểm tra cả hai: so hash trước (rẻ, loại nhanh), rồi mới gọi equals để chắc chắn.

Đây là câu gần như chắc chắn gặp. Trả lời theo thứ tự: contract → put/get → collision → resize.

Câu 1: Vì sao override equals phải override hashCode?

🇻🇳 Tiếng Việt:

Contract yêu cầu hai object equals phải có cùng hashCode. HashMap và HashSet dùng hashCode để chọn bucket trước rồi mới gọi equals. Nếu chỉ override equals, hai object bằng nhau có thể rơi vào hai bucket khác nhau và không bao giờ được so sánh, nên Set chứa trùng hoặc get trả null. Em thường dùng chung một tập field bất biến cho cả hai, hoặc dùng record.

🇬🇧 English:

The contract says equal objects must have equal hash codes. HashMap and HashSet use the hash code to pick a bucket before calling equals. If only equals is overridden, two equal objects may land in different buckets and never get compared, so a Set holds duplicates or get returns null. I use the same immutable fields for both, or simply use a record.

Câu 2: HashMap hoạt động bên trong thế nào?

🇻🇳 Tiếng Việt:

HashMap là mảng bucket, kích thước lũy thừa 2. Khi put, nó lấy hashCode, trộn 16 bit cao xuống, rồi & (n-1) để ra index. Nếu bucket đã có node thì so hash và equals: trùng thì ghi đè, không thì nối vào linked list. Từ Java 8, bucket có từ 8 node trở lên và table ít nhất 64 thì chuyển thành red-black tree, tìm kiếm O(log n). Khi size vượt capacity × load factor 0.75 thì resize gấp đôi. get/put trung bình O(1).

🇬🇧 English:

A HashMap is an array of buckets whose size is a power of two. On put it takes the hash code, spreads the high bits into the low bits, and masks with n-1 to get the index. If the bucket is occupied it compares hash and equals: a match replaces the value, otherwise the node is chained. Since Java 8 a bucket with eight or more nodes, in a table of at least 64, becomes a red-black tree with O(log n) lookup. When size exceeds capacity times the 0.75 load factor, the table doubles. Average get and put are O(1).

Câu 3: Dùng object mutable làm key có vấn đề gì?

🇻🇳 Tiếng Việt:

Hash được tính lúc put và lưu trong node. Nếu sau đó field tham gia hashCode thay đổi, get sẽ tìm ở bucket khác và trả null, còn entry cũ vẫn nằm trong map gây rò bộ nhớ. Vì vậy key nên immutable như String, enum, record.

🇬🇧 English:

The hash is computed at put time and stored in the node. If a field used by hashCode changes later, get looks in a different bucket and returns null, while the old entry stays in the map and leaks. That is why keys should be immutable, like String, enums or records.

Cách nhớ ngắn gọn

• equals ⇒ cùng hash; cùng hash ⇏ equals.
• put: hash → spread → &(n-1) → chain → treeify ở 8.
• Load factor 0.75, resize ×2, capacity lũy thừa 2.
• Key immutable; value object dùng record.