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

TL;DR: Hash function ánh xạ key bất kỳ sang số nguyên để định vị bucket trong O(1) — backbone của HashMap, HashSet, Bloom filter, distributed shard. Hai thuộc tính cốt lõi: uniform distribution (output rải đều bucket, tránh hot spot) và avalanche effect (1 bit input đổi → ~50% bit output đổi, tránh cluster). Contract bắt buộc: nếu a.equals(b) thì a.hashCode() == b.hashCode() — vi phạm khiến HashMap lookup thất bại hoàn toàn, không exception, chỉ silent wrong answer.

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. 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. Map 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.

graph LR
    K1["key-0"] --> H["Hàm băm h(k)"]
    K2["key-1"] --> H
    K3["key-2"] --> H
    H --> B0["Bucket 0"]
    H --> B1["Bucket 1"]
    H --> B2["Bucket 2"]
    H --> B3["Bucket 3 (quá tải)"]
    style B3 fill:#f88,stroke:#c00

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

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

-- Kiểm tra phân phối của hàm băm qua 16 bucket
-- Kỳ vọng: ~6250 key mỗi bucket (100_000 / 16)
buckets <- mảng kích thước 16, khởi tạo = 0
for i <- 0 đến 99_999:
    h <- hash("key" + i)
    idx <- h AND 15        -- tương đương mod 16 (power-of-2 trick)
    buckets[idx] <- buckets[idx] + 1
-- Kết quả đúng: mỗi bucket nhận khoảng 6100–6400 key

Time: O(n) Space: O(M)

Thử ngẫmở callout trên, h(k) = k % 8 dồn key 0, 8, 16, 24 vào cùng bucket 0. Đổi 8 thành số nguyên tố có chắc hết hot spot, hay còn tùy tập key thực tế?

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.

Hàm băm chuỗi 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 Map capacity nhỏ và dùng chỉ các bit thấp để tính bucket index.

Nhiều Map hiện đại xử lý bằng "supplemental hash" — trộn bit cao vào bit thấp trước khi tính bucket:

-- Supplemental hash: XOR nửa trên vào nửa dưới để cải thiện phân phối
-- Đặc biệt hữu ích cho key mà hashCode chỉ khác ở bit cao
h <- hashCode(key)
h <- h XOR (h dịch phải 16 bit)  -- trộn bit 16-31 vào bit 0-15
bucket_idx <- h AND (capacity - 1)

XOR h với h >> 16 (shift phải 16 bit): 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.

5. hashCode/equals contract

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

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 — Map 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 — Map 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.

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

-- User class với contract đúng
User:
    userId: long (final)
    email: String (final)

    equals(other):
        if other không phải User: return false
        return this.userId = other.userId

    hashCode():
        return hash(userId)       -- cùng field với equals → contract thoả

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.

Thử ngẫmnếu hai object có cùng hashCode nhưng equals trả false, cấu trúc phải làm gì tiếp để không trả nhầm kết quả — và bước đó tốn thêm chi phí gì?

6. Pitfall tổng hợp

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

Khi không override hashCode, hàm băm 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 → Map tìm sai bucket → lookup thất bại.

-- BUG: equals override nhưng hashCode dùng identity hash mặc định
UserBroken:
    equals(other): so sánh userId  -- đúng
    -- hashCode(): KHÔNG override → dùng địa chỉ object

u1 <- UserBroken(userId=1)
u2 <- UserBroken(userId=1)
u1.equals(u2)          -- true (cùng userId)
S <- Set rỗng
S.add(u1)
S.contains(u2)         -- false! u2 có hashCode khác u1 → tìm sai bucket

Time: O(1) (mong đợi) Space: O(n)

-- CORRECT: cả equals và hashCode đều dùng userId
User:
    equals(other): so sánh userId
    hashCode(): return hash(userId)  -- cùng field → contract thoả

u1 <- User(userId=1)
u2 <- User(userId=1)
S <- Set rỗng
S.add(u1)
S.contains(u2)         -- true ✓

Time: O(1) Space: O(n)

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 Map, hashCode sau khi mutation khác hashCode lúc put → key bị "lạc" trong sai bucket → get về null.

-- BUG: hashCode phụ thuộc vào field có thể thay đổi
MutableUser:
    userId: long (final)
    email: String     -- có thể thay đổi!
    hashCode(): return hash(userId, email)  -- email là mutable → NGUY HIỂM

u <- MutableUser(userId=1, email="[email protected]")
M <- Map rỗng
M.put(u, "admin")
M.get(u)              -- "admin" (đúng)

u.email <- "[email protected]"   -- thay đổi field dùng trong hashCode!
M.get(u)              -- null! hashCode đã đổi, key "lạc" sang bucket khác
-- Entry vẫn trong map (memory leak) nhưng không thể truy cập qua get()

Best practice: hashCode chỉ dùng final (immutable) field.

Pitfall 3 — Dùng hashCode làm ID lưu database

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

-- WRONG: lưu hashCode làm record ID
recordId <- user.hashCode()   -- int 32-bit, có thể collision, không stable
db.save(recordId, user)       -- sai khi restart JVM hoặc với object khác nhau

-- CORRECT: dùng UUID hoặc cryptographic hash cho persistence
recordId <- UUID.randomUUID()

Dùng UUID cho persistence identifier. Nếu cần deterministic ID từ nội dung, dùng cryptographic hash (SHA-256).

7. Bảng hàm băm phổ biến

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

Thử ngẫmbảng trên cho thấy hàm băm của Integer chỉ trả chính value — không mixing. Nếu bạn dùng các số liên tiếp 1, 2, 3... làm key trong một cấu trúc có capacity nhỏ, việc thiếu avalanche này có gây hot spot không?

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

Map collision handling — Java 8+ dùng chaining: mỗi bucket là linked list; khi chain đạt từ 8 node trở lên, treeify thành red-black tree — worst case lookup O(log n) thay vì O(n). HashMap internals (khoá Java) 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 — Hệ thống phân tán dùng hàm băm mạnh (như MurmurHash3) để tính vị trí 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. Thuật toán Ứng dụng — Module 4 (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. Module 1 bài 09 (Bloom filter) sẽ trình bày chi tiết.

9. Deep Dive

Đọc thêm: Key-range vs hash partitioning — khoá Tư duy hệ dữ liệu phân tán dùng lại đúng hash function này để rải dữ liệu đều lên nhiều node, và chỉ ra vì sao uniform distribution ở đây quan trọng hơn cả tốc độ hash.

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. Nhiều Map bù bằng supplemental hash (XOR bit cao vào bit thấp).
• hashCode/equals contract: a.equals(b) suy ra a.hashCode() == b.hashCode() — rule bắt buộc. Vi phạm → Map 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 Map sau khi mutation — memory leak và unreachable entry.
• Không dùng hashCode làm persistent ID — không stable across JVM; int 32-bit quá nhỏ và hay collision. Dùng UUID hoặc cryptographic hash cho persistence.

11. Tự kiểm tra

Bài tiếp theo: Open addressing — linear/quadratic probing, robin hood

Hash table này chạy thật ở đâu? HashMap của Java chính là một hiện thực của nó. Nếu bạn học Java, Java Internals — HashMap internals cho thấy cách JDK xử lý va chạm: separate chaining, và treeify từ Java 8 khi một bucket quá dài.