Open addressing — Linear / quadratic probing, Robin Hood, và vì sao Java chọn chaining

Bài 02 đã giải thích HashMap Java 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. Ba strategy probing phổ biến nhất là linear, quadratic, và double hashing. Robin Hood hashing là cải tiến giảm variance trên linear probing. Bài này giải thích 3 strategy probing, Robin Hood hashing, trade-off với chaining, và vì sao Java giữ chaining còn Python / Rust chọn open addressing.

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
public class OpenAddressMap<K, V> {
    private K[] keys;
    private V[] values;
    private int size;
    private int capacity;

    @SuppressWarnings("unchecked")
    public OpenAddressMap(int capacity) {
        this.capacity = capacity;
        this.keys     = (K[]) new Object[capacity];
        this.values   = (V[]) new Object[capacity];
    }
    // probe strategy determines how we find the next slot
}

Khi put(key, value):

1. Tính index = hash(key) % capacity.
2. Nếu keys[index] == null hoặc đúng key → ghi vào đó.
3. Nếu slot đó đã có key khác (collision) → probe sang slot tiếp theo theo strategy.
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) % 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).

public class LinearProbingMap<K, V> {
    private K[] keys;
    private V[] values;
    private boolean[] tombstone;  // marks deleted-but-probe-continues slots
    private int size;
    private int capacity;

    @SuppressWarnings("unchecked")
    public LinearProbingMap(int capacity) {
        this.capacity  = capacity;
        this.keys      = (K[]) new Object[capacity];
        this.values    = (V[]) new Object[capacity];
        this.tombstone = new boolean[capacity];
    }

    private int baseIndex(K key) {
        return (key.hashCode() & 0x7FFFFFFF) % capacity;
    }

    public V get(K key) {
        int i = baseIndex(key);
        while (keys[i] != null || tombstone[i]) {
            if (keys[i] != null && keys[i].equals(key)) return values[i];
            i = (i + 1) % capacity;
        }
        return null;
    }

    public void put(K key, V value) {
        if (size >= capacity * 0.7) resize();
        int i = baseIndex(key);
        while (keys[i] != null) {
            if (keys[i].equals(key)) {
                values[i] = value;  // update existing key
                return;
            }
            i = (i + 1) % capacity;
        }
        keys[i]      = key;
        values[i]    = value;
        tombstone[i] = false;
        size++;
    }
    // remove() and resize() covered in section 6
}

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

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

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

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

After put("d", hash=2):  -- slots 2, 3, 4 all taken, probe to 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, xác suất probe chain dài tăng theo.

Ư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) % capacity hoặc dạng triangular (hash + i*(i+1)/2) % capacity

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 -- probe sequence for a given base hash
// Using triangular variant: i*(i+1)/2 to guarantee coverage when capacity is power-of-2
private int probe(int baseHash, int i) {
    return (baseHash + i * (i + 1) / 2) % capacity;
}

public V get(K key) {
    int base = baseIndex(key);
    for (int i = 0; i < capacity; i++) {
        int idx = probe(base, i);
        if (keys[idx] == null && !tombstone[idx]) return null;
        if (keys[idx] != null && keys[idx].equals(key)) return values[idx];
    }
    return null;
}

Ư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. Nếu không, probe sequence có thể lặp lại một tập nhỏ slot trước khi bao phủ hết array.

5. Double hashing

Công thức: index = (hash1(key) + i * hash2(key)) % 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: two independent hash functions
// hash2 must be nonzero and coprime with capacity
// Common choice when capacity is prime: hash2(k) = PRIME - (hash1(k) % PRIME)
private int hash1(K key) {
    return (key.hashCode() & 0x7FFFFFFF) % capacity;
}

private int hash2(K key) {
    int h = (key.hashCode() & 0x7FFFFFFF);
    return 1 + (h % (capacity - 1));  // always in range [1, capacity-1]
}

private int probe(K key, int i) {
    return (hash1(key) + i * hash2(key)) % 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 after puts with some clustering:
  [0]  -    [1]  "x"(h=1)  [2]  "y"(h=1)  [3]  "z"(h=1)  [4]  -

get("z"): start at slot 1, probe 1->2->3, found. OK.

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

get("z") after delete: start at slot 1 -> probe to slot 2 -> keys[2] == null -> STOP
  Result: return null  <<< FALSE MISS -- "z" is still there at 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" with tombstone: set tombstone[2] = true, keys[2] = null
  [0]  -    [1]  "x"(h=1)  [2]  TOMB     [3]  "z"(h=1)  [4]  -

get("z") after tombstone delete:
  start at slot 1 -> slot 2 has tombstone -> continue probing -> slot 3 found "z"
  Result: return value of "z". Correct!

public void remove(K key) {
    int i = baseIndex(key);
    while (keys[i] != null || tombstone[i]) {
        if (keys[i] != null && keys[i].equals(key)) {
            keys[i]      = null;
            tombstone[i] = true;  // mark as tombstone, not plain null
            size--;
            return;
        }
        i = (i + 1) % capacity;
    }
    // key not found
}

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 "nghèo" (mới đến, chưa probe nhiều) nhường chỗ cho entry "giàu" (đã probe nhiều, xứng đáng được ở gần hơn). Thực ra ngược lại: 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: each slot stores displacement count
// displacement[i] = how many probes slot i's occupant needed to land here
public class RobinHoodMap<K, V> {
    private K[] keys;
    private V[] values;
    private int[] displacement; // probing distance for each occupied slot
    private int size;
    private int capacity;

    @SuppressWarnings("unchecked")
    public RobinHoodMap(int capacity) {
        this.capacity    = capacity;
        this.keys        = (K[]) new Object[capacity];
        this.values      = (V[]) new Object[capacity];
        this.displacement = new int[capacity];
        java.util.Arrays.fill(displacement, -1); // -1 = empty slot
    }

    public void put(K key, V value) {
        if (size >= capacity * 0.7) resize();
        int idx  = (key.hashCode() & 0x7FFFFFFF) % capacity;
        int dist = 0;
        K   curKey = key;
        V   curVal = value;

        while (true) {
            if (displacement[idx] == -1) {
                // empty slot: place here
                keys[idx]         = curKey;
                values[idx]       = curVal;
                displacement[idx] = dist;
                size++;
                return;
            }
            // Robin Hood swap: if current entry has less displacement, swap
            if (displacement[idx] < dist) {
                K tmpK = keys[idx];   V tmpV = values[idx];
                int tmpD = displacement[idx];
                keys[idx]         = curKey;
                values[idx]       = curVal;
                displacement[idx] = dist;
                curKey = tmpK;  curVal = tmpV;  dist = tmpD;
            }
            idx  = (idx + 1) % capacity;
            dist++;
        }
    }
}

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 (không cần probe đến hết cluster).

Adoption: Rust HashMap (default implementation dựa trên SwissTable của Google có Robin Hood influence), một phần của Python 3.6+ internal.

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

// BAD: load factor allowed to reach 0.9+
OpenAddressMap<String, Integer> map = new OpenAddressMap<>(16);
// After adding 14+ entries (87% full), average probe length > 5
// A single get() may scan half the array

// GOOD: resize at 0.7
if (size >= capacity * 0.7) resize();

Separate chaining tolerate load factor cao hơn (Java HashMap default 0.75, thực tế chaining thêm tới 1.0 vẫn O(1) amortized nếu hash đều) vì collision chỉ thêm vào chain của bucket đó, 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 sets slot to null
public void removeBroken(K key) {
    int i = baseIndex(key);
    while (keys[i] != null) {
        if (keys[i].equals(key)) {
            keys[i]   = null;   // breaks probe chain!
            values[i] = null;
            size--;
            return;
        }
        i = (i + 1) % capacity;
    }
}
// Any key that was probed past this slot is now unreachable via get()

Fix: luôn dùng tombstone marker 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.

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.

// TERRIBLE hash function -- everything goes to slot 0
public int hashCode() { return 0; }
// With linear probing: all keys probe sequentially from slot 0
// put() and get() are O(n) regardless of load factor

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 1996 (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 — chỉ có thể resize hoặc rehash toàn bộ.

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 — đổi sang open addressing sẽ phá vỡ behavioral contract dù spec không yêu cầu.

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) % 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. Source: Objects/dictobject.c trong CPython repository.

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. Dùng Robin Hood hashing với "control bytes" — một byte per slot lưu 7 bit thấp của hash (hoặc sentinel "empty"/"deleted"). Lookup so sánh 16 control bytes cùng lúc bằng SIMD instruction (_mm_cmpeq_epi8) — một instruction kiểm tra 16 slot, gần như O(1) thực sự ngay cả khi có cluster nhỏ.

Memcached slab allocator: dùng open addressing trên slab fixed-size để tránh memory fragmentation. Key ngắn (max 250 byte) + value nhỏ → node allocation overhead của chaining đáng kể so với value size.

12. Deep Dive

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ử (1996), 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