Cài đặt Hash Table với Open Addressing Linear Probing trong C++

Hash table lưu cặp key-value. Hàm băm ánh xạ key thành chỉ số mảng. Linear probing giải quyết va chạm: nếu ô đã chiếm, tìm ô trống tiếp theo theo tuần tự.

Các thao tác chính

• Insert(key, value): Tìm ô trống bằng linear probing, chèn hoặc cập nhật.
• Search(key): Duyệt tuyến tính từ vị trí băm cho đến khi tìm thấy hoặc gặp ô trống.
• Remove(key): Tìm key, xóa và đánh dấu ô là deleted (sentinel) để không phá vỡ chuỗi probing.

Ví dụ minh họa (menu-driven)

#include <iostream>
#include <cstdlib>
using namespace std;

const int TABLE_SIZE = 5;

struct Entry { int key, val; };
Entry *DELETED = new Entry{-1,-1}; // sentinel

class HashMap {
    Entry **table;
    int hash(int k) { return k % TABLE_SIZE; }
public:
    HashMap() { table = new Entry*[TABLE_SIZE](); }
    ~HashMap() { for(int i=0;ikey != k) {
            if (delIdx == -1 && table[h] == DELETED) delIdx = h;
            h = hash(h+1);
            if (h == start) break;
        }
        if (!table[h] || h == start) {
            if (delIdx != -1) table[delIdx] = new Entry{k,v};
            else table[h] = new Entry{k,v};
        } else if (table[h] != DELETED) {
            table[h]->val = v; // cập nhật
        } else {
            table[h] = new Entry{k,v};
        }
    }
    int Search(int k) {
        int h = hash(k), start = h;
        while (table[h] && (table[h] != DELETED) && table[h]->key != k) {
            h = hash(h+1);
            if (h == start) return -1;
        }
        if (!table[h] || h == start) return -1;
        return table[h]->val;
    }
    void Remove(int k) {
        int h = hash(k), start = h;
        while (table[h] && (table[h] != DELETED) && table[h]->key != k) {
            h = hash(h+1);
            if (h == start) return;
        }
        if (table[h] && table[h] != DELETED) {
            delete table[h];
            table[h] = DELETED;
        }
    }
};

int main() {
    HashMap hm; int ch, k, v;
    while (true) {
        cout << "\n1.Insert 2.Search 3.Delete 4.Exit\nChon: "; cin >> ch;
        if (ch==1) { cout << "Key: "; cin >> k; cout << "Val: "; cin >> v; hm.Insert(k,v); }
        else if (ch==2) { cout << "Key: "; cin >> k; int r=hm.Search(k); if(r==-1) cout<<"Khong tim thay\n"; else cout<<"Val: "<<r<<endl; }
        else if (ch==3) { cout << "Key: "; cin >> k; hm.Remove(k); }
        else if (ch==4) break;
    }
}