前言本系列文章承接C基础的学习需要有C语言的基础才能学会哦~第23篇主要讲的是有关于C的哈希表。C才起步都很简单目录前言哈希的概念直接定址法哈希冲突负载因子哈希函数除法散列法/除留余数法乘法散列法了解即可全域散列法了解即可其他方法处理哈希冲突开放定址法线性探测二次(方)探测双重散列了解开放定址法代码实现链地址法链地址法代码实现哈希封装哈希的概念又叫散列是一种组织数据的方式。通过哈希函数把关键字key与存储位置建立一个映射查找时通过哈希函数计算出Key存储的位置。直接定址法关键字范围集中时用关键字直接计算出一个绝对或相对的存储位置。如a-z的26个字母开26个数的数组用其ascll码做下标即可。哈希冲突关键字范围不集中时直接定址法需要创建大量的无用空间。例如只有在[0 999999]的N个值要给他映射到大小为MM N的空间中就要借助哈希函数来映射。但可能会出现一个问题多个Key经过哈希函数计算后映射到了同样一个位置这种情况就叫做哈希冲突哈希碰撞。冲突不可避免但是要尽量减少冲突的次数。负载因子负载因子load factor N为已存数据个数M为哈希表大小。负载因子越小哈希冲突概率越小空间利用率低负载因子越大哈希冲突概率越大空间利用率高。哈希函数好的哈希函数要尽可能让N个关键字均匀地分散到M个存储空间里减少冲突。除法散列法/除留余数法即 h(key) key % M。要点①尽量避免M为2、10的幂等。这些与进制相同的数字的幂区域之后相当于保留后x位这样一来哈希冲突很容易就会发生不够均摊。②尽量取M为不太接近2的整数次幂的质数。可以尽量让key的所有位都参与运算更“随机”更均摊。③使用这种方法要尽可能让Key更多的位数都参与运算。如在32位下Key右移16位变成Key‘通过Key 异或 Key’的结果作为哈希值。乘法散列法了解即可让Key乘上常数A0A1取其小数部分再用空间大小M*小数部分向下取整作为哈希值。即h(Key) M * ( ( A * Key ) % 1.0)这种方法对M大小没有要求。全域散列法了解即可若哈希函数是公开且确定的攻击者就可以刻意制造会发生严重冲突的数据集例如全映射到同一个位置。解决办法就是用全域散列法给哈希函数增加随机性。h(Key) ( (a * Key b) % P) % MP为足够大的质数a为[1,P-1]中的任意随机整数b为[0,P-1]中任意随机整数。因为随机性攻击者无法预测Key会映射到哪一个位置攻击难度增大。其他方法平方折中法、折叠法、随机数法、数学分析法等。处理哈希冲突冲突不可避免遇到冲突需要解决。开放定址法当Key用哈希函数计算出的位置冲突了则按照某种规则找一个没有存储数据的位置进行存储。探测无存储数据的位置有三种规则线性探测、二次探测、双重探测、线性探测从冲突位置开始依次线性向后探测直到寻找到下一个没有存储数据的位置为止如果走到哈希表尾就回到哈希表头。线性探测公式hc(key,i) (h(Key) i) % M, i {1,2,3,4,···,M-1}最多探测M-1次就能找到可以存储的位置。群集/堆积例如哈希值012即hash0、hash1、hash2都存储了数据那么hash0、hash1、hash2、hash3的Key都会争夺hash3的位置。此时使用二次探测可以一定程度改善这种情况。二次(方)探测从冲突位置开始一次左右按二次方跳跃式探测直到寻找到下一个没有存储数据的位置为止如果走到哈希表尾就回到哈希表头。二次探测公式hc(key,i) (h(Key) ± i * i ) % M, i {1,2,3,4,···,M/2}。探测顺序就是哈希值1然后-1接着4之后-4随后9-916-16如此类推。双重散列了解双重散列公式hc(Key, i) ( i *(Key) )% M, i {1,2,3,···,M}。再使用一个不同的哈希函数来获得不同的偏移量值直到寻找到下一个没有存储数据的位置为止。要求(Key) M且两者互为质数。开放定址法代码实现#pragma once #includevector #includeiostream #includemap #includeunordered_map using namespace std; enum State { Empty, Delete, Exist }; templateclass K, class V struct HashData { pairK, V _kv; State _state Empty; }; templateclass K class HashFunc { public: size_t operator()(const K key) { return (size_t)key; } }; //特化 //要把string转为整型才可以被哈希函数 template class HashFuncstring { public: size_t operator()(const string key) { size_t hash 0; for (auto ch : key) { hash ch; hash * 131; //BKDR哈希、DJB哈希、AP哈希··· } return hash; } }; templateclass K,class V,class Hash HashFuncK class HashTable { public: inline unsigned long __stl_next_prime(unsigned long n) { static const int __stl_num_primes 28; static const unsigned long __stl_prime_list[__stl_num_primes] { 53,97,193,389,768.1543,3079,6151,12289,24593,49157,98317,196613,393241,786433 ,1572869,3145739,6291469,12582917,25165843,50331653,100663319,201326611,402653189 ,805306457,1610612741,3221225473,4294967291 }; const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; const unsigned long* pos lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } HashTable() { _tables.resize(__stl_next_prime(1)); } bool Insert(const pairK, V kv) { //若不允许冗余则需要查找一下 if (Find(kv.first)) { return false; } //扩容 if ((double)_n / (double)_tables.size() 0.7) { // //获取素数表内比当前表大的一个素数 // size_t newSize __Stl_next_prime(_tables.size() 1); // //扩容之后要重新映射 // vectorHashDataK, V newTables(newSize); // //遍历旧表将数据重新遍历。 // for (size_t i 0; i _tables.size(); i) // { // if (_tables[i]._state Exist) // { // //... // } // } // _tables.swap(newTables); //} size_t newSize __stl_next_prime(_tables.size() 1); HashTableK, V, Hash newHT; newHT._tables.resize(newSize); //遍历旧表将数据重新遍历。 for (size_t i 0; i _tables.size(); i) { if (_tables[i]._state Exist) { newHT.Insert(_tables[i]._kv); } } //交换之后若函数完毕旧表就刚好被析构销毁 _tables.swap(newHT._tables); } Hash hs; //hash0为哈希值 size_t hash0 hs(kv.first) % _tables.size(); size_t i 1; //hashi为探测值 size_t hashi hash0; while (_tables[hashi]._state Exist) { //冲突探测 hashi (hash0 i) % _tables.size(); i; } _tables[hashi]._kv kv; _tables[hashi]._state Exist; return true; } HashDataK, V* Find(const K key) { Hash hs; size_t hash0 hs(key) % _tables.size(); size_t hashi hash0; size_t i 1; size_t flag 1; while (_tables[hashi]._state ! Empty) { if (_tables[hashi]._state Exist _tables[hashi]._kv.first key) { return _tables[hashi]; } //线性检测 hashi (hash0 i * flag) % _tables.size(); flag * -1; i; } return nullptr; } bool Erase(const K key) { HashDataK, V* ret Find(key); if (ret nullptr) { return false; } else { ret-_state Delete; --_n; return true; } } private: vectorHashDataK, V _tables; size_t _n 0; }; //void TestHT1() //{ // HashTableint, int ht1; // ht1.Insert({ 54,1 }); // ht1.Insert({ 1,1 }); // // cout ht1.Find(1) endl; // cout ht1.Erase(54) endl; // cout ht1.Find(1) endl; // cout ht1.Find(54) endl; // //for (size_t i 0; i 53; i) // //{ // // ht1.Insert({ rand(),i }); // //} //} void TestHT2() { HashTablestring, string,stringHashFunc ht2; ht2.Insert({ sort,排序 }); ht2.Insert({ string,字符串 }); cout stringHashFunc()(abcd) endl; cout stringHashFunc()(bcad) endl; cout stringHashFunc()(abbe) endl; unordered_mapstring, string dictMap; dictMap.insert({ sort,排序 }); dictMap.insert({ string,字符串 }); }链地址法也就是哈希桶我们把哈希冲突的数据以链表的方式链接在一起。如图这样一来负载因子就可以大于1了。链地址法代码实现templateclass, class V struct HashNode { pairK, V _kv; HashNodeK, V* _next; HashNode(const pairK, V kv) :_kv(kv) , _next(nullptr) { } }; templateclass K, class V class HashTable { typedef HashNodeK, V Node; public: inline unsigned long __stl_next_prime(unsigned long n) { static const int __stl_num_primes 28; static const unsigned long __stl_prime_list[__stl_num_primes] { 53,97,193,389,768.1543,3079,6151,12289,24593,49157,98317,196613,393241,786433 ,1572869,3145739,6291469,12582917,25165843,50331653,100663319,201326611,402653189 ,805306457,1610612741,3221225473,4294967291 }; const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; const unsigned long* pos lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } HashTable() { _tables.resize(__stl_next_prime(1), nullptr); } bool Insert(const pairK, V kv) { if (Find(kv.first)) { return false; } //负载因子到1就扩容 if (_n _tables.size()) { size_t newSize __stl_next_prime(_tables.size() 1); vectorNode* newtables(newSize, nullptr); //遍历旧表把旧表的结点挪动到新表 for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; //cur头插到新表 size_t hashi cur-_kv.first % newSize; //让下一个结点为对应哈希值的第一个结点 cur-_next newtables[hashi]; //插在对应哈希值的第一个结点 newtables[hashi] cur; //往下走 cur next; } //旧表置空 _tables[i] nullptr; } //交换哈希表旧表会自动析构 _tables.swap(newtables); } size_t hashi kv.first % _tables.size(); Node* newnode new Node(kv); //头插法 newnode-_next _table[hashi]; _tables[hashi] newnode; _n; return true; } Node* Find(const K key) { size_t hashi key % _tables.size(); Node* cur _tables[hashi]; while (cur) { if (cur-_kv.first key) { return cur; } cur cur-_next; } return nullptr; } bool Erase(const K key) { size_t hashi key % _tables.size(); Node* prev nullptr; Node* cur _tables[hashi]; while (cur) { if (cur-_kv.first key) { // 删除 if (prev nullptr) { // 头删 _tables[hashi] cur-_next; } else { prev-_next cur-_next; } delete cur; return true; } prev cur; cur cur-_next; } return false; } private: vectorNode*_tables; size_t _n 0; };哈希封装只展示代码示例内含解析~HashTable.h#define _CRT_SECURE_NO_WARNINGS 1 // 禁用VS的C运行时安全警告 #includevector // 引入vector容器用于存储哈希表数据 #includeiostream #includeunordered_map #includeunordered_set using namespace std; // 通用哈希函数模板默认适配int等数值类型 templateclass K class HashFunc { public: // 重载()运算符数值类型直接强转为size_t作为哈希值 size_t operator()(const K key) { return (size_t)key; } }; // 哈希函数特化针对string类型解决字符串无法直接强转的问题 template class HashFuncstring { public: size_t operator()(const string key) { size_t hash 0; // 初始化哈希值 for (auto ch : key) // 遍历字符串每个字符 { hash ch; // 累加字符ASCII值 hash * 131; // 乘以131经典哈希系数减少冲突 } return hash; // 返回最终哈希值 } }; // 开放定址法哈希表命名空间 namespace open_address { // 哈希表元素状态枚举解决删除后查找链断裂问题 enum State { EXIST, // 元素存在 EMPTY, // 位置为空 DELETE // 元素已删除伪删除 }; // 哈希表数据节点存储键值对 状态 templateclass K, class V struct HashData { pairK, V _kv; // 键值对 State _state EMPTY; // 初始状态为空 }; // 开放定址法哈希表类模板K-键V-值Hash-哈希函数默认HashFuncK templateclass K, class V, class Hash HashFuncK class HashTable { public: // 私有工具函数获取大于等于n的下一个素数STL经典素数表减少哈希冲突 inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. static const int __stl_num_primes 28; // 素数表长度 static const unsigned long __stl_prime_list[__stl_num_primes] { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; const unsigned long* first __stl_prime_list; // 素数表起始 const unsigned long* last __stl_prime_list __stl_num_primes; // 素数表结束 const unsigned long* pos lower_bound(first, last, n); // 二分找第一个n的素数 return pos last ? *(last - 1) : *pos; // 超出表则返回最后一个素数 } // 构造函数初始化哈希表容量为大于1的第一个素数53 HashTable() { _tables.resize(__stl_next_prime(1)); } // 插入键值对返回是否插入成功重复键返回false bool Insert(const pairK, V kv) { if (Find(kv.first)) // 先查找键已存在则返回false return false; // 扩容条件负载因子已存元素/表容量0.7开放定址法负载因子不宜过高 // if (_n*10 / _tables.size 7) // 注释的扩容写法等价 if ((double)_n / (double)_tables.size() 0.7) { // 注释的扩容逻辑替换为新建哈希表的方式 //size_t newSize __stl_next_prime(_tables.size() 1); //vetcorHashDataK, V newTables(newSize); // 笔误vector拼错 //// 遍历旧表将数据都映射到新表 //for (size_t i 0; i _tables.size(); i) //{ // if (_tables[i]._state EXIST) // { // // ... // } //} //_tables.swap(newTables); size_t newSize __stl_next_prime(_tables.size() 1); // 新容量为下一个素数 HashTableK, V, Hash newHT; // 新建空哈希表 newHT._tables.resize(newSize); // 调整新表容量 // 遍历旧表将有效数据重新插入新表重新计算哈希位置 for (size_t i 0; i _tables.size(); i) { if (_tables[i]._state EXIST) { newHT.Insert(_tables[i]._kv); } } _tables.swap(newHT._tables); // 交换新旧表完成扩容 } Hash hs; // 创建哈希函数对象 size_t hash0 hs(kv.first) % _tables.size(); // 计算初始哈希位置 size_t i 1; // 线性探测步长 size_t hashi hash0; // 当前探测位置 while (_tables[hashi]._state EXIST) { // 线性探测往后找空位置 hashi (hash0 i) % _tables.size(); i; } // 插入数据并更新状态 _tables[hashi]._kv kv; _tables[hashi]._state EXIST; _n; // 有效元素数1 return true; } // 查找键返回数据节点指针找不到返回nullptr HashDataK, V* Find(const K key) { Hash hs; size_t hash0 hs(key) % _tables.size(); // 初始哈希位置 size_t hashi hash0; size_t i 1; while (_tables[hashi]._state ! EMPTY) // 非空位置都要探测包括DELETE { // 找到存在且键匹配的元素 if (_tables[hashi]._state EXIST _tables[hashi]._kv.first key) { return _tables[hashi]; } // 继续线性探测 hashi (hash0 i) % _tables.size(); i; } return nullptr; // 未找到 } // 删除键返回是否删除成功伪删除仅改状态 bool Erase(const K key) { HashDataK, V* ret Find(key); if (ret nullptr) // 未找到 { return false; } else // 伪删除改状态为DELETE不直接清空避免查找链断裂 { --_n; ret-_state DELETE; return true; } } private: vectorHashDataK, V _tables; // 哈希表本体数组 size_t _n 0; // 有效元素个数 }; // 字符串哈希函数冗余仅测试用实际用上面的特化版本 class stringHashFunc { public: size_t operator()(const string s) { size_t hash 0; for (auto ch : s) { hash ch; hash * 131; } return hash; } }; // 开放定址法测试函数 void TestHT1() { HashTableint, int ht1; ht1.Insert({ 54, 1 }); ht1.Insert({ 1, 1 }); cout ht1.Find(1) endl; // 输出地址非空 cout ht1.Erase(54) endl; // 输出1删除成功 cout ht1.Find(1) endl; // 输出地址仍存在 cout ht1.Find(54) endl; // 输出0已删除 /*for (int i 0; i 53; i) { ht1.Insert({rand(), i}); }*/ } // 日期结构体仅占位未实际使用 struct Date { int _year; int _month; int _day; }; // 字符串哈希测试函数 void TestHT2() { //HashTablestring, string, stringHashFunc ht2; // 注释的写法等价 HashTablestring, string ht2; ht2.Insert({ sort, 排序 }); ht2.Insert({ string, 字符串 }); // 测试字符串哈希值验证不同字符串哈希值不同 cout stringHashFunc()(abcd) endl; cout stringHashFunc()(bcad) endl; cout stringHashFunc()(abbe) endl; // 对比标准库unordered_map unordered_mapstring, string dictMap; dictMap.insert({ sort, 排序 }); dictMap.insert({ string, 字符串 }); cout dictMap.load_factor() endl; // 输出负载因子 cout dictMap.max_load_factor() endl;// 输出最大负载因子 } } // 链式哈希表命名空间 namespace hash_bucket { // 链表节点模板存储任意类型数据 templateclass T struct HashNode { T _data; // 存储数据map存pairset存K HashNodeT* _next; // 指向下一个节点 HashNode(const T data) // 构造函数初始化数据next置空 :_data(data) , _next(nullptr) { } }; // 前置声明哈希表类供迭代器使用 templateclass K, class T, class KeyOfT, class Hash class HashTable; // 链式哈希表迭代器模板 // K-键类型T-存储类型Ref-引用类型Ptr-指针类型KeyOfT-提取键的仿函数Hash-哈希函数 templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash struct __HTIterator { typedef HashNodeT Node; // 节点类型 typedef HashTableK, T, KeyOfT, Hash HT; // 哈希表类型 typedef __HTIteratorK, T, Ref, Ptr, KeyOfT, Hash Self; // 迭代器自身类型 Node* _node; // 当前指向的节点 const HT* _ht; // 指向哈希表用于时找下一个桶 // 构造函数初始化节点和哈希表指针 __HTIterator(Node* node, const HT* ht) :_node(node) , _ht(ht) { } // 解引用运算符返回数据的引用 Ref operator*() { return _node-_data; } // 箭头运算符返回数据的指针支持it-first/second Ptr operator-() { return _node-_data; } // 前置迭代器后移核心逻辑 Self operator() { if (_node-_next) // 1. 当前桶内有下一个节点直接走链表 { _node _node-_next; } else // 2. 当前桶走完找下一个非空桶 { KeyOfT kot; // 提取键的仿函数 Hash hs; // 哈希函数 // 计算当前节点所在桶的下标 size_t hashi hs(kot(_node-_data)) % _ht-_tables.size(); hashi; // 从下一个桶开始找 while (hashi _ht-_tables.size()) { if (_ht-_tables[hashi]) // 找到非空桶 { _node _ht-_tables[hashi]; break; } else // 桶为空继续找下一个 { hashi; } } // 所有桶遍历完置空迭代器结束 if (hashi _ht-_tables.size()) { _node nullptr; } } return *this; } // 不等于运算符比较节点指针 bool operator!(const Self s) { return _node ! s._node; } // 等于运算符比较节点指针 bool operator(const Self s) { return _node s._node; } }; // 链式哈希表类模板核心 // K-键类型T-存储类型mappairconst K,Vsetconst KKeyOfT-提取键的仿函数Hash-哈希函数 templateclass K, class T, class KeyOfT, class Hash class HashTable { // 友元迭代器需要访问哈希表私有成员 templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash friend struct __HTIterator; typedef HashNodeT Node; // 节点类型 public: // 迭代器类型定义普通/const typedef __HTIteratorK, T, T, T*, KeyOfT, Hash Iterator; typedef __HTIteratorK, T, const T, const T*, KeyOfT, Hash ConstIterator; // 普通begin返回第一个有效元素的迭代器 Iterator Begin() { for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; if (cur) // 找到第一个非空桶 { return Iterator(cur, this); } } return End(); // 空表返回end } // 普通end返回尾后迭代器nullptr Iterator End() { return Iterator(nullptr, this); } // const版本begin只读遍历 ConstIterator Begin() const { for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; if (cur) { return ConstIterator(cur, this); } } return End(); } // const版本end只读遍历的尾后 ConstIterator End() const { return ConstIterator(nullptr, this); } // 构造函数初始化哈希表容量为53桶指针置空 HashTable() { _tables.resize(__stl_next_prime(1), nullptr); } // 析构函数释放所有节点 ~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; // 桶指针置空 } } // 私有工具函数获取下一个素数同开放定址法 inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. static const int __stl_num_primes 28; static const unsigned long __stl_prime_list[__stl_num_primes] { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; const unsigned long* pos lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } // 插入数据返回pair迭代器, bool迭代器指向元素bool表示是否插入成功 pairIterator, bool Insert(const T data) { KeyOfT kot; // 先查找键已存在则返回{迭代器, false} Iterator it Find(kot(data)); if (it ! End()) return { it, false }; Hash hs; // 负载因子到1就扩容链式哈希表负载因子可更高 if (_n _tables.size()) { size_t newSize __stl_next_prime(_tables.size() 1); vectorNode* newtables(newSize, nullptr); // 新桶数组 // 遍历旧表把旧表的节点挪动到新表 for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; // 保存下一个节点 // cur头插到新表 size_t hashi hs(kot(cur-_data)) % newSize; cur-_next newtables[hashi]; newtables[hashi] cur; cur next; } _tables[i] nullptr; // 旧桶置空 } _tables.swap(newtables); // 交换新旧桶数组 } // 插入新节点头插法 size_t hashi hs(kot(data)) % _tables.size(); // 计算哈希位置 Node* newnode new Node(data); // 新建节点 // 头插到桶里面 newnode-_next _tables[hashi]; _tables[hashi] newnode; _n; // 有效元素数1 return { Iterator(newnode, this), true }; // 返回迭代器和成功标志 } // 查找键返回迭代器找不到返回end Iterator Find(const K key) { Hash hs; size_t hashi hs(key) % _tables.size(); // 计算哈希位置 Node* cur _tables[hashi]; // 指向桶的第一个节点 KeyOfT kot; while (cur) // 遍历桶内链表 { if (kot(cur-_data) key) // 找到匹配键 { return Iterator(cur, this); } cur cur-_next; } return End(); // 未找到 } // 删除键返回是否删除成功 bool Erase(const K key) { Hash hs; KeyOfT kot; size_t hashi hs(key) % _tables.size(); // 哈希位置 Node* prev nullptr; Node* cur _tables[hashi]; while (cur) // 遍历桶内链表找目标节点 { if (kot(cur-_data) key) { // 删除 if (prev nullptr) // 头节点删除 { _tables[hashi] cur-_next; } else // 中间/尾节点删除 { prev-_next cur-_next; } delete cur; // 释放节点 _n--; // 有效元素数-1 return true; } prev cur; cur cur-_next; } return false; // 未找到 } private: //vectorlistpairK, V _tables; // 注释的写法用list替代指针数组 vectorNode* _tables; // 桶数组存储节点指针 size_t _n 0; // 表中存储数据个数 }; }unorderedset.h#pragma once // 防止头文件重复包含 // 依赖HashTable.h链式哈希表的核心实现 #include HashTable.h namespace bit { // unordered_set类模板单值存储元素唯一 templateclass K, class Hash HashFuncK class unordered_set { // 仿函数从K中提取键set的元素就是键 struct SetKeyOfT { const K operator()(const K key) { return key; // 直接返回自身 } }; public: // 迭代器类型定义存储const K元素不可修改 typedef typename hash_bucket::HashTableK, const K, SetKeyOfT, Hash::Iterator iterator; typedef typename hash_bucket::HashTableK, const K, SetKeyOfT, Hash::ConstIterator const_iterator; // 普通begin返回第一个有效元素的迭代器 iterator begin() { return _ht.Begin(); } // 普通end返回尾后迭代器 iterator end() { return _ht.End(); } // const版本begin只读遍历 const_iterator begin() const { return _ht.Begin(); } // const版本end只读遍历的尾后 const_iterator end() const { return _ht.End(); } // 插入元素单值返回pair迭代器, bool区分插入成功/元素已存在 pairiterator, bool insert(const K key) { return _ht.Insert(key); } private: // 底层存储链式哈希表存储const K元素不可修改 hash_bucket::HashTableK, const K, SetKeyOfT, Hash _ht; }; // 打印const的unordered_set只能用const迭代器 void Print(const unordered_setint s) { unordered_setint::const_iterator it s.begin(); while (it ! s.end()) { // *it 1; // 错误set元素不可修改 cout *it ; it; } cout endl; } // unordered_set测试函数 void test_set1() { unordered_setint s; s.insert(1); s.insert(12); s.insert(54); s.insert(107); // 普通迭代器遍历 unordered_setint::iterator it s.begin(); while (it ! s.end()) { // *it 1; // 错误set元素不可修改 cout *it ; it; } cout endl; // 范围for遍历底层调用begin/end for (auto e : s) { cout e ; } cout endl; } }unorderedmap.h#pragma once // 防止头文件重复包含 // 依赖HashTable.h链式哈希表的核心实现 #include HashTable.h namespace bit { // unordered_map类模板键值对存储键唯一 templateclass K, class V, class Hash HashFuncK class unordered_map { // 仿函数从pairK,V中提取键给底层哈希表用 struct MapKeyOfT { const K operator()(const pairK, V kv) { return kv.first; // 返回pair的第一个元素键 } }; public: // 迭代器类型定义重命名底层哈希表的迭代器 // 存储类型为pairconst K,V键不可修改符合map特性 typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash::Iterator iterator; typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash::ConstIterator const_iterator; // 普通begin返回第一个有效元素的迭代器 iterator begin() { return _ht.Begin(); } // 普通end返回尾后迭代器 iterator end() { return _ht.End(); } // const版本begin只读遍历 const_iterator begin() const { return _ht.Begin(); } // const版本end只读遍历的尾后 const_iterator end() const { return _ht.End(); } // 插入键值对返回pair迭代器, bool区分插入成功/键已存在 pairiterator, bool insert(const pairK, V kv) { return _ht.Insert(kv); } // []运算符重载核心接口支持map[key] value 或 map[key]取值 V operator[](const K key) { // 插入{key, 默认值}不存在则插入存在则返回已存在元素 pairiterator, bool ret _ht.Insert(make_pair(key, V())); // 返回值的引用可修改如map[a] b return ret.first-second; } private: // 底层存储链式哈希表存储pairconst K,V键不可修改 hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash _ht; }; // 打印const的unordered_map只能用const迭代器 void Print(const unordered_mapstring, string dict) { unordered_mapstring, string::const_iterator it dict.begin(); while (it ! dict.end()) { //it-first x; // 错误const迭代器不能修改键 //it-second x; // 错误const迭代器不能修改值 cout it-first it-second; it; } cout endl; } // unordered_map测试函数 void test_map1() { unordered_mapstring, string dict; unordered_mapstring, string::iterator it dict.begin(); while (it ! dict.end()) { //it-first x; // 错误map的键不可修改 it-second x; // 正确值可以修改 cout it-first it-second; it; } cout endl; // 统计字符串出现次数map的核心场景 string arr[] { ƻ, , ƻ, , ƻ, ƻ, , ƻ, 㽶, ƻ, 㽶 }; unordered_mapstring, int countMap; for (const auto str : arr) { countMap[str]; // 核心用法不存在则插入{str,0}再存在则直接 } // 遍历输出统计结果 for (const auto e : countMap) { cout e.first : e.second endl; } cout endl; } }❤~~本文完结感谢观看接下来更精彩欢迎来我博客做客~~❤
从C++开始的编程生活（23）——哈希表
前言本系列文章承接C基础的学习需要有C语言的基础才能学会哦~第23篇主要讲的是有关于C的哈希表。C才起步都很简单目录前言哈希的概念直接定址法哈希冲突负载因子哈希函数除法散列法/除留余数法乘法散列法了解即可全域散列法了解即可其他方法处理哈希冲突开放定址法线性探测二次(方)探测双重散列了解开放定址法代码实现链地址法链地址法代码实现哈希封装哈希的概念又叫散列是一种组织数据的方式。通过哈希函数把关键字key与存储位置建立一个映射查找时通过哈希函数计算出Key存储的位置。直接定址法关键字范围集中时用关键字直接计算出一个绝对或相对的存储位置。如a-z的26个字母开26个数的数组用其ascll码做下标即可。哈希冲突关键字范围不集中时直接定址法需要创建大量的无用空间。例如只有在[0 999999]的N个值要给他映射到大小为MM N的空间中就要借助哈希函数来映射。但可能会出现一个问题多个Key经过哈希函数计算后映射到了同样一个位置这种情况就叫做哈希冲突哈希碰撞。冲突不可避免但是要尽量减少冲突的次数。负载因子负载因子load factor N为已存数据个数M为哈希表大小。负载因子越小哈希冲突概率越小空间利用率低负载因子越大哈希冲突概率越大空间利用率高。哈希函数好的哈希函数要尽可能让N个关键字均匀地分散到M个存储空间里减少冲突。除法散列法/除留余数法即 h(key) key % M。要点①尽量避免M为2、10的幂等。这些与进制相同的数字的幂区域之后相当于保留后x位这样一来哈希冲突很容易就会发生不够均摊。②尽量取M为不太接近2的整数次幂的质数。可以尽量让key的所有位都参与运算更“随机”更均摊。③使用这种方法要尽可能让Key更多的位数都参与运算。如在32位下Key右移16位变成Key‘通过Key 异或 Key’的结果作为哈希值。乘法散列法了解即可让Key乘上常数A0A1取其小数部分再用空间大小M*小数部分向下取整作为哈希值。即h(Key) M * ( ( A * Key ) % 1.0)这种方法对M大小没有要求。全域散列法了解即可若哈希函数是公开且确定的攻击者就可以刻意制造会发生严重冲突的数据集例如全映射到同一个位置。解决办法就是用全域散列法给哈希函数增加随机性。h(Key) ( (a * Key b) % P) % MP为足够大的质数a为[1,P-1]中的任意随机整数b为[0,P-1]中任意随机整数。因为随机性攻击者无法预测Key会映射到哪一个位置攻击难度增大。其他方法平方折中法、折叠法、随机数法、数学分析法等。处理哈希冲突冲突不可避免遇到冲突需要解决。开放定址法当Key用哈希函数计算出的位置冲突了则按照某种规则找一个没有存储数据的位置进行存储。探测无存储数据的位置有三种规则线性探测、二次探测、双重探测、线性探测从冲突位置开始依次线性向后探测直到寻找到下一个没有存储数据的位置为止如果走到哈希表尾就回到哈希表头。线性探测公式hc(key,i) (h(Key) i) % M, i {1,2,3,4,···,M-1}最多探测M-1次就能找到可以存储的位置。群集/堆积例如哈希值012即hash0、hash1、hash2都存储了数据那么hash0、hash1、hash2、hash3的Key都会争夺hash3的位置。此时使用二次探测可以一定程度改善这种情况。二次(方)探测从冲突位置开始一次左右按二次方跳跃式探测直到寻找到下一个没有存储数据的位置为止如果走到哈希表尾就回到哈希表头。二次探测公式hc(key,i) (h(Key) ± i * i ) % M, i {1,2,3,4,···,M/2}。探测顺序就是哈希值1然后-1接着4之后-4随后9-916-16如此类推。双重散列了解双重散列公式hc(Key, i) ( i *(Key) )% M, i {1,2,3,···,M}。再使用一个不同的哈希函数来获得不同的偏移量值直到寻找到下一个没有存储数据的位置为止。要求(Key) M且两者互为质数。开放定址法代码实现#pragma once #includevector #includeiostream #includemap #includeunordered_map using namespace std; enum State { Empty, Delete, Exist }; templateclass K, class V struct HashData { pairK, V _kv; State _state Empty; }; templateclass K class HashFunc { public: size_t operator()(const K key) { return (size_t)key; } }; //特化 //要把string转为整型才可以被哈希函数 template class HashFuncstring { public: size_t operator()(const string key) { size_t hash 0; for (auto ch : key) { hash ch; hash * 131; //BKDR哈希、DJB哈希、AP哈希··· } return hash; } }; templateclass K,class V,class Hash HashFuncK class HashTable { public: inline unsigned long __stl_next_prime(unsigned long n) { static const int __stl_num_primes 28; static const unsigned long __stl_prime_list[__stl_num_primes] { 53,97,193,389,768.1543,3079,6151,12289,24593,49157,98317,196613,393241,786433 ,1572869,3145739,6291469,12582917,25165843,50331653,100663319,201326611,402653189 ,805306457,1610612741,3221225473,4294967291 }; const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; const unsigned long* pos lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } HashTable() { _tables.resize(__stl_next_prime(1)); } bool Insert(const pairK, V kv) { //若不允许冗余则需要查找一下 if (Find(kv.first)) { return false; } //扩容 if ((double)_n / (double)_tables.size() 0.7) { // //获取素数表内比当前表大的一个素数 // size_t newSize __Stl_next_prime(_tables.size() 1); // //扩容之后要重新映射 // vectorHashDataK, V newTables(newSize); // //遍历旧表将数据重新遍历。 // for (size_t i 0; i _tables.size(); i) // { // if (_tables[i]._state Exist) // { // //... // } // } // _tables.swap(newTables); //} size_t newSize __stl_next_prime(_tables.size() 1); HashTableK, V, Hash newHT; newHT._tables.resize(newSize); //遍历旧表将数据重新遍历。 for (size_t i 0; i _tables.size(); i) { if (_tables[i]._state Exist) { newHT.Insert(_tables[i]._kv); } } //交换之后若函数完毕旧表就刚好被析构销毁 _tables.swap(newHT._tables); } Hash hs; //hash0为哈希值 size_t hash0 hs(kv.first) % _tables.size(); size_t i 1; //hashi为探测值 size_t hashi hash0; while (_tables[hashi]._state Exist) { //冲突探测 hashi (hash0 i) % _tables.size(); i; } _tables[hashi]._kv kv; _tables[hashi]._state Exist; return true; } HashDataK, V* Find(const K key) { Hash hs; size_t hash0 hs(key) % _tables.size(); size_t hashi hash0; size_t i 1; size_t flag 1; while (_tables[hashi]._state ! Empty) { if (_tables[hashi]._state Exist _tables[hashi]._kv.first key) { return _tables[hashi]; } //线性检测 hashi (hash0 i * flag) % _tables.size(); flag * -1; i; } return nullptr; } bool Erase(const K key) { HashDataK, V* ret Find(key); if (ret nullptr) { return false; } else { ret-_state Delete; --_n; return true; } } private: vectorHashDataK, V _tables; size_t _n 0; }; //void TestHT1() //{ // HashTableint, int ht1; // ht1.Insert({ 54,1 }); // ht1.Insert({ 1,1 }); // // cout ht1.Find(1) endl; // cout ht1.Erase(54) endl; // cout ht1.Find(1) endl; // cout ht1.Find(54) endl; // //for (size_t i 0; i 53; i) // //{ // // ht1.Insert({ rand(),i }); // //} //} void TestHT2() { HashTablestring, string,stringHashFunc ht2; ht2.Insert({ sort,排序 }); ht2.Insert({ string,字符串 }); cout stringHashFunc()(abcd) endl; cout stringHashFunc()(bcad) endl; cout stringHashFunc()(abbe) endl; unordered_mapstring, string dictMap; dictMap.insert({ sort,排序 }); dictMap.insert({ string,字符串 }); }链地址法也就是哈希桶我们把哈希冲突的数据以链表的方式链接在一起。如图这样一来负载因子就可以大于1了。链地址法代码实现templateclass, class V struct HashNode { pairK, V _kv; HashNodeK, V* _next; HashNode(const pairK, V kv) :_kv(kv) , _next(nullptr) { } }; templateclass K, class V class HashTable { typedef HashNodeK, V Node; public: inline unsigned long __stl_next_prime(unsigned long n) { static const int __stl_num_primes 28; static const unsigned long __stl_prime_list[__stl_num_primes] { 53,97,193,389,768.1543,3079,6151,12289,24593,49157,98317,196613,393241,786433 ,1572869,3145739,6291469,12582917,25165843,50331653,100663319,201326611,402653189 ,805306457,1610612741,3221225473,4294967291 }; const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; const unsigned long* pos lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } HashTable() { _tables.resize(__stl_next_prime(1), nullptr); } bool Insert(const pairK, V kv) { if (Find(kv.first)) { return false; } //负载因子到1就扩容 if (_n _tables.size()) { size_t newSize __stl_next_prime(_tables.size() 1); vectorNode* newtables(newSize, nullptr); //遍历旧表把旧表的结点挪动到新表 for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; //cur头插到新表 size_t hashi cur-_kv.first % newSize; //让下一个结点为对应哈希值的第一个结点 cur-_next newtables[hashi]; //插在对应哈希值的第一个结点 newtables[hashi] cur; //往下走 cur next; } //旧表置空 _tables[i] nullptr; } //交换哈希表旧表会自动析构 _tables.swap(newtables); } size_t hashi kv.first % _tables.size(); Node* newnode new Node(kv); //头插法 newnode-_next _table[hashi]; _tables[hashi] newnode; _n; return true; } Node* Find(const K key) { size_t hashi key % _tables.size(); Node* cur _tables[hashi]; while (cur) { if (cur-_kv.first key) { return cur; } cur cur-_next; } return nullptr; } bool Erase(const K key) { size_t hashi key % _tables.size(); Node* prev nullptr; Node* cur _tables[hashi]; while (cur) { if (cur-_kv.first key) { // 删除 if (prev nullptr) { // 头删 _tables[hashi] cur-_next; } else { prev-_next cur-_next; } delete cur; return true; } prev cur; cur cur-_next; } return false; } private: vectorNode*_tables; size_t _n 0; };哈希封装只展示代码示例内含解析~HashTable.h#define _CRT_SECURE_NO_WARNINGS 1 // 禁用VS的C运行时安全警告 #includevector // 引入vector容器用于存储哈希表数据 #includeiostream #includeunordered_map #includeunordered_set using namespace std; // 通用哈希函数模板默认适配int等数值类型 templateclass K class HashFunc { public: // 重载()运算符数值类型直接强转为size_t作为哈希值 size_t operator()(const K key) { return (size_t)key; } }; // 哈希函数特化针对string类型解决字符串无法直接强转的问题 template class HashFuncstring { public: size_t operator()(const string key) { size_t hash 0; // 初始化哈希值 for (auto ch : key) // 遍历字符串每个字符 { hash ch; // 累加字符ASCII值 hash * 131; // 乘以131经典哈希系数减少冲突 } return hash; // 返回最终哈希值 } }; // 开放定址法哈希表命名空间 namespace open_address { // 哈希表元素状态枚举解决删除后查找链断裂问题 enum State { EXIST, // 元素存在 EMPTY, // 位置为空 DELETE // 元素已删除伪删除 }; // 哈希表数据节点存储键值对 状态 templateclass K, class V struct HashData { pairK, V _kv; // 键值对 State _state EMPTY; // 初始状态为空 }; // 开放定址法哈希表类模板K-键V-值Hash-哈希函数默认HashFuncK templateclass K, class V, class Hash HashFuncK class HashTable { public: // 私有工具函数获取大于等于n的下一个素数STL经典素数表减少哈希冲突 inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. static const int __stl_num_primes 28; // 素数表长度 static const unsigned long __stl_prime_list[__stl_num_primes] { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; const unsigned long* first __stl_prime_list; // 素数表起始 const unsigned long* last __stl_prime_list __stl_num_primes; // 素数表结束 const unsigned long* pos lower_bound(first, last, n); // 二分找第一个n的素数 return pos last ? *(last - 1) : *pos; // 超出表则返回最后一个素数 } // 构造函数初始化哈希表容量为大于1的第一个素数53 HashTable() { _tables.resize(__stl_next_prime(1)); } // 插入键值对返回是否插入成功重复键返回false bool Insert(const pairK, V kv) { if (Find(kv.first)) // 先查找键已存在则返回false return false; // 扩容条件负载因子已存元素/表容量0.7开放定址法负载因子不宜过高 // if (_n*10 / _tables.size 7) // 注释的扩容写法等价 if ((double)_n / (double)_tables.size() 0.7) { // 注释的扩容逻辑替换为新建哈希表的方式 //size_t newSize __stl_next_prime(_tables.size() 1); //vetcorHashDataK, V newTables(newSize); // 笔误vector拼错 //// 遍历旧表将数据都映射到新表 //for (size_t i 0; i _tables.size(); i) //{ // if (_tables[i]._state EXIST) // { // // ... // } //} //_tables.swap(newTables); size_t newSize __stl_next_prime(_tables.size() 1); // 新容量为下一个素数 HashTableK, V, Hash newHT; // 新建空哈希表 newHT._tables.resize(newSize); // 调整新表容量 // 遍历旧表将有效数据重新插入新表重新计算哈希位置 for (size_t i 0; i _tables.size(); i) { if (_tables[i]._state EXIST) { newHT.Insert(_tables[i]._kv); } } _tables.swap(newHT._tables); // 交换新旧表完成扩容 } Hash hs; // 创建哈希函数对象 size_t hash0 hs(kv.first) % _tables.size(); // 计算初始哈希位置 size_t i 1; // 线性探测步长 size_t hashi hash0; // 当前探测位置 while (_tables[hashi]._state EXIST) { // 线性探测往后找空位置 hashi (hash0 i) % _tables.size(); i; } // 插入数据并更新状态 _tables[hashi]._kv kv; _tables[hashi]._state EXIST; _n; // 有效元素数1 return true; } // 查找键返回数据节点指针找不到返回nullptr HashDataK, V* Find(const K key) { Hash hs; size_t hash0 hs(key) % _tables.size(); // 初始哈希位置 size_t hashi hash0; size_t i 1; while (_tables[hashi]._state ! EMPTY) // 非空位置都要探测包括DELETE { // 找到存在且键匹配的元素 if (_tables[hashi]._state EXIST _tables[hashi]._kv.first key) { return _tables[hashi]; } // 继续线性探测 hashi (hash0 i) % _tables.size(); i; } return nullptr; // 未找到 } // 删除键返回是否删除成功伪删除仅改状态 bool Erase(const K key) { HashDataK, V* ret Find(key); if (ret nullptr) // 未找到 { return false; } else // 伪删除改状态为DELETE不直接清空避免查找链断裂 { --_n; ret-_state DELETE; return true; } } private: vectorHashDataK, V _tables; // 哈希表本体数组 size_t _n 0; // 有效元素个数 }; // 字符串哈希函数冗余仅测试用实际用上面的特化版本 class stringHashFunc { public: size_t operator()(const string s) { size_t hash 0; for (auto ch : s) { hash ch; hash * 131; } return hash; } }; // 开放定址法测试函数 void TestHT1() { HashTableint, int ht1; ht1.Insert({ 54, 1 }); ht1.Insert({ 1, 1 }); cout ht1.Find(1) endl; // 输出地址非空 cout ht1.Erase(54) endl; // 输出1删除成功 cout ht1.Find(1) endl; // 输出地址仍存在 cout ht1.Find(54) endl; // 输出0已删除 /*for (int i 0; i 53; i) { ht1.Insert({rand(), i}); }*/ } // 日期结构体仅占位未实际使用 struct Date { int _year; int _month; int _day; }; // 字符串哈希测试函数 void TestHT2() { //HashTablestring, string, stringHashFunc ht2; // 注释的写法等价 HashTablestring, string ht2; ht2.Insert({ sort, 排序 }); ht2.Insert({ string, 字符串 }); // 测试字符串哈希值验证不同字符串哈希值不同 cout stringHashFunc()(abcd) endl; cout stringHashFunc()(bcad) endl; cout stringHashFunc()(abbe) endl; // 对比标准库unordered_map unordered_mapstring, string dictMap; dictMap.insert({ sort, 排序 }); dictMap.insert({ string, 字符串 }); cout dictMap.load_factor() endl; // 输出负载因子 cout dictMap.max_load_factor() endl;// 输出最大负载因子 } } // 链式哈希表命名空间 namespace hash_bucket { // 链表节点模板存储任意类型数据 templateclass T struct HashNode { T _data; // 存储数据map存pairset存K HashNodeT* _next; // 指向下一个节点 HashNode(const T data) // 构造函数初始化数据next置空 :_data(data) , _next(nullptr) { } }; // 前置声明哈希表类供迭代器使用 templateclass K, class T, class KeyOfT, class Hash class HashTable; // 链式哈希表迭代器模板 // K-键类型T-存储类型Ref-引用类型Ptr-指针类型KeyOfT-提取键的仿函数Hash-哈希函数 templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash struct __HTIterator { typedef HashNodeT Node; // 节点类型 typedef HashTableK, T, KeyOfT, Hash HT; // 哈希表类型 typedef __HTIteratorK, T, Ref, Ptr, KeyOfT, Hash Self; // 迭代器自身类型 Node* _node; // 当前指向的节点 const HT* _ht; // 指向哈希表用于时找下一个桶 // 构造函数初始化节点和哈希表指针 __HTIterator(Node* node, const HT* ht) :_node(node) , _ht(ht) { } // 解引用运算符返回数据的引用 Ref operator*() { return _node-_data; } // 箭头运算符返回数据的指针支持it-first/second Ptr operator-() { return _node-_data; } // 前置迭代器后移核心逻辑 Self operator() { if (_node-_next) // 1. 当前桶内有下一个节点直接走链表 { _node _node-_next; } else // 2. 当前桶走完找下一个非空桶 { KeyOfT kot; // 提取键的仿函数 Hash hs; // 哈希函数 // 计算当前节点所在桶的下标 size_t hashi hs(kot(_node-_data)) % _ht-_tables.size(); hashi; // 从下一个桶开始找 while (hashi _ht-_tables.size()) { if (_ht-_tables[hashi]) // 找到非空桶 { _node _ht-_tables[hashi]; break; } else // 桶为空继续找下一个 { hashi; } } // 所有桶遍历完置空迭代器结束 if (hashi _ht-_tables.size()) { _node nullptr; } } return *this; } // 不等于运算符比较节点指针 bool operator!(const Self s) { return _node ! s._node; } // 等于运算符比较节点指针 bool operator(const Self s) { return _node s._node; } }; // 链式哈希表类模板核心 // K-键类型T-存储类型mappairconst K,Vsetconst KKeyOfT-提取键的仿函数Hash-哈希函数 templateclass K, class T, class KeyOfT, class Hash class HashTable { // 友元迭代器需要访问哈希表私有成员 templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash friend struct __HTIterator; typedef HashNodeT Node; // 节点类型 public: // 迭代器类型定义普通/const typedef __HTIteratorK, T, T, T*, KeyOfT, Hash Iterator; typedef __HTIteratorK, T, const T, const T*, KeyOfT, Hash ConstIterator; // 普通begin返回第一个有效元素的迭代器 Iterator Begin() { for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; if (cur) // 找到第一个非空桶 { return Iterator(cur, this); } } return End(); // 空表返回end } // 普通end返回尾后迭代器nullptr Iterator End() { return Iterator(nullptr, this); } // const版本begin只读遍历 ConstIterator Begin() const { for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; if (cur) { return ConstIterator(cur, this); } } return End(); } // const版本end只读遍历的尾后 ConstIterator End() const { return ConstIterator(nullptr, this); } // 构造函数初始化哈希表容量为53桶指针置空 HashTable() { _tables.resize(__stl_next_prime(1), nullptr); } // 析构函数释放所有节点 ~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; // 桶指针置空 } } // 私有工具函数获取下一个素数同开放定址法 inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. static const int __stl_num_primes 28; static const unsigned long __stl_prime_list[__stl_num_primes] { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; const unsigned long* pos lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } // 插入数据返回pair迭代器, bool迭代器指向元素bool表示是否插入成功 pairIterator, bool Insert(const T data) { KeyOfT kot; // 先查找键已存在则返回{迭代器, false} Iterator it Find(kot(data)); if (it ! End()) return { it, false }; Hash hs; // 负载因子到1就扩容链式哈希表负载因子可更高 if (_n _tables.size()) { size_t newSize __stl_next_prime(_tables.size() 1); vectorNode* newtables(newSize, nullptr); // 新桶数组 // 遍历旧表把旧表的节点挪动到新表 for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; // 保存下一个节点 // cur头插到新表 size_t hashi hs(kot(cur-_data)) % newSize; cur-_next newtables[hashi]; newtables[hashi] cur; cur next; } _tables[i] nullptr; // 旧桶置空 } _tables.swap(newtables); // 交换新旧桶数组 } // 插入新节点头插法 size_t hashi hs(kot(data)) % _tables.size(); // 计算哈希位置 Node* newnode new Node(data); // 新建节点 // 头插到桶里面 newnode-_next _tables[hashi]; _tables[hashi] newnode; _n; // 有效元素数1 return { Iterator(newnode, this), true }; // 返回迭代器和成功标志 } // 查找键返回迭代器找不到返回end Iterator Find(const K key) { Hash hs; size_t hashi hs(key) % _tables.size(); // 计算哈希位置 Node* cur _tables[hashi]; // 指向桶的第一个节点 KeyOfT kot; while (cur) // 遍历桶内链表 { if (kot(cur-_data) key) // 找到匹配键 { return Iterator(cur, this); } cur cur-_next; } return End(); // 未找到 } // 删除键返回是否删除成功 bool Erase(const K key) { Hash hs; KeyOfT kot; size_t hashi hs(key) % _tables.size(); // 哈希位置 Node* prev nullptr; Node* cur _tables[hashi]; while (cur) // 遍历桶内链表找目标节点 { if (kot(cur-_data) key) { // 删除 if (prev nullptr) // 头节点删除 { _tables[hashi] cur-_next; } else // 中间/尾节点删除 { prev-_next cur-_next; } delete cur; // 释放节点 _n--; // 有效元素数-1 return true; } prev cur; cur cur-_next; } return false; // 未找到 } private: //vectorlistpairK, V _tables; // 注释的写法用list替代指针数组 vectorNode* _tables; // 桶数组存储节点指针 size_t _n 0; // 表中存储数据个数 }; }unorderedset.h#pragma once // 防止头文件重复包含 // 依赖HashTable.h链式哈希表的核心实现 #include HashTable.h namespace bit { // unordered_set类模板单值存储元素唯一 templateclass K, class Hash HashFuncK class unordered_set { // 仿函数从K中提取键set的元素就是键 struct SetKeyOfT { const K operator()(const K key) { return key; // 直接返回自身 } }; public: // 迭代器类型定义存储const K元素不可修改 typedef typename hash_bucket::HashTableK, const K, SetKeyOfT, Hash::Iterator iterator; typedef typename hash_bucket::HashTableK, const K, SetKeyOfT, Hash::ConstIterator const_iterator; // 普通begin返回第一个有效元素的迭代器 iterator begin() { return _ht.Begin(); } // 普通end返回尾后迭代器 iterator end() { return _ht.End(); } // const版本begin只读遍历 const_iterator begin() const { return _ht.Begin(); } // const版本end只读遍历的尾后 const_iterator end() const { return _ht.End(); } // 插入元素单值返回pair迭代器, bool区分插入成功/元素已存在 pairiterator, bool insert(const K key) { return _ht.Insert(key); } private: // 底层存储链式哈希表存储const K元素不可修改 hash_bucket::HashTableK, const K, SetKeyOfT, Hash _ht; }; // 打印const的unordered_set只能用const迭代器 void Print(const unordered_setint s) { unordered_setint::const_iterator it s.begin(); while (it ! s.end()) { // *it 1; // 错误set元素不可修改 cout *it ; it; } cout endl; } // unordered_set测试函数 void test_set1() { unordered_setint s; s.insert(1); s.insert(12); s.insert(54); s.insert(107); // 普通迭代器遍历 unordered_setint::iterator it s.begin(); while (it ! s.end()) { // *it 1; // 错误set元素不可修改 cout *it ; it; } cout endl; // 范围for遍历底层调用begin/end for (auto e : s) { cout e ; } cout endl; } }unorderedmap.h#pragma once // 防止头文件重复包含 // 依赖HashTable.h链式哈希表的核心实现 #include HashTable.h namespace bit { // unordered_map类模板键值对存储键唯一 templateclass K, class V, class Hash HashFuncK class unordered_map { // 仿函数从pairK,V中提取键给底层哈希表用 struct MapKeyOfT { const K operator()(const pairK, V kv) { return kv.first; // 返回pair的第一个元素键 } }; public: // 迭代器类型定义重命名底层哈希表的迭代器 // 存储类型为pairconst K,V键不可修改符合map特性 typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash::Iterator iterator; typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash::ConstIterator const_iterator; // 普通begin返回第一个有效元素的迭代器 iterator begin() { return _ht.Begin(); } // 普通end返回尾后迭代器 iterator end() { return _ht.End(); } // const版本begin只读遍历 const_iterator begin() const { return _ht.Begin(); } // const版本end只读遍历的尾后 const_iterator end() const { return _ht.End(); } // 插入键值对返回pair迭代器, bool区分插入成功/键已存在 pairiterator, bool insert(const pairK, V kv) { return _ht.Insert(kv); } // []运算符重载核心接口支持map[key] value 或 map[key]取值 V operator[](const K key) { // 插入{key, 默认值}不存在则插入存在则返回已存在元素 pairiterator, bool ret _ht.Insert(make_pair(key, V())); // 返回值的引用可修改如map[a] b return ret.first-second; } private: // 底层存储链式哈希表存储pairconst K,V键不可修改 hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash _ht; }; // 打印const的unordered_map只能用const迭代器 void Print(const unordered_mapstring, string dict) { unordered_mapstring, string::const_iterator it dict.begin(); while (it ! dict.end()) { //it-first x; // 错误const迭代器不能修改键 //it-second x; // 错误const迭代器不能修改值 cout it-first it-second; it; } cout endl; } // unordered_map测试函数 void test_map1() { unordered_mapstring, string dict; unordered_mapstring, string::iterator it dict.begin(); while (it ! dict.end()) { //it-first x; // 错误map的键不可修改 it-second x; // 正确值可以修改 cout it-first it-second; it; } cout endl; // 统计字符串出现次数map的核心场景 string arr[] { ƻ, , ƻ, , ƻ, ƻ, , ƻ, 㽶, ƻ, 㽶 }; unordered_mapstring, int countMap; for (const auto str : arr) { countMap[str]; // 核心用法不存在则插入{str,0}再存在则直接 } // 遍历输出统计结果 for (const auto e : countMap) { cout e.first : e.second endl; } cout endl; } }❤~~本文完结感谢观看接下来更精彩欢迎来我博客做客~~❤
