Chương trình C++ cài đặt bảng băm (Hash Table) cơ bản

Bảng băm (hash table) lưu trữ cặp khóa-giá trị. Bài này cài đặt bảng băm định địa chỉ mở (open addressing) với dò tuyến tính (linear probing) đơn giản – không dùng chaining.

Ý tưởng

• Mảng con trỏ HashTableEntry* kích thước cố định T_S.
• Hàm băm: h(k) = k % T_S.
• Va chạm: dò tuyến tính h(k), h(k+1), h(k+2)....
• Xóa: xóa entry và để NULL (có thể gây lỗ hổng cho tìm kiếm – bản cài này chấp nhận rủi ro).

Mã nguồn

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

const int T_S = 200;

class HashTableEntry {
public:
    int k, v;
    HashTableEntry(int k, int v) : k(k), v(v) {}
};

class HashMapTable {
    HashTableEntry **t;
public:
    HashMapTable() {
        t = new HashTableEntry*[T_S];
        for (int i = 0; i < T_S; i++) t[i] = NULL;
    }

    int HashFunc(int k) { return k % T_S; }

    void Insert(int k, int v) {
        int h = HashFunc(k);
        while (t[h] != NULL && t[h]->k != k)
            h = HashFunc(h + 1); // linear probe
        if (t[h] != NULL) delete t[h]; // cập nhật
        t[h] = new HashTableEntry(k, v);
    }

    int SearchKey(int k) {
        int h = HashFunc(k);
        while (t[h] != NULL && t[h]->k != k)
            h = HashFunc(h + 1);
        if (t[h] == NULL) return -1;
        return t[h]->v;
    }

    void Remove(int k) {
        int h = HashFunc(k);
        while (t[h] != NULL) {
            if (t[h]->k == k) break;
            h = HashFunc(h + 1);
        }
        if (t[h] == NULL) { cout << "No Element found at key " << k << endl; return; }
        delete t[h];
        t[h] = NULL; // ⚠️ có thể làm hỏng chuỗi dò cho các key sau nó
        cout << "Element Deleted" << endl;
    }

    ~HashMapTable() {
        for (int i = 0; i < T_S; i++)
            if (t[i] != NULL) delete t[i];
        delete[] t;
    }
};

int main() {
    HashMapTable hash;
    int k, v, c;
    while (1) {
        cout << "1.Insert\n2.Search\n3.Delete\n4.Exit\nChoice: "; cin >> c;
        switch (c) {
            case 1: cout << "Value: "; cin >> v;
                    cout << "Key: "; cin >> k; hash.Insert(k, v); break;
            case 2: cout << "Key: "; cin >> k;
                    if (hash.SearchKey(k) == -1) cout << "No element at key " << k << endl;
                    else cout << "Element at key " << k << " : " << hash.SearchKey(k) << endl;
                    break;
            case 3: cout << "Key: "; cin >> k; hash.Remove(k); break;
            case 4: return 0;
            default: cout << "Invalid\n";
        }
    }
}

Kết quả mẫu

1.Insert
Value: 1 Key: 1
...
2.Search
Key: 6
Element at key 6 : 7
3.Delete
Key: 1
Element Deleted
4.Exit

Vấn đề xóa trong Open Addressing

Khi xóa và để NULL, các key đã chèn sau nó (do va chạm) sẽ không tìm thấy vì dò dừng tại NULL.

Giải pháp chuẩn: dùng tombstone (đánh dấu xóa) – một đối tượng đặc biệt DELETED khác NULL. Khi dò: bỏ qua DELETED; khi chèn: có thể tái sử dụng ô DELETED.

So sánh nhanh

Khuyến nghị

• Học tập: hiểu cơ chế.
• Sản xuất: std::unordered_map (C++11), absl::flat_hash_map, robin_hood_hashing.