散列表C++實現：探測法解決沖突（線性/平方/雙散列）完整教程

散列表通過散列函數將鍵映射到數組下標，實現平均 O(1) 的插入、刪除、查找。本文實現基於開放定址法的探測散列表，詳細對比線性探測、平方探測、雙散列三種沖突解決策略，並提供生產級模板代碼。

核心設計

散列函數

採用多項式滾動雜湊：hashVal = 37 * hashVal + key[i]，最終取模表大小。表大小取素數以減少沖突。

int hash(const string& key, int tableSize) {
    int hashVal = 0;
    for (char c : key) hashVal = 37 * hashVal + c;
    hashVal %= tableSize;
    return hashVal < 0 ? hashVal + tableSize : hashVal;
}

數據單元結構

enum EntryType { ACTIVE, EMPTY, DELETED };
struct HashEntry {
    HashedObj element;
    EntryType info;
    HashEntry(const HashedObj& e = HashedObj(), EntryType i = EMPTY) : element(e), info(i) {}
};

三種探測策略對比

關鍵成員函數實現

查找位置 findPos（以平方探測為例）

int findPos(const HashedObj& x) {
    int offset = 1;
    int currentPos = myhash(x);
    while (array[currentPos].info != EMPTY && array[currentPos].element != x) {
        currentPos += 2 * offset - 1; // 平方探測：f(i) - f(i-1) = 2i-1
        if (currentPos >= array.size()) currentPos -= array.size();
        offset++;
    }
    return currentPos;
}

插入 insert 與 再散列 rehash

bool insert(const HashedObj& x) {
    int pos = findPos(x);
    if (isActive(pos)) return false; // 已存在
    array[pos] = HashEntry(x, ACTIVE);
    if (++currentSize > array.size() / 2) rehash(); // 裝填因子>0.5擴容
    return true;
}

void rehash() {
    vector oldArray = array;
    array.resize(nextPrime(2 * oldArray.size()));
    fill(array.begin(), array.end(), HashEntry());
    currentSize = 0;
    for (auto& entry : oldArray)
        if (entry.info == ACTIVE) insert(entry.element); // 必須用insert重新計算hash
}

刪除 remove（懶惰刪除）

bool remove(const HashedObj& x) {
    int pos = findPos(x);
    if (!isActive(pos)) return false;
    array[pos].info = DELETED; // 標記刪除，不物理移除
    --currentSize;
    return true;
}

測試用例：Employee 類

class Employee {
    string name; double salary; int seniority;
public:
    Employee(const string& n, double s, int se) : name(n), salary(s), seniority(se) {}
    const string& getName() const { return name; }
    bool operator==(const Employee& rhs) const { return name == rhs.name; }
    friend ostream& operator<<(ostream& os, const Employee& e) {
        return os << "name: " << e.name << ", salary: " << e.salary << ", seniority: " << e.seniority;
    }
};

運行結果

輸出散列表中的內容:
1: element: name: kro, salary: 109, seniority: 9, info = 0
3: element: name: jan, salary: 108, seniority: 8, info = 0
4: element: name: may, salary: 104, seniority: 4, info = 0
5: element: name: bei, salary: 110, seniority: 10, info = 0
6: element: name: usa, salary: 105, seniority: 5, info = 0
17: element: name: ever, salary: 102, seniority: 2, info = 0
18: element: name: sal, salary: 106, seniority: 6, info = 0
21: element: name: peter, salary: 103, seniority: 3, info = 0
22: element: name: linux, salary: 101, seniority: 1, info = 0

測試包含函數containes: containe e10 / not containe e12
測試findElement(): e11: name: jan, salary: 108, seniority: 8
測試isEmpty(): hashTable is not Empty
測試makeEmpty(): hashTable is Empty

工程建議

• 生產環境優先考慮 std::unordered_map 或成熟庫（如 absl::flat_hash_map）。
• 自定義散列函數時，針對鍵類型特化 std::hash。
• 高併發場景需考慮無鎖散列表或分段鎖。