哈希桶这个说法老读者应该不陌生——但大部分人和它初次见面是在课本的插图上一个个桶每个桶里挂着几个元素哈希函数把键均匀撒进去。真正让我决定自己动手写一份桶式哈希的是用了两三年std::unordered_map之后的那点好奇心它凭什么做到平均 O(1) 查找为什么标准库的迭代器在插入后大概率还健在以及最常见的疑问——unordered_map 和 unordered_set 明明一个存键值对、一个只存键底层能不能共用同一套哈希桶逻辑。这篇文章就是我基于纯 C 模板实现的一份完整封装记录核心产出物是UnorderedMap和UnorderedSet两个容器类底层共用一份HashTable骨架。写出来之后我才发现真正的难点根本不在哈希函数上而在迭代器设计和接口兼容上。1. 为什么选桶式哈希冲突方案选型背后的取舍哈希表绕不开一个话题冲突处理。就算哈希函数写得再好只要键空间远大于存储规模鸽子笼原理就会逼着多个键落到同一个位置。市面上主流的冲突策略无非两类——开放定址法和链地址法而哈希桶属于链地址法的经典形态底层是一个固定大小的桶数组每个桶指向一条链表冲突的元素在同一桶里串起来。我当时先画了个对比表把两个方案的关键属性摆在一起看维度开放定址法链地址法哈希桶删除操作麻烦需要墓碑标记链表常规删除即可满载容忍度负载因子通常得压在 0.5~0.7 以下默认可到 1.0 甚至更高元素存储位置在桶数组内部连续存储每个元素独立节点散落堆上迭代器/引用稳定性搬迁时全部失效只要不删除当前元素引用稳定为什么 C 标准库的 unordered 系列最终选择了链地址我查过标准里的一个细节无序容器的insert和erase有明确的迭代器失效规则——erase只会让指向被删除元素的迭代器失效insert只要不触发扩容就不会让任何已有元素的引用失效。开放定址法天然做不到这一点因为元素存在桶数组里扩容时全部元素都得搬新家引用全断。链地址法就轻松了每个元素就是堆上一个独立节点桶数组只存入口地址扩容只是把链表节点重新挂到新桶元素本体纹丝不动。所以从标准库的角度讲链地址法不是性能最优而是语义约束下的必然选择。这也给了我一个明确信号我自己封装时如果希望接口行为尽量贴近 STL就必须用节点式存储。换句话来说标题里的哈希桶不只是一个实现细节它直接决定了后续迭代器、引用稳定性、扩容逻辑的整套设计。当然开放定址法在现代工程里也有它的高光时刻——absl::flat_hash_map这类内存紧凑型容器就是开放定址的产物性能在某些场景下比标准 unordered 还猛。但那是另一个故事了。作为学习项目的实现方案桶式哈希有着最清晰的结构逻辑和最低的落地成本我最后拍板用它还有一个很实际的原因调试过程中一眼就能看明白哪个键挂在哪个桶排查问题的体验比开放定址友好得多。2. 底层结构设计桶数组、节点和内存的那些细节结构定下来之后第一步就是把HashTable的骨架写对。我的做法是让底层哈希表不要关心存的是单个键还是键值对它只需要知道三件事怎么从存储对象里取出键、怎么计算哈希值、怎么比较两个键相等。template typename Key, typename Value, typename KeyOfValue, typename Hash std::hashKey, typename KeyEqual std::equal_toKey class HashTable { public: using size_type std::size_t; private: using Bucket std::listValue; using BucketIt typename Bucket::iterator; using Buckets std::vectorBucket; Buckets _buckets; size_type _elementCount 0; double _maxLoadFactor 1.0; };_buckets是一个std::vectorstd::listValue。这里我特意选了std::list而不是手写单链表节点原因很简单std::list的节点独立性天然保证元素引用稳定而且它内置的splice操作可以在 O(1) 时间内把一个节点从一条链表搬到另一条链表这在扩容时是杀手锏。什么情况下你会想换成裸链表如果你对内存占用有极致的强迫症一个std::list节点通常带两个指针和一个大小字段配合桶数组里的空 list 对象内存确实比一个next指针的单链表夸张。我当时也手写过一版裸节点链表结果很快被内存释放的问题拖住了调试进度——插入、删除、异常路径都要自己记挂着节点的生命周期。后来换回std::list一行splice解决迁移代码干净一个量级。我的结论是学习项目优先保证逻辑清晰性能差距后面再谈。桶数组的容量我刻意设计成 2 的幂。这样计算桶索引时可以用hash (bucketCount - 1)代替hash % bucketCount省掉一次除法。现代 CPU 对取模有硬件加速这个省下来的时间在 1e6 规模下其实不明显但它让代码至少看起来是懂行的。真正要注意的是当容量是 2 的幂时哈希值的高位变化会被丢弃只取低位算索引。如果哈希函数质量差低位分布差就会引发集中冲突。为了对冲这个风险我默认的哈希函数必须是扩散良好的这点会在后面专门展开。节点存储类型有个隐蔽的坑提前说出来省得你踩对于UnorderedMap底层存储的Value是std::pairconst Key, V。第一个模板参数带const这是为了让外部无法通过迭代器修改键。但const成员也给构造带来了麻烦你不能给pairconst K, V直接赋值只能构造。这意味着底层在插入新节点时必须用构造而不是先默认构造再赋值的方式创建节点。std::list::push_back好就好在它是原地构造传一个Value对象进去直接被完美转发到节点内存天然适合pairconst K, V这种不可赋值类型。初始化时_buckets默认构造出一堆空 list。插入第一个元素前我会顺手调用一次rehash(8)把桶数量预设出来免得首次插入就扩容。这个细节不写出来不影响功能但对性能影响挺实在——第一次插入就触发 rehash等于白付一次搬迁成本。3. 迭代器哈希容器封装里最烧脑的一块如果说哈希桶是整个项目的地基那迭代器就是地基上的承重墙。我封装过程里百分之七十的功夫都花在这上面所以单独拿出来讲。先看迭代器需要维护什么状态。它至少得知道两件事当前指向的是哪个桶里的哪个节点以及哈希表本体在哪里为了自增时找到下一个桶。我设计的迭代器是这样的template typename Table class HTIterator { using Value typename Table::value_type; using BucketIt typename Table::BucketIt; public: HTIterator(Table* table, std::size_t bucketIndex, BucketIt cur) : _table(table), _bucketIndex(bucketIndex), _cur(cur) {} Value operator*() const { return *_cur; } Value* operator-() const { return std::addressof(*_cur); } HTIterator operator() { _cur; if (_cur _table-_buckets[_bucketIndex].end()) moveToNextNonEmptyBucket(); return *this; } private: void moveToNextNonEmptyBucket() { _bucketIndex; while (_bucketIndex _table-_buckets.size() _table-_buckets[_bucketIndex].empty()) { _bucketIndex; } if (_bucketIndex _table-_buckets.size()) _cur _table-_buckets[_bucketIndex].begin(); else _cur typename Table::BucketIt{}; // 哨兵指向末尾 } Table* _table; std::size_t _bucketIndex; BucketIt _cur; friend class HashTable...; };注意operator的逻辑先把当前桶里的迭代器往后挪一格如果挪到了当前桶的end()就要跳到下一个非空桶。这里有一个微妙点——如果当前桶里有很多个元素那么一轮自增只走一个元素非常快如果刚跳到的新桶是空的就需要连续跳过多个空桶。所以哈希表迭代器的单次自增在最坏情况下是 O(桶数)平均下来仍是 O(1)。这也是桶式哈希迭代器的一个典型特征你没法保证每次都是常数时间。我有一次在这里写出过一个经典的 bug跳桶时忘了处理尾部哨兵导致遍历到大桶数组末尾后_bucketIndex越界访问。调试的时候表现得很诡异——不是每次都崩而是只有遍历完所有元素之后下一次才崩。后来我养成了一个习惯在这个moveToNextNonEmptyBucket里先把越界检查写满再写跳桶逻辑顺序绝对不能反。再说const_iterator。我的做法是用模板参数抽象迭代器的可变性——把iterator和const_iterator归结为同一个模板的不同实例template bool IsConst class HTIterator { using BucketIt typename std::conditionalIsConst, typename Table::BucketConstIt, typename Table::BucketIt::type; ... };这样iterator可以隐式转换成const_iterator只要提供对应的转换构造函数HTIteratortrue(const HTIteratorfalse)。为了避免const_iterator内部持有Table*却能修改表结构的问题我在operator里已经保证了只读_table-_buckets不修改任何成员——也就是说const_iterator读到的表结构实际上来自一个const HashTable*。这一步的正确性是在编译层面用const限定符保证的。还有个容易忽略的细节begin()必须跳过所有空桶直接指向第一个非空桶的首元素如果全是空桶就返回end()。写的时候我建议把找第一个非空桶单独抽成一个私有函数begin()和moveToNextNonEmptyBucket都能复用它。别嫌麻烦这个函数你会在调试迭代器的时候反复看。4. 一个底层两个容器类型萃取与接口复用底层哈希表准备好了接下来才是标题里的重头戏怎么用同一份HashTable封装出unordered_map和unordered_set两个长得不一样的容器。核心思路是模板参数注入差异而不是继承。HashTable的第三个模板参数KeyOfValue是一个函数对象类型它的职责很简单从存储对象里提取出键。对unordered_set来说存储对象本身就是键提取就是恒等函数对unordered_map来说存储对象是pairconst K, V提取就是取.first。template typename K, typename V, typename Hash std::hashK, typename KeyEqual std::equal_toK class UnorderedMap { private: using Value std::pairconst K, V; struct Select1st { const K operator()(const Value kv) const { return kv.first; } }; HashTableK, Value, Select1st, Hash, KeyEqual _table; public: using key_type K; using mapped_type V; using value_type Value; using iterator typename decltype(_table)::iterator; // ... 接口转发 };UnorderedSet那边更简单template typename K, typename Hash std::hashK, typename KeyEqual std::equal_toK class UnorderedSet { private: struct Identity { const K operator()(const K k) const { return k; } }; HashTableK, K, Identity, Hash, KeyEqual _table; // ... };这套Select1st/Identity的命名是从 SGI STL 里继承过来的老设计。它让我意识到所谓封装在这个语境下更多是编译期的多态——所有差异在模板实例化那一刻被编译器展开运行期零开销。对比封装继承多态里那种通过基类虚函数实现的运行时多态这里用的是完全不同的思路接口相同但行为在模板参数层面分岔。接口转发阶段有几个坑。第一个是insert。unordered_map对外接口的value_type是pairconst K, V但用户写m.insert({1, 2})传进来的是一个pairint, int两者的类型不同。底层的HashTable::insert接收的是Value即pairconst K, V所以顶层需要一个转换构造。好消息是std::pair提供了从另一个 pair 转换构造的模板构造函数pairconst K, V可以从pairK, V构造所以直接转发就能过编译。第二个坑是operator[]。它和insert的语义不同如果键存在返回已有值的引用如果不存在插入一个默认值再返回引用。你可能会想先find再决定插入但这会触发两次查找。更高效的做法是借助底层insert的返回值——它返回一个pairiterator, bool迭代器总是指向目标元素V operator[](const K key) { auto result _table.insert(Value{key, V{}}); return result.first-second; }注意一个问题如果插入触发了扩容扩容前的迭代器会失效但insert返回的迭代器是新扩容后重新定位过的所以return result.first-second是安全的。我最初为了省事先find找不到再insert结果在自定义类型上因为要求 V 可默认构造反而绕了远路。直接用insert的返回值的方案逻辑更短还能顺便利用底层对重复键的检测。第三个坑是erase的返回值。C11 之前erase(iterator)返回 voidC11 之后标准要求 unordered 容器的erase返回被删除元素的下一个迭代器。我们的底层用std::list实现erase天然返回下一个迭代器所以转发时只要把底层返回值原样透传即可。但如果你用的是手写单链表这一步就得自己维护下一个指针——又费神又容易写错。这也是我推荐std::list做桶的又一个理由。5. 哈希函数、相等比较与自定义类型支持封装的顶层接口里我把Hash和KeyEqual作为默认模板参数暴露给用户默认值分别是std::hashK和std::equal_toK。这意味着如果你只是往UnorderedSetint里塞整数什么都不用改。但实际的工程里你大概率会遇到需要放进 unordered 容器的自定义类型。这里涉及一个很容易被误解的点为什么需要同时提供哈希函数和相等比较哈希函数的职责是把键映射到桶索引相等比较的职责是判断两个落在同一桶里的键是否真的相同。两者缺一不可——哈希表靠必有一致这条约定工作只要两个键相等它们的哈希值必然相同所以它们必然落到同一个桶里。std::equal_to保证相等比较std::hash配合桶索引保证相同的键进相同的桶。如果这个约定被破坏表里就会藏着永远不会被找到的元素。一个典型的反面例子你给某个自定义类型写了哈希函数却忘了重载operator结果equal_to退化成最朴素的按内存比较——两个逻辑上相等但字段顺序不同的对象进不了同一个槽查找直接失败。我在开发时遇到过这种问题当时查了很久才发现是operator没写对。先看自定义类型的哈希怎么写。假设有一个二维点结构struct Point2D { int x; int y; bool operator(const Point2D other) const { return x other.x y other.y; } }; struct Point2DHash { std::size_t operator()(const Point2D p) const { std::size_t seed 0; seed ^ std::hashint{}(p.x) 0x9e3779b9 (seed 6) (seed 2); seed ^ std::hashint{}(p.y) 0x9e3779b9 (seed 6) (seed 2); return seed; } };那个神秘常数0x9e3779b9是黄金比例在 32 位空间里的近似值用在位混淆上能有效打散相近输入的哈希值。这个seed ^ h golden_ratio (seed6) (seed2)的组合方式就是赫赫有名的hash_combine类算法它比简单地把两个子哈希异或靠谱得多。简单异或的问题在于hash(a,b)和hash(b,a)得到一样的结果而且如果多个子字段哈希值相同异或会把它们抵消。hash_combine通过每次累加时做移位和加法让 seed 充分吸收每个字段的贡献。还有个小提示自定义类型的operator尽量写成 member function 或 hidden friend。只要能保证同类型对象间可以比较即可。哈希容器内部用的是KeyEqual()(a, b)这种函数对象调用形式所以自定义的仿函数只要实现了operator()一样能用。哈希函数质量这块还有一个容易被忽视的问题当你用 2 的幂作为桶数量时桶索引只取哈希值的低位。如果自定义哈希返回的 size_t 天然集中在低 4 位有差异、高位全是零那不管桶数量多大所有键都挤在十几个桶里。所以我在默认设计里要求哈希函数至少做到低位扩散。对于标准库的std::hashint它通常就是返回整数本身质量本来就不算好但它配合 STL 那些质数桶容量能缓解这个问题——而我们用的 2 的幂容量就吃这个亏。好在现在的编译器和库版本里std::hash实现普遍做了位混洗实测下来随机 int 的分布是够用的。如果你的键是自己设计的高低位差异明显的整数建议加一步hash ^ hash 16之类的位混淆。6. 扩容、删除与迭代器失效最容易翻车的地方哈希桶容器里insert和erase在特定条件下会改变桶的结构处理不好就用出内存问题或语义错误。这一节把最容易翻车的三件事讲清楚。6.1 触发条件与扩容过程我实现的触发阈值是_elementCount / _buckets.size() _maxLoadFactor默认_maxLoadFactor 1.0。每次insert前检查一次如果达到或超过阈值就扩容。容量增长策略是翻倍——从 8 到 16 到 32保证始终是 2 的幂。扩容过程的核心操作是splice。因为std::list的节点迁移是 O(1)而且不会触发元素拷贝和构造整个过程都不会抛异常。我先把这一步写成伪代码再贴真实现void rehash(size_type newBucketCount) { Buckets newBuckets(newBucketCount); for (auto bucket : _buckets) { for (auto it bucket.begin(); it ! bucket.end(); ) { auto next std::next(it); std::size_t newIndex hashOf(*it) (newBucketCount - 1); newBuckets[newIndex].splice(newBuckets[newIndex].end(), bucket, it); it next; } } _buckets.swap(newBuckets); }newBuckets构造时一次性分配好全部空桶这一步可能抛异常内存不够。但一旦进入节点迁移阶段全程不分配内存、不拷贝元素只是调整链表指针所以不会抛异常。这意味着扩容过程中途数据损坏这种事被结构性地杜绝了——新桶数组要么分配成功要么整个操作直接抛出异常旧表纹丝不动。这个设计天然提供了很强的异常安全保证。有朋友问过为什么不用构造一个全新的 HashTable 再 swap这种更简单的方案省事是省事但它要把所有元素重新拷贝一遍对非平凡类型是巨大的浪费。splice方案本质上是把元素所有权从一个 list 转移到另一个 list一毛钱拷贝都没有。这个差距在元素是 string 或者自定义大对象时非常明显。6.2 迭代器失效的语义边界标准库对 unordered 容器的规定是rehash会让所有迭代器失效但元素的引用和指针不受影响。我们抄这个语义做扩容后你手里旧的迭代器不能再但如果你提前保存了某个元素的Value*它依然能访问——因为元素节点没动只是换了个桶挂。删除则更敏感。erase(iterator)只让被删元素的迭代器失效其余全部健在。由于底层是std::list这个语义是自动满足的。我曾经在这上面踩过一个坑遍历容器时想边遍历边删除用for (auto it c.begin(); it ! c.end(); ) { if (cond) it c.erase(it); else it; }这个写法属于标准做法。但如果我偷懒写成c.erase(it);虽然合法但可读性差一些在代码审查里容易被质疑。建议统一用前者。6.3 调试用的 sanity check哈希容器做出来之后我投入了大量时间在 bug 上。后来写了一个debugSanityCheck()函数在每次插入、删除、扩容后调用它验证三条不变式_elementCount等于所有桶的元素数量之和每个元素通过KeyOfValue取出的键重新哈希后确实落在它当前的桶里满足相等条件的两个不同对象不会同时出现在同一个桶里如果出现说明哈希约定被破坏这个检查函数在 release 模式里会被宏关掉在 debug 模式下帮了我大忙。有一次自定义类型的operator写错了导致重复元素被当成不同键存进同一个桶就是靠第三条不变式揪出来的。写容器类时埋一个这样的内部自检钩子实战价值极高。7. 实测对比自研容器与 std::unordered_map 的差距代码写完不能只停留在能跑我用一个简单的基准测试评估了一下自家容器和标准库的差距。测试环境是 GCC 11 配合-O2数据集是 1e6 个随机int分别测插入、查找、遍历三个场景。先说结论自研UnorderedMap的时间复杂度量级和std::unordered_map完全一致绝对耗时整体慢 10%~30%差距主要来自几个方面。第一是哈希函数。std::unordered_map底层在哈希值上做了额外的位混洗而我们直接用std::hashint的原始结果配合低位掩码。随机 int 的场景下问题不大但如果数据是连续的整数低位分布其实还行所以差距有限。真要说大差距场景还是得回到分布差的哈希上去。第二是桶结构。我们用std::list做桶每个节点有两个指针的开销遍历时缓存局部性差——一条链表上的节点在堆上随机散布CPU 缓存命中率自然不如 STL 里那种更紧凑的节点布局。这也是链地址法普遍比开放定址法慢的内存层面的原因。第三是operator[]的插入路径。自研版在find失败后走insert而insert内部还要再做一次查找来确认是否重复。虽然可以优化成一次查找同时完成定位与插入判断但实现复杂度就上去了。目前这个版本能和标准库保持在同一个数量级已经达到我封装这个项目时的预期。内存占用方面我们每个元素多出的开销是std::list节点的额外指针在int这种小对象上尤其明显。标准库的 unordered 实现也保留了类似结构只是节点组织方式更紧凑。这里提一个可能的方向如果你对内存和数据局部性有硬性要求可以考虑换用开放定址法的 flat hash map 系列——这是后话了。最后说一个我在实测中发现的有趣现象用同样的插入顺序自研容器和std::unordered_map的遍历输出顺序完全不同。哈希表的遍历顺序本来就是由哈希值对桶数取模决定的和插入顺序无关。所以写业务代码时永远不要依赖 unordered 容器的遍历顺序这是用哈希容器的人最容易忽略的一条铁律。回看整个封装过程我最大的体会是哈希桶项目真正难的地方不是把哈希函数写对而是把迭代器边界和容器接口语义理顺。当一个底层HashTable同时喂给UnorderedMap和UnorderedSet时你会被迫把容器通用逻辑和键值存储差异拆得干干净净这种抽象能力是刷多少算法题都换不来的。如果你也想动手写一遍我的建议是先把迭代器的自增逻辑在纸上画出三个桶的状态图标清楚end()的位置再动手写代码——这一步做好了后面整个项目会顺畅得多。
纯C++实现哈希桶：从unordered_map到unordered_set的封装实践
哈希桶这个说法老读者应该不陌生——但大部分人和它初次见面是在课本的插图上一个个桶每个桶里挂着几个元素哈希函数把键均匀撒进去。真正让我决定自己动手写一份桶式哈希的是用了两三年std::unordered_map之后的那点好奇心它凭什么做到平均 O(1) 查找为什么标准库的迭代器在插入后大概率还健在以及最常见的疑问——unordered_map 和 unordered_set 明明一个存键值对、一个只存键底层能不能共用同一套哈希桶逻辑。这篇文章就是我基于纯 C 模板实现的一份完整封装记录核心产出物是UnorderedMap和UnorderedSet两个容器类底层共用一份HashTable骨架。写出来之后我才发现真正的难点根本不在哈希函数上而在迭代器设计和接口兼容上。1. 为什么选桶式哈希冲突方案选型背后的取舍哈希表绕不开一个话题冲突处理。就算哈希函数写得再好只要键空间远大于存储规模鸽子笼原理就会逼着多个键落到同一个位置。市面上主流的冲突策略无非两类——开放定址法和链地址法而哈希桶属于链地址法的经典形态底层是一个固定大小的桶数组每个桶指向一条链表冲突的元素在同一桶里串起来。我当时先画了个对比表把两个方案的关键属性摆在一起看维度开放定址法链地址法哈希桶删除操作麻烦需要墓碑标记链表常规删除即可满载容忍度负载因子通常得压在 0.5~0.7 以下默认可到 1.0 甚至更高元素存储位置在桶数组内部连续存储每个元素独立节点散落堆上迭代器/引用稳定性搬迁时全部失效只要不删除当前元素引用稳定为什么 C 标准库的 unordered 系列最终选择了链地址我查过标准里的一个细节无序容器的insert和erase有明确的迭代器失效规则——erase只会让指向被删除元素的迭代器失效insert只要不触发扩容就不会让任何已有元素的引用失效。开放定址法天然做不到这一点因为元素存在桶数组里扩容时全部元素都得搬新家引用全断。链地址法就轻松了每个元素就是堆上一个独立节点桶数组只存入口地址扩容只是把链表节点重新挂到新桶元素本体纹丝不动。所以从标准库的角度讲链地址法不是性能最优而是语义约束下的必然选择。这也给了我一个明确信号我自己封装时如果希望接口行为尽量贴近 STL就必须用节点式存储。换句话来说标题里的哈希桶不只是一个实现细节它直接决定了后续迭代器、引用稳定性、扩容逻辑的整套设计。当然开放定址法在现代工程里也有它的高光时刻——absl::flat_hash_map这类内存紧凑型容器就是开放定址的产物性能在某些场景下比标准 unordered 还猛。但那是另一个故事了。作为学习项目的实现方案桶式哈希有着最清晰的结构逻辑和最低的落地成本我最后拍板用它还有一个很实际的原因调试过程中一眼就能看明白哪个键挂在哪个桶排查问题的体验比开放定址友好得多。2. 底层结构设计桶数组、节点和内存的那些细节结构定下来之后第一步就是把HashTable的骨架写对。我的做法是让底层哈希表不要关心存的是单个键还是键值对它只需要知道三件事怎么从存储对象里取出键、怎么计算哈希值、怎么比较两个键相等。template typename Key, typename Value, typename KeyOfValue, typename Hash std::hashKey, typename KeyEqual std::equal_toKey class HashTable { public: using size_type std::size_t; private: using Bucket std::listValue; using BucketIt typename Bucket::iterator; using Buckets std::vectorBucket; Buckets _buckets; size_type _elementCount 0; double _maxLoadFactor 1.0; };_buckets是一个std::vectorstd::listValue。这里我特意选了std::list而不是手写单链表节点原因很简单std::list的节点独立性天然保证元素引用稳定而且它内置的splice操作可以在 O(1) 时间内把一个节点从一条链表搬到另一条链表这在扩容时是杀手锏。什么情况下你会想换成裸链表如果你对内存占用有极致的强迫症一个std::list节点通常带两个指针和一个大小字段配合桶数组里的空 list 对象内存确实比一个next指针的单链表夸张。我当时也手写过一版裸节点链表结果很快被内存释放的问题拖住了调试进度——插入、删除、异常路径都要自己记挂着节点的生命周期。后来换回std::list一行splice解决迁移代码干净一个量级。我的结论是学习项目优先保证逻辑清晰性能差距后面再谈。桶数组的容量我刻意设计成 2 的幂。这样计算桶索引时可以用hash (bucketCount - 1)代替hash % bucketCount省掉一次除法。现代 CPU 对取模有硬件加速这个省下来的时间在 1e6 规模下其实不明显但它让代码至少看起来是懂行的。真正要注意的是当容量是 2 的幂时哈希值的高位变化会被丢弃只取低位算索引。如果哈希函数质量差低位分布差就会引发集中冲突。为了对冲这个风险我默认的哈希函数必须是扩散良好的这点会在后面专门展开。节点存储类型有个隐蔽的坑提前说出来省得你踩对于UnorderedMap底层存储的Value是std::pairconst Key, V。第一个模板参数带const这是为了让外部无法通过迭代器修改键。但const成员也给构造带来了麻烦你不能给pairconst K, V直接赋值只能构造。这意味着底层在插入新节点时必须用构造而不是先默认构造再赋值的方式创建节点。std::list::push_back好就好在它是原地构造传一个Value对象进去直接被完美转发到节点内存天然适合pairconst K, V这种不可赋值类型。初始化时_buckets默认构造出一堆空 list。插入第一个元素前我会顺手调用一次rehash(8)把桶数量预设出来免得首次插入就扩容。这个细节不写出来不影响功能但对性能影响挺实在——第一次插入就触发 rehash等于白付一次搬迁成本。3. 迭代器哈希容器封装里最烧脑的一块如果说哈希桶是整个项目的地基那迭代器就是地基上的承重墙。我封装过程里百分之七十的功夫都花在这上面所以单独拿出来讲。先看迭代器需要维护什么状态。它至少得知道两件事当前指向的是哪个桶里的哪个节点以及哈希表本体在哪里为了自增时找到下一个桶。我设计的迭代器是这样的template typename Table class HTIterator { using Value typename Table::value_type; using BucketIt typename Table::BucketIt; public: HTIterator(Table* table, std::size_t bucketIndex, BucketIt cur) : _table(table), _bucketIndex(bucketIndex), _cur(cur) {} Value operator*() const { return *_cur; } Value* operator-() const { return std::addressof(*_cur); } HTIterator operator() { _cur; if (_cur _table-_buckets[_bucketIndex].end()) moveToNextNonEmptyBucket(); return *this; } private: void moveToNextNonEmptyBucket() { _bucketIndex; while (_bucketIndex _table-_buckets.size() _table-_buckets[_bucketIndex].empty()) { _bucketIndex; } if (_bucketIndex _table-_buckets.size()) _cur _table-_buckets[_bucketIndex].begin(); else _cur typename Table::BucketIt{}; // 哨兵指向末尾 } Table* _table; std::size_t _bucketIndex; BucketIt _cur; friend class HashTable...; };注意operator的逻辑先把当前桶里的迭代器往后挪一格如果挪到了当前桶的end()就要跳到下一个非空桶。这里有一个微妙点——如果当前桶里有很多个元素那么一轮自增只走一个元素非常快如果刚跳到的新桶是空的就需要连续跳过多个空桶。所以哈希表迭代器的单次自增在最坏情况下是 O(桶数)平均下来仍是 O(1)。这也是桶式哈希迭代器的一个典型特征你没法保证每次都是常数时间。我有一次在这里写出过一个经典的 bug跳桶时忘了处理尾部哨兵导致遍历到大桶数组末尾后_bucketIndex越界访问。调试的时候表现得很诡异——不是每次都崩而是只有遍历完所有元素之后下一次才崩。后来我养成了一个习惯在这个moveToNextNonEmptyBucket里先把越界检查写满再写跳桶逻辑顺序绝对不能反。再说const_iterator。我的做法是用模板参数抽象迭代器的可变性——把iterator和const_iterator归结为同一个模板的不同实例template bool IsConst class HTIterator { using BucketIt typename std::conditionalIsConst, typename Table::BucketConstIt, typename Table::BucketIt::type; ... };这样iterator可以隐式转换成const_iterator只要提供对应的转换构造函数HTIteratortrue(const HTIteratorfalse)。为了避免const_iterator内部持有Table*却能修改表结构的问题我在operator里已经保证了只读_table-_buckets不修改任何成员——也就是说const_iterator读到的表结构实际上来自一个const HashTable*。这一步的正确性是在编译层面用const限定符保证的。还有个容易忽略的细节begin()必须跳过所有空桶直接指向第一个非空桶的首元素如果全是空桶就返回end()。写的时候我建议把找第一个非空桶单独抽成一个私有函数begin()和moveToNextNonEmptyBucket都能复用它。别嫌麻烦这个函数你会在调试迭代器的时候反复看。4. 一个底层两个容器类型萃取与接口复用底层哈希表准备好了接下来才是标题里的重头戏怎么用同一份HashTable封装出unordered_map和unordered_set两个长得不一样的容器。核心思路是模板参数注入差异而不是继承。HashTable的第三个模板参数KeyOfValue是一个函数对象类型它的职责很简单从存储对象里提取出键。对unordered_set来说存储对象本身就是键提取就是恒等函数对unordered_map来说存储对象是pairconst K, V提取就是取.first。template typename K, typename V, typename Hash std::hashK, typename KeyEqual std::equal_toK class UnorderedMap { private: using Value std::pairconst K, V; struct Select1st { const K operator()(const Value kv) const { return kv.first; } }; HashTableK, Value, Select1st, Hash, KeyEqual _table; public: using key_type K; using mapped_type V; using value_type Value; using iterator typename decltype(_table)::iterator; // ... 接口转发 };UnorderedSet那边更简单template typename K, typename Hash std::hashK, typename KeyEqual std::equal_toK class UnorderedSet { private: struct Identity { const K operator()(const K k) const { return k; } }; HashTableK, K, Identity, Hash, KeyEqual _table; // ... };这套Select1st/Identity的命名是从 SGI STL 里继承过来的老设计。它让我意识到所谓封装在这个语境下更多是编译期的多态——所有差异在模板实例化那一刻被编译器展开运行期零开销。对比封装继承多态里那种通过基类虚函数实现的运行时多态这里用的是完全不同的思路接口相同但行为在模板参数层面分岔。接口转发阶段有几个坑。第一个是insert。unordered_map对外接口的value_type是pairconst K, V但用户写m.insert({1, 2})传进来的是一个pairint, int两者的类型不同。底层的HashTable::insert接收的是Value即pairconst K, V所以顶层需要一个转换构造。好消息是std::pair提供了从另一个 pair 转换构造的模板构造函数pairconst K, V可以从pairK, V构造所以直接转发就能过编译。第二个坑是operator[]。它和insert的语义不同如果键存在返回已有值的引用如果不存在插入一个默认值再返回引用。你可能会想先find再决定插入但这会触发两次查找。更高效的做法是借助底层insert的返回值——它返回一个pairiterator, bool迭代器总是指向目标元素V operator[](const K key) { auto result _table.insert(Value{key, V{}}); return result.first-second; }注意一个问题如果插入触发了扩容扩容前的迭代器会失效但insert返回的迭代器是新扩容后重新定位过的所以return result.first-second是安全的。我最初为了省事先find找不到再insert结果在自定义类型上因为要求 V 可默认构造反而绕了远路。直接用insert的返回值的方案逻辑更短还能顺便利用底层对重复键的检测。第三个坑是erase的返回值。C11 之前erase(iterator)返回 voidC11 之后标准要求 unordered 容器的erase返回被删除元素的下一个迭代器。我们的底层用std::list实现erase天然返回下一个迭代器所以转发时只要把底层返回值原样透传即可。但如果你用的是手写单链表这一步就得自己维护下一个指针——又费神又容易写错。这也是我推荐std::list做桶的又一个理由。5. 哈希函数、相等比较与自定义类型支持封装的顶层接口里我把Hash和KeyEqual作为默认模板参数暴露给用户默认值分别是std::hashK和std::equal_toK。这意味着如果你只是往UnorderedSetint里塞整数什么都不用改。但实际的工程里你大概率会遇到需要放进 unordered 容器的自定义类型。这里涉及一个很容易被误解的点为什么需要同时提供哈希函数和相等比较哈希函数的职责是把键映射到桶索引相等比较的职责是判断两个落在同一桶里的键是否真的相同。两者缺一不可——哈希表靠必有一致这条约定工作只要两个键相等它们的哈希值必然相同所以它们必然落到同一个桶里。std::equal_to保证相等比较std::hash配合桶索引保证相同的键进相同的桶。如果这个约定被破坏表里就会藏着永远不会被找到的元素。一个典型的反面例子你给某个自定义类型写了哈希函数却忘了重载operator结果equal_to退化成最朴素的按内存比较——两个逻辑上相等但字段顺序不同的对象进不了同一个槽查找直接失败。我在开发时遇到过这种问题当时查了很久才发现是operator没写对。先看自定义类型的哈希怎么写。假设有一个二维点结构struct Point2D { int x; int y; bool operator(const Point2D other) const { return x other.x y other.y; } }; struct Point2DHash { std::size_t operator()(const Point2D p) const { std::size_t seed 0; seed ^ std::hashint{}(p.x) 0x9e3779b9 (seed 6) (seed 2); seed ^ std::hashint{}(p.y) 0x9e3779b9 (seed 6) (seed 2); return seed; } };那个神秘常数0x9e3779b9是黄金比例在 32 位空间里的近似值用在位混淆上能有效打散相近输入的哈希值。这个seed ^ h golden_ratio (seed6) (seed2)的组合方式就是赫赫有名的hash_combine类算法它比简单地把两个子哈希异或靠谱得多。简单异或的问题在于hash(a,b)和hash(b,a)得到一样的结果而且如果多个子字段哈希值相同异或会把它们抵消。hash_combine通过每次累加时做移位和加法让 seed 充分吸收每个字段的贡献。还有个小提示自定义类型的operator尽量写成 member function 或 hidden friend。只要能保证同类型对象间可以比较即可。哈希容器内部用的是KeyEqual()(a, b)这种函数对象调用形式所以自定义的仿函数只要实现了operator()一样能用。哈希函数质量这块还有一个容易被忽视的问题当你用 2 的幂作为桶数量时桶索引只取哈希值的低位。如果自定义哈希返回的 size_t 天然集中在低 4 位有差异、高位全是零那不管桶数量多大所有键都挤在十几个桶里。所以我在默认设计里要求哈希函数至少做到低位扩散。对于标准库的std::hashint它通常就是返回整数本身质量本来就不算好但它配合 STL 那些质数桶容量能缓解这个问题——而我们用的 2 的幂容量就吃这个亏。好在现在的编译器和库版本里std::hash实现普遍做了位混洗实测下来随机 int 的分布是够用的。如果你的键是自己设计的高低位差异明显的整数建议加一步hash ^ hash 16之类的位混淆。6. 扩容、删除与迭代器失效最容易翻车的地方哈希桶容器里insert和erase在特定条件下会改变桶的结构处理不好就用出内存问题或语义错误。这一节把最容易翻车的三件事讲清楚。6.1 触发条件与扩容过程我实现的触发阈值是_elementCount / _buckets.size() _maxLoadFactor默认_maxLoadFactor 1.0。每次insert前检查一次如果达到或超过阈值就扩容。容量增长策略是翻倍——从 8 到 16 到 32保证始终是 2 的幂。扩容过程的核心操作是splice。因为std::list的节点迁移是 O(1)而且不会触发元素拷贝和构造整个过程都不会抛异常。我先把这一步写成伪代码再贴真实现void rehash(size_type newBucketCount) { Buckets newBuckets(newBucketCount); for (auto bucket : _buckets) { for (auto it bucket.begin(); it ! bucket.end(); ) { auto next std::next(it); std::size_t newIndex hashOf(*it) (newBucketCount - 1); newBuckets[newIndex].splice(newBuckets[newIndex].end(), bucket, it); it next; } } _buckets.swap(newBuckets); }newBuckets构造时一次性分配好全部空桶这一步可能抛异常内存不够。但一旦进入节点迁移阶段全程不分配内存、不拷贝元素只是调整链表指针所以不会抛异常。这意味着扩容过程中途数据损坏这种事被结构性地杜绝了——新桶数组要么分配成功要么整个操作直接抛出异常旧表纹丝不动。这个设计天然提供了很强的异常安全保证。有朋友问过为什么不用构造一个全新的 HashTable 再 swap这种更简单的方案省事是省事但它要把所有元素重新拷贝一遍对非平凡类型是巨大的浪费。splice方案本质上是把元素所有权从一个 list 转移到另一个 list一毛钱拷贝都没有。这个差距在元素是 string 或者自定义大对象时非常明显。6.2 迭代器失效的语义边界标准库对 unordered 容器的规定是rehash会让所有迭代器失效但元素的引用和指针不受影响。我们抄这个语义做扩容后你手里旧的迭代器不能再但如果你提前保存了某个元素的Value*它依然能访问——因为元素节点没动只是换了个桶挂。删除则更敏感。erase(iterator)只让被删元素的迭代器失效其余全部健在。由于底层是std::list这个语义是自动满足的。我曾经在这上面踩过一个坑遍历容器时想边遍历边删除用for (auto it c.begin(); it ! c.end(); ) { if (cond) it c.erase(it); else it; }这个写法属于标准做法。但如果我偷懒写成c.erase(it);虽然合法但可读性差一些在代码审查里容易被质疑。建议统一用前者。6.3 调试用的 sanity check哈希容器做出来之后我投入了大量时间在 bug 上。后来写了一个debugSanityCheck()函数在每次插入、删除、扩容后调用它验证三条不变式_elementCount等于所有桶的元素数量之和每个元素通过KeyOfValue取出的键重新哈希后确实落在它当前的桶里满足相等条件的两个不同对象不会同时出现在同一个桶里如果出现说明哈希约定被破坏这个检查函数在 release 模式里会被宏关掉在 debug 模式下帮了我大忙。有一次自定义类型的operator写错了导致重复元素被当成不同键存进同一个桶就是靠第三条不变式揪出来的。写容器类时埋一个这样的内部自检钩子实战价值极高。7. 实测对比自研容器与 std::unordered_map 的差距代码写完不能只停留在能跑我用一个简单的基准测试评估了一下自家容器和标准库的差距。测试环境是 GCC 11 配合-O2数据集是 1e6 个随机int分别测插入、查找、遍历三个场景。先说结论自研UnorderedMap的时间复杂度量级和std::unordered_map完全一致绝对耗时整体慢 10%~30%差距主要来自几个方面。第一是哈希函数。std::unordered_map底层在哈希值上做了额外的位混洗而我们直接用std::hashint的原始结果配合低位掩码。随机 int 的场景下问题不大但如果数据是连续的整数低位分布其实还行所以差距有限。真要说大差距场景还是得回到分布差的哈希上去。第二是桶结构。我们用std::list做桶每个节点有两个指针的开销遍历时缓存局部性差——一条链表上的节点在堆上随机散布CPU 缓存命中率自然不如 STL 里那种更紧凑的节点布局。这也是链地址法普遍比开放定址法慢的内存层面的原因。第三是operator[]的插入路径。自研版在find失败后走insert而insert内部还要再做一次查找来确认是否重复。虽然可以优化成一次查找同时完成定位与插入判断但实现复杂度就上去了。目前这个版本能和标准库保持在同一个数量级已经达到我封装这个项目时的预期。内存占用方面我们每个元素多出的开销是std::list节点的额外指针在int这种小对象上尤其明显。标准库的 unordered 实现也保留了类似结构只是节点组织方式更紧凑。这里提一个可能的方向如果你对内存和数据局部性有硬性要求可以考虑换用开放定址法的 flat hash map 系列——这是后话了。最后说一个我在实测中发现的有趣现象用同样的插入顺序自研容器和std::unordered_map的遍历输出顺序完全不同。哈希表的遍历顺序本来就是由哈希值对桶数取模决定的和插入顺序无关。所以写业务代码时永远不要依赖 unordered 容器的遍历顺序这是用哈希容器的人最容易忽略的一条铁律。回看整个封装过程我最大的体会是哈希桶项目真正难的地方不是把哈希函数写对而是把迭代器边界和容器接口语义理顺。当一个底层HashTable同时喂给UnorderedMap和UnorderedSet时你会被迫把容器通用逻辑和键值存储差异拆得干干净净这种抽象能力是刷多少算法题都换不来的。如果你也想动手写一遍我的建议是先把迭代器的自增逻辑在纸上画出三个桶的状态图标清楚end()的位置再动手写代码——这一步做好了后面整个项目会顺畅得多。
