这个项目我断断续续折腾了两三天起因其实挺简单项目里要频繁往内存里塞大量中间键值对标准库的 unordered_map 用得好好的但一旦涉及到自定义哈希策略、批量插入后的内存分布、以及想把查找接口封装成一套统一入口时黑盒就不太够用了。于是干脆自己用哈希桶手写了一套容器层再把 UnorderedMap 和 UnorderedSet 两个对外接口分别封装出来既当工具也当一次底层原理复盘。这篇文章就把整个思路、完整实现和我踩过的坑都记录下来给同样想“拆开标准库看看里面到底怎么回事”的同学参考。先交代一下这套项目的适用范围适合已经写过链表和模板类、但对哈希表只有概念性认识的同学也适合准备面试时被问“unordered_map 底层怎么实现”的人。跟着做一遍之后你会很清楚哈希函数、负载因子、迭代器失效这些词在实际代码里是怎么落地的。我尽量用最小可运行的代码讲清楚核心设计而不是贴一大坨别人看不懂的工程源码。1. 项目背景为什么自己手写哈希桶容器1.1 哈希桶方案链表挂在数组上解决冲突最简单粗暴先想清楚一个问题哈希表的“哈希”到底干了什么。简单说就是通过一个哈希函数把任意类型的 key 映射成一个整数再用这个整数对桶数组长度取模得到该元素应该存放的位置。但任意 key 映射到有限的桶位必然会出现两个不同 key 落到同一个桶的情况这就是哈希冲突。处理冲突的主流方案有两种一种是开放定址法冲突了就往下一个空闲位置探测另一种就是本项目用的哈希桶也叫拉链法每个桶位不直接存元素而是挂一条链表冲突的元素全部链到同一条链表上。哈希桶方案的优势非常明显实现简单、删除元素不需要像开放定址法那样考虑“墓碑”标记、对负载因子的容忍度更高。开放定址法在负载因子接近 0.7 之后性能会急剧恶化而哈希桶即使负载因子到 1.0也只是链变长一点不至于不可用。我最终选择哈希桶还有一个工程上的理由扩容迁移非常直观。开放定址法扩容时需要把每个元素重新探测插入逻辑上要小心处理探测序列而哈希桶扩容只需要遍历所有旧链表把每个节点重新算一次桶位然后头插到新桶数组里就行了节点本身不用重新分配迁移成本低很多。1.2 封装目标一个哈希表同时撑起 Map 和 Set如果只是实现一个哈希表那事情就简单多了。真正有意思的是 UnorderedMap 和 UnorderedSet 的差异Map 存的是键值对Set 存的只有键Map 有operator[]、atSet 没有同样一个insertMap 插入的是 pairSet 插入的是元素本身。但如果仔细想Map 的键值对和 Set 的键在哈希表底层眼里其实都是“一个节点里保存的一份数据 T”。底层哈希表根本不需要关心 T 是 pair 还是裸 key它只需要知道两件事第一从 T 里怎么取出 key第二key 之间的比较规则。这就是整个封装设计的核心。所以我的方案是底层写一个泛型HashTableKey, T, KeyOfT, Hash其中Key是键类型T是节点存储的数据类型KeyOfT是一个萃取器负责从 T 中拿出 Key。UnorderedMap 实例化时T std::pairconst Key, MappedUnorderedSet 实例化时T Key。底层哈希表完全不关心上层是 Map 还是 Set它只面向“节点 键提取”这个抽象。这样一套底表就能封装出两个风格统一的对外容器。这里顺带说一句“封装”这个词的歧义。硬件工程师眼里的封装是引脚尺寸前端同学眼里的封装可能是请求函数二次包装而在 C 容器实现这个语境下封装的核心是把“变化的差异”与“不变的结构”分离。Map 和 Set 的差异只在数据形态和暴露接口哈希表的增删查改和迭代器遍历是不变的骨架把骨架写好把差异留给上层适配这就是这套项目的基本设计哲学。1.3 功能范围与验收标准动手之前我给自己定了一个明确的验收标准不做成 STL 那种几百个方法的庞然大物只求核心行为一致支持 insert、find、erase、size、empty、bucket_count、clear支持基于范围的 for 循环也就是要有 begin/end 和可递增的迭代器UnorderedMap 要有operator[]插入不存在的 key 时默认构造映射值支持拷贝构造、赋值运算和析构时完整的内存回收自定义类型可以通过提供哈希函数或 std::hash 特化接入。这六个点覆盖了哈希表最常见的应用场景也基本覆盖了面试官喜欢问的几个技术点负载因子、扩容、迭代器失效、深拷贝。后面所有设计和代码都是围绕这些验收标准展开的。2. 核心机制拆解哈希桶底层的四个关键设计2.1 桶位计算与哈希冲突的处理策略桶位计算我直接采用hash(key) % bucket_count()。这里有个看起来不起眼、实际很影响分布的点桶数组的容量选什么数。如果你用bucket_count 2^n那取模等价于保留 hash 值的低位一旦哈希函数低位的分布不好或者 key 本身有规律冲突就会集中在某几个桶里。所以我选择了质数容量默认初始桶数是 7扩容后的新桶数按2 * old 1的方式增长保证始终是奇数尽量减少 key 的哈希值与桶数之间的公约数。当然这不是最严格的质数序列工程上更讲究的做法是预先准备一份质数表比如 7、17、37、79、163……按需取用但我为了示例代码的简洁性先用奇数增长策略原理是一样的。插入节点到桶内链表时我采用头插法新节点直接node-next _buckets[idx]然后让桶头指向新节点。头插的好处是 O(1) 完成且不用遍历链表尾部找最后一个节点代价是同一桶内的元素顺序和插入顺序相反。这一点对无需容器没有影响因为 unordered 本就保证“无稳定顺序”只保证“相同 key 在同一桶内”。2.2 负载因子阈值与扩容迁移流程负载因子是哈希表里最重要的一个指标定义是元素个数 / 桶数量。它衡量的是每个桶平均挂了多少个节点。负载因子越大链表越长查找时线性扫描的成本越高负载因子越小内存浪费越严重。标准库实现一般把阈值控制在 1.0 附近教学实现里压到 0.7~0.75 更稳妥冲突少、查询快。我的扩容检查写成这样void _maybeRehash() { if (_buckets.empty()) { _buckets.resize(7); return; } if (_size * 10 _buckets.size() * 7) { _rehash(_buckets.size() * 2 1); } }这里我故意没有写浮点除法而是用_size * 10 _buckets.size() * 7来判断“负载是否超过 0.7”。原因很简单整数比较比浮点除法快也避免了浮点误差。对于int类型的 size 和 bucket_count这个写法在数据量到亿级别之前都不会溢出够用。真正的迁移逻辑_rehash是这样的先 new 一个全新的桶数组然后把旧桶数组里每条链表的节点一个个摘下来重新计算桶位并头插到新桶里最后让旧桶数组和新桶数组整体 swap。注意整个过程中节点对象本身没有被删除重建只是改指针方向所以扩容代价主要在于遍历一遍节点而不是重新分配节点内存。2.3 节点内存管理从 new/delete 到深浅拷贝哈希桶里每个节点是new出来的所以内存管理的核心就两个字配对。每个new出来的节点最后一定要有对应的delete否则析构时必然内存泄漏。析构这块我专门写了一个clear()方法遍历每个桶的整条链表逐个节点 delete最后把桶数组清空。这个逻辑看起来简单但很容易写错的地方是在while循环里一边 delete 当前节点一边要继续访问当前节点的next。必须先保存下一个节点指针再删除当前节点顺序反了就是经典的“悬空指针后访问”。拷贝构造也不能偷懒。默认的拷贝构造只会把_buckets这个指针数组原样拷贝一份结果是两个表的所有桶头都指向同一批节点析构时第一批节点被 delete 两次直接 double free。所以我的拷贝构造做的是完整深拷贝先分配同样大小的新桶数组然后遍历原表每条链表逐个节点new一份并串成新链表。赋值运算我用了 copy-and-swap 惯用法按值传参利用拷贝构造生成临时对象再整体 swap这样只要拷贝构造和析构正确赋值就是安全且自带异常保证的。2.4 迭代器为什么要携带桶索引哈希桶的迭代器比链表迭代器麻烦的地方在于从当前桶的链表尾部跳到下一个桶时你不知道下一个非空桶在哪。链表迭代器只需要持有节点指针就行因为next就在节点里哈希桶迭代器还必须能访问底层的桶数组才能从当前桶索引开始往后扫描。所以我的迭代器内部有三个成员当前节点指针_node、指向哈希表的指针_table、当前节点所在桶的索引_index。_index的作用是让operator知道从哪个位置开始往后找非空桶。如果不存这个索引就只能每次从桶数组的头开始扫描整个表才能确定当前节点位置遍历一次变成 O(n^2)完全不可接受。这里还有个设计细节迭代器里的_table我用的是const HashTable*即使非 const 容器的迭代器也要能接受把它当成 const 指针访问。原因是通过 const 指针读取桶数组已经足够迭代器本身不修改哈希表结构它只负责移动和读取节点。这样一套迭代器模板同时给普通迭代器和 const 迭代器复用只需要通过模板参数区分引用类型和指针类型即可。3. 实操实现手写哈希表并封装出两个容器3.1 基础设施HashNode 与键值萃取器 KeyOfT先定义节点结构。节点里保存数据data和指向下一个节点的指针next构造函数区分左值版本和右值版本分别调用拷贝构造和移动构造template typename T struct HashNode { T data; HashNode* next; explicit HashNode(const T val) : data(val), next(nullptr) {} explicit HashNode(T val) : data(std::move(val)), next(nullptr) {} };然后是公开给外层容器使用的两个键值萃取器。Set 场景下 T 就是 Key直接返回 key 本身Map 场景下 T 是std::pairconst Key, Mapped返回kv.firsttemplate typename Key struct KeyOfSet { const Key operator()(const Key key) const { return key; } }; template typename Key, typename Mapped struct KeyOfMap { const Key operator()(const std::pairconst Key, Mapped kv) const { return kv.first; } };这两个萃取器是整个封装方案里最灵巧的一环。底层HashTable的模板参数KeyOfT只要求“能从 T 中拿出 Key”所以它对 Map 和 Set 完全一视同仁。将来如果想封装一个存自定义结构体的哈希集合只需要再写一个萃取器底层完全不用动。3.2 核心插入查找删除的实现细节哈希表主类我命名为HashTable核心成员就四个桶数组_buckets、元素个数_size、哈希函数对象_hash外加类型萃取器。为了防止迭代器访问私有桶数组需要在类内声明迭代器模板为友元template typename K, typename V, typename KOF, typename H, typename R, typename P friend class HTIterator;查找是其他操作的地基我单独抽了一个函数它返回“节点指针 桶索引”的组合这样find和insert拿到结果后都能直接构造迭代器std::pairNode*, size_t _findNode(const Key key) { if (_buckets.empty()) return {nullptr, 0}; size_t idx _bucketIndex(key); for (Node* cur _buckets[idx]; cur; cur cur-next) { if (KeyOfT()(cur-data) key) { return {cur, idx}; } } return {nullptr, 0}; }插入的逻辑是先查找如果 key 已存在直接返回“已有节点 false”不存在才触发扩容检查然后头插新节点。这里我把扩容检查放在查找之后避免“明明 key 已存在却白白扩容一次”的浪费std::pairiterator, bool insert(const T value) { Key key KeyOfT()(value); auto [node, idx] _findNode(key); if (node) { return {iterator(node, this, idx), false}; } _maybeRehash(); size_t i _bucketIndex(key); Node* cur new Node(value); cur-next _buckets[i]; _buckets[i] cur; _size; return {iterator(cur, this, i), true}; }删除则相对直接找到 key 所在桶在链表中定位前驱节点按“是否头节点”分两种情况摘除节点然后 delete 并减 sizebool erase(const Key key) { if (_buckets.empty()) return false; size_t idx _bucketIndex(key); Node* prev nullptr; Node* cur _buckets[idx]; while (cur) { if (KeyOfT()(cur-data) key) { if (prev) { prev-next cur-next; } else { _buckets[idx] cur-next; } delete cur; --_size; return true; } prev cur; cur cur-next; } return false; }这个删除是 O(1) 平均复杂度但要注意删除某个节点后任何指向该节点的迭代器都会失效。这符合标准库行为后面第 4 章我会专门讲这个坑。3.3 迭代器完整代码与遍历逻辑迭代器模板参数一共有六个哈希表的四个模板参数加上引用类型Ref和指针类型Ptr。普通迭代器是HTIterator..., T, T*const 迭代器是HTIterator..., const T, const T*template typename Key, typename T, typename KeyOfT, typename Hash, typename Ref, typename Ptr class HTIterator { using Node HashNodeT; using HTable HashTableKey, T, KeyOfT, Hash; Node* _node; const HTable* _table; size_t _index; public: using iterator_category std::forward_iterator_tag; using value_type T; using reference Ref; using pointer Ptr; using difference_type std::ptrdiff_t; HTIterator(Node* node nullptr, const HTable* table nullptr, size_t index 0) : _node(node), _table(table), _index(index) {} Ref operator*() const { return _node-data; } Ptr operator-() const { return _node-data; } bool operator(const HTIterator other) const { return _node other._node; } bool operator!(const HTIterator other) const { return !(*this other); } HTIterator operator() { if (_node-next) { _node _node-next; return *this; } // 当前桶链表已经走到尾部从下一个桶开始找第一个非空桶 for (size_t i _index 1; i _table-_buckets.size(); i) { if (_table-_buckets[i]) { _node _table-_buckets[i]; _index i; return *this; } } _node nullptr; _index _table-_buckets.size(); return *this; } };这个operator是理解哈希桶迭代器的关键。如果当前节点的next不为空很简单直接往前移动一格如果当前节点正好是这条链表的尾巴就必须借助_table和_index往后扫描桶数组找到下一个非空桶的链表头否则就走到end()。begin()的实现也很直白从 0 号桶开始扫描找一个非空桶的链表头作为起点如果所有桶都是空的直接返回end()iterator begin() { for (size_t i 0; i _buckets.size(); i) { if (_buckets[i]) return iterator(_buckets[i], this, i); } return end(); } iterator end() { return iterator(nullptr, this, _buckets.size()); }这里有个隐藏性质值得强调迭代器只能支持向前移动不支持反向遍历也不支持随意跳转。这是哈希桶天然决定的我把iterator_category标成std::forward_iterator_tag也是在告诉使用者别指望它像 vector 迭代器那样做随机访问。3.4 适配层UnorderedMap 和 UnorderedSet 的区别底层完成后上层封装就是“翻译”工作。UnorderedMap 的核心是把存储类型固定为std::pairconst Key, Mapped并提供operator[]template typename Key, typename Mapped, typename Hash std::hashKey class UnorderedMap { using value_type std::pairconst Key, Mapped; using HTable HashTableKey, value_type, KeyOfMapKey, Mapped, Hash; public: using iterator typename HTable::iterator; using const_iterator typename HTable::const_iterator; iterator begin() { return _table.begin(); } iterator end() { return _table.end(); } const_iterator begin() const { return _table.begin(); } const_iterator end() const { return _table.end(); } std::pairiterator, bool insert(const value_type kv) { return _table.insert(kv); } std::pairiterator, bool insert(value_type kv) { return _table.insert(std::move(kv)); } iterator find(const Key key) { return _table.find(key); } const_iterator find(const Key key) const { return _table.find(key); } bool erase(const Key key) { return _table.erase(key); } Mapped operator[](const Key key) { auto ret insert(value_type(key, Mapped())); return ret.first-second; } size_t size() const { return _table.size(); } bool empty() const { return _table.empty(); } size_t bucket_count() const { return _table.bucket_count(); } private: HTable _table; };operator[]的实现逻辑是“找不到就插入默认值返回引用”。注意这里insert(value_type(key, Mapped()))里的临时对象会触发移动版本避免一次多余的拷贝。这是operator[]和find的最大区别operator[]永远会改变容器即使只是读取它也会插入一个空值这也是 C 面试里经常被问到的细节。UnorderedSet 的封装更简单T Key并且没有operator[]template typename Key, typename Hash std::hashKey class UnorderedSet { using HTable HashTableKey, Key, KeyOfSetKey, Hash; public: using iterator typename HTable::iterator; using const_iterator typename HTable::const_iterator; iterator begin() { return _table.begin(); } iterator end() { return _table.end(); } const_iterator begin() const { return _table.begin(); } const_iterator end() const { return _table.end(); } std::pairiterator, bool insert(const Key key) { return _table.insert(key); } bool erase(const Key key) { return _table.erase(key); } iterator find(const Key key) { return _table.find(key); } const_iterator find(const Key key) const { return _table.find(key); } size_t size() const { return _table.size(); } bool empty() const { return _table.empty(); } private: HTable _table; };到这里“一套底表两个容器”的目标就完成了。后续如果要加containsC20 才进标准、count、at等接口都是在适配层加一行转发的事底表完全不用碰。3.5 自测代码与运行结果写完之后一定要实测否则语法过了也不能证明行为对。我的最小自测程序长这样#include iostream #include string #include utility #include hash_table.h int main() { my_ht::UnorderedMapstd::string, int scores; scores[alice] 90; scores.insert(std::make_pair(bob, 85)); scores[carol] 92; auto it scores.find(alice); if (it ! scores.end()) { std::cout it-first : it-second std::endl; } scores.erase(bob); for (const auto kv : scores) { std::cout kv.first - kv.second std::endl; } my_ht::UnorderedSetint nums; for (int i 0; i 50; i) { nums.insert(i % 30); } for (int v : nums) { std::cout v ; } std::cout std::endl; std::cout map size scores.size() , bucket_count scores.bucket_count() std::endl; return 0; }实测下来Set 里插入 0 到 49 的i % 30最终只会保留 0 到 29 共 30 个不重复元素说明去重逻辑是对的。Map 的erase之后 size 正确减少基于范围的 for 循环也能完整遍历所有桶里的节点迭代器从桶尾跳到下一个非空桶的逻辑工作正常。这一步通过后整个封装项目就算立住了。4. 常见问题与排查技巧这些坑我全部踩过4.1 扩容引起遍历乱序与迭代器失效第一次测试范围遍历时我发现扩容前后打印出来的元素顺序明显变了一开始还以为是自己代码写错了。后来想明白这是哈希表的天然行为扩容会改变桶数组大小同一个 key 的桶位是hash % bucket_count桶数一变桶位就会变遍历顺带也就变了。所以 unordered 容器才叫“无序”它唯一能保证的是相同 key 一定在同一个桶里。更需要注意的是迭代器失效问题。只要发生扩容所有迭代器都失效原因很直接扩容迁移过程中节点还是那些节点但桶数组整体被 swap 了旧迭代器里保存的_table指针指向的已经是被迁移后的新表但它的_index是旧桶数组的索引可能已经越界或者指向了不正确的桶。标准库里这也是明确规定的插入操作只要触发 rehash所有迭代器全部失效不仅仅是“被插入位置附近的迭代器”失效。避免方法也很简单不要在遍历过程中插入大量数据。如果必须边遍历边插入可以先_maybeRehash预留足够的桶或者把要插入的数据先收集到临时容器里遍历完再统一插入。4.2 erase 后继续 fetch 指针导致悬空我曾经在删除节点后拿着旧的迭代器继续执行结果程序直接崩了。排查了一下问题出在我的 delete 放在摘链之后迭代器里_node还指向已经被 delete 的节点这个时候访问_node-next就是读已释放内存行为未定义。标准库的erase会返回“被删除元素的下一个迭代器”方便循环删除。我的简化实现只支持按 key 删除没返回下一个迭代器所以使用时就得多留个心眼删除后不能再用任何指向该节点的迭代器。如果要实现标准库那样的语义可以给迭代器加一个erase的配合接口让删除函数接受迭代器并返回下一个有效迭代器这个我放在第 5 章的扩展方向里。4.3 自定义结构体没有哈希函数编译直接报错用字符串和整数测试没问题但一旦换成自己定义的结构体代码直接编译不过报错一大片模板实例化的内部错误。原因很简单我的哈希表模板默认Hash std::hashKey而标准库的std::hash只为内置类型和常用标准库类型提供了特化自定义结构体没有。解决办法有两个。第一个是给自定义类型特化std::hash比如struct Point { int x; int y; bool operator(const Point other) const { return x other.x y other.y; } }; namespace std { template struct hashPoint { size_t operator()(const Point p) const { return std::hashint()(p.x) ^ (std::hashint()(p.y) 1); } }; }第二个更灵活的办法是给 UnorderedMap/UnorderedSet 传第三个模板参数自定义哈希函数对象。推荐第二种因为不同的业务场景可能需要不同的哈希策略硬绑到 std::hash 特化里不够灵活。4.4 拷贝构造写成浅拷贝析构时重复释放这个坑是我在给哈希表加拷贝构造时踩过的直接后果是 double free。排查方式也很有代表性程序在析构时报malloc(): invalid pointer用地址检查发现两个对象的桶头指针完全一样也就是说拷贝构造只复制了指针数组没有复制节点链表。修复方式就是第 2.3 节说的深拷贝。这里有个调试技巧推荐这种问题用 AddressSanitizer 一跑就能定位编译时加-fsanitizeaddress它会在 double free 的第一现场直接告诉你错误发生在哪个 delete 语句。不要靠肉眼盯着一大段析构代码猜效率太低了。4.5 与 std 容器做一组简单性能对照我拿整数和字符串各做了一轮十万级数据的插入、查找、删除对照趋势大致是整数场景下手写版和 std::unordered_map 在同一个数量级手写版大约慢 30%~60%字符串场景下差距会稍微拉大主要差在节点内存分配上。标准库的 unordered_map 在底层用了一套高效的内存分配策略每次插入新节点的时候不需要走通用new而我这个版本每个节点都是一次独立new字符串本身也在堆上分配碎片化和分配开销叠加起来就明显了。这个问题我不建议一开始就过度优化。先把功能做对性能问题放在最后而且优先考虑加一个节点内存池而不是盲目改哈希函数。内存池的收益在大量小对象场景下立竿见影后面第 5 章会说怎么搞。我把这轮问题整理成一个速查表方便以后遇到类似情况直接对照现象可能原因排查思路扩容后遍历顺序变乱桶数组大小变化导致桶位改变正常现象不要依赖容器顺序扩容后迭代器异常旧迭代器 index 失效插入后重新获取迭代器不要复用旧迭代器erase 后崩溃使用了指向已删除节点的迭代器删除后立即停止使用旧迭代器自定义类型编译不过没有对应的 hash 实现特化 std::hash 或自定义哈希函数对象析构时 double free拷贝构造是浅拷贝深拷贝节点链表或使用 copy-and-swap字符串场景性能差每次 new 节点 字符串分配加节点内存池减少堆分配次数5. 进一步扩展这套封装还能怎么升级5.1 三个升级方向内存池、素数桶表、并发锁当前版本是“用来学习非常合适用来上线还差点意思”的中间状态。如果要继续往工程化方向走我建议按优先级做三件事。第一件事就是加节点内存池。哈希表频繁 insert/erase 会产生大量的小块内存分配这是性能瓶颈的主要来源。一个简单的做法是维护一个空闲链表删除节点时把节点放回空闲池插入节点时优先从池里复用不够了再向系统批量申请。这个优化对整数、指针这类小对象提升很明显。第二件事是用素数表替代当前的奇数扩容策略。虽然2n1能保证奇数但有些 key 的哈希值如果和奇数桶数有规律性公约数分布还是会倾斜。提前准备一份增长比例合适的质数表扩容时直接查表选下一个质数工程上更稳妥。第三件事是考虑并发访问。如果多线程读多写少可以给哈希表加一把shared_mutex读操作加共享锁写操作加独占锁如果并发量再高就要做“锁桶”而不是“锁全表”每个桶一把锁降低锁竞争。这一步涉及线程安全复杂度会上一个台阶但也是真实项目里躲不开的问题。5.2 我最后的工程实践体会做完这套项目我最大的体会是写容器类最重要的不是把每个函数写出来而是把“谁负责持有资源、谁负责释放资源、什么操作会让既有视图失效”这三件事想清楚。哈希桶比数组、链表复杂的地方就在于它同时涉及指针数组、动态节点和迭代器状态任何一个环节管理不周都会变成线上才爆发的内存问题。如果让我给一个学习路线的建议先用链表实现一个简化版 unordered 容器把迭代器、深拷贝、扩容全跑通再对照标准库文档逐个补齐像reserve、load_factor、bucket这样的关键接口最后再考虑性能优化。顺序不要反先把行为做对性能永远排在正确性之后。这套方法不仅适用于哈希桶放在任何自己封装的数据结构上都一样。