C++开放地址法详解（手把手教你用C++实现哈希表的开放寻址法）

C++实现开放地址法哈希表

下面我们将用C++从零开始实现一个基于开放地址法的简单哈希表。为了便于理解，我们只实现插入（insert）和查找（search）两个核心功能。

1. 定义哈希表结构

首先，我们需要一个数组来存储数据，并用特殊值（如-1）表示空槽。同时，为了避免无限循环，哈希表不能完全填满，通常会设置一个负载因子（load factor）上限（例如0.7）。

#include <iostream>#include <vector>#include <climits>const int EMPTY = -1;        // 表示空槽const int DELETED = -2;      // 表示已删除（可选，用于支持删除操作）class OpenAddressingHashTable {private:    std::vector<int> table;    int size;    int capacity;    int hash(int key) {        return key % capacity;    }public:    OpenAddressingHashTable(int cap) : capacity(cap), size(0) {        table.assign(capacity, EMPTY);    }    void insert(int key);    bool search(int key);};

2. 实现插入操作（线性探测）

插入时，先计算哈希值。如果该位置已被占用，则依次检查下一个位置（i+1, i+2, ...），直到找到空槽或已删除槽。

void OpenAddressingHashTable::insert(int key) {    if (size >= capacity * 0.7) {        std::cout << "哈希表已满，无法插入！\n";        return;    }    int index = hash(key);    int originalIndex = index;    // 线性探测：逐个检查下一个位置    while (table[index] != EMPTY && table[index] != DELETED) {        if (table[index] == key) {            std::cout << "键值 " << key << " 已存在！\n";            return;        }        index = (index + 1) % capacity;        // 防止无限循环        if (index == originalIndex) {            std::cout << "哈希表已满！\n";            return;        }    }    table[index] = key;    size++;    std::cout << "成功插入: " << key << " 到位置 " << index << "\n";}

3. 实现查找操作

查找过程与插入类似：从哈希位置开始，线性探测直到找到目标键或遇到空槽（表示不存在）。

bool OpenAddressingHashTable::search(int key) {    int index = hash(key);    int originalIndex = index;    while (table[index] != EMPTY) {        if (table[index] == key) {            return true;        }        index = (index + 1) % capacity;        if (index == originalIndex) {            break; // 已遍历整个表        }    }    return false;}

4. 测试代码

int main() {    OpenAddressingHashTable hashTable(7); // 容量为7    hashTable.insert(10);    hashTable.insert(20);    hashTable.insert(15);    hashTable.insert(7);    std::cout << "查找 15: " << (hashTable.search(15) ? "找到" : "未找到") << "\n";    std::cout << "查找 25: " << (hashTable.search(25) ? "找到" : "未找到") << "\n";    return 0;}

总结

通过本教程，你已经学会了如何用C++实现基于开放地址法的哈希表。这种方法避免了动态内存分配，缓存友好，适合对性能要求高的场景。但要注意，当负载因子过高时，性能会急剧下降，因此合理设置容量和再哈希策略非常重要。

希望这篇关于C++哈希冲突解决的教程对你有帮助！如果你是初学者，建议动手敲一遍代码，加深理解。后续可以尝试实现二次探测或支持删除操作，进一步提升你的开放寻址法教程实战能力。

SEO关键词回顾：

• C++开放地址法
• 哈希表实现
• C++哈希冲突解决
• 开放寻址法教程