C++ 雜湊表二次探測完整實現模板

設計目標

實現一個通用的雜湊表類別 HashTable<Type>，支援：
- 二次探測解決衝突。
- 三種槽位狀態：Empty (0)、Active (1)、Deleted (2)。
- 動態擴容：負載因子超閾值時自動重雜湊到更大表（通常為 2×舊容量+1）。
- 基本操作：Insert、Find、Remove、Show。

核心數據結構

enum KindOfStatus { Empty = 0, Active, Deleted };

template
class HashTable {
private:
    Type* data;              // 元素數組
    KindOfStatus* status;    // 狀態數組
    int capacity;            // 當前容量 (質數)
    int size;                // 當前元素數
    static const int DEFAULT_SIZE = 11; // 初始容量

    int hash(const Type& val) const { return val % capacity; } // 簡單取模，實際應用可換更強雜湊
    int findPos(const Type& val) const; // 尋找位置（含探測）
    void rehash(); // 擴容重雜湊
public:
    HashTable(int sz = DEFAULT_SIZE);
    ~HashTable() { delete[] data; delete[] status; }
    bool insert(const Type& val);
    bool remove(const Type& val);
    bool find(const Type& val) const;
    void show() const;
};

二次探測邏輯

int HashTable::findPos(const Type& val) const {
    int index = hash(val);
    for (int k = 0; k < capacity; ++k) {
        int pos = (index + k * k) % capacity; // 二次探測：+k²
        if (status[pos] == Empty) return pos; // 找到空位（插入用）或確認不存在（查找用）
        if (status[pos] == Active && data[pos] == val) return pos; // 找到目標
        // Deleted 視為佔用，繼續探測
    }
    return -1; // 表滿
}

插入與擴容

bool HashTable::insert(const Type& val) {
    if (size * 2 >= capacity) rehash(); // 負載因子 > 0.5 擴容
    int pos = findPos(val);
    if (pos == -1) return false; // 理論上 rehash 後不會滿
    if (status[pos] == Active) return false; // 已存在
    data[pos] = val;
    status[pos] = Active;
    ++size;
    return true;
}

void HashTable::rehash() {
    int oldCap = capacity;
    Type* oldData = data;
    KindOfStatus* oldStatus = status;
    capacity = 2 * capacity + 1; // 新質數，簡化處理
    data = new Type[capacity];
    status = new KindOfStatus[capacity];
    for (int i = 0; i < capacity; ++i) status[i] = Empty;
    size = 0;
    for (int i = 0; i < oldCap; ++i)
        if (oldStatus[i] == Active) insert(oldData[i]);
    delete[] oldData;
    delete[] oldStatus;
}

刪除（懶惰刪除）

bool HashTable::remove(const Type& val) {
    int pos = findPos(val);
    if (pos == -1 || status[pos] != Active) return false;
    status[pos] = Deleted; // 標記刪除，不實際清空 data
    --size;
    return true;
}

測試主程式

int main() {
    HashTable ht(3);
    int a[] = {1, 4, 7, 10};
    for (int x : a) ht.insert(x);
    ht.show(); // 輸出表內容驗證
    return 0;
}

關鍵點總結

• 狀態機：Empty/Active/Deleted 三態正確處理探測路徑，Deleted 不中斷查找，但可被插入復用。
• 二次探測：(h + k²) % M 保證在 M 為質數且負載因子 ≤ 0.5 時能遍歷所有槽位。
• 擴容策略：負載因子超 0.5 觸發，新容量取 2×舊+1（簡易質數），重新插入所有 Active 元素。
• 模板泛型：支援任意可取模、可比較的型別 Type。

改進方向

• 雜湊函數泛化（傳入仿函數）。
• 迭代器支援。
• 用 std::vector 替換裸指針管理內存。