C++哈希表实现详解（开放地址法解决哈希冲突）

C++实现：基于线性探测的开放地址哈希表

下面我们使用C++实现一个简单的哈希表，采用线性探测作为冲突解决策略。为了简化，我们只支持整数键值对。

1. 定义哈希表结构

首先，我们需要定义一个哈希表类，包含以下要素：

• 存储桶数组（buckets）
• 标记空槽、已删除槽和有效槽的状态
• 当前元素数量

#include <iostream>#include <vector>#include <climits>enum class EntryStatus { EMPTY, OCCUPIED, DELETED };struct HashEntry {    int key;    int value;    EntryStatus status;    HashEntry() : key(0), value(0), status(EntryStatus::EMPTY) {}};class OpenAddressHashTable {private:    std::vector<HashEntry> table;    int size; // 当前元素个数    int capacity; // 表容量    int hash(int key) {        return key % capacity;    }public:    OpenAddressHashTable(int cap = 101) : capacity(cap), size(0) {        table.resize(capacity);    }    bool insert(int key, int value);    bool search(int key, int& value);    bool remove(int key);    void display();};

2. 插入操作实现

插入时，若发生冲突，则线性探测下一个位置，直到找到空槽或已删除槽。

bool OpenAddressHashTable::insert(int key, int value) {    if (size >= capacity * 0.75) {        std::cout << "哈希表已满，无法插入！\n";        return false;    }    int index = hash(key);    int originalIndex = index;    // 线性探测    while (table[index].status == EntryStatus::OCCUPIED) {        if (table[index].key == key) {            // 更新已有键的值            table[index].value = value;            return true;        }        index = (index + 1) % capacity;        if (index == originalIndex) {            // 表已满（理论上不应发生，因有负载因子限制）            return false;        }    }    // 找到空槽或已删除槽    table[index].key = key;    table[index].value = value;    table[index].status = EntryStatus::OCCUPIED;    size++;    return true;}

3. 查找与删除操作

bool OpenAddressHashTable::search(int key, int& value) {    int index = hash(key);    int originalIndex = index;    while (table[index].status != EntryStatus::EMPTY) {        if (table[index].status == EntryStatus::OCCUPIED &&             table[index].key == key) {            value = table[index].value;            return true;        }        index = (index + 1) % capacity;        if (index == originalIndex) break; // 已遍历完整个表    }    return false;}bool OpenAddressHashTable::remove(int key) {    int index = hash(key);    int originalIndex = index;    while (table[index].status != EntryStatus::EMPTY) {        if (table[index].status == EntryStatus::OCCUPIED &&             table[index].key == key) {            table[index].status = EntryStatus::DELETED;            size--;            return true;        }        index = (index + 1) % capacity;        if (index == originalIndex) break;    }    return false;}

为什么需要“已删除”状态？

在开放地址法中，直接将删除的槽设为空（EMPTY）会破坏后续查找的连续性。例如，若A、B、C因冲突被依次存放在位置i、i+1、i+2，删除B后若将i+1设为空，则查找C时会在i+1停止（误以为C不存在）。因此，我们引入DELETED状态，表示该位置可被新元素覆盖，但查找时需继续探测。

性能与注意事项

- 负载因子（Load Factor）应控制在0.75以下，以避免过多冲突。
- 线性探测容易产生聚集（Clustering），可考虑使用二次探测或双重哈希优化。
- 本实现适用于教学目的，实际项目中建议使用标准库的std::unordered_map。

总结

通过本文，你已经学会了如何在C++中使用开放地址法实现一个简单的哈希表。这种技术是理解高级数据结构的基础，也是面试中常见的考点。掌握C++哈希表、哈希冲突解决和C++数据结构的核心思想，将为你打下坚实的编程基础。

希望这篇教程对你有所帮助！如果你有任何问题，欢迎在评论区留言交流。