您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

哈希表線性探測法 C++ 模板實現：插入、刪除、查找、拷貝構造

編輯：關於C++

設計要點

模板類支援任意可哈希類型
三態標記：Active（有效）、Empty（從未使用）、Deleted（邏輯刪除）
線性探測解決衝突：pos = (pos + 1) % size
負載因子超過閾值需擴容（示例簡化為固定大小）

核心代碼

#include 
#include 
using namespace std;

enum Status { Empty, Active, Deleted };

template
class HashTable {
    T* data;
    Status* state;
    int capacity, size;
    int hash_func(const T& key) const { return key % capacity; }
public:
    HashTable(int cap = 10) : capacity(cap), size(0) {
        data = new T[capacity];
        state = new Status[capacity];
        fill(state, state + capacity, Empty);
    }
    ~HashTable() { delete[] data; delete[] state; }
    
    // 拷貝構造
    HashTable(const HashTable& other) : capacity(other.capacity), size(other.size) {
        data = new T[capacity];
        state = new Status[capacity];
        copy(other.data, other.data + capacity, data);
        copy(other.state, other.state + capacity, state);
    }
    
    bool insert(const T& key) {
        if (size * 2 >= capacity) return false;  // 簡化：不擴容
        int pos = hash_func(key);
        for (int i = 0; i < capacity; ++i) {
            int idx = (pos + i) % capacity;
            if (state[idx] != Active) {
                data[idx] = key;
                state[idx] = Active;
                ++size;
                return true;
            }
            if (data[idx] == key) return false;  // 已存在
        }
        return false;
    }
    
    bool remove(const T& key) {
        int pos = hash_func(key);
        for (int i = 0; i < capacity; ++i) {
            int idx = (pos + i) % capacity;
            if (state[idx] == Empty) return false;
            if (state[idx] == Active && data[idx] == key) {
                state[idx] = Deleted;
                --size;
                return true;
            }
        }
        return false;
    }
    
    bool find(const T& key) const {
        int pos = hash_func(key);
        for (int i = 0; i < capacity; ++i) {
            int idx = (pos + i) % capacity;
            if (state[idx] == Empty) return false;
            if (state[idx] == Active && data[idx] == key) return true;
        }
        return false;
    }
    
    void display() const {
        for (int i = 0; i < capacity; ++i) {
            cout << setw(3) << i << ": ";
            if (state[i] == Active) cout << data[i];
            else if (state[i] == Deleted) cout << "DEL";
            else cout << "---";
            cout << '\n';
        }
    }
};

int main() {
    HashTable ht(10);
    for (int x : {1,8,15,22,29,36,43,50,57,64}) ht.insert(x);
    cout << "初始狀態:\n"; ht.display();
    
    HashTable ht2(ht);  // 拷貝構造
    ht2.remove(8);
    cout << "\n刪除 8 後:\n"; ht2.display();
    return 0;
}

關鍵操作詳解

操作	關鍵邏輯
插入	從哈希位置線性探測，遇到 Empty/Deleted 可插入，遇到相同 key 視為重複
查找	同插入探測路徑，遇到 Empty 停止（後續不可能有目標）
刪除	標記 Deleted，不可設為 Empty（會斷開探測鏈）
拷貝構造	深拷貝 data 和 state 數組