Open addressing — Probing, Robin Hood và vì sao Java chọn chaining

TL;DR: Open addressing đặt tất cả entry trong một array duy nhất — không có node object, không có pointer ra ngoài. Khi collision xảy ra, thuật toán "probe" sang ô tiếp theo theo quy tắc: linear (bước 1 cố định), quadratic (bước nhảy tăng bình phương), double hashing (bước nhảy từ hash function thứ hai). Delete không được naive null-out — phải dùng tombstone để không phá probe chain. Java chọn chaining (vì lý do lịch sử 1998 + LinkedHashMap contract), trong khi Python, Go, Rust chọn open addressing vì cache locality tốt hơn và khả năng tận dụng SIMD instruction hiện đại.

Bài 01 — Hash function đã giải thích cơ chế định vị bucket và hashCode/equals contract. Java HashMap dùng separate chaining: mỗi bucket là một linked list (treeify khi chain dài từ 8 trở lên). Nhưng nếu mở source của Python dict, Go map, hay Rust HashMap, bạn sẽ thấy kiến trúc khác hẳn — không có Node object, không có next pointer. Tất cả entry nằm thẳng trong một array duy nhất.

Đây là open addressing: thay vì chain entry ra ngoài khi collision, tất cả entry sống trong cùng bucket array — khi collision xảy ra, thuật toán "probe" (thăm dò) sang ô tiếp theo theo quy tắc nhất định.

1. Analogy — Bãi đậu xe có quy tắc

Hình dung một bãi đậu xe có 16 ô đánh số 0 đến 15. Mỗi xe có một ô "được chỉ định" dựa trên biển số (hash function). Khi ô đó đã có xe khác (collision), tài xế phải tìm ô trống khác — và quy tắc tìm ô trống chính là probing strategy.

• Linear probing: không tìm được ô 5 → thử ô 6, 7, 8... tuần tự đến khi có ô trống.
• Quadratic probing: không tìm được ô 5 → thử ô 6 (bước 1), ô 9 (bước 4), ô 14 (bước 9)... bước nhảy tăng theo bình phương.
• Double hashing: không tìm được ô 5 → bước nhảy do hash function thứ hai quyết định, không cố định.
• Robin Hood: khi một xe "đã đi xa quá nhiều ô" so với xe hiện tại trong ô đó → hai xe đổi chỗ cho nhau để cân bằng khoảng cách.

2. Open addressing là gì

Trong separate chaining (Java HashMap), mỗi bucket trỏ tới một linked list bên ngoài. Trong open addressing, không có pointer, không có node object — tất cả key và value nằm thẳng trong bucket array:

-- Skeleton: open addressing hash map
OpenAddressMap:
    keys[capacity]      -- mảng key, null = trống
    values[capacity]    -- mảng value tương ứng
    size: int
    capacity: int

-- Khi put(key, value):
--   1. idx <- hash(key) mod capacity
--   2. Nếu keys[idx] = null hoặc keys[idx] = key → ghi vào đó
--   3. Nếu slot đã có key khác (collision) → probe sang slot tiếp theo
--   4. Lặp đến khi tìm được slot trống hoặc tìm lại đúng key

Yêu cầu bắt buộc: load factor phải dưới 1 — luôn phải có ít nhất một slot trống, nếu không probe loop vô hạn. Thực tế giữ load factor dưới 0.7 để tránh probe chain dài.

Lợi thế so với chaining: chỉ cần một array thay vì một array cộng với N node object nằm rải rác trong heap. Entry nằm kề nhau trong memory → CPU cache load một cache line có thể bao gồm nhiều entry liên tiếp → ít cache miss hơn.

3. Linear probing

Công thức: index = (hash + i) mod capacity, với i = 0, 1, 2, ...

Tìm slot tiếp theo bằng cách đi tuần tự: thử index ban đầu, rồi index+1, index+2... Khi vượt cuối array thì quay về đầu (modulo).

LinearProbingMap:
    keys[capacity]
    values[capacity]
    tombstone[capacity]   -- đánh dấu slot đã xóa nhưng probe phải đi qua
    size: int
    capacity: int

    baseIndex(key):
        return (hash(key) AND 0x7FFFFFFF) mod capacity

    get(key):
        i <- baseIndex(key)
        while keys[i] != null OR tombstone[i]:
            if keys[i] != null AND keys[i] = key: return values[i]
            i <- (i + 1) mod capacity
        return null

    put(key, value):
        if size >= capacity * 0.7: resize()
        i <- baseIndex(key)
        firstTombstone <- -1
        -- Duyệt toàn bộ probe chain; tombstone KHÔNG phải điểm dừng.
        -- Chỉ dừng tại slot chưa từng dùng (keys[i]=null VÀ !tombstone[i]).
        while keys[i] != null OR tombstone[i]:
            if keys[i] != null AND keys[i] = key:
                values[i] <- value    -- cập nhật key đã có
                return
            if keys[i] = null AND firstTombstone = -1:
                firstTombstone <- i   -- nhớ slot tombstone đầu tiên để tái dùng
            i <- (i + 1) mod capacity
        -- Key chưa có. Tái dùng tombstone nếu có, nếu không dùng slot trống này.
        target <- firstTombstone nếu firstTombstone != -1 else i
        keys[target]      <- key
        values[target]    <- value
        tombstone[target] <- false
        size              <- size + 1

Time: O(1) amortized Space: O(capacity)

Minh họa linear probing với 8 slot, thêm 4 key có hash 2, 2, 3, 2 (cố ý collision):

Sau put("a", hash=2):
  [0]-  [1]-  [2]"a"  [3]-  ...

Sau put("b", hash=2): -- slot 2 occupied, probe sang slot 3
  [0]-  [1]-  [2]"a"  [3]"b"  ...

Sau put("c", hash=3): -- slot 3 occupied, probe sang slot 4
  [0]-  [1]-  [2]"a"  [3]"b"  [4]"c"  ...

Sau put("d", hash=2): -- slots 2,3,4 đều chiếm, probe sang slot 5
  [0]-  [1]-  [2]"a"  [3]"b"  [4]"c"  [5]"d"  ...

Entry "a", "b", "c", "d" tích tụ thành một cluster liên tiếp. Đây là primary clustering: entry có hash khác nhau (hash=3 của "c") cũng bị kéo vào cluster — cluster ngày càng dài hơn.

graph LR
    K1["key (hash=2)"] --> S2["Slot 2 ✓"]
    K2["key (hash=2)"] --> S2
    S2 -->|"đã chiếm"| S3["Slot 3"]
    K3["key (hash=3)"] --> S3
    S3 -->|"đã chiếm"| S4["Slot 4"]
    K4["key (hash=2)"] --> S2
    S2 -->|"đã chiếm"| S3
    S3 -->|"đã chiếm"| S4
    S4 -->|"đã chiếm"| S5["Slot 5 ✓"]

Ưu điểm: sequential memory access — CPU prefetch hoạt động hiệu quả, cache hit rate cao.

Nhược điểm: primary clustering — entry tích tụ thành dải dài. Cluster tự khuếch đại: ô trống nằm cạnh cluster bị chiếm đầu tiên → cluster nối dài thêm.

4. Quadratic probing

Công thức: index = (hash + i*(i+1)/2) mod capacity (dạng triangular)

Thay vì bước 1 cố định, bước nhảy tăng theo bình phương: thử hash, hash+1, hash+4, hash+9, hash+16...

-- Quadratic probing: bước nhảy tăng theo bình phương
probe(baseHash, i):
    return (baseHash + i*(i+1)/2) mod capacity

get(key):
    base <- baseIndex(key)
    for i <- 0 đến capacity-1:
        idx <- probe(base, i)
        if keys[idx] = null AND NOT tombstone[idx]: return null
        if keys[idx] != null AND keys[idx] = key: return values[idx]
    return null

Time: O(1) amortized Space: O(capacity)

Ưu điểm: tránh primary clustering — entry có hash khác nhau sẽ đi theo probe path khác nhau, không tích tụ thành cluster liên tiếp.

Nhược điểm: secondary clustering — hai key có cùng hash ban đầu sẽ đi theo cùng probe path và vẫn cluster với nhau. Ít nghiêm trọng hơn primary clustering, nhưng vẫn là vấn đề khi hash function tệ.

Yêu cầu: để triangular variant đảm bảo probe qua tất cả slot (không bỏ sót), capacity phải là lũy thừa của 2.

5. Double hashing

Công thức: index = (hash1(key) + i * hash2(key)) mod capacity

Thay vì bước nhảy cố định, bước nhảy được tính từ hash function thứ hai riêng cho mỗi key. Hai key có cùng hash1 nhưng hash2 khác nhau sẽ đi theo path hoàn toàn khác.

-- Double hashing: hai hàm băm độc lập
hash1(key):
    return (hash(key) AND 0x7FFFFFFF) mod capacity

hash2(key):
    h <- hash(key) AND 0x7FFFFFFF
    return 1 + (h mod (capacity - 1))   -- luôn trong [1, capacity-1]

probe(key, i):
    return (hash1(key) + i * hash2(key)) mod capacity

Time: O(1) amortized Space: O(capacity)

Ưu điểm: phá cả primary và secondary clustering. Probe path của mỗi key phụ thuộc vào cả hai hash function — phân tán tốt nhất trong ba strategy.

Nhược điểm: phức tạp hơn — cần hai hash function chất lượng tốt. Bước nhảy không sequential → cache miss cao hơn linear probing. CPU tốn thêm một lần tính hash.

Bảng so sánh 3 strategy:

6. Tombstone — vì sao cần khi delete

Delete trong open addressing không thể chỉ đơn giản set slot thành null. Đây là lý do:

Table sau một số put:
  [0]-  [1]"x"(h=1)  [2]"y"(h=1)  [3]"z"(h=1)  [4]-

get("z"): bắt đầu slot 1, probe 1→2→3, tìm thấy. OK.

Naive delete "y": set keys[2] = null
  [0]-  [1]"x"(h=1)  [2]NULL  [3]"z"(h=1)  [4]-

get("z") sau delete: bắt đầu slot 1 → probe sang slot 2 → null → DỪNG
  Kết quả: return null  <<< FALSE MISS -- "z" vẫn ở slot 3!

Xóa "y" tạo ra lỗ hổng ở slot 2. Khi tìm "z" sau đó, probe sequence gặp null ở slot 2 và dừng lại — không bao giờ đến slot 3 nơi "z" đang nằm.

Tombstone là giải pháp: thay vì xóa hẳn, đánh dấu slot là "deleted but probing must continue here":

Delete "y" với tombstone: set tombstone[2] = true, keys[2] = null
  [0]-  [1]"x"(h=1)  [2]TOMB  [3]"z"(h=1)  [4]-

get("z") sau tombstone delete:
  bắt đầu slot 1 → slot 2 có tombstone → tiếp tục probe → slot 3 tìm thấy "z"
  Kết quả: trả về giá trị của "z". Đúng!

remove(key):
    i <- baseIndex(key)
    while keys[i] != null OR tombstone[i]:
        if keys[i] != null AND keys[i] = key:
            keys[i]      <- null
            tombstone[i] <- true   -- đánh dấu tombstone, không phải null thông thường
            size         <- size - 1
            return
        i <- (i + 1) mod capacity
    -- key không tìm thấy

Time: O(1) amortized Space: O(1)

Trade-off của tombstone:

• get() phải đi qua tombstone slot → không dừng sớm được → hiệu năng giảm khi nhiều tombstone tích tụ.
• put() có thể ghi đè tombstone slot (reuse), nhưng cần thêm logic tracking.
• Sau nhiều delete/insert, tombstone tích tụ → cần rehash định kỳ: tạo array mới, copy lại toàn bộ entry sống (bỏ tombstone), phân phối lại.

7. Robin Hood hashing

Ý tưởng: mỗi entry theo dõi displacement — số bước probe đã đi từ vị trí hash ban đầu. Khi insert một entry mới, nếu entry mới đã đi nhiều bước hơn entry hiện tại đang ngồi ở slot đó → hai entry đổi chỗ, entry mới chiếm slot, entry cũ phải probe tiếp.

Hình ảnh: entry đã probe nhiều ("giàu" về effort) được quyền "lấy lại" slot từ entry mới vào chưa phải probe nhiều ("nghèo" về effort). Tên Robin Hood vì nó "lấy từ người giàu (ít effort) cho người nghèo (nhiều effort)".

-- Robin Hood linear probing: mỗi slot lưu thêm displacement
RobinHoodMap:
    keys[capacity]
    values[capacity]
    displacement[capacity]   -- số bước probe của entry đang ngồi ở slot đó
                             -- -1 = slot trống
    size: int
    capacity: int

    put(key, value):
        if size >= capacity * 0.7: resize()
        idx      <- (hash(key) AND 0x7FFFFFFF) mod capacity
        dist     <- 0
        curKey   <- key
        curVal   <- value

        while true:
            if displacement[idx] = -1:
                -- slot trống: đặt entry vào đây
                keys[idx]         <- curKey
                values[idx]       <- curVal
                displacement[idx] <- dist
                size              <- size + 1
                return
            -- Robin Hood swap: nếu entry hiện tại có displacement nhỏ hơn, đổi chỗ
            if displacement[idx] < dist:
                hoán đổi (keys[idx], curKey)
                hoán đổi (values[idx], curVal)
                hoán đổi (displacement[idx], dist)
            idx  <- (idx + 1) mod capacity
            dist <- dist + 1

Time: O(1) amortized Space: O(capacity)

Outcome: variance của probe length giảm đáng kể. Không có entry nào bị đẩy quá xa trong khi entry khác nằm sát vị trí ban đầu — phân phối đều hơn.

Trade-off:

• Code phức tạp hơn, đặc biệt là delete (cần backward shift hoặc tombstone cải tiến).
• Mỗi slot cần thêm một field displacement (thêm memory per entry).
• Lookup có thể dừng sớm: nếu displacement[i] < expected_displacement → key không thể nằm xa hơn → trả về không tìm thấy ngay.

Adoption: Robin Hood hashing được dùng trong một số implementation như hashbrown crate phiên bản đầu. Python 3.6+ không dùng Robin Hood — CPython dict dùng perturbation probing (i = 5*i + perturb + 1) như đã mô tả ở section 11. SwissTable (Google Abseil / Rust std từ 2018) từ bỏ Robin Hood, thay bằng SIMD group probing với control bytes — xem section 11.

8. Pitfall tổng hợp

Pitfall 1 — Load factor quá cao

Open addressing với load factor vượt 0.7 → probe chain dài → get() và put() thoái hóa về O(n).

-- BUG: không resize khi load factor vượt ngưỡng
-- Sau khi thêm 14+ entry vào array 16 slot (87% full):
--   probe length trung bình vượt 5
--   một get() đơn lẻ có thể duyệt nửa array

-- CORRECT: resize khi vượt 0.7
put(key, value):
    if size >= capacity * 0.7: resize()
    ...

Separate chaining tolerate load factor cao hơn (Java HashMap default 0.75) vì collision của bucket A không ảnh hưởng bucket khác. Open addressing thì collision của bucket A làm chậm cả B, C, D nằm kề.

Pitfall 2 — Quên handle tombstone

-- WRONG: naive delete set slot thành null
remove_broken(key):
    i <- baseIndex(key)
    while keys[i] != null:
        if keys[i] = key:
            keys[i]   <- null    -- phá vỡ probe chain!
            values[i] <- null
            size      <- size - 1
            return
        i <- (i + 1) mod capacity
-- Mọi key đã probe qua slot này sẽ không tìm thấy được nữa

-- CORRECT: dùng tombstone như đã trình bày ở section 6

Pitfall 3 — Hash function tệ với linear probing

Linear probing cực kỳ nhạy cảm với chất lượng hash function. Hash function tệ tạo primary cluster → put, get, remove đều trở thành O(n) dù load factor thấp.

-- Hash function tệ: mọi key đều cho hash = 0
hashCode(key): return 0

-- Với linear probing: mọi key probe tuần tự từ slot 0
-- put() và get() là O(n) bất kể load factor

Quadratic probing và double hashing chịu đựng hash function tệ tốt hơn — probe path đa dạng hơn nên cluster nhỏ hơn. Nhưng không có probing strategy nào cứu được hash function trả về cùng giá trị cho mọi key.

9. Chaining vs open addressing

Khi nào open addressing tốt hơn: key nhỏ (int, pointer), dataset vừa, cần cache-friendly lookup, memory overhead của Node là vấn đề.

Khi nào chaining tốt hơn: key lớn (object phức tạp), cần delete thường xuyên, load factor có thể cao, hoặc cần inherit từ hash map (LinkedHashMap pattern).

10. Vì sao Java chọn chaining

Java chọn separate chaining không phải vì chaining "tốt hơn" mặt kỹ thuật — mà vì một tập lý do lịch sử và kiến trúc:

1. Thiết kế từ năm 1998 (Java 1.2): năm đó, cache hierarchy chưa phải ưu tiên hàng đầu khi thiết kế collection. Memory dư dả hơn so với tốc độ CPU — node allocation không bị xem là vấn đề.

2. Inheritance contract của LinkedHashMap: LinkedHashMap extends HashMap bằng cách thêm một doubly linked list xuyên qua tất cả entry theo insertion order. Thiết kế này cực kỳ tự nhiên với chaining — chỉ cần thêm before/after pointer vào Node class. Nếu HashMap dùng open addressing, LinkedHashMap phải duy trì một linked list riêng hoàn toàn bên ngoài → duplicate overhead.

3. Java 8 treeify là biện pháp defensive: khi attacker tạo collision có chủ ý, chaining + red-black tree giới hạn worst case còn O(log n). Open addressing không có cơ chế tương đương thanh lịch.

4. Backward compatibility: Map.Entry interface, entrySet(), keySet(), values() view đều phản ánh internal Node structure. Hàng triệu line code Java trong thế giới phụ thuộc vào behavior cụ thể của HashMap.

11. Open addressing trong thực tế

Python dict (CPython 3.6+): dùng open addressing với probe sequence có perturbation: i = (5*i + perturb + 1) mod capacity, với perturb = hash ban đầu và dần shift phải mỗi bước. perturb mix high bit của hash vào probe sequence — tránh secondary clustering khi hash function tập trung ở bit thấp.

Go map: open addressing với kiến trúc "bucket cell" — mỗi "bucket" chứa 8 slot, kèm tophash array 8 byte lưu 8 bit cao của hash. Khi lookup, so sánh tophash trước (SIMD-friendly byte comparison) trước khi dùng full key equality. Nhóm 8 slot vào một cache line → giảm cache miss ngay cả khi có collision trong bucket.

Rust HashMap — SwissTable: Google thiết kế SwissTable (2017) và Rust adopt vào standard library từ 2018. SwissTable từ bỏ Robin Hood hashing, dùng SIMD control bytes: mỗi slot có một "control byte" lưu 7 bit thấp của hash (H2) hoặc sentinel "empty"/"deleted". Khi lookup, 16 control bytes được so sánh cùng lúc bằng một SIMD instruction — kiểm tra 16 slot chỉ trong một instruction, gần như O(1) thực sự ngay cả khi có cluster nhỏ.

12. Deep Dive

Liên hệ các bài khác

• Bài 01 — Hash function: uniform distribution và avalanche effect quyết định chất lượng probing — hash function tệ thì cả ba strategy đều cluster nặng.
• HashMap internals (khoá Java): Java chọn separate chaining + treeify, load factor 0.75 — đọc để hiểu vì sao họ không chọn open addressing dù cache locality của nó tốt hơn.

13. Tóm tắt

• Open addressing đặt tất cả entry trong một array duy nhất — không có node object, không có pointer. Cache-friendly hơn chaining nhưng yêu cầu load factor dưới 0.7.
• Linear probing đơn giản và cache-friendly nhất, nhưng gây primary clustering — entry tích tụ thành dải dài kéo cả key có hash khác vào cùng cluster.
• Quadratic probing tránh primary clustering bằng bước nhảy tăng theo bình phương, nhưng vẫn có secondary clustering khi hai key cùng hash ban đầu.
• Double hashing phá cả hai loại clustering với bước nhảy từ hash function thứ hai — phân tán tốt nhất nhưng phức tạp nhất và cache locality kém nhất.
• Tombstone là bắt buộc khi delete: naive null-out phá probe chain, gây false miss cho key nằm sau lỗ hổng. Tombstone tích tụ cần rehash định kỳ.
• Robin Hood hashing cân bằng probe length bằng cách swap entry "ít effort" nhường chỗ cho entry "nhiều effort" — giảm variance, cho phép dừng lookup sớm hơn.
• Java chọn chaining vì lý do lịch sử (1998), contract của LinkedHashMap, defensive treeify Java 8, và backward compatibility — không phải vì chaining vượt trội.
• Python / Go / Rust chọn open addressing vì cache locality tốt hơn, memory overhead thấp hơn, và khả năng tận dụng SIMD instruction hiện đại.

14. Tự kiểm tra

Bài tiếp theo: Binary search — invariant, lower/upper bound, search-on-answer