Chương trình C++ cài đặt bảng băm chaining với danh sách liên kết đơn

Bảng băm (hash table) lưu trữ cặp khóa-giá trị. Chaining (phân xích) giải quyết va chạm bằng cách lưu trữ các phần tử cùng chỉ mục băm trong một danh sách liên kết. Bài này cài đặt với danh sách liên kết đơn (singly linked list).

Thuật toán

Chèn (Insert)

Bắt đầu
    Insert(k, v)
    hash_v = HashFunc(k)
    p = NULL, en = ht[hash_v]
    Khi (en != NULL): p = en; en = en->n
    Nếu (en == NULL):
        en = new HashTableEntry(k, v)
        Nếu (p == NULL) ht[hash_v] = en
        Ngược lại p->n = en
    Ngược lại: en->v = v  // cập nhật giá trị nếu khóa đã tồn tại
Kết thúc

Xóa (Delete)

Bắt đầu
    Remove(k)
    hash_v = HashFunc(k)
    en = ht[hash_v], p = NULL
    Nếu (en == NULL HOẶC en->k != k): in "No Element found at key"; trả về
    Khi (en->n != NULL): p = en; en = en->n
    Nếu (p != NULL) p->n = en->n
    xóa en; in "Element Deleted"
Kết thúc

Tìm kiếm (Search)

Bắt đầu
    SearchKey(k)
    hash_v = HashFunc(k)
    flag = false, en = ht[hash_v]
    Nếu (en != NULL):
        Khi (en != NULL):
            Nếu (en->k == k) flag = true
            Nếu (flag) in "Element found at key", in en->v
            en = en->n
    Nếu (!flag) in "No Element found at key"
Kết thúc

Mã nguồn

#include <iostream>
const int T_S = 200;
using namespace std;

struct HashTableEntry {
    int v, k;
    HashTableEntry *n, *p; // p không dùng cho singly list, có thể bỏ
    HashTableEntry(int k, int v) : k(k), v(v), n(NULL) {}
};

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

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

    void Insert(int k, int v) {
        int hash_v = HashFunc(k);
        HashTableEntry *p = NULL, *en = ht[hash_v];
        while (en != NULL) { p = en; en = en->n; }
        if (en == NULL) {
            en = new HashTableEntry(k, v);
            if (p == NULL) ht[hash_v] = en;
            else p->n = en;
        } else en->v = v;
    }

    void Remove(int k) {
        int hash_v = HashFunc(k);
        HashTableEntry *en = ht[hash_v], *p = NULL;
        if (en == NULL || en->k != k) { cout << "No Element found at key " << k << endl; return; }
        while (en->n != NULL) { p = en; en = en->n; }
        if (p != NULL) p->n = en->n;
        delete en; cout << "Element Deleted" << endl;
    }

    void SearchKey(int k) {
        int hash_v = HashFunc(k);
        bool flag = false;
        HashTableEntry *en = ht[hash_v];
        if (en != NULL) {
            while (en != NULL) {
                if (en->k == k) flag = true;
                if (flag) { cout << "Element found at key " << k << ": " << en->v << endl; }
                en = en->n;
            }
        }
        if (!flag) cout << "No Element found at key " << k << endl;
    }

    ~HashMapTable() { delete[] ht; }
};

int main() {
    HashMapTable hash;
    int k, v, c;
    while (1) {
        cout << "1.Insert element into the table" << endl;
        cout << "2.Search element from the key" << endl;
        cout << "3.Delete element at a key" << endl;
        cout << "4.Exit" << endl;
        cout << "Enter your choice: "; cin >> c;
        switch (c) {
            case 1: cout << "Enter element to be inserted: "; cin >> v;
                    cout << "Enter key at which element to be inserted: "; cin >> k;
                    hash.Insert(k, v); break;
            case 2: cout << "Enter key of the element to be searched: "; cin >> k; hash.SearchKey(k); break;
            case 3: cout << "Enter key of the element to be deleted: "; cin >> k; hash.Remove(k); break;
            case 4: exit(1);
            default: cout << "\nEnter correct option\n";
        }
    }
    return 0;
}

Kết quả chạy

1.Insert element into the table
Enter element to be inserted: 2
Enter key at which element to be inserted: 1
...
Enter your choice: 2
Enter key of the element to be searched: 6
Element found at key 6: 7
Enter your choice: 2
Enter key of the element to be searched: 7
No Element found at key 7
Enter your choice: 3
Enter key of the element to be deleted: 9
Element Deleted
Enter your choice: 4

Đánh giá

• Ưu điểm: Cài đặt đơn giản, không giới hạn số phần tử mỗi bucket, hiệu suất ổn định O(1+α) (α = hệ số tải).
• Nhược điểm: Tốn bộ nhớ con trỏ, cache miss do phân tán bộ nhớ, xóa phần tử giữa danh sách đơn cần duyệt từ đầu (code trên chỉ xóa cuối danh sách – logic Remove cần sửa để xóa đúng nút khớp khóa).
• Cải tiến: Dùng std::list hoặc std::forward_list (C++11) thay vì tự quản lý con trỏ.