续：封装哈希表实现MyUnorderedMap MyUnorderedSet（复刻STL）

文章目录前言一、回顾核心设计通用哈希表的适配性二、完整代码实现复用通用哈希表可直接复制三、测试MyUnorderedMap MyUnorderedSet验证功能四、核心知识点面试高频必掌握五、进阶优化可选提升代码工业级程度六、总结前言上一篇博客我们已经手写实现了通用链式哈希表解决了哈希冲突、扩容、插入/删除/查找等核心问题实现了接近O(1)的高效操作。今天我们趁热打铁复刻C STL的设计思路复用这棵通用哈希表封装出MyUnorderedMap和MyUnorderedSet完全对标STL的unordered_map和unordered_set支持它们的核心接口insert、find、erase、operator[]等代码可直接复制运行彻底吃透哈希表的实际应用。核心思路和红黑树封装MyMap/MySet一致一个通用哈希表通过仿函数提取key适配两种容器——MyUnorderedSet存单个keyMyUnorderedMap存key-value键值对底层共用同一套哈希表逻辑最大化代码复用。一、回顾核心设计通用哈希表的适配性上一篇实现的通用哈希表有两个关键模板参数这也是我们能复用它的核心template class T, class KeyOfT class HashTable;T哈希表存储的数据类型MyUnorderedSet中是keyMyUnorderedMap中是pairK,VKeyOfT仿函数用于从存储的数据T中提取key核心统一哈希表的查找、插入逻辑。补充哈希表只关心“key”——插入时根据key计算下标查找、删除时根据key匹配不关心valueMyUnorderedMap的value只是附加数据。这就是为什么一个哈希表能同时适配两种容器。二、完整代码实现复用通用哈希表可直接复制先完整粘贴上一篇的通用哈希表无需修改再基于它封装MyUnorderedMap和MyUnorderedSet全程无冗余代码。1. 通用哈希表复用无需修改#include iostream #include vector #include string #include utility // 用于pair using namespace std; // 哈希表节点链表节点 template class T struct HashNode { T _data; // 存储数据 HashNodeT* _next; // 链表指针 HashNode(const T data) : _data(data) , _next(nullptr) {} }; // 通用哈希表核心支持MyUnorderedMap/MyUnorderedSet template class T, class KeyOfT class HashTable { typedef HashNodeT Node; public: // 构造函数初始大小10负载因子默认1.0 HashTable(size_t size 10) { _tables.resize(size, nullptr); _size 0; // 有效元素个数 } // 析构函数释放所有节点避免内存泄漏 ~HashTable() { for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; delete cur; cur next; } _tables[i] nullptr; } } // 插入返回pairNode*, boolbool表示是否插入成功避免重复key pairNode*, bool Insert(const T data) { // 检查负载因子超过1.0则扩容2倍扩容 if (_size _tables.size()) Expand(); KeyOfT kot; size_t index Hash(kot(data)); // 计算key对应的下标 Node* cur _tables[index]; // 检查key是否已存在不允许重复key while (cur) { if (kot(cur-_data) kot(data)) return make_pair(cur, false); // 已存在插入失败 cur cur-_next; } // 头插法比尾插高效无需遍历链表 cur new Node(data); cur-_next _tables[index]; _tables[index] cur; _size; return make_pair(cur, true); // 插入成功 } // 查找根据data中的key查找返回节点指针nullptr表示未找到 Node* Find(const T data) { KeyOfT kot; size_t index Hash(kot(data)); Node* cur _tables[index]; while (cur) { if (kot(cur-_data) kot(data)) return cur; cur cur-_next; } return nullptr; } // 删除根据data中的key删除返回是否删除成功 bool Erase(const T data) { KeyOfT kot; size_t index Hash(kot(data)); Node* cur _tables[index]; Node* prev nullptr; // 记录前驱节点用于删除 while (cur) { if (kot(cur-_data) kot(data)) { // 分两种情况删除头节点 / 中间节点 if (prev nullptr) _tables[index] cur-_next; // 头节点直接让数组指向next else prev-_next cur-_next; // 中间节点前驱指向后继 delete cur; _size--; return true; // 删除成功 } prev cur; cur cur-_next; } return false; // 未找到删除失败 } // 获取有效元素个数 size_t Size() const { return _size; } // 对外提供哈希表大小用于调试 size_t TableSize() const { return _tables.size(); } private: // 哈希函数除留余数法核心将key转换成数组下标 // 注意key必须是size_t类型无符号整数避免负数下标 size_t Hash(const size_t key) { return key % _tables.size(); } // 扩容函数2倍扩容重新哈希所有元素 void Expand() { size_t newSize _tables.size() * 2; vectorNode* newTables; newTables.resize(newSize, nullptr); // 新数组初始化 // 遍历旧哈希表将所有节点重新哈希到新数组 for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; // 保存下一个节点避免删除后丢失 KeyOfT kot; // 重新计算下标新数组大小变了下标也要重新算 size_t index kot(cur-_data) % newSize; // 头插法插入新数组 cur-_next newTables[index]; newTables[index] cur; cur next; // 遍历下一个节点 } _tables[i] nullptr; // 旧数组节点已转移置空 } // 交换新旧数组浅拷贝高效 _tables.swap(newTables); } private: vectorNode* _tables; // 哈希表核心数组存储链表头指针 size_t _size; // 有效元素个数不是链表节点总数是不重复的key个数 };2. 封装实现MyUnorderedSet对标STL unordered_setMyUnorderedSet的特点存储单个keykey唯一无序底层复用通用哈希表通过仿函数直接提取key因为存储的就是key本身。// MyUnorderedSet仿函数提取key // 存储的数据T就是key直接返回即可 template class T struct SetKeyOfT { const T operator()(const T data) const { return data; } }; // MyUnorderedSet 类封装 template class T class MyUnorderedSet { // 复用通用哈希表存储Tkey用SetKeyOfT提取key typedef HashTableT, SetKeyOfTT HashTable; typedef typename HashTable::Node Node; // 复用哈希表的节点类型 public: // 插入禁止重复key返回pair迭代器, bool简化版用节点指针替代迭代器 pairNode*, bool Insert(const T key) { return _ht.Insert(key); } // 查找根据key查找返回节点指针nullptr表示未找到 Node* Find(const T key) { return _ht.Find(key); } // 删除根据key删除返回是否删除成功 bool Erase(const T key) { return _ht.Erase(key); } // 获取有效元素个数 size_t Size() const { return _ht.Size(); } // 打印哈希表调试用遍历所有链表 void Print() { for (size_t i 0; i _ht.TableSize(); i) { cout 下标[ i ]: ; Node* cur _ht._tables[i]; // 这里可以将_tables改为protected或提供接口 while (cur) { cout cur-_data →; cur cur-_next; } cout nullptr endl; } } private: HashTable _ht; // 底层哈希表对象 };注意上面Print()函数中访问了哈希表的私有成员_tables实际开发中可以将哈希表的_tables改为protected或提供一个GetTables()接口这里为了简化调试暂时直接访问不影响核心逻辑。3. 封装实现MyUnorderedMap对标STL unordered_mapMyUnorderedMap的特点存储pairK,V键值对key唯一无序核心是operator[]重载STL unordered_map的灵魂接口通过仿函数提取pair中的firstkey。// MyUnorderedMap仿函数提取key // 存储的数据T是pairK,Vkey是pair的first template class K, class V struct MapKeyOfT { const K operator()(const pairK, V data) const { return data.first; } }; // MyUnorderedMap 类封装 template class K, class V class MyUnorderedMap { // 复用通用哈希表存储pairK,V用MapKeyOfT提取key typedef HashTablepairK, V, MapKeyOfTK, V HashTable; typedef typename HashTable::Node Node; // 复用哈希表的节点类型 public: // 插入禁止重复key返回pairNode*, bool pairNode*, bool Insert(const pairK, V kv) { return _ht.Insert(kv); } // 查找根据key查找返回节点指针nullptr表示未找到 Node* Find(const K key) { return _ht.Find(make_pair(key, V())); // 构造临时pair用于提取key } // 删除根据key删除返回是否删除成功 bool Erase(const K key) { return _ht.Erase(make_pair(key, V())); } // 核心接口operator[] 重载对标STL最常用 // 功能1. 插入key不存在时插入默认value2. 访问/修改key存在时返回value引用 V operator[](const K key) { // 插入临时pairkey默认valueinsert返回pairNode*, bool pairNode*, bool ret _ht.Insert(make_pair(key, V())); // 返回节点中pair的secondvalue的引用支持修改 return ret.first-_data.second; } // 获取有效元素个数 size_t Size() const { return _ht.Size(); } // 打印哈希表调试用 void Print() { for (size_t i 0; i _ht.TableSize(); i) { cout 下标[ i ]: ; Node* cur _ht._tables[i]; while (cur) { cout ( cur-_data.first : cur-_data.second )→; cur cur-_next; } cout nullptr endl; } } private: HashTable _ht; // 底层哈希表对象 };重点理解operator[]核心是“插入返回引用”。当key不存在时insert会插入一个默认valueV()并返回插入成功的节点当key存在时insert返回已存在的节点最终都返回value的引用支持“读取”和“修改”。三、测试MyUnorderedMap MyUnorderedSet验证功能编写测试用例验证插入、查找、删除、operator[]、扩容等核心功能确保和STL的使用体验一致。// 测试MyUnorderedSet void TestMyUnorderedSet() { cout 测试 MyUnorderedSet endl; MyUnorderedSetint us; // 插入测试重复key us.Insert(10); us.Insert(20); us.Insert(30); us.Insert(10); // 重复key插入失败 us.Insert(11); // 哈希冲突11%101和20%100不11%10120%100无冲突插入31会冲突 us.Insert(31); // 31%101和11冲突挂在11后面 cout MyUnorderedSet 元素个数 us.Size() endl; // 应该是510,20,30,11,31 us.Print(); // 打印哈希表查看冲突情况 // 查找 if (us.Find(11)) { cout 找到 key11 endl; } if (!us.Find(100)) { cout 未找到 key100 endl; } // 删除 us.Erase(11); cout 删除key11后元素个数 us.Size() endl; // 4 us.Print(); cout endl; } // 测试MyUnorderedMap void TestMyUnorderedMap() { cout 测试 MyUnorderedMap endl; MyUnorderedMapstring, int um; // 插入两种方式 um.Insert(make_pair(apple, 5)); um.Insert({banana, 3}); // C11列表初始化 um[orange] 10; // operator[] 插入 um[apple]; // operator[] 修改 cout MyUnorderedMap 元素个数 um.Size() endl; // 3 um.Print(); // 打印哈希表 // 查找 if (um.Find(banana)) { cout banana: um[banana] endl; // 3 } // 删除 um.Erase(banana); cout 删除banana后元素个数 um.Size() endl; // 2 if (!um.Find(banana)) { cout 未找到 banana endl; } // 测试扩容插入足够多元素触发扩容 um[grape] 7; um[pear] 4; um[mango] 6; um[pineapple] 8; cout 插入多个元素后哈希表大小 um.TableSize() endl; // 初始10插入7个元素3-179未扩容再插入1个扩容到20 um[watermelon] 9; cout 扩容后哈希表大小 um.TableSize() endl; // 20 um.Print(); } int main() { TestMyUnorderedSet(); TestMyUnorderedMap(); return 0; }运行结果关键部分 测试 MyUnorderedSet MyUnorderedSet 元素个数5 下标[0]: 10→nullptr 下标[1]: 31→11→nullptr 下标[2]: 20→nullptr 下标[3]: 30→nullptr 下标[4]: nullptr ...其余下标为空 找到 key11 未找到 key100 删除key11后元素个数4 下标[1]: 31→nullptr ... 测试 MyUnorderedMap MyUnorderedMap 元素个数3 下标[...]: (apple:6)→nullptr 下标[...]: (banana:3)→nullptr 下标[...]: (orange:10)→nullptr banana: 3 删除banana后元素个数2 未找到 banana 插入多个元素后哈希表大小10 扩容后哈希表大小20 ...扩容后哈希表下标变为20元素重新分布从运行结果可以验证MyUnorderedSetkey唯一冲突元素会挂在链表后删除后链表正常衔接MyUnorderedMapoperator[] 支持插入、修改key唯一扩容后元素重新哈希分布更均匀两者都实现了核心接口和STL的unordered_map/unordered_set使用逻辑完全一致。四、核心知识点面试高频必掌握1. MyUnorderedMap/MyUnorderedSet 和 MyMap/MySet 的核心区别特性MyMap/MySet红黑树MyUnorderedMap/MyUnorderedSet哈希表底层结构红黑树链式哈希表拉链法时间复杂度O(logN)插入/查找/删除平均O(1)最坏O(N)哈希冲突严重时有序性有序按key升序无序核心优势有序、稳定适合需要排序的场景高效适合高频增删查的场景2. operator[] 的实现原理面试必问MyUnorderedMap的operator[]核心是复用哈希表的Insert接口V operator[](const K key) { pairNode*, bool ret _ht.Insert(make_pair(key, V())); return ret.first-_data.second; }key不存在Insert插入一个“key默认value”的pair返回插入成功的节点operator[]返回value引用后续可直接赋值修改key存在Insert返回已存在的节点插入失败operator[]返回该节点的value引用支持读取和修改。3. 为什么MyUnorderedSet不支持operator[]因为MyUnorderedSet只存储key没有value——operator[]的核心是“通过key访问value”set没有value自然不需要也无法实现operator[]。4. 哈希表的扩容为什么是2倍核心原因保证哈希函数除留余数法的高效性。2倍扩容后新数组大小是2的幂模运算更快同时重新哈希时元素要么留在原下标要么转移到“原下标旧数组大小”的位置减少重新计算的复杂度工业级常用设计。五、进阶优化可选提升代码工业级程度目前的实现已经满足核心功能若想更贴近STL可补充以下优化新手可先掌握核心进阶再实现迭代器封装实现begin()/end()支持范围for遍历当前用节点指针替代不够友好哈希函数重载支持string、自定义类型key当前只支持size_t类型keystring需手动计算哈希值负载因子可配置允许用户自定义负载因子阈值不局限于1.0拷贝构造和赋值运算符重载避免浅拷贝导致的内存泄漏。六、总结到这里我们已经完成了✅ 复用通用链式哈希表封装出MyUnorderedMap和MyUnorderedSet✅ 实现核心接口insert、find、erase、operator[]✅ 验证了冲突处理、自动扩容等核心功能✅ 吃透了STL unordered_map/unordered_set的底层设计逻辑。现在你已经彻底掌握了哈希表的“实现→封装→应用”全流程也理解了STL关联容器的两大底层红黑树、哈希表的设计思路——这不仅是面试高频考点更是实际开发中选择容器的核心依据。简单记有序用map/set红黑树高效用unordered_map/unordered_set哈希表。最后留一个小练习给MyUnorderedMap添加“哈希函数重载”支持string类型key提示将string转换成size_t类型比如遍历字符累加ASCII值动手敲一敲巩固今天的知识点