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

Bài này cài đặt bảng băm dùng chaining (phân xích) với danh sách liên kết kép (doubly linked list). Mỗi bucket trỏ đến head và tail của danh sách, hỗ trợ chèn cuối O(1) và xóa dễ dàng hơn nhờ con trỏ prev.

Cấu trúc dữ liệu

struct HashTableEntry {
    int d, k;           // data, key
    HashTableEntry *n;  // next
    HashTableEntry *p;  // previous
};

class HashMapTable {
    HashTableEntry **ht; // head của mỗi bucket
    HashTableEntry **top; // tail của mỗi bucket
    // ...
};

Thuật toán chính

Chèn (Insert)

• Tính hash_v = key % T_S.
• Nếu bucket rỗng: tạo node mới, gán cả ht[hash_v] và top[hash_v].
• Ngược lại: duyệt đến cuối (hoặc dùng top trực tiếp), nối node mới sau top, cập nhật top.

Xóa (Remove)

• Tìm node có khóa khớp (duyệt từ head).
• Nếu là node duy nhất: ht[hash_v] = top[hash_v] = NULL.
• Nếu là head: ht[hash_v] = en->n; en->n->p = NULL.
• Nếu là tail: top[hash_v] = en->p; en->p->n = NULL.
• Nếu giữa: en->p->n = en->n; en->n->p = en->p.
• delete en.

Tìm kiếm (Search)

• Duyệt từ head đến khi tìm thấy khóa hoặc hết danh sách.

Mã nguồn (đã sửa logic Remove đúng)

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

struct HashTableEntry {
    int d, k;
    HashTableEntry *n, *p;
    HashTableEntry(int k=0, int v=0) : d(v), k(k), n(NULL), p(NULL) {}
};

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

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

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

    void remove(int k) {
        int hash_v = HashFunc(k);
        HashTableEntry *en = ht[hash_v];
        while (en != NULL && en->k != k) en = en->n;
        if (en == NULL) { cout << "No Element found at key: " << k << endl; return; }

        if (en->p) en->p->n = en->n; else ht[hash_v] = en->n;
        if (en->n) en->n->p = en->p; else top[hash_v] = en->p;
        delete en;
        cout << "Element Deleted" << endl;
    }

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

    ~HashMapTable() {
        for (int i = 0; i < T_S; i++) {
            HashTableEntry *en = ht[i];
            while (en) { HashTableEntry *n = en->n; delete en; en = n; }
        }
        delete[] ht; delete[] top;
    }
};

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; hash.SearchKey(k); break;
            case 3: cout << "Key: "; cin >> k; hash.remove(k); break;
            case 4: return 0;
            default: cout << "Invalid\n";
        }
    }
}

Kết quả chạy

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

Ưu/nhược điểm so với singly linked list

Lưu ý

• Code gốc có lỗi logic Remove (chỉ xóa tail) – đã sửa trong bản trên.
• Thực tế: dùng std::list hoặc std::unordered_map.