Hash function — Uniform, avalanche, và hashCode/equals contract

Junior Java dev viết class User với equals so sánh userId nhưng quên override hashCode. Unit test pass sạch. Deploy production: userSet.contains(user) trả về false dù user đã được add() vào set. HashMap dùng User làm key cũng vỡ tương tự — put vào rồi get về null. Không có exception, không có warning, chỉ có behavior sai im lặng.

Bug này xuất hiện vì HashSet, HashMap, ConcurrentHashMap đều dựa vào hashCode() để định vị phần tử — không có hashCode đúng, mọi lookup đều thất bại dù equals báo hai object là "bằng nhau". Hash function là backbone của HashMap, HashSet, ConcurrentHashMap, cache, Bloom filter, distributed shard. Bài này giải thích uniform distribution, avalanche effect, hashCode/equals contract, và vì sao bug hashCode lại silent.

1. Analogy — Phòng đăng ký số thứ tự

Hình dung một phòng khám có N quầy phục vụ. Khi bệnh nhân vào, nhân viên phát số dựa trên một đặc điểm của bệnh nhân (số CMND, năm sinh) và chỉ họ đến quầy tương ứng.

Hash function là quy tắc phát số đó — biến đặc điểm của bệnh nhân thành chỉ số quầy. Bucket là quầy phục vụ. Khi cần tìm một bệnh nhân, thay vì hỏi tất cả N quầy, bạn chạy lại quy tắc phát số để biết họ đang ở quầy nào — tìm kiếm O(1) thay vì O(n).

Uniform — mỗi quầy nhận xấp xỉ tổng số bệnh nhân chia N, không quầy nào bị ngộp. Avalanche — thay đổi 1 ký tự trong CMND khiến bệnh nhân được chỉ đến quầy hoàn toàn khác, không phải quầy lân cận.

2. Định nghĩa hash function

Hash function là hàm h: K -> int ánh xạ key bất kỳ sang số nguyên trong miền cố định. Trong Java, hashCode() trả về int 32-bit — miền từ -2^31 đến 2^31 - 1. HashMap thu nhỏ kết quả về index trong internal array bằng phép hash & (capacity - 1).

Bốn thuộc tính cần thiết cho hash function dùng trong cấu trúc dữ liệu:

Hai thuộc tính không cần cho non-crypto hash function: one-way (không thể reverse) và collision-resistant (không thể tìm hai input cùng output). Đây là yêu cầu của cryptographic hash — SHA-256, bcrypt — học ở Module 12. HashMap chỉ cần nhanh và đều; collision là điều chấp nhận được, miễn hiếm.

3. Uniform distribution

Uniform distribution nghĩa là với tập input ngẫu nhiên, output trải đều qua tất cả bucket — không có "hot spot" nào nhận quá nhiều key.

Đo bằng cách phân phối N key vào M bucket rồi kiểm tra độ lệch:

// Demo: check bucket distribution of String.hashCode() across 16 buckets
// Expected: ~6250 keys per bucket (100_000 / 16)
int[] buckets = new int[16];
for (int i = 0; i < 100_000; i++) {
    int h = ("key" + i).hashCode();
    buckets[h & 15]++;  // mod 16 == & 15 (power-of-2 trick)
}
for (int i = 0; i < 16; i++) {
    System.out.printf("bucket[%2d] = %d%n", i, buckets[i]);
}
// Output range: roughly 6100-6400 per bucket -- uniform

Nếu hash function tệ, một bucket có thể nhận 80% key trong khi bucket khác gần trống. HashMap dùng chaining — mỗi bucket là một linked list (Java 8+: treeify thành red-black tree khi chain dài hơn 8). Bucket quá tải → chain dài → lookup O(n) thay vì O(1).

4. Avalanche effect

Avalanche effect: thay đổi 1 bit input nên dẫn đến khoảng 50% bit output thay đổi. Mục tiêu là đảm bảo hai key "gần nhau" (khác nhau ở vài bit) không cluster vào cùng bucket.

String.hashCode() dùng công thức polynomial: s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]. Với string ngắn và khác nhau ở byte cuối, phần lớn bit cao trong hashCode giống hệt nhau. Điều này thành vấn đề khi HashMap capacity nhỏ và dùng chỉ các bit thấp để tính bucket index.

Java 8+ HashMap xử lý bằng "supplemental hash" — trộn bit cao vào bit thấp trước khi tính bucket:

// HashMap.hash(key) -- Java 8+ source
// XOR upper 16 bits into lower 16 bits to improve bucket distribution
// for keys whose hashCode() differs mainly in high bits
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

XOR h với h >>> 16 (shift phải 16 bit, zero-fill): các bit từ vị trí 16-31 được trộn vào vị trí 0-15. Kết quả: kể cả khi hai key có hashCode chỉ khác ở bit cao, bucket index của chúng vẫn khác nhau. Đây là cách HashMap bù đắp cho hash function không đủ avalanche.

Cross-link: Module 3 bài 02 (HashMap internals — chaining, treeify, load factor) sẽ đi sâu hơn vào toàn bộ lifecycle của một HashMap operation.

5. hashCode/equals contract

Contract gồm ba rule bắt buộc trong Java:

Rule 1 — Consistency với equals (MUST): nếu a.equals(b) == true thì a.hashCode() == b.hashCode(). Đây là rule không thể vi phạm — HashMap dùng hashCode để định vị bucket, sau đó dùng equals để xác nhận đúng key. Nếu hai object "bằng nhau" theo equals nhưng hashCode khác, lookup sẽ tìm sai bucket và không bao giờ gặp nhau.

Rule 2 — Collision OK: nếu a.hashCode() == b.hashCode() không có nghĩa a.equals(b). Collision là điều chấp nhận được — HashMap xử lý qua chaining. Rule 1 là one-way implication, không phải equivalence.

Rule 3 — Stability (SHOULD): hashCode() phải trả về cùng giá trị giữa các lần gọi trong cùng JVM session, miễn object không thay đổi các field dùng trong tính toán. Không có yêu cầu stable across JVM restart — Object.hashCode() mặc định có thể thay đổi mỗi lần chạy.

Ví dụ User class đúng contract — equals và hashCode cùng dùng userId:

public class User {
    private final long userId;
    private final String email;

    public User(long userId, String email) {
        this.userId = userId;
        this.email  = email;
    }

    // equals uses only userId -- two User objects are "same" if userId matches
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User u)) return false;  // Java 16+ pattern matching
        return userId == u.userId;
    }

    // hashCode uses ONLY userId -- same field as equals, contract satisfied
    @Override
    public int hashCode() {
        return Long.hashCode(userId);
    }
}

Key principle: hashCode phải consistent với equals — các field dùng trong equals phải là tập con (hoặc bằng) các field dùng trong hashCode. Nếu equals so sánh userId, hashCode không được dùng email một mình (dù có thể include thêm userId).

6. Pitfall tổng hợp

Pitfall 1 — Override equals nhưng quên override hashCode

Đây là bug gốc của hook mở đầu. Khi không override hashCode, Java dùng Object.hashCode() mặc định — trả về identity hash (dựa trên địa chỉ object trong heap). Hai object khác nhau trong memory → hashCode khác nhau → HashMap/HashSet tìm sai bucket → lookup thất bại.

// WRONG: equals overridden, hashCode is Object default (identity)
public class UserBroken {
    private final long userId;

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof UserBroken u)) return false;
        return userId == u.userId;
    }
    // NO hashCode override -- uses Object.hashCode() == identity hash
}

// Bug demonstration:
UserBroken u1 = new UserBroken(1L);
UserBroken u2 = new UserBroken(1L);
System.out.println(u1.equals(u2));              // true -- same userId
Set<UserBroken> set = new HashSet<>();
set.add(u1);
System.out.println(set.contains(u2));           // false -- different hashCode!
Map<UserBroken, String> map = new HashMap<>();
map.put(u1, "admin");
System.out.println(map.get(u2));               // null -- lookup finds wrong bucket

// CORRECT: both equals and hashCode use userId
public class User {
    private final long userId;

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof User u)) return false;
        return userId == u.userId;
    }

    @Override
    public int hashCode() {
        return Long.hashCode(userId);
    }
}

Pitfall 2 — Mutable field trong hashCode

Nếu hashCode dựa trên field có thể thay đổi sau khi object được put vào HashMap, hashCode sau khi mutation khác hashCode lúc put → key bị "lạc" trong sai bucket → get về null.

// DANGEROUS: hashCode depends on mutable field
public class MutableUser {
    private long userId;
    private String email;  // mutable!

    @Override
    public int hashCode() {
        return Objects.hash(userId, email);  // email is mutable -- DANGER
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof MutableUser u)) return false;
        return userId == u.userId && email.equals(u.email);
    }
}

// What goes wrong:
MutableUser u = new MutableUser(1L, "[email protected]");
Map<MutableUser, String> roles = new HashMap<>();
roles.put(u, "admin");
System.out.println(roles.get(u));    // "admin" -- correct

u.email = "[email protected]";        // mutate field used in hashCode!
System.out.println(roles.get(u));    // null -- hashCode changed, key "lost"
// Entry is still in map (memory leak) but unreachable via get()

Best practice: hashCode chỉ dùng final (immutable) field. Java record (Java 14+) tự generate hashCode từ tất cả component — tất cả đều final bởi default, nên an toàn.

Pitfall 3 — Dùng hashCode làm ID lưu database hoặc serialization

hashCode() không stable across JVM restart. Object.hashCode() mặc định dựa trên identity — thay đổi mỗi lần chạy. Ngay cả String.hashCode() — dù spec cố định thuật toán — trả về int 32-bit có thể trùng (collision) và không đủ entropy làm ID.

// WRONG: persist hashCode as ID
long recordId = user.hashCode();  // int cast to long
db.save(recordId, user);          // might collide; changes between runs for non-String

// CORRECT: dung UUID hoac cryptographic hash cho persistence
String recordId = UUID.randomUUID().toString();
// Hoac dung SHA-256 neu can deterministic ID tu content:
// MessageDigest.getInstance("SHA-256").digest(content.getBytes())

Dùng UUID cho persistence identifier. Nếu cần deterministic ID từ nội dung, dùng cryptographic hash (SHA-256, SHA-3) — đây là territory của Module 12 (Crypto & Integrity).

7. Java built-in hash functions tour

Long.hashCode(v) đáng chú ý: (int)(v ^ (v >>> 32)) — XOR nửa trên vào nửa dưới của long 64-bit để mix entropy trước khi cắt về int. Cùng tư tưởng với supplemental hash của HashMap nhưng ở tầng key.

Integer.hashCode(v) trả về chính v — hash function tốt nhất có thể vì input đã là int 32-bit, không cần trộn thêm. Nhưng điều này có nghĩa các Integer key liên tiếp (0, 1, 2...) có hashCode liên tiếp — HashMap phụ thuộc vào supplemental hash để tránh cluster.

String.hashCode() tệ về avalanche cho string ngắn khác nhau ở vị trí cuối: "key1" và "key2" có hashCode chỉ khác 1 — bit cao giống nhau. Java HashMap bù bằng ^ (h >>> 16) như đã thấy ở section 4.

8. Ứng dụng thực tế

HashMap collision handling — Java 8+ dùng chaining: mỗi bucket là linked list; khi chain dài hơn 8 node, treeify thành red-black tree — worst case lookup O(log n) thay vì O(n). Cross-link Module 3 bài 02 (HashMap internals) sẽ đào sâu resize, load factor 0.75, treeify threshold.

ConcurrentHashMap — Java 8+ dùng lock-striping: thay vì một lock toàn table, mỗi bucket (hay nhóm bucket) có lock riêng. Hai thread write vào bucket khác nhau không block nhau. Hash function quyết định bucket → quyết định lock granularity → quyết định throughput.

Distributed sharding — Cassandra dùng MurmurHash3 để tính ring position cho mỗi partition key. Consistent hashing map hash value vào vị trí trên ring; node nào "gần" nhất trên ring sẽ own partition đó. Uniform distribution của hash function trực tiếp ảnh hưởng đến cân bằng tải giữa node. Module 9 (Phân tán) sẽ đào sâu consistent hashing.

Bloom filter — cần k hash function độc lập cho cùng key. Trong thực tế, dùng 2-hash linear combination: h_i(k) = h1(k) + i * h2(k) để tạo k hash function từ hai hash function ban đầu. Độc lập thống kê đủ dùng mà không cần k hash function thật sự riêng biệt. Module 3 bài 09 (Bloom filter) sẽ trình bày chi tiết.

Cache key generation — Spring @Cacheable(key="#user.id") tạo cache key từ biểu thức SpEL. Underlying, SimpleKeyGenerator dùng Arrays.deepHashCode trên parameter. Nếu parameter là custom object, hashCode() của nó ảnh hưởng trực tiếp đến cache hit/miss — object "bằng nhau" về logic nhưng hashCode khác → cache miss mỗi lần gọi.

9. Deep Dive

10. Tóm tắt

• Hash function ánh xạ key bất kỳ sang int để định vị bucket trong O(1) — backbone của HashMap, HashSet, ConcurrentHashMap, Bloom filter, distributed shard.
• Uniform distribution: output rải đều bucket — hash function tệ gây hot spot, một bucket nhận phần lớn key, lookup thoái hóa về O(n).
• Avalanche effect: 1 bit input đổi → ~50% bit output đổi — tránh cluster key "gần nhau" vào cùng bucket. Java HashMap bù cho hash function yếu bằng supplemental hash ^ (h >>> 16).
• hashCode/equals contract: a.equals(b) suy ra a.hashCode() == b.hashCode() — rule bắt buộc. Vi phạm → HashMap lookup silent fail.
• Override equals thì phải override hashCode — quên override = dùng identity hash = hai object "bằng nhau" theo equals nằm ở hai bucket khác nhau = contains/get luôn thất bại.
• Mutable field trong hashCode = key có thể bị "lạc" trong HashMap sau khi mutation — memory leak và unreachable entry.
• Không dùng hashCode làm persistent ID — Object.hashCode() không stable across JVM; int 32-bit quá nhỏ và hay collision. Dùng UUID hoặc cryptographic hash cho persistence.
• Java record tự generate hashCode/equals đúng contract từ tất cả component final — lựa chọn tốt nhất cho value object làm HashMap key.

11. Tự kiểm tra

Bài tiếp theo: HashMap internals — chaining, treeify