1. 项目概述从零封装自己的哈希容器在C的日常开发中std::unordered_map和std::unordered_set是我们处理快速查找、去重问题的利器。它们背后的核心数据结构是哈希表而哈希表的具体实现方式之一就是我们常说的“哈希桶”Hash Bucket或“开链法”。很多朋友在面试时被问到STL容器的底层原理都能说出“哈希表”三个字但当你被追问“如何自己动手实现一个”时是不是感觉有点无从下手或者你虽然看过一些源码解析但总觉得隔着一层纱没有真正“拥有”过它。这次我们不满足于仅仅理解原理。我将带你从零开始亲手封装一个基于哈希桶的、简化版的unordered_map和unordered_set。这个项目的价值远不止于应付面试。通过亲手实现你会深刻理解哈希函数的设计、冲突解决策略、负载因子的控制、迭代器的封装等核心概念。你会发现原来STL中那些看似复杂的模板和迭代器设计其内在逻辑是如此清晰和优雅。更重要的是当你自己踩过扩容时数据迁移的坑、处理过迭代器失效的边界情况后你再使用标准库的容器时会多一份底气和掌控感。无论你是想夯实C基础深入理解数据结构还是为参与底层基础库开发做准备这个项目都是一次绝佳的实践。2. 核心数据结构哈希桶的设计与实现2.1 哈希桶的本质开链法解决冲突哈希表的核心思想是通过一个哈希函数将关键字Key映射到数组哈希表中的一个位置。理想情况下每个关键字对应唯一的位置但现实是不同的关键字可能被映射到同一个位置这就是“哈希冲突”。哈希桶开链法是解决冲突最经典的方法之一。它的设计非常直观哈希表的每个位置称为一个“桶”bucket不再直接存储单个元素而是存储一个链表的头指针。当多个关键字被哈希到同一个桶时我们就把它们以节点的形式链接到这个桶对应的链表上。你可以把它想象成一个有很多格子的储物柜哈希表数组每个格子里挂着一个钩子链表头指针用来挂一串物品链表节点。查找时先根据关键字找到对应的格子O(1)再在这个格子的链表里顺序查找O(k)k为链表平均长度。这种方法的优点在于实现简单且不会产生“堆积”现象即冲突的元素不会占用其他空桶的位置。它的性能瓶颈在于链表的长度。如果哈希函数设计得不好或者数据量激增导致大量元素堆积到少数几个桶里链表就会变得很长查找效率会退化为O(n)。因此控制链表长度即控制“负载因子”元素总数/桶的数量是哈希桶性能优化的关键。2.2 节点与桶结构定义我们首先需要定义哈希桶中最基本的单元节点Node。对于unordered_set节点只需要存储一个值Key对于unordered_map节点需要存储一个键值对Key-Value Pair。为了代码的复用我们采用一个通用的结构。// 哈希表节点的基础结构 template class T struct HashNode { T _data; // 存储的数据对于set是Key对于map是pairconst Key, V HashNodeT* _next; // 指向下一个节点的指针 HashNode(const T data) : _data(data) , _next(nullptr) {} };接下来我们需要定义哈希表本身也就是“桶”的集合。我们将使用一个std::vector来管理这些桶每个桶是一个HashNodeT*类型的指针指向该桶链表的头节点。template class T class HashTable { public: // ... 后续的成员函数 private: std::vectorHashNodeT* _tables; // 哈希桶数组 size_t _size 0; // 存储的有效元素个数 };这里有一个关键点_tables是桶数组它的长度_tables.size()就是当前哈希表的桶数量bucket_count。_size是表中所有链表的节点总数即容器中实际存储的元素个数。负载因子load factor就是_size / _tables.size()。注意初始容量与素数表在构造哈希表时桶的数量最好选择一个素数。这是因为使用素数作为模数可以在一定程度上减少哈希冲突使关键字分布更均匀。标准库的实现中通常会维护一个素数表在扩容时选择下一个更大的素数作为新的桶数量。在我们的简化实现中可以初始化一个较小的素数如7并在扩容时大致翻倍然后寻找一个接近的素数这是一个常见的策略。3. 关键操作插入、查找与删除的实现逻辑3.1 哈希函数与定位桶任何哈希表操作的第一步都是通过哈希函数将关键字转换成一个整型的哈希值然后通过取模运算映射到具体的桶下标。template class K struct DefaultHashFunc { size_t operator()(const K key) { // 一个简单的默认哈希函数直接返回key如果key是整数类型 // 对于字符串等类型需要特化 return (size_t)key; } }; // 针对std::string的特化版本 template struct DefaultHashFuncstd::string { size_t operator()(const std::string str) { // BKDR哈希算法 size_t hash 0; for (auto ch : str) { hash hash * 131 ch; // 乘数131是一个经验值 } return hash; } };在HashTable类中定位桶的函数如下size_t GetBucketIndex(const T data) { // 首先我们需要从data中提取出关键字Key。 // 这里需要一个“KeyOfT”的仿函数来提取后面会详细说明。 KeyOfT kot; const K key kot(data); HashFunc hf; size_t hashVal hf(key); // 计算哈希值 return hashVal % _tables.size(); // 取模得到桶下标 }3.2 插入元素与去重逻辑插入是哈希表的核心操作之一需要处理查找是否存在去重和插入新节点两个步骤。std::pairiterator, bool Insert(const T data) { // 0. 检查负载因子判断是否需要扩容 CheckAndResize(); // 1. 计算桶下标 size_t bucketIndex GetBucketIndex(data); // 2. 遍历该桶的链表查找是否已存在相同key的元素 HashNodeT* cur _tables[bucketIndex]; KeyOfT kot; while (cur) { if (kot(cur-_data) kot(data)) { // 找到相同key插入失败 return std::make_pair(iterator(cur, this, bucketIndex), false); } cur cur-_next; } // 3. 未找到进行头插头插效率高 HashNodeT* newNode new HashNodeT(data); newNode-_next _tables[bucketIndex]; _tables[bucketIndex] newNode; _size; // 4. 返回新插入节点的迭代器和true return std::make_pair(iterator(newNode, this, bucketIndex), true); }实操心得头插法与尾插法的选择在链表头部插入新节点头插的时间复杂度是O(1)而在尾部插入需要遍历链表是O(n)。对于哈希桶而言我们假设每个链表的长度不会很长由负载因子控制所以头插和尾插的差异在平均情况下不大。但头插实现更简单效率也略高因此是更常见的选择。需要注意的是这会导致桶内链表的元素顺序与插入顺序相反。3.3 查找与删除操作查找操作相对直接就是定位桶然后遍历链表。iterator Find(const K key) { // 如果表为空直接返回end() if (_tables.size() 0) { return end(); } size_t bucketIndex GetBucketIndexByKey(key); // 一个专门通过key计算下标的函数 HashNodeT* cur _tables[bucketIndex]; KeyOfT kot; while (cur) { if (kot(cur-_data) key) { return iterator(cur, this, bucketIndex); } cur cur-_next; } return end(); }删除操作则需要小心处理因为需要修改前一个节点的_next指针。对于单链表我们需要记录前驱节点。bool Erase(const K key) { size_t bucketIndex GetBucketIndexByKey(key); HashNodeT* cur _tables[bucketIndex]; HashNodeT* prev nullptr; // 前驱节点 KeyOfT kot; while (cur) { if (kot(cur-_data) key) { // 找到要删除的节点 if (prev nullptr) { // 要删除的是链表的头节点 _tables[bucketIndex] cur-_next; } else { // 要删除的是链表中间或尾部节点 prev-_next cur-_next; } delete cur; --_size; return true; } prev cur; cur cur-_next; } // 未找到key return false; }4. 性能之魂扩容机制与负载因子控制4.1 为什么需要扩容哈希表的性能高度依赖于负载因子Load Factor。负载因子 元素数量 / 桶数量。当负载因子过高时意味着平均每个桶里的链表长度变长查找、插入、删除操作的平均时间复杂度会从理想的O(1)向O(n)退化。标准库的unordered_map默认最大负载因子max_load_factor()通常是1.0。当当前负载因子超过或等于最大负载因子时容器会自动进行“重哈希”rehash即增加桶的数量并将所有已有元素重新计算哈希值放入新的桶中。这是一个相对耗时的操作O(n)但能保证长期操作的效率。4.2 扩容的实现策略在我们的HashTable中我们需要一个CheckAndResize函数在每次插入前检查。void CheckAndResize() { // 如果桶数组为空或者负载因子超过阈值则扩容 if (_size _tables.size()) { // 这里设置负载因子阈值为1.0 size_t newSize GetNextPrime(_tables.size() 0 ? 10 : _tables.size() * 2); std::vectorHashNodeT* newTables(newSize, nullptr); // 遍历旧表的所有节点 for (size_t i 0; i _tables.size(); i) { HashNodeT* cur _tables[i]; while (cur) { HashNodeT* next cur-_next; // 保存下一个节点 // 重新计算在新表中的桶下标 size_t newBucketIndex GetBucketIndexForResize(cur-_data, newSize); // 将当前节点头插到新表的对应桶中 cur-_next newTables[newBucketIndex]; newTables[newBucketIndex] cur; cur next; // 处理下一个节点 } _tables[i] nullptr; // 旧桶置空节点已转移 } // 交换新旧表 _tables.swap(newTables); // newTables离开作用域其内部的空指针会被自动释放 } }踩坑记录扩容时的迭代器失效这是实现哈希表迭代器时最需要注意的一点扩容操作会重新分配桶数组并将所有节点迁移到新的内存位置。这意味着扩容之后所有之前获取的迭代器、指针、引用都将失效除非你像标准库某些实现那样做了特殊处理。在我们的实现中扩容后原有的HashNode节点对象本身没有被delete只是改变了它们_next指针的指向以及它们在桶数组中的位置。因此如果用户持有某个节点的指针这个指针本身仍然有效指向同一个节点对象但通过这个迭代器无法正确遍历到下一个节点因为桶数组已经变了。所以我们必须将扩容视为一个导致所有迭代器失效的操作。在标准库中unordered_map::insert操作在发生重哈希后会导致所有迭代器失效但指向元素的引用和指针仍然有效。我们的简化实现可以遵循这一规则。4.3 素数表的使用GetNextPrime函数用于获取一个大于等于给定数字的素数。使用素数作为桶数量可以减少哈希冲突。我们可以预先定义一个素数数组。inline size_t GetNextPrime(size_t num) { // 一个静态的素数序列 static const size_t primeList[] { 7, 17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949, 21911, 43853, 87719, 175447, 350899, 701819, 1403641, 2807303, 5614657, 11229331, 22458671, 44917381, 89834777, 179669557, 359339171, 718678369, 1437356741, 2147483647 }; for (size_t prime : primeList) { if (prime num) { return prime; } } // 如果数字太大返回列表最后一个最大的素数 return primeList[sizeof(primeList)/sizeof(primeList[0]) - 1]; }5. 迭代器封装让哈希桶支持STL风格遍历5.1 迭代器设计的挑战哈希桶的迭代器比向量vector或链表list的迭代器要复杂因为它需要在两个维度上移动桶内移动在一个桶的链表上从当前节点移动到下一个节点node node-_next。跨桶移动当当前桶的链表遍历完毕后需要找到下一个非空的桶。因此迭代器对象至少需要知道当前指向的节点HashNodeT* _node。所属的哈希表对象HashTableT* _ht以便访问桶数组。当前节点所在的桶下标size_t _bucketIndex用于高效地寻找下一个桶。5.2 迭代器类的实现// 前置声明HashTable因为迭代器需要用它作为友元 template class T, class K, class HashFunc, class KeyOfT class HashTable; template class T, class K, class HashFunc, class KeyOfT struct __HashIterator { typedef HashNodeT Node; typedef __HashIteratorT, K, HashFunc, KeyOfT Self; typedef HashTableT, K, HashFunc, KeyOfT HT; Node* _node; // 当前节点指针 HT* _ht; // 哈希表指针 size_t _bucketIndex; // 当前节点所在的桶下标 __HashIterator(Node* node, HT* ht, size_t bucketIndex) : _node(node) , _ht(ht) , _bucketIndex(bucketIndex) {} // 解引用操作符 T operator*() { return _node-_data; } T* operator-() { return (_node-_data); } // 前置操作符核心难点 Self operator() { if (_node-_next) { // 情况1当前桶内还有下一个节点 _node _node-_next; } else { // 情况2当前桶的链表已遍历完需要找下一个非空桶 _bucketIndex; while (_bucketIndex _ht-_tables.size() _ht-_tables[_bucketIndex] nullptr) { _bucketIndex; } if (_bucketIndex _ht-_tables.size()) { // 找到了下一个非空桶 _node _ht-_tables[_bucketIndex]; } else { // 已经遍历完所有桶迭代器指向end() _node nullptr; // _bucketIndex 可以保持不变或设为无效值 } } return *this; } // 后置操作符 Self operator(int) { Self tmp *this; (*this); return tmp; } bool operator!(const Self it) const { return _node ! it._node; } bool operator(const Self it) const { return _node it._node; } };5.3 在HashTable中提供迭代器接口我们需要在HashTable类中定义迭代器类型并提供begin()和end()方法。template class T, class K, class HashFunc, class KeyOfT class HashTable { // ... 其他成员 public: typedef __HashIteratorT, K, HashFunc, KeyOfT iterator; iterator begin() { // 找到第一个非空桶 for (size_t i 0; i _tables.size(); i) { if (_tables[i]) { return iterator(_tables[i], this, i); } } // 如果表为空返回end() return end(); } iterator end() { // end()迭代器通常用空指针表示 return iterator(nullptr, this, -1); // 桶下标-1表示无效 } // 为了让迭代器能访问HashTable的私有成员_tables需要声明为友元 friend struct __HashIteratorT, K, HashFunc, KeyOfT; };注意事项迭代器失效的严格处理我们的迭代器保存了哈希表对象的指针_ht和桶下标_bucketIndex。这意味着一旦哈希表发生扩容_tables被重新分配和填充所有现有的迭代器内部记录的_bucketIndex很可能就失效了因为节点被移动到了新的桶而迭代器还记录着旧的桶下标继续使用操作会导致未定义行为。因此在文档和使用说明中必须明确指出任何可能引起重哈希的操作如Insert导致扩容都会使所有现有迭代器失效。这是与标准库行为一致的。6. 最终封装实现unordered_map与unordered_set6.1 利用模板与仿函数实现泛型这是整个项目设计最精妙的部分。我们希望用同一个HashTable模板类通过传递不同的模板参数来同时实现unordered_map和unordered_set。它们的核心区别在于存储的数据类型T不同set:T就是Key。map:T是std::pairconst Key, V。从数据T中提取关键字Key的方式不同set: 关键字就是数据本身。map: 关键字是pair的第一个元素first。我们可以通过一个叫做“仿函数”Functor或“函数对象”的模板参数KeyOfT来解决第二个问题。// 用于unordered_set的仿函数Key就是T template class K struct SetKeyOfT { const K operator()(const K key) { return key; } }; // 用于unordered_map的仿函数Key是pair的first template class K, class V struct MapKeyOfT { const K operator()(const std::pairconst K, V kv) { return kv.first; } };6.2 unordered_set的封装实现有了上面的准备unordered_set的封装就非常清晰了。它内部包含一个HashTable成员并将SetKeyOfT作为模板参数传递。template class K, class HashFunc DefaultHashFuncK class unordered_set { private: // 底层哈希表存储的数据类型T就是K用SetKeyOfT来提取Key HashTableK, K, HashFunc, SetKeyOfTK _ht; public: typedef typename HashTableK, K, HashFunc, SetKeyOfTK::iterator iterator; iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } std::pairiterator, bool insert(const K key) { return _ht.Insert(key); } iterator find(const K key) { return _ht.Find(key); } bool erase(const K key) { return _ht.Erase(key); } // ... 其他接口如size(), empty(), clear()等直接调用_ht的对应方法 size_t size() const { return _ht.Size(); } bool empty() const { return _ht.Empty(); } void clear() { _ht.Clear(); } };6.3 unordered_map的封装实现unordered_map的实现类似但存储的数据类型是pair并使用MapKeyOfT仿函数。template class K, class V, class HashFunc DefaultHashFuncK class unordered_map { private: // 注意存储的数据类型T是pairconst K, V // 关键字类型是K用MapKeyOfT来从pair中提取Key HashTablestd::pairconst K, V, K, HashFunc, MapKeyOfTK, V _ht; public: typedef typename HashTablestd::pairconst K, V, K, HashFunc, MapKeyOfTK, V::iterator iterator; iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } std::pairiterator, bool insert(const std::pairconst K, V kv) { return _ht.Insert(kv); } // map特有的operator[]功能强大若key存在返回其value的引用若不存在则插入该key并返回其value的引用。 V operator[](const K key) { std::pairiterator, bool ret _ht.Insert(std::make_pair(key, V())); // ret.first是迭代器指向插入的或已存在的pair return ret.first-second; // 返回value的引用 } iterator find(const K key) { return _ht.Find(key); } bool erase(const K key) { return _ht.Erase(key); } size_t size() const { return _ht.Size(); } // ... 其他接口 };关键技巧operator[]的实现unordered_map::operator[]是STL中非常方便的一个接口。它的实现巧妙地利用了insert的返回值。insert会返回一个pairiterator, bool其中bool表示是否插入成功。operator[]的逻辑是尝试插入一个以key为关键字以V()value类型的默认值为value的键值对。如果key已存在insert什么也不做但返回的迭代器指向已存在的元素如果key不存在insert会成功插入这个新pair。无论哪种情况最后都通过迭代器返回这个pair中value的引用。这使得我们可以像使用数组一样使用mapmap[key] value;。7. 测试、调试与常见问题排查7.1 基础功能测试实现完成后必须进行全面的测试。可以从简单到复杂基本插入与查找测试insert、find、size。去重测试向set插入重复元素检查insert返回的bool值是否为false且size不变。删除测试测试erase删除存在和不存在的元素。遍历测试使用迭代器begin()和end()遍历容器检查元素是否都被访问到且不重复、不遗漏。operator[]测试针对map测试map[key]的读写功能包括对不存在的key进行赋值。7.2 扩容与迭代器失效测试这是最容易出问题的地方。触发扩容编写一个循环插入大量元素比如10000个确保在插入过程中没有崩溃。可以在HashTable的CheckAndResize函数中加入打印语句观察扩容是否被触发。迭代器失效验证在扩容前后获取一个迭代器it。触发扩容后尝试对it进行操作。在我们的实现中这应该会导致程序出错或遍历到错误的位置。这证明了我们的迭代器失效规则。指针/引用有效性测试针对map的value对于map在扩容前获取一个元素的引用V ref map[key]。触发扩容后尝试修改ref。由于节点对象本身没有销毁这个引用应该仍然有效并且修改会成功。这符合标准库的部分规则引用和指针不失效。7.3 常见问题与排查技巧插入后查找不到检查哈希函数确保你的哈希函数对于自定义类型有正确的特化版本。对于自定义类需要重载operator并提供哈希仿函数。检查KeyOfT仿函数在map中确保MapKeyOfT正确地从pair中提取了firstkey。检查桶下标计算在GetBucketIndex函数中打印哈希值和取模后的结果确认计算逻辑正确。内存泄漏实现析构函数HashTable的析构函数必须遍历所有桶删除所有链表节点。实现Clear()函数用于清空所有元素同样需要遍历删除节点并将桶指针置为nullptr。使用Valgrind或AddressSanitizer等工具进行内存检查。迭代器操作死循环或越界仔细检查operator逻辑特别是跨桶寻找的逻辑。确保while循环的条件是_bucketIndex _ht-_tables.size()并且访问_ht-_tables[_bucketIndex]是安全的。处理空表情况当哈希表为空时begin()应该直接返回end()。性能低下监控负载因子如果插入大量数据后性能下降可能是默认的桶数量增长策略如翻倍不够平滑或者哈希函数分布不均匀导致某些桶过长。可以尝试调整最大负载因子比如降到0.75或者优化哈希函数。模板编译错误这类错误信息通常又长又晦涩。关键是从第一个错误看起检查模板参数是否匹配。例如在HashTable中调用KeyOfT仿函数时确保传递给它的参数类型是T而仿函数返回的类型是K。7.4 一个简单的测试用例#include iostream #include string #include MyUnorderedMap.h // 你的头文件 #include MyUnorderedSet.h void TestMap() { my::unordered_mapstd::string, int wordCount; wordCount[apple] 5; wordCount[banana] 3; wordCount[apple] 10; // 修改已存在的key std::cout apple: wordCount[apple] std::endl; // 输出 10 std::cout banana: wordCount[banana] std::endl; // 输出 3 std::cout orange: wordCount[orange] std::endl; // 输出 0 (key不存在但operator[]会插入) std::cout Size: wordCount.size() std::endl; // 输出 3 // 遍历 for (auto kv : wordCount) { std::cout kv.first : kv.second std::endl; } // 查找与删除 auto it wordCount.find(banana); if (it ! wordCount.end()) { wordCount.erase(it); // 通过迭代器删除 // wordCount.erase(banana); // 通过key删除也可以 } std::cout After erase, size: wordCount.size() std::endl; } void TestSet() { my::unordered_setint numSet; for (int i 0; i 100; i) { numSet.insert(i % 10); // 只会插入0-9测试去重 } std::cout Set size (should be 10): numSet.size() std::endl; for (auto it numSet.begin(); it ! numSet.end(); it) { std::cout *it ; } std::cout std::endl; } int main() { TestMap(); std::cout ----- std::endl; TestSet(); return 0; }通过这个从底层哈希桶搭建到迭代器封装最后实现出unordered_map和unordered_set的完整过程你收获的不仅仅是一段可以运行的代码。你深入理解了哈希表这个数据结构的高效与脆弱并存的特质明白了负载因子和扩容的重要性体会了迭代器设计的精巧与陷阱并掌握了利用模板和仿函数实现泛型容器的核心技巧。下次当你再使用std::unordered_map时你看到的将不再是一个黑盒而是一个由桶、链表、哈希函数和负载因子共同构建的、清晰可见的精密机器。这才是动手实现一个轮子的最大意义。
1. 项目概述从零封装自己的哈希容器在C的日常开发中std::unordered_map和std::unordered_set是我们处理快速查找、去重问题的利器。它们背后的核心数据结构是哈希表而哈希表的具体实现方式之一就是我们常说的“哈希桶”Hash Bucket或“开链法”。很多朋友在面试时被问到STL容器的底层原理都能说出“哈希表”三个字但当你被追问“如何自己动手实现一个”时是不是感觉有点无从下手或者你虽然看过一些源码解析但总觉得隔着一层纱没有真正“拥有”过它。这次我们不满足于仅仅理解原理。我将带你从零开始亲手封装一个基于哈希桶的、简化版的unordered_map和unordered_set。这个项目的价值远不止于应付面试。通过亲手实现你会深刻理解哈希函数的设计、冲突解决策略、负载因子的控制、迭代器的封装等核心概念。你会发现原来STL中那些看似复杂的模板和迭代器设计其内在逻辑是如此清晰和优雅。更重要的是当你自己踩过扩容时数据迁移的坑、处理过迭代器失效的边界情况后你再使用标准库的容器时会多一份底气和掌控感。无论你是想夯实C基础深入理解数据结构还是为参与底层基础库开发做准备这个项目都是一次绝佳的实践。2. 核心数据结构哈希桶的设计与实现2.1 哈希桶的本质开链法解决冲突哈希表的核心思想是通过一个哈希函数将关键字Key映射到数组哈希表中的一个位置。理想情况下每个关键字对应唯一的位置但现实是不同的关键字可能被映射到同一个位置这就是“哈希冲突”。哈希桶开链法是解决冲突最经典的方法之一。它的设计非常直观哈希表的每个位置称为一个“桶”bucket不再直接存储单个元素而是存储一个链表的头指针。当多个关键字被哈希到同一个桶时我们就把它们以节点的形式链接到这个桶对应的链表上。你可以把它想象成一个有很多格子的储物柜哈希表数组每个格子里挂着一个钩子链表头指针用来挂一串物品链表节点。查找时先根据关键字找到对应的格子O(1)再在这个格子的链表里顺序查找O(k)k为链表平均长度。这种方法的优点在于实现简单且不会产生“堆积”现象即冲突的元素不会占用其他空桶的位置。它的性能瓶颈在于链表的长度。如果哈希函数设计得不好或者数据量激增导致大量元素堆积到少数几个桶里链表就会变得很长查找效率会退化为O(n)。因此控制链表长度即控制“负载因子”元素总数/桶的数量是哈希桶性能优化的关键。2.2 节点与桶结构定义我们首先需要定义哈希桶中最基本的单元节点Node。对于unordered_set节点只需要存储一个值Key对于unordered_map节点需要存储一个键值对Key-Value Pair。为了代码的复用我们采用一个通用的结构。// 哈希表节点的基础结构 template class T struct HashNode { T _data; // 存储的数据对于set是Key对于map是pairconst Key, V HashNodeT* _next; // 指向下一个节点的指针 HashNode(const T data) : _data(data) , _next(nullptr) {} };接下来我们需要定义哈希表本身也就是“桶”的集合。我们将使用一个std::vector来管理这些桶每个桶是一个HashNodeT*类型的指针指向该桶链表的头节点。template class T class HashTable { public: // ... 后续的成员函数 private: std::vectorHashNodeT* _tables; // 哈希桶数组 size_t _size 0; // 存储的有效元素个数 };这里有一个关键点_tables是桶数组它的长度_tables.size()就是当前哈希表的桶数量bucket_count。_size是表中所有链表的节点总数即容器中实际存储的元素个数。负载因子load factor就是_size / _tables.size()。注意初始容量与素数表在构造哈希表时桶的数量最好选择一个素数。这是因为使用素数作为模数可以在一定程度上减少哈希冲突使关键字分布更均匀。标准库的实现中通常会维护一个素数表在扩容时选择下一个更大的素数作为新的桶数量。在我们的简化实现中可以初始化一个较小的素数如7并在扩容时大致翻倍然后寻找一个接近的素数这是一个常见的策略。3. 关键操作插入、查找与删除的实现逻辑3.1 哈希函数与定位桶任何哈希表操作的第一步都是通过哈希函数将关键字转换成一个整型的哈希值然后通过取模运算映射到具体的桶下标。template class K struct DefaultHashFunc { size_t operator()(const K key) { // 一个简单的默认哈希函数直接返回key如果key是整数类型 // 对于字符串等类型需要特化 return (size_t)key; } }; // 针对std::string的特化版本 template struct DefaultHashFuncstd::string { size_t operator()(const std::string str) { // BKDR哈希算法 size_t hash 0; for (auto ch : str) { hash hash * 131 ch; // 乘数131是一个经验值 } return hash; } };在HashTable类中定位桶的函数如下size_t GetBucketIndex(const T data) { // 首先我们需要从data中提取出关键字Key。 // 这里需要一个“KeyOfT”的仿函数来提取后面会详细说明。 KeyOfT kot; const K key kot(data); HashFunc hf; size_t hashVal hf(key); // 计算哈希值 return hashVal % _tables.size(); // 取模得到桶下标 }3.2 插入元素与去重逻辑插入是哈希表的核心操作之一需要处理查找是否存在去重和插入新节点两个步骤。std::pairiterator, bool Insert(const T data) { // 0. 检查负载因子判断是否需要扩容 CheckAndResize(); // 1. 计算桶下标 size_t bucketIndex GetBucketIndex(data); // 2. 遍历该桶的链表查找是否已存在相同key的元素 HashNodeT* cur _tables[bucketIndex]; KeyOfT kot; while (cur) { if (kot(cur-_data) kot(data)) { // 找到相同key插入失败 return std::make_pair(iterator(cur, this, bucketIndex), false); } cur cur-_next; } // 3. 未找到进行头插头插效率高 HashNodeT* newNode new HashNodeT(data); newNode-_next _tables[bucketIndex]; _tables[bucketIndex] newNode; _size; // 4. 返回新插入节点的迭代器和true return std::make_pair(iterator(newNode, this, bucketIndex), true); }实操心得头插法与尾插法的选择在链表头部插入新节点头插的时间复杂度是O(1)而在尾部插入需要遍历链表是O(n)。对于哈希桶而言我们假设每个链表的长度不会很长由负载因子控制所以头插和尾插的差异在平均情况下不大。但头插实现更简单效率也略高因此是更常见的选择。需要注意的是这会导致桶内链表的元素顺序与插入顺序相反。3.3 查找与删除操作查找操作相对直接就是定位桶然后遍历链表。iterator Find(const K key) { // 如果表为空直接返回end() if (_tables.size() 0) { return end(); } size_t bucketIndex GetBucketIndexByKey(key); // 一个专门通过key计算下标的函数 HashNodeT* cur _tables[bucketIndex]; KeyOfT kot; while (cur) { if (kot(cur-_data) key) { return iterator(cur, this, bucketIndex); } cur cur-_next; } return end(); }删除操作则需要小心处理因为需要修改前一个节点的_next指针。对于单链表我们需要记录前驱节点。bool Erase(const K key) { size_t bucketIndex GetBucketIndexByKey(key); HashNodeT* cur _tables[bucketIndex]; HashNodeT* prev nullptr; // 前驱节点 KeyOfT kot; while (cur) { if (kot(cur-_data) key) { // 找到要删除的节点 if (prev nullptr) { // 要删除的是链表的头节点 _tables[bucketIndex] cur-_next; } else { // 要删除的是链表中间或尾部节点 prev-_next cur-_next; } delete cur; --_size; return true; } prev cur; cur cur-_next; } // 未找到key return false; }4. 性能之魂扩容机制与负载因子控制4.1 为什么需要扩容哈希表的性能高度依赖于负载因子Load Factor。负载因子 元素数量 / 桶数量。当负载因子过高时意味着平均每个桶里的链表长度变长查找、插入、删除操作的平均时间复杂度会从理想的O(1)向O(n)退化。标准库的unordered_map默认最大负载因子max_load_factor()通常是1.0。当当前负载因子超过或等于最大负载因子时容器会自动进行“重哈希”rehash即增加桶的数量并将所有已有元素重新计算哈希值放入新的桶中。这是一个相对耗时的操作O(n)但能保证长期操作的效率。4.2 扩容的实现策略在我们的HashTable中我们需要一个CheckAndResize函数在每次插入前检查。void CheckAndResize() { // 如果桶数组为空或者负载因子超过阈值则扩容 if (_size _tables.size()) { // 这里设置负载因子阈值为1.0 size_t newSize GetNextPrime(_tables.size() 0 ? 10 : _tables.size() * 2); std::vectorHashNodeT* newTables(newSize, nullptr); // 遍历旧表的所有节点 for (size_t i 0; i _tables.size(); i) { HashNodeT* cur _tables[i]; while (cur) { HashNodeT* next cur-_next; // 保存下一个节点 // 重新计算在新表中的桶下标 size_t newBucketIndex GetBucketIndexForResize(cur-_data, newSize); // 将当前节点头插到新表的对应桶中 cur-_next newTables[newBucketIndex]; newTables[newBucketIndex] cur; cur next; // 处理下一个节点 } _tables[i] nullptr; // 旧桶置空节点已转移 } // 交换新旧表 _tables.swap(newTables); // newTables离开作用域其内部的空指针会被自动释放 } }踩坑记录扩容时的迭代器失效这是实现哈希表迭代器时最需要注意的一点扩容操作会重新分配桶数组并将所有节点迁移到新的内存位置。这意味着扩容之后所有之前获取的迭代器、指针、引用都将失效除非你像标准库某些实现那样做了特殊处理。在我们的实现中扩容后原有的HashNode节点对象本身没有被delete只是改变了它们_next指针的指向以及它们在桶数组中的位置。因此如果用户持有某个节点的指针这个指针本身仍然有效指向同一个节点对象但通过这个迭代器无法正确遍历到下一个节点因为桶数组已经变了。所以我们必须将扩容视为一个导致所有迭代器失效的操作。在标准库中unordered_map::insert操作在发生重哈希后会导致所有迭代器失效但指向元素的引用和指针仍然有效。我们的简化实现可以遵循这一规则。4.3 素数表的使用GetNextPrime函数用于获取一个大于等于给定数字的素数。使用素数作为桶数量可以减少哈希冲突。我们可以预先定义一个素数数组。inline size_t GetNextPrime(size_t num) { // 一个静态的素数序列 static const size_t primeList[] { 7, 17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949, 21911, 43853, 87719, 175447, 350899, 701819, 1403641, 2807303, 5614657, 11229331, 22458671, 44917381, 89834777, 179669557, 359339171, 718678369, 1437356741, 2147483647 }; for (size_t prime : primeList) { if (prime num) { return prime; } } // 如果数字太大返回列表最后一个最大的素数 return primeList[sizeof(primeList)/sizeof(primeList[0]) - 1]; }5. 迭代器封装让哈希桶支持STL风格遍历5.1 迭代器设计的挑战哈希桶的迭代器比向量vector或链表list的迭代器要复杂因为它需要在两个维度上移动桶内移动在一个桶的链表上从当前节点移动到下一个节点node node-_next。跨桶移动当当前桶的链表遍历完毕后需要找到下一个非空的桶。因此迭代器对象至少需要知道当前指向的节点HashNodeT* _node。所属的哈希表对象HashTableT* _ht以便访问桶数组。当前节点所在的桶下标size_t _bucketIndex用于高效地寻找下一个桶。5.2 迭代器类的实现// 前置声明HashTable因为迭代器需要用它作为友元 template class T, class K, class HashFunc, class KeyOfT class HashTable; template class T, class K, class HashFunc, class KeyOfT struct __HashIterator { typedef HashNodeT Node; typedef __HashIteratorT, K, HashFunc, KeyOfT Self; typedef HashTableT, K, HashFunc, KeyOfT HT; Node* _node; // 当前节点指针 HT* _ht; // 哈希表指针 size_t _bucketIndex; // 当前节点所在的桶下标 __HashIterator(Node* node, HT* ht, size_t bucketIndex) : _node(node) , _ht(ht) , _bucketIndex(bucketIndex) {} // 解引用操作符 T operator*() { return _node-_data; } T* operator-() { return (_node-_data); } // 前置操作符核心难点 Self operator() { if (_node-_next) { // 情况1当前桶内还有下一个节点 _node _node-_next; } else { // 情况2当前桶的链表已遍历完需要找下一个非空桶 _bucketIndex; while (_bucketIndex _ht-_tables.size() _ht-_tables[_bucketIndex] nullptr) { _bucketIndex; } if (_bucketIndex _ht-_tables.size()) { // 找到了下一个非空桶 _node _ht-_tables[_bucketIndex]; } else { // 已经遍历完所有桶迭代器指向end() _node nullptr; // _bucketIndex 可以保持不变或设为无效值 } } return *this; } // 后置操作符 Self operator(int) { Self tmp *this; (*this); return tmp; } bool operator!(const Self it) const { return _node ! it._node; } bool operator(const Self it) const { return _node it._node; } };5.3 在HashTable中提供迭代器接口我们需要在HashTable类中定义迭代器类型并提供begin()和end()方法。template class T, class K, class HashFunc, class KeyOfT class HashTable { // ... 其他成员 public: typedef __HashIteratorT, K, HashFunc, KeyOfT iterator; iterator begin() { // 找到第一个非空桶 for (size_t i 0; i _tables.size(); i) { if (_tables[i]) { return iterator(_tables[i], this, i); } } // 如果表为空返回end() return end(); } iterator end() { // end()迭代器通常用空指针表示 return iterator(nullptr, this, -1); // 桶下标-1表示无效 } // 为了让迭代器能访问HashTable的私有成员_tables需要声明为友元 friend struct __HashIteratorT, K, HashFunc, KeyOfT; };注意事项迭代器失效的严格处理我们的迭代器保存了哈希表对象的指针_ht和桶下标_bucketIndex。这意味着一旦哈希表发生扩容_tables被重新分配和填充所有现有的迭代器内部记录的_bucketIndex很可能就失效了因为节点被移动到了新的桶而迭代器还记录着旧的桶下标继续使用操作会导致未定义行为。因此在文档和使用说明中必须明确指出任何可能引起重哈希的操作如Insert导致扩容都会使所有现有迭代器失效。这是与标准库行为一致的。6. 最终封装实现unordered_map与unordered_set6.1 利用模板与仿函数实现泛型这是整个项目设计最精妙的部分。我们希望用同一个HashTable模板类通过传递不同的模板参数来同时实现unordered_map和unordered_set。它们的核心区别在于存储的数据类型T不同set:T就是Key。map:T是std::pairconst Key, V。从数据T中提取关键字Key的方式不同set: 关键字就是数据本身。map: 关键字是pair的第一个元素first。我们可以通过一个叫做“仿函数”Functor或“函数对象”的模板参数KeyOfT来解决第二个问题。// 用于unordered_set的仿函数Key就是T template class K struct SetKeyOfT { const K operator()(const K key) { return key; } }; // 用于unordered_map的仿函数Key是pair的first template class K, class V struct MapKeyOfT { const K operator()(const std::pairconst K, V kv) { return kv.first; } };6.2 unordered_set的封装实现有了上面的准备unordered_set的封装就非常清晰了。它内部包含一个HashTable成员并将SetKeyOfT作为模板参数传递。template class K, class HashFunc DefaultHashFuncK class unordered_set { private: // 底层哈希表存储的数据类型T就是K用SetKeyOfT来提取Key HashTableK, K, HashFunc, SetKeyOfTK _ht; public: typedef typename HashTableK, K, HashFunc, SetKeyOfTK::iterator iterator; iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } std::pairiterator, bool insert(const K key) { return _ht.Insert(key); } iterator find(const K key) { return _ht.Find(key); } bool erase(const K key) { return _ht.Erase(key); } // ... 其他接口如size(), empty(), clear()等直接调用_ht的对应方法 size_t size() const { return _ht.Size(); } bool empty() const { return _ht.Empty(); } void clear() { _ht.Clear(); } };6.3 unordered_map的封装实现unordered_map的实现类似但存储的数据类型是pair并使用MapKeyOfT仿函数。template class K, class V, class HashFunc DefaultHashFuncK class unordered_map { private: // 注意存储的数据类型T是pairconst K, V // 关键字类型是K用MapKeyOfT来从pair中提取Key HashTablestd::pairconst K, V, K, HashFunc, MapKeyOfTK, V _ht; public: typedef typename HashTablestd::pairconst K, V, K, HashFunc, MapKeyOfTK, V::iterator iterator; iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } std::pairiterator, bool insert(const std::pairconst K, V kv) { return _ht.Insert(kv); } // map特有的operator[]功能强大若key存在返回其value的引用若不存在则插入该key并返回其value的引用。 V operator[](const K key) { std::pairiterator, bool ret _ht.Insert(std::make_pair(key, V())); // ret.first是迭代器指向插入的或已存在的pair return ret.first-second; // 返回value的引用 } iterator find(const K key) { return _ht.Find(key); } bool erase(const K key) { return _ht.Erase(key); } size_t size() const { return _ht.Size(); } // ... 其他接口 };关键技巧operator[]的实现unordered_map::operator[]是STL中非常方便的一个接口。它的实现巧妙地利用了insert的返回值。insert会返回一个pairiterator, bool其中bool表示是否插入成功。operator[]的逻辑是尝试插入一个以key为关键字以V()value类型的默认值为value的键值对。如果key已存在insert什么也不做但返回的迭代器指向已存在的元素如果key不存在insert会成功插入这个新pair。无论哪种情况最后都通过迭代器返回这个pair中value的引用。这使得我们可以像使用数组一样使用mapmap[key] value;。7. 测试、调试与常见问题排查7.1 基础功能测试实现完成后必须进行全面的测试。可以从简单到复杂基本插入与查找测试insert、find、size。去重测试向set插入重复元素检查insert返回的bool值是否为false且size不变。删除测试测试erase删除存在和不存在的元素。遍历测试使用迭代器begin()和end()遍历容器检查元素是否都被访问到且不重复、不遗漏。operator[]测试针对map测试map[key]的读写功能包括对不存在的key进行赋值。7.2 扩容与迭代器失效测试这是最容易出问题的地方。触发扩容编写一个循环插入大量元素比如10000个确保在插入过程中没有崩溃。可以在HashTable的CheckAndResize函数中加入打印语句观察扩容是否被触发。迭代器失效验证在扩容前后获取一个迭代器it。触发扩容后尝试对it进行操作。在我们的实现中这应该会导致程序出错或遍历到错误的位置。这证明了我们的迭代器失效规则。指针/引用有效性测试针对map的value对于map在扩容前获取一个元素的引用V ref map[key]。触发扩容后尝试修改ref。由于节点对象本身没有销毁这个引用应该仍然有效并且修改会成功。这符合标准库的部分规则引用和指针不失效。7.3 常见问题与排查技巧插入后查找不到检查哈希函数确保你的哈希函数对于自定义类型有正确的特化版本。对于自定义类需要重载operator并提供哈希仿函数。检查KeyOfT仿函数在map中确保MapKeyOfT正确地从pair中提取了firstkey。检查桶下标计算在GetBucketIndex函数中打印哈希值和取模后的结果确认计算逻辑正确。内存泄漏实现析构函数HashTable的析构函数必须遍历所有桶删除所有链表节点。实现Clear()函数用于清空所有元素同样需要遍历删除节点并将桶指针置为nullptr。使用Valgrind或AddressSanitizer等工具进行内存检查。迭代器操作死循环或越界仔细检查operator逻辑特别是跨桶寻找的逻辑。确保while循环的条件是_bucketIndex _ht-_tables.size()并且访问_ht-_tables[_bucketIndex]是安全的。处理空表情况当哈希表为空时begin()应该直接返回end()。性能低下监控负载因子如果插入大量数据后性能下降可能是默认的桶数量增长策略如翻倍不够平滑或者哈希函数分布不均匀导致某些桶过长。可以尝试调整最大负载因子比如降到0.75或者优化哈希函数。模板编译错误这类错误信息通常又长又晦涩。关键是从第一个错误看起检查模板参数是否匹配。例如在HashTable中调用KeyOfT仿函数时确保传递给它的参数类型是T而仿函数返回的类型是K。7.4 一个简单的测试用例#include iostream #include string #include MyUnorderedMap.h // 你的头文件 #include MyUnorderedSet.h void TestMap() { my::unordered_mapstd::string, int wordCount; wordCount[apple] 5; wordCount[banana] 3; wordCount[apple] 10; // 修改已存在的key std::cout apple: wordCount[apple] std::endl; // 输出 10 std::cout banana: wordCount[banana] std::endl; // 输出 3 std::cout orange: wordCount[orange] std::endl; // 输出 0 (key不存在但operator[]会插入) std::cout Size: wordCount.size() std::endl; // 输出 3 // 遍历 for (auto kv : wordCount) { std::cout kv.first : kv.second std::endl; } // 查找与删除 auto it wordCount.find(banana); if (it ! wordCount.end()) { wordCount.erase(it); // 通过迭代器删除 // wordCount.erase(banana); // 通过key删除也可以 } std::cout After erase, size: wordCount.size() std::endl; } void TestSet() { my::unordered_setint numSet; for (int i 0; i 100; i) { numSet.insert(i % 10); // 只会插入0-9测试去重 } std::cout Set size (should be 10): numSet.size() std::endl; for (auto it numSet.begin(); it ! numSet.end(); it) { std::cout *it ; } std::cout std::endl; } int main() { TestMap(); std::cout ----- std::endl; TestSet(); return 0; }通过这个从底层哈希桶搭建到迭代器封装最后实现出unordered_map和unordered_set的完整过程你收获的不仅仅是一段可以运行的代码。你深入理解了哈希表这个数据结构的高效与脆弱并存的特质明白了负载因子和扩容的重要性体会了迭代器设计的精巧与陷阱并掌握了利用模板和仿函数实现泛型容器的核心技巧。下次当你再使用std::unordered_map时你看到的将不再是一个黑盒而是一个由桶、链表、哈希函数和负载因子共同构建的、清晰可见的精密机器。这才是动手实现一个轮子的最大意义。
