C++哈希表之闭散列方法的模拟实现详解

前言

哈希表（hash table）解决的是「按 key 快速查找」的问题。当不同 key 被映射到同一个桶时，就需要冲突处理。常见做法有两类：开链法（separate chaining）在每个桶上挂一条链表；闭散列（open addressing，也叫开放定址）则把所有元素都放在表内，冲突时按某种探测序列寻找下一个空槽。

std::unordered_map的具体实现由标准库厂商决定，标准只规定接口和复杂度，不规定必须用哪种冲突处理。因此「闭散列」是一个很好的练手项目：它能让你真正理解负载因子、探测序列、删除标记这些概念，也能解释为什么删除操作在开放定址表里比插入和查找都麻烦。

常见的误解是「删除就是把槽位置空」。在闭散列里，这样做会切断探测链：一个本来通过线性探测存放在后面的 key，会因为前面的空槽而找不到。正确做法是引入「墓碑（tombstone）」标记，把删除过的槽标记为「曾经占用、现在可复用」，查找时继续前进，插入时可以复用。另一个误解是「负载因子可以到 1.0」，表满之后探测循环必须有终止条件，否则就是死循环。

本文用 C++17 实现一个线性探测的OpenAddressingMap，覆盖插入、查找、删除、扩容和墓碑清理。

一、闭散列与开链法的差异

闭散列的优点是省掉了节点指针，探测往往落在同一缓存行附近；缺点是对负载因子敏感，接近满表时探测长度急剧上升，删除也要额外维护状态。

二、三种槽状态与探测循环

每个槽有三种状态：

• 
  
• 空（empty）：从未被占用。查找遇到它可以断定 key 不存在。
• 
  
• 占用（occupied）：存着一个键值对。
• 
  
• 墓碑（tombstone）：曾经占用、已被删除。查找遇到它不能停，必须继续；插入可以复用它。
• 
  

这三种状态用一个std::optional<std::pair<K, V>>加一个bool tombstone表示：

// 适用于 C++17
struct Slot {
std::optional<std::pair<K, V>> data;
bool tombstone = false;
};

用std::optional而不是「用特殊 key 表示空」，是因为 key 的取值空间是用户决定的，0、空字符串、全零结构体都可能是合法 key，拿它们当哨兵必然冲突。

线性探测的查找逻辑是：从hash(key) % capacity出发，依次检查(h + 1) % capacity、(h + 2) % capacity，直到遇到空槽（不存在）或找到相同 key（存在）。探测次数最多为表容量，因此循环上界必须写probe < capacity，否则表满时会绕圈。

插入时记录遇到的第一个墓碑位置。如果最终没找到相同 key，就优先复用那个墓碑；没有墓碑才用第一个空槽。这样能避免墓碑长期占位。

三、完整实现

// 适用于 C++17
#include <cstddef>
#include <functional>
#include <iostream>
#include <optional>
#include <string>
#include <utility>
#include <vector>

template <typename K, typename V,
typename Hash = std::hash<K>,
typename Eq = std::equal_to<K>>
class OpenAddressingMap {
public:
explicit OpenAddressingMap(std::size_t initial = 8)
: slots_(normalize(initial)), size_(0), tombstones_(0) {}

std::size_t size() const noexcept { return size_; }
std::size_t capacity() const noexcept { return slots_.size(); }

bool insert(K key, V value) {
ensureCapacity();

std::size_t index = 0;
bool occupied = false;
locate(key, index, occupied);

if (occupied) {
slots_[index].data->second = std::move(value);
return false; // key 已存在，更新值
}
if (slots_[index].tombstone) {
--tombstones_; // 复用墓碑
}
slots_[index].data.emplace(std::move(key), std::move(value));
slots_[index].tombstone = false;
++size_;
return true;
}

V* find(const K& key) {
std::size_t index = 0;
bool occupied = false;
if (!locate(key, index, occupied) || !occupied) return nullptr;
return &slots_[index].data->second;
}

const V* find(const K& key) const {
std::size_t index = 0;
bool occupied = false;
if (!locate(key, index, occupied) || !occupied) return nullptr;
return &slots_[index].data->second;
}

bool erase(const K& key) {
std::size_t index = 0;
bool occupied = false;
if (!locate(key, index, occupied) || !occupied) return false;

slots_[index].data.reset();
slots_[index].tombstone = true;
--size_;
++tombstones_;
return true;
}

private:
struct Slot {
std::optional<std::pair<K, V>> data;
bool tombstone = false;
};

static std::size_t normalize(std::size_t n) {
std::size_t cap = 8;
while (cap < n) cap <<= 1;
return cap;
}

// 返回 false 表示整张表没有任何空槽或墓碑（正常不会发生）
bool locate(const K& key, std::size_t& index, bool& occupied) const {
const std::size_t n = slots_.size();
const std::size_t start = hash_(key) % n;
std::size_t firstTombstone = n; // n 表示「没有墓碑」

for (std::size_t probe = 0; probe < n; ++probe) {
const std::size_t idx = (start + probe) % n;
const Slot& slot = slots_[idx];

if (slot.data.has_value()) {
if (eq_(slot.data->first, key)) {
index = idx;
occupied = true;
return true;
}
} else if (slot.tombstone) {
if (firstTombstone == n) firstTombstone = idx;
} else {
index = (firstTombstone != n) ? firstTombstone : idx;
occupied = false;
return true;
}
}

if (firstTombstone != n) {
index = firstTombstone;
occupied = false;
return true;
}
index = 0;
occupied = false;
return false;
}

void ensureCapacity() {
// 保持 (已用 + 墓碑) 不超过容量的 3/4
if ((size_ + tombstones_ + 1) * 4 < slots_.size() * 3) return;

std::size_t target = slots_.size();
if ((size_ + 1) * 4 >= target * 3) {
target *= 2; // 活跃元素太多，扩容
}
rehash(target); // 否则原地清理墓碑
}

void rehash(std::size_t newCapacity) {
std::vector<Slot> old = std::move(slots_);
slots_.assign(normalize(newCapacity), Slot{});
size_ = 0;
tombstones_ = 0;

for (Slot& slot : old) {
if (!slot.data.has_value()) continue;
std::size_t index = 0;
bool occupied = false;
locate(slot.data->first, index, occupied);
slots_[index].data = std::move(slot.data);
slots_[index].tombstone = false;
++size_;
}
}

std::vector<Slot> slots_;
std::size_t size_;
std::size_t tombstones_;
Hash hash_{};
Eq eq_{};
};

int main() {
OpenAddressingMap<std::string, int> map;
map.insert("apple", 1);
map.insert("banana", 2);
map.insert("cherry", 3);

if (int* v = map.find("banana")) {
std::cout << "banana=" << *v << '\n';
}

map.erase("banana");
std::cout << "after erase: " << (map.find("banana") ? "found" : "missing") << '\n';
std::cout << "size=" << map.size() << " capacity=" << map.capacity() << '\n';
return 0;
}

逐段核对几个关键点。insert先调用ensureCapacity，保证随后一定能找到空槽或墓碑；如果key已存在，locate把occupied置真并返回其下标，此时只更新值，不增加size_。复用墓碑时tombstones_减一，因为那个槽不再是墓碑。rehash先把旧数组整体移走，再把size_和tombstones_清零，然后对每个有效元素重新locate插入；由于新表容量更大（或至少相同且已清空），不会出现找不到位置的情况。

locate是const成员函数，却通过输出参数返回下标，这是为了同时服务查找、插入和删除。它不修改slots_，只读状态，因此不会破坏 const 正确性。

四、负载因子、墓碑与复杂度

负载因子（load factor）通常定义为「已占用的槽数 / 容量」。闭散列里墓碑也算「占用探测序列的槽」，所以真正影响探测长度的是(size_ + tombstones_) / capacity。上面的实现用 3/4 作为阈值：达到阈值时，如果活跃元素本身也超过 3/4，就扩容一倍；否则说明墓碑太多，原地rehash到同样大小即可清理。

这个区分很重要。若只看size_决定是否扩容，大量删除后表里全是墓碑，查找仍要走过很长的探测链，性能退化却不会触发扩容。若一见墓碑就扩容，又浪费内存。按「活跃元素」和「墓碑」分别判断，是折中的做法。

复杂度方面，在负载因子有上界、哈希分布均匀的假设下，线性探测的期望查找、插入、删除都是O(1)；最坏情况所有 key 落到同一探测序列，退化为O(n)。标准对std::unordered_map的平均复杂度要求也是常数，但同样不保证最坏情况。删除后留下的墓碑会让探测链变长，这是闭散列固有的代价。

常见坑点

1. 删除时直接置空

❌slots_[idx].data.reset();不设墓碑，后续同探测链的 key 查不到。 ✅ 删除后置tombstone = true，查找遇到墓碑继续探测。

2. 查找遇到墓碑就停

❌else if (!slot.data) return not_found;把墓碑当成空槽。 ✅ 只有「非占用且非墓碑」才是真正的空槽，才能终止查找。

3. 探测循环没有上界

❌for (std::size_t i = 0; ; ++i)，表满或全墓碑时死循环。 ✅ 探测次数限制为capacity，并在找不到空槽时返回失败。

4. 负载因子取到 1.0

❌ 等到size_ == capacity才扩容，插入时已无空槽。 ✅ 在 0.7 到 0.75 附近扩容，给探测留出余量。

5. 只按size_判断扩容

❌ 大量删除后墓碑堆积，查找变慢却不触发整理。 ✅ 同时统计tombstones_，必要时原地rehash。

6. 用特殊 key 表示空槽

❌ 用key == 0或空字符串表示「未使用」，与合法 key 冲突。 ✅ 用std::optional或独立的状态枚举。

7. 扩容后继续使用旧指针

❌int* p = map.find(k);之后插入触发rehash，仍解引用p。 ✅ 把rehash视为使所有元素地址失效，重新find获取指针。

8. 自定义哈希返回负数

❌int h = customHash(key); std::size_t idx = h % n;，负数取模得到负下标。 ✅ 哈希函数返回std::size_t，或在取模前转换为无符号类型。

总结

闭散列的实现难点不在哈希函数，而在「删除」和「扩容」这两处状态维护。把空槽、墓碑、占用三种状态分清，把探测循环的上界写死，再让负载因子留出余量，线性探测就能稳定工作。理解这套机制之后，再看std::unordered_map的rehash、迭代器失效规则，会清楚得多。