Chương trình C++ cài đặt bảng băm chaining với List Heads

Bài này cài đặt bảng băm dùng kỹ thuật chaining (phân xích) với cấu trúc List Head – mỗi bucket trỏ đến đầu một danh sách liên kết đơn chứa các entry (khóa, giá trị).

Thuật toán

Chèn (Insert)

Bắt đầu
    Insert(k, v)
    hash_v = HashFunc(k)
    Nếu (ht[hash_v] == NULL) ht[hash_v] = new ListHead(k, v)
    Ngược lại:
        en = ht[hash_v]
        Khi (en->n != NULL) en = en->n
        Nếu (en->k == k) en->v = v
        Ngược lại en->n = new ListHead(k, v)
Kết thúc

Tìm kiếm (Search)

Bắt đầu
    SearchKey(k)
    hash_v = HashFunc(k)
    Nếu (ht[hash_v] == NULL) trả về -1
    Ngược lại:
        en = ht[hash_v]
        Khi (en != NULL VÀ en->k != k) en = en->n
        Nếu (en == NULL) trả về -1
        Ngược lại trả về en->v
Kết thúc

Xóa (Remove)

Bắt đầu
    Remove(k)
    hash_v = HashFunc(k)
    Nếu (ht[hash_v] != NULL):
        en = ht[hash_v], p = NULL
        Khi (en->n != NULL VÀ en->k != k): p = en; en = en->n
        Nếu (en->k == k):
            Nếu (p == NULL): n = en->n; xóa en; ht[hash_v] = n
            Ngược lại: n = en->n; xóa en; p->n = n
Kết thúc

Mã nguồn

#include <iostream>
using namespace std;

const int T_S = 20;

class ListHead {
public:
    int k, v;
    ListHead *n;
    ListHead(int k, int v) : k(k), v(v), n(NULL) {}
};

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

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

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

    int SearchKey(int k) {
        int hash_v = HashFunc(k);
        if (ht[hash_v] == NULL) return -1;
        ListHead *en = ht[hash_v];
        while (en != NULL && en->k != k) en = en->n;
        if (en == NULL) return -1;
        else return en->v;
    }

    void Remove(int k) {
        int hash_v = HashFunc(k);
        if (ht[hash_v] != NULL) {
            ListHead *en = ht[hash_v], *p = NULL;
            while (en->n != NULL && en->k != k) { p = en; en = en->n; }
            if (en->k == k) {
                if (p == NULL) { ListHead *n = en->n; delete en; ht[hash_v] = n; }
                else { ListHead *n = en->n; delete en; p->n = n; }
            }
        }
    }

    ~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;
                    if (hash.SearchKey(k) == -1) cout << "No element found at key " << k << endl;
                    else { cout << "Elements at key " << k << " : " << hash.SearchKey(k) << endl; }
                    break;
            case 3: cout << "Enter key of the element to be deleted: "; cin >> k;
                    if (hash.SearchKey(k) == -1) cout << "Key " << k << " is empty" << endl;
                    else { hash.Remove(k); cout << "Entry Removed" << endl; }
                    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: 1
Enter key at which element to be inserted: 2
...
Enter your choice: 2
Enter key of the element to be searched: 6
Elements at key 6 : 7
Enter your choice: 3
Enter key of the element to be deleted: 1
Entry Removed
Enter your choice: 4

So sánh với chaining danh sách liên kết đơn thông thường

• List Head: Mỗi bucket là con trỏ trực tiếp đến nút đầu (head) của danh sách. Code đơn giản hơn, không cần mảng con trỏ phụ top.
• Cài đặt trên dùng chèn cuối (append) – O(độ dài danh sách). Có thể tối ưu bằng chèn đầu (prepend) O(1) nếu không yêu cầu thứ tự.
• Phù hợp cho bài tập học tập, hệ thống nhúng nhỏ. Với ứng dụng thực tế, nên dùng std::unordered_map hoặc std::vector<std::list<pair<K,V>>>.