c++怎么进行哈希表碰撞处理_c++ 链地址法与开放定址法实现【详解】

哈希表碰撞时，std::unordered_map 默认用链地址法，但你无法直接控制底层实现

标准库的 std::unordered_map 和 std::unordered_set 确实基于哈希，且主流实现（如 libstdc++、libc++）内部采用链地址法（separate chaining），每个桶（bucket）挂一个链表或小动态数组来存冲突元素。但这是封装好的——你调用 insert() 或 find() 时完全感知不到碰撞逻辑，也**不能替换为开放定址法**。想自定义碰撞处理？必须手写容器。

手写链地址法：用 std::vector + std::list 实现简易哈希表

核心是维护一个桶数组，每个桶存一个链表；哈希函数决定下标，冲突时往对应链表尾部插入。注意三点：

• std::hash 可复用标准哈希，但需特化自定义类型（否则编译失败）
• 桶数量应为质数，减少聚集；扩容时需重新哈希全部元素（rehash）
• 查找/删除需遍历链表，最坏 O(n)，但平均 O(1) —— 前提是负载因子（size() / bucket_count()）控制在 0.75 以下

template 
class SimpleHashMap {
    std::vector>> buckets;
    size_t num_elements = 0;
    static size_t next_prime(size_t n) { /* 返回大于 n 的最小质数 */ }
public:
SimpleHashMap(size_t init_buckets = 11) : buckets(init_buckets) {}
void insert(const K& key, const V& val) {
    size_t idx = std::hashzuojiankuohaophpcnKyoujiankuohaophpcn{}(key) % buckets.size();
    for (auto& p : buckets[idx]) {
        if (p.first == key) { p.second = val; return; }
    }
    buckets[idx].emplace_back(key, val);
    ++num_elements;
    if (num_elements youjiankuohaophpcn buckets.size() * 0.75) rehash();
}
private:
void rehash() {
auto old = std::move(buckets);
size_t new_size = next_prime(buckets.size() * 2);
buckets.assign(new_size, std::list<:pair v>>{});
for (const auto& list : old)
for (const auto& p : list)
insert(p.first, p.second);
}
};
开放定址法难点在探测序列与删除标记，线性探测最易写但容易聚集
所有元素存于单一数组，碰撞时按固定规则（如线性、二次、双重哈希）找下一个空位。关键问题不是“怎么找”，而是：

删除不能真删（否则断开探测链），得用特殊标记（如 EMPTY、DELETED）区分“从未用过”和“曾用过已删”
线性探测（(hash + i) % capacity）实现简单，但连续冲突会形成“聚集”，性能骤降
二次探测（(hash + i*i) % capacity）缓解聚集，但可能找不到空位（即使有），需容量为质数且负载因子严格 
双重哈希（(hash1 + i * hash2) % capacity）效果最好，但 hash2 必须与容量互质，实现稍复杂
template 
class OpenAddressingMap {
    struct Entry { K key; V val; enum { EMPTY, VALID, DELETED } state; };
    std::vector data;
    size_t num_valid = 0;
size_t probe(size_t hash, size_t i) const {
    return (hash + i * i) % data.size(); // 二次探测
}
public:
V& operator[](const K& key) {
size_t h = std::hash{}(key);
for (size_t i = 0; i 
选链地址法还是开放定址法？看场景，别只看理论平均复杂度
链地址法内存开销略大（指针 + 动态分配），但实现鲁棒、支持任意负载因子、删除即释放；开放定址法缓存友好（数据连续）、无指针开销，但扩容成本高、删除麻烦、对哈希质量更敏感。实际选型时：

							

								
								

									堆友
									
Alibaba Design打造的设计师全成长周期服务平台，旨在成为设计师的好朋友
								
								下载 
							
						
立即学习“C++免费学习笔记（深入）”；

元素小（如 int 键值对）、读多写少、内存敏感 → 开放定址法更合适
键类型复杂、需频繁增删、不希望手动管理探测逻辑 → 链地址法更省心
用 std::unordered_map 就别纠结——它已针对通用场景优化过桶结构（如 libc++ 用小数组代替链表，减少分配）
真正要极致性能？别自己写，用 absl::flat_hash_map（开放定址+混合策略）或 tsl::robin_map


手写开放定址法时，DELETED 标记状态和探测终止条件最容易漏判，一错就导致查不到或无限循环。