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

哈希表 C++ 實現詳解：開放地址法與鏈地址法

編輯：關於C++

哈希表 C++ 實現詳解

本文梳理哈希表核心概念，並給出基於開放地址法（線性探測）的完整 C++ 實現代碼，包含動態擴容、衝突統計、查找/插入/遍歷操作。

核心概念

哈希函數：將關鍵字映射為表索引（Hash(key) = key % TableSize）。
衝突：不同關鍵字經哈希函數得到相同索引。
處理衝突：
1. 開放地址法：衝突時按探測序列尋找下一個空槽（線性/二次/雙重雜湊）。
2. 鏈地址法：同義詞鏈入單鏈表。
3. 再哈希法：更換哈希函數重試（較少用）。
負載因子 α = N / M：當 α 超過閾值（如 0.75）觸發擴容重雜湊。

代碼實現（開放地址法 + 線性探測）

myhash.h — 核心類定義

#ifndef MYHASH_H
#define MYHASH_H
#include 
#include 
using namespace std;

typedef int KeyType;
const int NULLKEY = -1;          // 標記空槽，避免 0 為合法鍵值

struct ElemType {
    KeyType key;
    int ord;                     // 附加數據（如記錄序號）
    ElemType(KeyType k = NULLKEY, int o = 0) : key(k), ord(o) {}
    bool isNull() const { return key == NULLKEY; }
};

class HashTable {
    vector elem;       // 動態數組存儲
    int count;                   // 當前元素數
    int sizeIdx;                 // hashsize 索引
    static const int hashsize[]; // 容量遞增表

    int HashLength() const { return hashsize[sizeIdx]; }
    int Hash(KeyType key) const { return key % HashLength(); }

    void Rehash();               // 擴容重雜湊
public:
    HashTable() : count(0), sizeIdx(0) { elem.assign(HashLength(), ElemType()); }

    bool Insert(const ElemType& e);     // 插入，返回是否成功
    bool Search(KeyType key, ElemType& out) const; // 查找
    void Traverse() const;              // 遍歷輸出
    int CollisionCount() const;         // 統計衝突次數
};
#endif

myhash.cpp — 關鍵方法實現

#include "myhash.h"

const int HashTable::hashsize[] = { 11, 19, 29, 37, 47, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869 };

void HashTable::Rehash() {
    vector old = elem;
    sizeIdx++;
    elem.assign(HashLength(), ElemType());
    count = 0;
    for (const auto& e : old) if (!e.isNull()) Insert(e);
}

bool HashTable::Insert(const ElemType& e) {
    if (count * 4 >= HashLength() * 3) Rehash(); // α > 0.75 擴容
    int addr = Hash(e.key);
    int start = addr;
    do {
        if (elem[addr].isNull()) {
            elem[addr] = e;
            ++count;
            return true;
        }
        if (elem[addr].key == e.key) return false; // 鍵值重複
        addr = (addr + 1) % HashLength();          // 線性探測
    } while (addr != start);
    return false; // 理論上不會滿（已擴容）
}

bool HashTable::Search(KeyType key, ElemType& out) const {
    int addr = Hash(key);
    int start = addr;
    do {
        if (elem[addr].isNull()) return false;
        if (elem[addr].key == key) { out = elem[addr]; return true; }
        addr = (addr + 1) % HashLength();
    } while (addr != start);
    return false;
}

void HashTable::Traverse() const {
    cout << "Index  Key  Ord\n";
    for (int i = 0; i < HashLength(); ++i)
        if (!elem[i].isNull()) cout << i << "      " << elem[i].key << "    " << elem[i].ord << "\n";
}

int HashTable::CollisionCount() const {
    // 簡易統計：非空槽中 key%len != 索引 的數量
    int c = 0;
    for (int i = 0; i < HashLength(); ++i)
        if (!elem[i].isNull() && Hash(elem[i].key) != i) ++c;
    return c;
}

main.cpp — 測試驅動

#include "myhash.h"

int main() {
    HashTable H;
    ElemType data[] = { {17,1}, {60,2}, {29,3}, {38,4}, {1,5}, {2,6}, {3,7}, {4,8}, {5,9}, {6,10}, {7,11}, {8,12} };
    for (auto& e : data) {
        if (!H.Insert(e)) cout << "Duplicate key: " << e.key << "\n";
    }
    H.Traverse();
    cout << "Collisions: " << H.CollisionCount() << "\n";

    ElemType found;
    if (H.Search(29, found)) cout << "Found: " << found.key << " ord=" << found.ord << "\n";
    return 0;
}

運行示例輸出

Index  Key  Ord
0      1    5
1      60   2
2      38   4
3      17   1
4      4    8
5      5    9
6      6    10
7      7    11
8      8    12
9      2    6
10     3    7
Collisions: 5
Found: 29 ord=3