Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Chương trình C++ cài đặt bảng băm với dò tuyến tính (Linear Probing)

Bảng băm (hash table) là cấu trúc dữ liệu dùng để lưu trữ các cặp khóa-giá trị (key-value). Hàm băm tính toán chỉ mục trong mảng để chèn hoặc tìm kiếm phần tử.

Dò tuyến tính (Linear Probing)

Dò tuyến tính là kỹ thuật giải quyết va chạm trong bảng băm định địa chỉ mở (open addressing). Mỗi ô lưu trữ một cặp khóa-giá trị. Khi xảy ra va chạm (khóa mới ánh xạ tới ô đã có khóa khác), phương pháp này tìm kiếm tuần tự các ô tiếp theo cho đến khi tìm thấy ô trống để chèn khóa mới.

Thuật toán

Chèn (Insert)

Bắt đầu
    Hàm Insert(k, v)
    hash_val = HashFunc(k)
    init = -1
    delindex = -1
    Khi (hash_val != init VÀ (ht[hash_val] == DelNode::getNode() HOẶC ht[hash_val] != NULL VÀ ht[hash_val]->k != k))
        Nếu (init == -1) init = hash_val
        Nếu (ht[hash_val] == DelNode::getNode()) delindex = hash_val
        hash_val = HashFunc(hash_val + 1)
    Nếu (ht[hash_val] == NULL HOẶC hash_val == init)
        Nếu (delindex != -1) ht[delindex] = new HashTable(k, v)
        Ngược lại ht[hash_val] = new HashTable(k, v)
    Nếu (init != hash_val)
        Nếu (ht[hash_val] != DelNode::getNode())
            Nếu (ht[hash_val] != NULL)
                Nếu (ht[hash_val]->k == k) ht[hash_val]->v = v
        Ngược lại ht[hash_val] = new HashTable(k, v)
Kết thúc

Tìm kiếm khóa (Search)

Bắt đầu
    Hàm SearchKey(k)
    hash_val = HashFunc(k)
    init = -1
    Khi (hash_val != init VÀ (ht[hash_val] == DelNode::getNode() HOẶC ht[hash_val] != NULL VÀ ht[hash_val]->k != k))
        Nếu (init == -1) init = hash_val
        hash_val = HashFunc(hash_val + 1)
    Nếu (ht[hash_val] == NULL HOẶC hash_val == init) trả về -1
    Ngược lại trả về ht[hash_val]->v
Kết thúc

Xóa (Delete)

Bắt đầu
    Hàm Remove(k)
    hash_val = HashFunc(k)
    init = -1
    Khi (hash_val != init VÀ (ht[hash_val] == DelNode::getNode() HOẶC ht[hash_val] != NULL VÀ ht[hash_val]->k != k))
        Nếu (init == -1) init = hash_val
        hash_val = HashFunc(hash_val + 1)
    Nếu (hash_val != init VÀ ht[hash_val] != NULL)
        xóa ht[hash_val]
        ht[hash_val] = DelNode::getNode()
Kết thúc

Mã nguồn hoàn chỉnh

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

const int T_S = 5;

class HashTable {
public:
    int k, v;
    HashTable(int k, int v) { this->k = k; this->v = v; }
};

class DelNode : public HashTable {
private:
    static DelNode *en;
    DelNode() : HashTable(-1, -1) {}
public:
    static DelNode* getNode() {
        if (en == NULL) en = new DelNode();
        return en;
    }
};
DelNode *DelNode::en = NULL;

class HashMapTable {
private:
    HashTable **ht;
public:
    HashMapTable() {
        ht = new HashTable*[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_val = HashFunc(k);
        int init = -1, delindex = -1;
        while (hash_val != init && (ht[hash_val] == DelNode::getNode() || (ht[hash_val] != NULL && ht[hash_val]->k != k))) {
            if (init == -1) init = hash_val;
            if (ht[hash_val] == DelNode::getNode()) delindex = hash_val;
            hash_val = HashFunc(hash_val + 1);
        }
        if (ht[hash_val] == NULL || hash_val == init) {
            if (delindex != -1) ht[delindex] = new HashTable(k, v);
            else ht[hash_val] = new HashTable(k, v);
        }
        if (init != hash_val) {
            if (ht[hash_val] != DelNode::getNode()) {
                if (ht[hash_val] != NULL && ht[hash_val]->k == k)
                    ht[hash_val]->v = v;
            } else ht[hash_val] = new HashTable(k, v);
        }
    }

    int SearchKey(int k) {
        int hash_val = HashFunc(k);
        int init = -1;
        while (hash_val != init && (ht[hash_val] == DelNode::getNode() || (ht[hash_val] != NULL && ht[hash_val]->k != k))) {
            if (init == -1) init = hash_val;
            hash_val = HashFunc(hash_val + 1);
        }
        if (ht[hash_val] == NULL || hash_val == init) return -1;
        else return ht[hash_val]->v;
    }

    void Remove(int k) {
        int hash_val = HashFunc(k);
        int init = -1;
        while (hash_val != init && (ht[hash_val] == DelNode::getNode() || (ht[hash_val] != NULL && ht[hash_val]->k != k))) {
            if (init == -1) init = hash_val;
            hash_val = HashFunc(hash_val + 1);
        }
        if (hash_val != init && ht[hash_val] != NULL) {
            delete ht[hash_val];
            ht[hash_val] = DelNode::getNode();
        }
    }

    ~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; continue;
                } else {
                    cout << "Element at key " << k << " : " << hash.SearchKey(k) << endl;
                } 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ả mẫu

1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 10
Enter key at which element to be inserted: 2
...
Enter your choice: 2
Enter key of the element to be searched: 6
Element at key 6 : 7
...
Enter your choice: 3
Enter key of the element to be deleted: 2
...
Enter your choice: 2
Enter key of the element to be searched: 2
No element found at key 2
Enter your choice: 4

Giải thích thêm

  • DelNode: Lớp đánh dấu ô đã xóa (tombstone) để dò tuyến tính không bị ngắt quãng khi tìm kiếm.
  • HashFunc(k) = k % T_S: Hàm băm đơn giản lấy phần dư.
  • Khi bảng đầy, dò tuyến tính có thể dẫn đến cụm (clustering) làm giảm hiệu suất. Giải pháp: dùng dò bậc hai (quadratic probing) hoặc băm kép (double hashing).