C++如何实现一个哈希表_C++数据结构中散列表的冲突解决方法-C++-PHP中文网

C++如何实现一个哈希表_C++数据结构中散列表的冲突解决方法

裘德小鎮的故事

发布： 2025-11-23 00:17:23

原创

186人浏览过

答案：C++实现哈希表需通过哈希函数将键映射到数组索引，并用链地址法或开放定址法处理冲突；链地址法使用链表存储同桶元素，实现简单且支持高效删除，而开放定址法通过探测寻找空位，节省空间但易产生聚集；实际应用中需结合负载因子、扩容机制与高质量哈希函数以确保性能。

c++如何实现一个哈希表_c++数据结构中散列表的冲突解决方法

在C++中实现哈希表，核心是将键（key）通过哈希函数映射到数组索引，并处理可能出现的冲突。冲突是指不同的键经过哈希函数后得到相同的索引位置。为解决这个问题，常用的方法有开放定址法和链地址法。下面详细介绍如何用C++实现一个简单的哈希表，并展示两种主要的冲突处理策略。

哈希表的基本结构

哈希表本质上是一个数组，每个位置称为“桶”（bucket）。给定一个键值对，通过哈希函数计算出索引，然后将数据存入对应位置。理想情况下，每个键都有唯一的索引，但现实中冲突不可避免。

哈希函数示例：

对于字符串键，可以使用简单多项式哈希：

立即学习“C++免费学习笔记（深入）”；

size_t hash(const string& key) {
  size_t h = 0;
  for (char c : key) {
    h = h * 31 + c;
  }
  return h % table.size();
}

链地址法（Separate Chaining）

链地址法将每个桶设计成一个链表（或其他容器），所有哈希到同一位置的元素都插入该链表中。这种方法实现简单，且能有效处理大量冲突。

实现要点：

使用vector<list<pair<string, int>>>作为底层存储
插入时，在对应链表中查找是否已存在键，若存在则更新，否则插入新节点
查找和删除操作遍历链表完成

代码片段：

class HashTable {
private:
  vector<list<pair<string, int>>> table;
  size_t size;

public:
  HashTable(size_t n) : size(n), table(n) {}

  void insert(const string& key, int value) {
    size_t index = hash(key);
    auto& chain = table[index];
    for (auto& p : chain) {
      if (p.first == key) {
        p.second = value;
        return;
      }
    }
    chain.push_back({key, value});
  }

  int get(const string& key) {
    size_t index = hash(key);
    const auto& chain = table[index];
    for (const auto& p : chain) {
      if (p.first == key) return p.second;
    }
    throw invalid_argument("Key not found");
  }
};

开放定址法（Open Addressing）

开放定址法在发生冲突时，按某种规则探测下一个空位，直到找到可用位置。常见探测方式包括线性探测、二次探测和双重哈希。

线性探测示例：

当index位置被占用，尝试(index+1)%size, (index+2)%size...
删除操作需要标记“墓碑”，避免查找中断
负载因子过高时需扩容并重新哈希

插入逻辑简写：

while (table[index].state == OCCUPIED) {
  if (table[index].key == key) {
    table[index].value = value;
    return;
  }
  index = (index + 1) % size;
}
table[index] = Entry{key, value, OCCUPIED};

开放定址法节省指针空间，但容易产生聚集现象，影响性能。