踏入 C++ 的深邃世界：实现 unordered_set 与 unordered_map 的优雅之旅

Ne0inhk

— 16 min read
踏入 C++ 的深邃世界：实现 unordered_set 与 unordered_map 的优雅之旅
在这里插入图片描述

文章目录

前言

在 C++ 标准库中，unordered_set 和 unordered_map 是常用的哈希容器，分别用于存储唯一元素集合和键值对关联表。它们的实现基于哈希表，因此能在平均
O ( 1 ) O(1) O(1) 时间内完成插入、查找和删除操作。理解它们的实现机制有助于我们更深入地掌握哈希表的核心原理和高效数据结构的设计。本篇文章将详细讲解如何使用 C++ 模板实现 HashTable 类，并基于该类构建 unordered_set 和 unordered_map，同时深入分析每个成员函数及其实现细节。

☎️一、改造HashTable

改造HashTable以适配unordered_map和unordered_set容器，主要涉及到如何根据这两种容器的特性来设计和实现HashTable节点的存储以及相应的操作。unordered_map和unordered_set的主要区别在于它们存储的元素类型：map存储键值对（key-value pairs），而set仅存储唯一的键值（通常是键本身作为值）。尽管如此，它们在底层数据结构（如HashTable）的实现上有很多相似之处。

改造内容：

  • K：key的类型
  • T：如果是unordered_map，则为pair<K, V>; 如果是unordered_set，则为K
  • KeyOfT：通过T来获取key的一个仿函数类
  • HashFunc: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能
    取模

📞1.1 HashNode 类

HashNode 类用于构成链表，用于处理哈希表中冲突的元素。

template<classT>classHashNode{public: T _data;// 键值对 HashNode<T>* _next;// 链表下一个节点的指针HashNode(const T& data):_data(data),_next(nullptr){}};

【详细说明】：

  • _data 存储键值对或元素本身。
  • _next 指针用于形成链表，处理哈希冲突。
  • const 用在构造函数参数 const T& data 中，确保插入时不会修改原始数据，保证了数据的安全传递。

📞1.2 HashTable类框架

template<classK,classT,classKeyOfT,classHashFunc= DefaultHashFunc<K>>classHashTable{typedef HashNode<T> Node;// 友元声明template<classK,classT,classPtr,classRef,classKeyOfT,classHashFunc>friendstructHTIterator;public:typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;typedef HTIterator<K, T,const T*,const T&, KeyOfT, HashFunc> const_iterator;// ...成员函数private: vector<Node*> _table;// 指针数组 size_t _n =0;// 存储了多少有效数据};
  • 注意：HTIterator 迭代器结构声明为 HashTable 的友元，以便访问哈希表的私有成员变量 _table 和 _n。这种设计使得迭代器能够顺利地访问哈希表内部的桶和数据，实现无缝的遍历功能。

📞1.3 插入操作 Insert

pair<iterator,bool>Insert(const T& data){ HashFunc hf; KeyOfT kot;// 检查是否存在相同的元素 iterator it =Find(kot(data));if(it !=end()){returnmake_pair(iterator(it),false);}// 扩容逻辑，当负载因子为1时扩容if(_n == _table.size()){ size_t newSize = _table.size()*2; vector<Node*>newTable(newSize,nullptr);// 将旧表中的节点重新分配到新表for(size_t i =0; i < _table.size();++i){ Node* cur = _table[i];while(cur){ Node* next = cur->_next; size_t hashi =hf(kot(cur->_data))% newSize; cur->_next = newTable[hashi]; newTable[hashi]= cur; cur = next;}} _table.swap(newTable);}// 插入新节点到表中 size_t hashi =hf(kot(data))% _table.size(); Node* newnode =newNode(data); newnode->_next = _table[hashi]; _table[hashi]= newnode;++_n;returnmake_pair(iterator(newnode,this),true);}

【详细说明】：

  1. 查找重复元素：Find 函数被用来检查表中是否已经存在与 data 相同的元素。如果找到相同的元素，则返回一个指向该元素的迭代器以及 false 表示插入失败。
  2. 扩容逻辑：如果哈希表中已存储的元素数量 _n 达到或超过当前桶数 _table.size()（即负载因子为 1），则执行扩容操作，将哈希表的大小增加一倍。
    • 重新计算旧表中每个节点的哈希值，并将节点重新插入到新表的适当位置。
    • 扩容后使用 swap 替换旧表，这种方式可以避免拷贝新表中的元素，提高效率。
  3. 插入新节点：通过计算哈希值来确定新元素的插入位置 hashi，并将新节点 newnode 插入到对应桶的链表头部（使用头插法）。
  4. const 的使用：
    • 函数参数 const T& data 保证传入的数据在插入过程中不会被修改。
    • const 确保了数据传递的安全性，避免数据在插入时发生意外更改。

📞1.4 查找操作 Find

iterator Find(const K& key){ HashFunc hf; KeyOfT kot; size_t hashi =hf(key)% _table.size(); Node* cur = _table[hashi];while(cur){if(kot(cur->_data)== key){returniterator(cur,this);} cur = cur->_next;}returniterator(nullptr,this);}

【详细说明】：

  1. 定位桶：通过哈希函数计算 key 的哈希值，找到对应的桶位置 hashi。在此位置上可以通过链表查找目标元素。
  2. 遍历链表：从桶的链表头开始，逐一检查每个节点的键值。如果找到与 key 匹配的节点，则返回指向该节点的迭代器。
  3. 返回空迭代器：如果遍历完链表后仍未找到匹配的键，则返回一个空迭代器（nullptr）。
  4. const 的使用：
    • 参数 const K& key 保证在查找过程中不会修改传入的键值，确保了查找操作的安全性和一致性。
    • const 修饰 key 可以避免传递过程中被无意改变，从而保证数据的一致性。

📞1.5 删除操作 Erase

boolErase(const K& key){ HashFunc hf; KeyOfT kot; size_t hashi =hf(key)% _table.size(); Node* prev =nullptr; Node* cur = _table[hashi];while(cur){if(kot(cur->_data)== key){if(prev ==nullptr){ _table[hashi]= cur->_next;}else{ prev->_next = cur->_next;}--_n;delete cur;returntrue;} prev = cur; cur = cur->_next;}returnfalse;}

【详细说明】：

  1. 定位桶并遍历链表：通过哈希值定位 key 对应的桶 hashi，然后遍历该桶的链表查找目标节点。
  2. 删除目标节点：
    • 如果目标节点在链表的头部，则将桶的头指针指向目标节点的下一个节点。
    • 如果目标节点在链表的中间或尾部，则通过 prev->_next = cur->_next 跳过目标节点，将其从链表中移除。
  3. 更新元素数量：删除目标节点后，减少元素计数 _n，并释放节点内存。
  4. 返回删除结果：若删除成功则返回 true，否则返回 false。
  5. const 的使用：
    • const K& key 参数修饰确保在删除过程中不会修改 key。
    • const 在这里保证了删除过程的安全性，不会意外更改 key，确保查找与删除逻辑的一致性。

📞1.6 析构函数~HashTable()

~HashTable(){for(size_t i =0; i < _table.size();++i){ Node* cur = _table[i];while(cur){ Node* next = cur->_next;delete cur; cur = next;} _table[i]=nullptr;}}

【详细说明】：

  1. 遍历哈希表的每个桶：
    • for (size_t i = 0; i < _table.size(); ++i) 循环用于访问哈希表中的每一个桶。_table.size() 是桶的数量。
  2. 遍历每个桶的链表：
    • Node* cur = _table[i]; 获取桶的链表头指针 cur。
    • while (cur) 表示当 cur 不为空时，继续删除链表的节点。
  3. 逐节点释放链表：
    • Node* next = cur->_next; 在删除 cur 之前，先保存当前节点的下一个节点 next。
    • delete cur; 删除当前节点以释放其内存。
    • cur = next; 更新 cur 指针为 next，即指向下一个节点，重复此过程直至链表尾部。
  4. 清空桶指针：
    • _table[i] = nullptr; 将当前桶指针置为 nullptr，确保析构后哈希表的所有桶均为空指针。

☎️二、 HTIterator 迭代器简介

HTIterator 是 HashTable 的自定义迭代器结构，支持遍历哈希表中的每一个元素。它通过遍历链表节点 _node 和跳转到非空桶位置，实现无序遍历。通过重载操作符，它具备了和标准迭代器类似的操作功能。

📞2.1 前置声明

template<classK,classT,classKeyOfT,classHashFunc>classHashTable;

由于 HTIterator 中引用了 HashTable，而 HashTable 中也可能引用 HTIterator，因此需要在声明 HashTable 前先进行前置声明，以避免编译时出现未定义的行为。

📞2.2 成员变量

Node* _node;const HashTable<K, T, KeyOfT, HashFunc>* _pht;
  • _node：指向当前遍历的链表节点。
  • _pht：指向迭代器所属的哈希表实例，允许迭代器在链表结束后跳转到下一个非空桶，继续遍历。

const 修饰哈希表指针 _pht，确保迭代器在遍历过程中不会修改哈希表结构，提高了安全性。

📞2.3 构造函数

HTIterator(Node* node,const HashTable<K, T, KeyOfT, HashFunc>* pht):_node(node),_pht(pht){}
  • 构造函数初始化 _node 和 _pht，使得迭代器具备遍历链表和桶的能力。
  • 这里的 const 确保哈希表指针 _pht 不会被修改。

📞2.4 拷贝构造函数

HTIterator(const Iterator& it):_node(it._node),_pht(it._pht){}
  • 允许从另一个普通迭代器 Iterator 进行构造，用于将普通迭代器转换为 const_iterator。

📞2.5 operator* 和 operator->

Ref operator*(){return _node->_data;}
  • 解引用运算符，返回当前 _node 所指向节点的值 _data。
  • 返回类型 Ref 允许返回 T& 或 const T&，实现灵活的访问。
Ptr operator->(){return&_node->_data;}
  • 提供成员访问功能，返回当前节点的数据地址（指针）。
  • 返回类型 Ptr 允许返回 T* 或 const T*。

📞2.6 自增操作符 operator++

Self&operator++(){if(!_node ||!_pht)return*this;// 边界检查if(_node->_next){ _node = _node->_next;}else{ KeyOfT kot; HashFunc hf; size_t hashi =hf(kot(_node->_data))% _pht->_table.size();// 查找下一个非空桶++hashi;while(hashi < _pht->_table.size()&& _pht->_table[hashi]==nullptr){++hashi;}// 若找到下一个非空桶，更新 _node；否则置为 nullptr _node =(hashi < _pht->_table.size())? _pht->_table[hashi]:nullptr;}return*this;}

【详细说明】：

  1. 边界检查：如果 _node 或 _pht 为 nullptr，直接返回当前迭代器，不进行操作。
  2. 遍历链表节点：如果当前节点有下一个节点 _next，则直接将 _node 移动到 _next，继续链表的遍历。
  3. 跳转到下一个非空桶：
    • 若当前链表遍历完毕，通过哈希函数定位到当前元素所在的桶 hashi。
    • 自增 hashi，开始查找下一个非空桶的位置。
    • 若找到下一个非空桶，则将 _node 指向该桶的第一个节点；若无更多桶，则将 _node 置为 nullptr，表示迭代结束。
  4. 返回迭代器引用：返回 *this 使得该操作符支持前置自增的链式调用。

📞2.7operator!= 和 operator==

booloperator!=(const Self& s){return _node != s._node;}
  • 比较两个迭代器是否指向不同的节点。
  • 用于迭代结束检查，若 _node 指针不同则返回 true，表示未到达结束。
booloperator==(const Self& s){return _node == s._node;}
  • 比较两个迭代器是否指向相同的节点。
  • 若 _node 指针相同，则返回 true，用于判断两个迭代器是否相等。

☎️三、Unordered_Set 的实现

unordered_set 是一个无序集合，包含唯一的元素，不支持重复插入。为了实现 unordered_set，我们使用了前面定义的 HashTable。unordered_set 通过 HashTable 来完成元素的存储和冲突解决。

📞3.1 unordered_set 的基本设计

unordered_set 通过哈希表 HashTable 存储集合中的元素。为了从 HashTable 中获取键，unordered_set 中定义了一个 SetKeyOfT 仿函数类：

namespace xny {template<classK>classunordered_set{structSetKeyOfT{const K&operator()(const K& key){return key;}};public:typedeftypenamehash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;typedeftypenamehash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator; pair<iterator,bool>insert(const K& key){ pair<typenamehash_bucket::HashTable<K, K, SetKeyOfT>::iterator,bool> ret = _ht.Insert(key);return pair<const_iterator,bool>(ret.first, ret.second);} iterator begin(){return _ht.begin();} iterator end(){return _ht.end();} const_iterator begin()const{return _ht.begin();} const_iterator end()const{return _ht.end();}private: hash_bucket::HashTable<K, K, SetKeyOfT> _ht;};}

📞3.2 详细分析每个函数

    • const 修饰符确保传入的 key 不会在插入过程中被修改。
    • pair<const_iterator, bool> 确保返回类型的安全性，使得外部代码无法修改集合中的元素。

begin 和 end: begin 和 end 返回集合的起始和结束迭代器，以支持集合的遍历。它们调用哈希表的 begin 和 end 方法。

iterator begin(){return _ht.begin();} iterator end(){return _ht.end();}

这两个函数还分别提供了 const 版本，允许在常量上下文中进行集合遍历操作。

insert: insert 函数用于向集合中插入一个元素。它调用 _ht.Insert(key) 方法将元素插入到哈希表中，并返回一个 pair，包含一个指向新插入元素的迭代器和一个布尔值，表示插入是否成功。

pair<iterator,bool>insert(const K& key){ pair<typenamehash_bucket::HashTable<K, K, SetKeyOfT>::iterator,bool> ret = _ht.Insert(key);return pair<const_iterator,bool>(ret.first, ret.second);}

📞3.3 Unordered_Set 测试

以下代码展示了 unordered_set 的基本操作：

xny::unordered_set<int> uset; uset.insert(10); uset.insert(20); uset.insert(30);for(auto it = uset.begin(); it != uset.end();++it){ cout <<*it <<" ";}
在这里插入图片描述

此测试代码向集合插入几个整数，并使用迭代器遍历集合，输出结果不保证顺序，但每个元素唯一。

☎️四、Unordered_Map 的实现

unordered_map 是一种无序的关联容器，存储键值对（key-value），通过键来快速访问对应的值。与 unordered_set 类似，unordered_map 也依赖 HashTable 实现底层存储。

📞4.1 unordered_map 的基本设计

unordered_map 通过哈希表 HashTable 存储键值对。为了支持键值对的存储，它定义了一个 MapKeyOfT 仿函数，用于从键值对中提取键：

namespace xny {template<classK,classV>classunordered_map{structMapKeyOfT{const K&operator()(const pair<const K, V>& kv){return kv.first;}};public:typedeftypenamehash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedeftypenamehash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator; pair<const_iterator,bool>insert(const pair<K, V>& kv){return _ht.Insert(kv);} V&operator[](const K& key){ pair<iterator,bool> ret = _ht.Insert(make_pair(key,V()));return ret.first->second;} iterator begin(){return _ht.begin();} iterator end(){return _ht.end();} const_iterator begin()const{return _ht.begin();} const_iterator end()const{return _ht.end();}private: hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;};}

📞4.2 详细分析每个函数

    • 这里的 pair<const_iterator, bool> 确保返回的键值对不可被外部代码修改，保证了数据安全性。
    • const 修饰符用于 insert 函数的参数 kv，以确保键值对在插入时不被修改。
    • const 确保传入的 key 不会在操作过程中被修改。
    • 若键不存在，通过 make_pair 创建一个默认值，并插入哈希表。

begin 和 end: begin 和 end 返回容器的起始和结束迭代器，用于遍历 unordered_map 的所有键值对。

iterator begin(){return _ht.begin();} iterator end(){return _ht.end();}

同样，提供了 const 版本的 begin 和 end，使得可以在 const 上下文中遍历容器。

operator[]: operator[] 提供通过键访问对应值的方式，若键不存在则插入一个默认值，若存在则直接返回对应的值。

V&operator[](const K& key){ pair<iterator,bool> ret = _ht.Insert(make_pair(key,V()));return ret.first->second;}

insert: insert 函数用于插入键值对。它调用哈希表的 _ht.Insert(kv) 方法，并返回一个 pair，包含一个指向新插入键值对的迭代器和一个布尔值，表示是否成功插入。

pair<const_iterator,bool>insert(const pair<K, V>& kv){return _ht.Insert(kv);}

📞4.3 Unordered_Map 测试

以下代码展示了 unordered_map 的基本操作：

xny::unordered_map<string,int> umap; umap["apple"]=3; umap["banana"]=5; umap["orange"]=8;for(auto it = umap.begin(); it != umap.end();++it){ cout << it->first <<" : "<< it->second << endl;}
在这里插入图片描述

此代码演示了通过 operator[] 插入键值对以及使用迭代器遍历容器的方式。它展示了 unordered_map 的键值对存储和查找功能。

结语

通过实现 HashTable 以及基于它构建 unordered_set 和 unordered_map，我们不仅深入了解了哈希表的基本操作和冲突解决方法，还学习了如何使用 C++ 模板和仿函数来设计通用数据结构。此外，本文还讨论了 const 的使用技巧，以确保在数据访问时增强安全性和可读性。掌握这些实现细节，可以帮助我们更好地理解 STL 的实现原理，并在日常开发中设计出高效、可复用的数据结构。希望本文能够对您深入理解哈希表和无序容器的实现有所帮助！

在这里插入图片描述

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，17的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是17前进的动力！

在这里插入图片描述

Read more

SPI通信失败排查：c++spidev0.0读取255的数据意义解读

SPI通信读到255？别慌，这可能是你的系统在“求救” 你有没有遇到过这种情况：C++程序通过 /dev/spidev0.0 读取SPI设备，结果每次拿到的都是 255 （即 0xFF ）？ 代码明明写得没问题， ioctl(SPI_IOC_MESSAGE) 也执行成功了，但数据就是不对劲。 这时候千万别急着怀疑人生—— 这不是玄学，而是硬件世界在用最直白的方式告诉你：“我根本没连上！” 今天我们就来深挖这个经典问题的本质。从底层信号讲到驱动实现，再到实战排查路径，带你把“读出255”这件事彻底看透。 一、现象背后的真相：为什么是255？ 先破个题：“c++spidev0.0 read读出来255”，这句话其实有点误导性。 它不是 read() 调用返回255 注意！我们说的“read”并不是真的调用了 read(fd,

By Ne0inhk
【Linux/C++网络篇(一) 】网络编程入门：一文搞懂 TCP/UDP 编程模型与 Socket 网络编程

【Linux/C++网络篇(一) 】网络编程入门：一文搞懂 TCP/UDP 编程模型与 Socket 网络编程

⭐️在这个怀疑的年代，我们依然需要信仰。 个人主页：YYYing. ⭐️Linux/C++进阶系列专栏：【从零开始的linux/c++进阶编程】 系列上期内容：【Linux/C++多线程篇(二) 】同步互斥机制& C++ 11下的多线程 系列下期内容：暂无 目录 引言：程序如何“联网”？ 网络编程基本概念 一、字节序 二、IP地址 IP地址的分类 特殊的IP地址 点分十进制 三、端口号 端口号的分类 网络编程基础 一、套接字（socket）的概念 二、基于TCP面向连接的通信方式  📖 bind函数  📖 listen函数  📖 accept函数  📖 recv、send数据收发  📖 close关闭套接字  📖 connect连接函数

By Ne0inhk
字节跳动 Linux C/C++ 后端 面经

字节跳动 Linux C/C++ 后端 面经

今天和大家分享 字节跳动 后端 面试~ 在竞争激烈的后端开发岗位中，大厂面试不仅考察知识的广度，更注重对技术原理的深度理解和实际应用能力。 这20多个问题几乎覆盖了后端工程师必须掌握的所有核心知识点。 如果你也在准备后端面试，不妨看看下面这些问题是否都能对答如流。 Part1、Http 请求中有哪些请求方式？ 考察重点：HTTP 协议的请求方法语义、适用场景区分，避免仅罗列不说明用途。 回答思路： 按 “常用 + 少见” 分类，结合后端业务场景说明： 常用方法： * GET：查询资源（如商品详情），幂等（多次请求结果一致）、安全（不修改资源），参数拼在 URL（长度有限制）； * POST：提交资源（如用户注册），非幂等（多次提交可能重复创建），参数放请求体（支持大体积数据、二进制）； * PUT：全量更新资源（如修改用户信息），幂等（多次更新结果一致），需指定资源唯一标识（如

By Ne0inhk
C++:set/multiset和map/multimap文档详细解析

C++:set/multiset和map/multimap文档详细解析

Hello大家好！ 很高兴与大家见面！ 给生活添点快乐，开始今天的编程之路。 我的博客:<但愿. 我的专栏:C语言、题目精讲、算法与数据结构、C++ 欢迎点赞，关注 目录   前言   一 容器的分类(根据容器中各个数据之间的关系）          1.1序列式容器                  1.1.1序列式容器的概念                  1.1.2序列式容器的例子           1.2关联式容器                  1.2.1关联式容器的概念                  1.2.2关联式容器的例子   二  set/multiset           2.1参考文档(multiset包在set中所以其没有头文件）           2.2set类的介绍                   2.2.1set类的实现的简单介绍                  2.2.2set类的接口介绍                           2.

By Ne0inhk