////// 欢迎来到 aramae 的博客愿 Bug 远离好运常伴 //////博主的Gitee地址阿拉美 (aramae) - Gitee.com时代不会辜负长期主义者愿每一个努力的人都能达到理想的彼岸。目录1. 哈希表数据结构基础1.1 为什么需要哈希表1.2 哈希概念1.3 哈希冲突1.4 哈希函数设计原则常见哈希函数1.5 哈希冲突解决1.5.1 闭散列开放定址法1线性探测2二次探测1.5.2 开散列链地址法结构示意实现扩容处理非整数关键码素数表1.6 开散列与闭散列比较2.unordered系列关联式容器2.1 unordered_map2.2 unordered_set2.3 两容器的常用接口使用案例unorder_map常用接口1. 构造与插入​编辑2. 查找元素​编辑3. 删除元素​编辑4. 容量与清空5. 桶操作接口6. 综合案例统计单词频率unorder_set常用接口1. 构造与插入2. 查找元素3. 删除元素4. 综合案例去除重复元素5. 综合案例两个数组的交集哈希表数据结构基础unordered系列关联式容器引言在C标准库中std::map和std::set基于红黑树实现能够保证元素有序但查找、插入、删除的时间复杂度为O(log N)。当数据量极大时对数时间依然可能成为瓶颈。C11引入的unordered_map、unordered_set等系列容器底层采用哈希表在理想情况下可以达到常数时间的操作效率。本文将带领读者从零开始理解哈希表数据结构进而剖析STL中unordered容器的设计最后探讨如何将底层哈希表封装成易用的容器接口。1. 哈希表数据结构基础1.1 为什么需要哈希表在顺序结构如数组、链表和树结构中元素的存储位置与关键码之间没有直接关系查找时必须通过比较关键码才能定位。理想情况下我们希望能够不经过任何比较一次直接访问到目标元素。哈希表正是为此而生它通过一个哈希函数将关键码映射为存储地址从而实现快速访问。1.2 哈希概念在顺序结构如数组、链表和平衡树中元素关键码与存储位置之间没有直接对应关系查找需经过多次比较。顺序查找 O(N)平衡树 O(log N)。理想情况是不经过任何比较一次直接得到元素。哈希方法通过一个哈希函数hashFunc建立关键码与存储位置的一一映射。插入时根据关键码计算位置存放查找时再次计算位置取出元素比较关键码。例如集合 {1,7,6,4,5,9}设hash(key) key % 10则存储位置为 {1,7,6,4,5,9}。用该方法进行搜索不必进行多次关键码的比较因此搜索的速度比较快问题按照上述哈希方式向集合中插入元素44会出现什么问题插入 44 时44 % 10 4但位置 4 已被 4 占据产生冲突叫做哈希冲突。1.3 哈希冲突不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突 或哈希碰撞。 把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。发生哈希冲突该如何处理呢解决哈希冲突的主要方案包括开放定址法在表内探测空位、链地址法同一位置用链表存储冲突元素、再哈希法使用多个哈希函数和公共溢出区法冲突元素存入独立区域等等。本文主要讲解前两种。1.4 哈希函数设计原则定义域包含全部关键码值域在 [0, m-1] 之间m 为表长地址均匀分布计算简单常见哈希函数方法公式/描述适用场景直接定址法Hash(key) A * key B关键字连续且范围小如字符统计除留余数法Hash(key) key % pp ≤ mp 为质数最常用平方取中法取 key² 的中间几位不知道分布位数不大折叠法将 key 分割成等长部分叠加求和取后几位位数多事先不知分布随机数法Hash(key) random(key)关键字长度不等数学分析法选择分布均匀的若干位作为地址已知分布位数大如手机号后四位哈希函数设计得越精妙冲突概率越低但无法完全避免。1.5 哈希冲突解决1.5.1 闭散列开放定址法当发生冲突时在哈希表中寻找下一个空位置存放元素。1线性探测插入从冲突位置开始依次向后探测可循环直到找到空位。查找从计算地址开始依次比较关键码直到找到目标或遇到空位。删除不能直接物理删除否则影响后续查找。采用标记法为每个槽位设置状态enum State { EMPTY, EXIST, DELETE };删除时仅将状态置为 DELETE查找时需跳过 DELETE 继续探测。实现框架#includevector enum STATE { EXIST, EMPTY, DELETE }; templateclass K, class V struct HashData { pairK, V _kv; STATE _state EMPTY; }; //每个桶存放一个键值对 pairK, V 和一个状态标记 // _state 默认初始化为 EMPTY templateclass K struct DefaultHashFunc { size_t operator()(const K key) { return (size_t)key; } }; //这是一个函数对象仿函数接受一个键 key返回一个 size_t 类型的哈希值 //默认实现直接将键转换为 size_t适用于整数类型或可以隐式转换为整数的类型 //注意对于指针类型这种转换是合理的但对于自定义类型需要用户提供特化版本 //struct StringHashFunc //{ // size_t operator()(const string str) // { // return str[0]; // } //}; template struct DefaultHashFuncstring { size_t operator()(const string str) { // BKDR size_t hash 0; for (auto ch : str) { hash * 131; hash ch; } return hash; } }; //为 std::string 提供了特化使用 BKDR 哈希算法乘 131 并累加字符的 ASCII 码 //注释掉的部分是另一种简单的字符串哈希取首字符容易引起大量冲突因此被替换为更均匀的 BKDR //模板参数 //K键类型 //V值类型 //HashFunc哈希函数类型默认使用 DefaultHashFuncK templateclass K,class V, class HashFunc DefaultHashFuncK class HashTable { public: HashTable() { _table.resize(10); } bool Insert(const pairK, V kv) { // 扩容 //if ((double)_n / (double)_table.size() 0.7) if (_n*10 / _table.size() 7) { size_t newSize _table.size() * 2; // 遍历旧表重新映射到新表 HashTableK, V, HashFunc newHT; newHT._table.resize(newSize); // 遍历旧表的数据插入到新表即可 for (size_t i 0; i _table.size(); i) { if (_table[i]._state EXIST) { newHT.Insert(_table[i]._kv); } } _table.swap(newHT._table); } // 线性探测 HashFunc hf; size_t hashi hf(kv.first) % _table.size(); while (_table[hashi]._state EXIST) { hashi; hashi % _table.size(); } _table[hashi]._kv kv; _table[hashi]._state EXIST; _n; return true; } HashDataconst K, V* Find(const K key) { // 线性探测 HashFunc hf; size_t hashi hf(key) % _table.size(); while (_table[hashi]._state ! EMPTY) { if (_table[hashi]._state EXIST _table[hashi]._kv.first key) { return (HashDataconst K, V*)_table[hashi]; } hashi; hashi % _table.size(); } return nullptr; } // 按需编译 bool Erase(const K key) { HashDataconst K, V* ret Find(key); if (ret) { ret-_state DELETE; --_n; return true; } return false; } private: vectorHashDataK, V _table; size_t _n 0; // 存储有效数据的个数 };线性探测优点实现非常简单线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降低。如何缓解呢二次探测缺点容易产生堆积即冲突数据连续占据区域导致后续查找变慢。void CheckCapacity() { if(_size * 10 / _ht.capacity() 7) { HashTableK, V, HF newHt(GetNextPrime(ht.capacity)); for(size_t i 0; i _ht.capacity(); i) { if(_ht[i]._state EXIST) newHt.Insert(_ht[i]._val); } Swap(newHt); }2二次探测为避免堆积二次探测的步长为平方序列H_i (H_0 ± i²) % mi 1,2,…。两个接口的重新设计:bool Insert(const pairK, V kv) { if (Find(kv.first)) return false; // 键已存在 // 扩容判断保持原有负载因子 0.7但二次探测建议 ≤0.5可自行调整 if (_n * 10 / _table.size() 7) { size_t newSize _table.size() * 2; HashTableK, V, HashFunc newHT; newHT._table.resize(newSize); for (size_t i 0; i _table.size(); i) { if (_table[i]._state EXIST) newHT.Insert(_table[i]._kv); } _table.swap(newHT._table); } HashFunc hf; size_t start hf(kv.first) % _table.size(); // 初始哈希地址 size_t i 0; // 探测步数 size_t hashi start; // 二次探测遇到 EXIST 则继续遇到 EMPTY/DELETE 则停止 while (_table[hashi]._state EXIST) { i; hashi (start i * i) % _table.size(); // 防止无限循环当表全满或负载因子过高时 if (i _table.size()) return false; // 无法插入理论上不会发生因负载因子 ≤0.7 仍有空位 } _table[hashi]._kv kv; _table[hashi]._state EXIST; _n; return true; }HashDataconst K, V* Find(const K key) { HashFunc hf; size_t start hf(key) % _table.size(); size_t i 0; size_t hashi start; // 二次探测直到遇到 EMPTY 才停止DELETE 需继续探测 while (_table[hashi]._state ! EMPTY) { if (_table[hashi]._state EXIST _table[hashi]._kv.first key) return (HashDataconst K, V*)_table[hashi]; i; hashi (start i * i) % _table.size(); // 探测一圈未找到退出循环 if (i _table.size()) break; } return nullptr; }研究表明当表长为质数且负载因子 α ≤ 0.5 时二次探测总能插入成功且任一位置不会被探查两次。但空间利用率低是其缺陷。1.5.2 开散列链地址法将具有相同地址的关键码归于同一子集合桶每个桶用单链表链接链表的头结点存储在哈希表中。结构示意哈希表数组[ nullptr, node1→node2, nullptr, node3, ... ] 每个桶内是一个链表存放所有冲突的元素。从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素。实现#pragma once #includevector templateclass K struct DefaultHashFunc { size_t operator()(const K key) { return (size_t)key; } }; template struct DefaultHashFuncstring { size_t operator()(const string str) { // BKDR size_t hash 0; for (auto ch : str) { hash * 131; hash ch; } return hash; } }; //作用提供默认的哈希函数对象支持整数类型直接转换并为 string 提供 BKDR 哈希特化 //优点泛型设计用户可自定义哈希函数字符串哈希采用 BKDR 算法冲突较少 //注意此部分位于全局作用域不属于 hash_bucket 命名空间但被后续哈希表使用 // 泛型编程不是针对某种具体类型针对广泛的类型(两种及以上) -- 模板 namespace hash_bucket { templateclass T struct HashNode { T _data; HashNodeT* _next; HashNode(const T data) :_data(data) ,_next(nullptr) {} }; //作用表示哈希桶中的链表节点存储数据 _data 和指向下一个节点的指针 _next //优点结构简单使用构造函数初始化列表 //注意节点内存需手动管理new/delete // 前置声明 templateclass K, class T, class KeyOfT, class HashFunc class HashTable; //作用由于迭代器需要访问 HashTable 的私有成员如 _table需要前置声明以便在迭代器中引用 //迭代器 HTIterator templateclass K, class T, class KeyOfT, class HashFunc struct HTIterator { typedef HashNodeT Node; typedef HTIteratorK, T, KeyOfT, HashFunc Self; Node* _node; HashTableK, T, KeyOfT, HashFunc* _pht; HTIterator(Node* node, HashTableK, T, KeyOfT, HashFunc* pht) :_node(node) ,_pht(pht) {} //成员 //_node当前指向的节点。 //_pht指向所属哈希表的指针用于跨桶查找下一个非空桶。 //构造初始化节点和哈希表指针 T operator*() { return _node-_data; } T* operator-() { return _node-_data; } //作用提供指针式访问符合迭代器规范。 Self operator() { 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()) { if (_pht-_table[hashi]) { _node _pht-_table[hashi]; return *this; } else { hashi; } } _node nullptr; } return *this; } bool operator!(const Self s) { return _node ! s._node; } }; // set - hash_bucket::HashTableK, K _ht; // map - hash_bucket::HashTableK, pairK, V _ht; //哈希表类 HashTable //模板参数 //K键类型 //T存储的数据类型对于 set 为 K对于 map 为 pairconst K, V //KeyOfT从 T 中提取 K 的函数对象 //HashFunc哈希函数默认使用 DefaultHashFuncK //友元声明迭代器为友元使其能访问 _table 等私有成员 //迭代器类型定义iterator 为 HTIterator templateclass K, class T, class KeyOfT, class HashFunc DefaultHashFuncK class HashTable { typedef HashNodeT Node; // 友元声明 templateclass K, class T, class KeyOfT, class HashFunc friend struct HTIterator; public: typedef HTIteratorK, T, KeyOfT, HashFunc iterator; iterator begin() { // 找第一个桶 for (size_t i 0; i _table.size(); i) { Node* cur _table[i]; if (cur) { return iterator(cur, this); } } return iterator(nullptr, this); } iterator end() { return iterator(nullptr, this); } HashTable() { _table.resize(10, nullptr); } ~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; } } bool Insert(const T data) { KeyOfT kot; if(Find(kot(data))) { return false; } HashFunc hf; // 负载因子到1就扩容 if (_n _table.size()) { // 16:03继续 size_t newSize _table.size()*2; vectorNode* newTable; newTable.resize(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[i] nullptr; } _table.swap(newTable); } size_t hashi hf(kot(data)) % _table.size(); // 头插 Node* newnode new Node(data); newnode-_next _table[hashi]; _table[hashi] newnode; _n; return true; } Node* 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) { return cur; } cur cur-_next; } return nullptr; } bool Erase(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; return true; } prev cur; cur cur-_next; } return false; } void Print() { for (size_t i 0; i _table.size(); i) { printf([%d]-, i); Node* cur _table[i]; while (cur) { cout cur-_kv.first : cur-_kv.second -; cur cur-_next; } printf(NULL\n); } cout endl; } private: vectorNode* _table; // 指针数组 size_t _n 0; // 存储了多少个有效数据 }; }扩容// 负载因子到1就扩容 if (_n _table.size()) { size_t newSize _table.size() * 2; vectorNode* newTable; newTable.resize(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[i] nullptr; } _table.swap(newTable); }开散列最好的情况是每个桶一个节点当元素个数等于桶数时再插入必然冲突此时可考虑扩容。处理非整数关键码需要将任意类型转换为整型通过仿函数实现templateclass K struct DefaultHashFunc { size_t operator()(const K key) { return (size_t)key; // 对于整数类型直接转换 } }; // 特化std::string 使用 BKDR 哈希算法 template struct DefaultHashFuncstring { size_t operator()(const string str) { size_t hash 0; for (auto ch : str) { hash * 131; hash ch; } return hash; } };在哈希桶中使用时通过模板参数传入templateclass K, class T, class KeyOfT, class HashFunc DefaultHashFuncK class HashTable { // ... public: bool Insert(const T data) { // ... HashFunc hf; // 创建哈希函数对象 size_t hashi hf(kot(data)) % _table.size(); // 调用 operator() 计算哈希值 // ... } Node* Find(const K key) { // ... HashFunc hf; size_t hashi hf(key) % _table.size(); // 同样用于查找 // ... } };HashFunc默认使用DefaultHashFuncK因此对于K int等类型直接转换对于K string会自动使用特化版本。也可以自定义哈希函数只需定义仿函数并作为模板参数传入即可。素数表除留余数法最好模素数可预先生成素数列表扩容时取下一个素数size_t GetNextPrime(size_t prime) { static const size_t primeList[] { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611 }; for (auto p : primeList) { if (p prime) return p; } return primeList.back(); }1.6 开散列与闭散列比较特性闭散列开放定址开散列链地址解决冲突方式寻找其他空位同一位置用链表存储负载因子必须小于1通常 ≤0.7可以大于1删除操作需标记不能直接物理删除直接链表删除缓存性能较好连续内存较差节点分散空间利用率需留大量空闲空间指针额外开销但总空间可能更省最坏情况堆积导致探测链长链表过长退化为 O(N)由于开放定址法必须保持大量空闲空间以保证效率而链地址法只需少量指针实际中链地址法往往更节省空间。2.unordered系列关联式容器简述在C98中STL提供了底层为红黑树结构的一系列关联式容器在查询时效率可达到$log_2 N$即最差情况下需要比较红黑树的高度次当树中的节点非常多时查询效率也不理想。最好 的查询是进行很少的比较次数就能够将元素找到因此在C11中STL又提供了4个 unordered系列的关联式容器这四个容器与红黑树结构的关联式容器使用方式基本类似只是 其底层结构不同本文中只对unordered_map和unordered_set进行介绍 unordered_multimap和unordered_multiset可自行查看文档介绍。https://legacy.cplusplus.com/reference/stl/https://legacy.cplusplus.com/reference/stl/2.1 unordered_map无序映射是一种关联容器用于存储由键值和映射值组合而成的元素并允许根据键快速检索单个元素。在unordered_map中键值通常用于唯一标识元素而映射值是与该键相关联的内容对象。键和映射值的类型可以不同。内部而言unordered_map中的元素既不按键也不按映射值的任何特定顺序排序而是根据其哈希值组织到不同的桶中以便通过键值直接快速访问单个元素平均时间复杂度为常数。与通过键访问单个元素相比unordered_map容器比map容器更快尽管它们通常对于遍历其部分元素的范围效率较低。无序映射实现了直接访问运算符operator[]允许使用键值作为参数直接访问映射值。容器中的迭代器至少是前向迭代器。2.2 unordered_set无序集合是一种容器用于存储无特定顺序的唯一元素并允许根据元素的值快速检索单个元素。在无序集合中元素的值同时作为其键用于唯一标识该元素。由于键是不可变的因此一旦将元素放入无序集合中就无法对其进行修改——不过可以插入和删除元素。无序集合内部的元素不会按任何特定顺序排序而是根据其哈希值组织到不同的桶中以便能够直接通过值快速访问单个元素平均时间复杂度为常数。与通过键访问单个元素相比无序集合容器比集合容器更快但通常对于遍历其部分元素的范围效率较低。容器中的迭代器至少是前向迭代器。2.3 两容器的常用接口使用案例unorder_map常用接口1. 构造与插入注意该函数中实际调用哈希桶的插入操作用参数key与V()构造一个默认值往底层哈希桶中插入如果key不在哈希桶中插入成功返回V()插入失败说明key已经在哈希桶中将key对应的value返回。2. 查找元素// 接上例 string key banana; auto it umap.find(key); if (it ! umap.end()) { cout Found: it-first - it-second endl; } else { cout key not found endl; } // count 函数对于 unordered_map返回 0 或 1键唯一 if (umap.count(apple)) { cout apple exists, value umap[apple] endl; }3. 删除元素// 通过键删除 umap.erase(banana); // 通过迭代器删除 auto it umap.find(orange); if (it ! umap.end()) { umap.erase(it); } // 条件删除C11 无 erase_if可手动循环 for (auto it umap.begin(); it ! umap.end(); ) { if (it-second 5) { it umap.erase(it); // erase 返回下一个迭代器 } else { it; } }4. 容量与清空cout size: umap.size() endl; cout empty: umap.empty() endl; umap.clear(); // 清空所有元素 cout after clear, size umap.size() endl;5. 桶操作接口unordered_mapint, string m {{1, one}, {2, two}, {3, three}, {11, eleven}}; cout bucket count m.bucket_count() endl; for (size_t i 0; i m.bucket_count(); i) { cout bucket i has m.bucket_size(i) elements. endl; } // 查看某个 key 所在的桶 int key 11; cout key key is in bucket m.bucket(key) endl;6. 综合案例统计单词频率#include iostream #include unordered_map #include string #include sstream using namespace std; int main() { string text apple banana apple orange banana apple; unordered_mapstring, int freq; stringstream ss(text); string word; while (ss word) { freq[word]; // 若 word 不存在operator[] 会插入并初始化为 0然后递增 } for (const auto p : freq) { cout p.first : p.second endl; } return 0; }unorder_set常用接口1. 构造与插入#include iostream #include unordered_set #include string using namespace std; int main() { unordered_setstring uset; // 插入单个元素 uset.insert(apple); uset.insert(banana); uset.insert(orange); // 插入重复元素会被忽略 uset.insert(apple); // 使用初始化列表构造 unordered_setint numbers {1, 2, 3, 4, 5}; // 遍历 for (const auto s : uset) { cout s ; } cout endl; return 0; }2. 查找元素string key banana; if (uset.find(key) ! uset.end()) { cout key is in the set endl; } else { cout key not found endl; } // count 返回 0 或 1 if (uset.count(apple)) { cout apple exists endl; }3. 删除元素// 按值删除 uset.erase(banana); // 按迭代器删除 auto it uset.find(orange); if (it ! uset.end()) { uset.erase(it); } // 清空 uset.clear();4. 综合案例去除重复元素#include iostream #include vector #include unordered_set using namespace std; int main() { vectorint vec {1, 2, 3, 2, 1, 4, 5, 5, 6}; unordered_setint unique(vec.begin(), vec.end()); cout Unique elements: ; for (int x : unique) { cout x ; } cout endl; return 0; }5. 综合案例两个数组的交集#include iostream #include vector #include unordered_set using namespace std; vectorint intersection(vectorint nums1, vectorint nums2) { unordered_setint s1(nums1.begin(), nums1.end()); unordered_setint s2(nums2.begin(), nums2.end()); vectorint result; for (int x : s1) { if (s2.find(x) ! s2.end()) { result.push_back(x); } } return result; } int main() { vectorint a {1, 2, 2, 1}; vectorint b {2, 2}; auto res intersection(a, b); for (int x : res) cout x ; return 0; }结语感谢相遇/// 高山仰止景行行止。虽不能至心向往之 ///