哈希——unordered系列关联式容器
目录
unordered系列关联式容器
概念
unordered_map
无序+去重
operator[]
unordered_set
无序+去重
OJ练习题
重复n次的元素
两个数组的交集
两个数的交集二
底层结构
概念
哈希冲突
闭散列
结点的定义
扩容
字符串取模
插入
查找
删除
闭散列完整代码
开散列
结点定义
释放桶(析构函数)
扩容
插入
查找
删除
开散列完整代码
用开散列哈希表封装unordered系列容器
HashTable.h
UnorderSet.h
UnorderMap.h
unordered系列关联式容器
概念
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 log2n，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。map与set的底层是红黑树，然而unordered_map和unordered_set的底层使用的是哈希表。
unordered_map
无序+去重
我们需要注意的是unordered_map中存放的是键值对，并且去重也是根据key来进行去重的。
int main()
{unordered_map<int, int> ump;ump.insert(make_pair<int, int>(8, 0));ump.insert(make_pair<int, int>(6, 0));ump.insert(make_pair<int, int>(4, 0));ump.insert(make_pair<int, int>(8, 0));ump.insert(make_pair<int, int>(5, 0));ump.insert(make_pair<int, int>(0, 0));ump.insert(make_pair<int, int>(8, 0));for (auto e : ump){cout << e.first << ":" << e.second << endl;}return 0;
}
operator[]
operator[]是unordered_map独有的，unordered_set中并没有这个操作符，operator[]的主要作用是通过key可以访问并且修改value的值，非常好用。
int main()
{unordered_map<int, int> ump;ump.insert(make_pair<int, int>(8, 0));ump.insert(make_pair<int, int>(6, 0));ump.insert(make_pair<int, int>(4, 0));ump.insert(make_pair<int, int>(8, 0));ump.insert(make_pair<int, int>(5, 0));ump.insert(make_pair<int, int>(0, 0));ump.insert(make_pair<int, int>(8, 0));ump[5] = 10;for (auto& e : ump){cout << e.first << ":" << e.second << endl;}return 0;
}
unordered_set
无序+去重
这个跟unordered_map一样，只不过unordered_map传入的是键值对pair<K,V>然而unordered_set传入的则是K(实质是pair<K,V>)。
并且unordered_set并不支持operator[]。
OJ练习题
重复n次的元素
力扣
方法一：巧用unordered_set中的count函数来操作。
count函数具体作用，详见C++—— set、map、multiset、multimap_袁百万的博客-CSDN博客
class Solution {
public:
//分析题目非常关键，题中明确说明一共有2*n个元素，其中包含
//n+1个不同的元素，且有一个元素重复了n次，那么由此我们可以得出
//除了重复n次那个元素，其余元素都不可能重复。
//那么只要找到有重复的 其值就是我们要找的重复n次的数int repeatedNTimes(vector<int>& nums) {unordered_set<int> found;for (auto num: nums) {//如果遍历的时候此数已经在found中了//说明次数已经出现两次了，返回此数if (found.count(num)) {return num;}//反之，没有出现次数就将其插入foundfound.insert(num);}return -1;}
};方法二：使用unordered_map中的[]来统计每个数出现的次数，根据次数求得答案。
class Solution {
public:int repeatedNTimes(vector<int>& nums) {unordered_map<int,int> ump;//利用[]来对每个数进行计数for(auto& e:nums){ump[e]++;}int n=nums.size()/2;for(auto& e:ump){//若某个数的个数为n则说明该数就是重复n次的数if(e.second==n)return e.first;}return 0;}
};两个数组的交集
力扣
class Solution
{
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> v;//分别对nums1和nums2进行去重unordered_set<int> ust1,ust2;for(auto e: nums1){ust1.insert(e);}for(auto e: nums2){ust2.insert(e);}// 遍历ust2,，若ust2的值在ust1也存在则存入v中for(auto e : ust2){if(ust1.count(e)){v.push_back(e);}}// 返回vreturn v;}
};两个数的交集二
力扣
class Solution
{
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {unordered_map<int,int> ump1;unordered_map<int,int> ump2;vector<int> v;for(auto e : nums1){ump1[e]++;}for(auto e : nums2){ump2[e]++;}for(auto e : ump2){if(ump1.count(e.first)){int count=ump1[e.first]>=ump2[e.first]?ump2[e.first]:ump1[e.first];// int count=0;// if(ump1[e.first]>=ump2[e.first])// count=ump2[e.first];// else// count=ump1[e.first];for(int i=0;i<count;i++)v.push_back(e.first);}}return v;}
};底层结构
unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。
概念
哈希方法是以映射的方式搜索或者插入元素，因此效率极高。哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)。
哈希冲突
虽然是通过映射(取模)的方式去找自己的位置，但是总有映射到相同位置的数据，该现象称为哈希冲突或者哈希碰撞。
闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。
注意：当我们删除元素的时候不能直接删除，这样会影响其他元素的查找。比如删除了元素4，那么我们在查找44的时候就很难去寻找了。因此我们选择来使用伪删除的方式，给每个空间设置一个状态位，通过修改他们的状态来达到删除的作用。
enum State{EMPTY,//0EXIST,//1DELETE,//2};结点的定义
template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;//自定义类型会调用他的默认构造，内置类型不处理};扩容
我们是根据负载因子的大小进行扩容的，负载因子=填入表中的元素个数/散列表的长度。
一般情况下我们是控制在0.7的，这样能降低哈希冲突。
//注意判断载荷因子的时候类型需要转换if (_n * 1.0 / _tables.size() >= 0.7){//扩容之后映射位置发生改变，不能直接把数据给拷贝进来//因此需要搞一个新表，重新去算映射的位置//这里还是线性探测，如果遇到位置有值，就向后探测// //旧表数据，重新计算，映射到新表/*vector<Data> newTable;newTable.resize(2 * _tables.size());for (){}*///创建新表HashTable<K, V, Hash> newHT;//局部对象出作用域销毁//大小扩容二倍newHT._tables.resize(_tables.size() * 2);//将旧表数据插入到新表中for (auto& e : _tables)//&减少拷贝{//旧表中位置存在才插入if (e._state == EXIST){//复用了旧表的插入 newHT.Insert(e._kv);}}//最后交换旧表与新表，由于新表是局部对象，出作用域自动销毁_tables.swap(newHT._tables);}字符串取模
我们在学习map和set的时候了解到有时我们会使用map来统计水果的次数，其实unordered_map也可以统计水果的次数。那么就避免不了key传的是string，也就是pair<string,int>这种情况，我们在插入数据的时候需要注意的是需要对key进行取模，根据取模得到的数据来在表中找出对应的值，那么如果我们传的是字符串的话应该怎么取模呢。
我们在学习红黑树的时候我们知道，key的作用是来比较大小的，也根据比较大小来确定这个结点的位置。那么在哈希表这一节课中，我们的key就是用来取模的，因为只有你能取模才能找到映射的位置，进而才能插入数据等等。
我们这里使用仿函数来解决这个问题。
//仿函数
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
//模板的特化
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;//BKDRhashfor (auto ch : key){hash *= 131;hash += ch;}return hash;}
};至于为什么将每一位*131然后相加后取模请查看以下文档，这个是C语言之父写的一本书中提到的并且这个BKDRhash的方法是最优的。
https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html
插入
bool Insert(const pair<K, V>& kv)//传引用减少拷贝{//如果已经存在我们需要插入的值，则直接返回falseif (Find(kv.first))return false;//注意判断载荷因子的时候类型需要转换if (_n * 1.0 / _tables.size() >= 0.7){//扩容之后映射位置发生改变，不能直接把数据给拷贝进来//因此需要搞一个新表，重新去算映射的位置//这里还是线性探测，如果遇到位置有值，就向后探测// //旧表数据，重新计算，映射到新表/*vector<Data> newTable;newTable.resize(2 * _tables.size());for (){}*///创建新表HashTable<K, V, Hash> newHT;//局部对象出作用域销毁//大小扩容二倍newHT._tables.resize(_tables.size() * 2);//将旧表数据插入到新表中for (auto& e : _tables)//&减少拷贝{//旧表中位置存在才插入if (e._state == EXIST){//复用了旧表的插入 newHT.Insert(e._kv);}}//最后交换旧表与新表，由于新表是局部对象，出作用域自动销毁_tables.swap(newHT._tables);}Hash hf;//hashi为存入的数据对表长进行取模size_t hashi = hf(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){//线性探测hashi++;//探测完之后需要再次模sizehashi %= _tables.size();}//将该结点赋给hashi位置_tables[hashi]._kv = kv;//改变状态_tables[hashi]._state = EXIST;//表中的有效数据++_n++;return true;}当我们明白了如何对字符串进行取模后，其实插入就迎刃而解了。先取模找到该元素的位置，然后去寻找合适的位置插入。
查找
//这里返回所找到结点的地址是为了便于删除操作Data* Find(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();size_t starti = hashi;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];//返回这个位置的地址}hashi++;hashi %= _tables.size();//极端情况下：哈希表中没有空的，全是存在或者删除状态if (hashi == starti){break;}}return nullptr;}我们这的查找返回Data*是为了便于进行下面的删除操作，在这里需要注意的是极端情况下，哈希表是满的并且全是存在或者删除状态，也就是没有地方插入，那么hashi已经遍历了一圈之后就让其break;就行了。
删除
bool Erase(const K& key){Data* ret = Find(key);//如果找到了返回找到的地址if (ret->_state != EMPTY)//检查状态是否存在{ret->_state = DELETE;_n--;//把有效数据数量-1return true;}elsereturn false;/*删除失败返回false*/}复用我们前面实现的查找，如果找到了就将其状态位设置为DELETE并且将_n减一，并且返回true如果删除失败返回false即可。
闭散列完整代码
//仿函数
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
//模板的特化
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;//BKDRhashfor (auto ch : key){hash *= 131;hash += ch;}return hash;}
};
namespace closehash
{//状态enum State{EMPTY,//0EXIST,//1DELETE,//2};////struct HashFuncString//{// size_t operator()(const string& key)// {// size_t hash = 0;// for (auto ch : key)// {// hash += ch;// }// return hash;// //return key[0];// }//};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;//自定义类型会调用他的默认构造，内置类型不处理};template<class K, class V, class Hash = HashFunc<K>>//并且给个缺省的class HashTable{typedef HashData<K, V> Data;public://构造函数用于初始化HashTable():_n(0){_tables.resize(10);}bool Insert(const pair<K, V>& kv)//传引用减少拷贝{//如果已经存在我们需要插入的值，则直接返回falseif (Find(kv.first))return false;//注意判断载荷因子的时候类型需要转换if (_n * 1.0 / _tables.size() >= 0.7){//扩容之后映射位置发生改变，不能直接把数据给拷贝进来//因此需要搞一个新表，重新去算映射的位置//这里还是线性探测，如果遇到位置有值，就向后探测// //旧表数据，重新计算，映射到新表/*vector<Data> newTable;newTable.resize(2 * _tables.size());for (){}*///创建新表HashTable<K, V, Hash> newHT;//局部对象出作用域销毁//大小扩容二倍newHT._tables.resize(_tables.size() * 2);//将旧表数据插入到新表中for (auto& e : _tables)//&减少拷贝{//旧表中位置存在才插入if (e._state == EXIST){//复用了旧表的插入 newHT.Insert(e._kv);}}//最后交换旧表与新表，由于新表是局部对象，出作用域自动销毁_tables.swap(newHT._tables);}Hash hf;//hashi为存入的数据对表长进行取模size_t hashi = hf(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){//线性探测hashi++;//探测完之后需要再次模sizehashi %= _tables.size();}//将该结点赋给hashi位置_tables[hashi]._kv = kv;//改变状态_tables[hashi]._state = EXIST;//表中的有效数据++_n++;return true;}//这里返回所找到结点的地址是为了便于删除操作Data* Find(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();size_t starti = hashi;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];//返回这个位置的地址}hashi++;hashi %= _tables.size();//极端情况下：哈希表中没有空的，全是存在或者删除状态if (hashi == starti){break;}}return nullptr;}bool Erase(const K& key){Data* ret = Find(key);//如果找到了返回找到的地址if (ret->_state != EMPTY)//检查状态是否存在{ret->_state = DELETE;_n--;//把有效数据数量-1return true;}elsereturn false;/*删除失败返回false*/}private://该vector里面存的是结点的值vector<Data> _tables;size_t _n = 0; //表中存储的有效数据的个数};void TestHT1(){HashTable<int, int> ht;int a[] = { 18,8,7,27,57,38 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(17, 17));ht.Insert(make_pair(18, 18));ht.Insert(make_pair(5, 5));ht.Insert(make_pair(2, 2));ht.Insert(make_pair(1, 1));ht.Erase(1);cout << "Find(1)：" << ht.Find(1) << endl;/*for (auto e : ht){cout << e << " ";}cout << endl;*/}void TestHT2(){//这里是为了统计水果的次数//但是有一个致命的问题就是我们的key是一个string类型的//在通过key找该结点在哈希表中的位置的时候需要取模//我们忽略了一个问题，string对int取模，很明显是行不通的string arr[] = { "苹果","梨","桃子" };//countHT只是一个哈希表//HashTable<string, int, HashFuncString> countHT;HashTable<string, int> countHT;//我们要对结点里面的对象进行操作的话//需要定义一个结点的对象来接受Find返回的指针for (auto& e : arr){HashData<string, int>* ret = countHT.Find(e);if (ret)//如果条件为真，就是找到了//ret是指向结点的指针{//通过ret找到_kv再找到secondret->_kv.second++;}elsecountHT.Insert(make_pair(e, 1));}HashFunc<string> hf;cout << hf("abc") << endl;cout << hf("bac") << endl;cout << hf("acb") << endl;cout << hf("add") << endl;}
}开散列
开散列才是我们这章学习的重点，unordered系列的容器底层就是这种开散列的方式。这种方式的优越性极强。其意思就是在表的每个位置挂一个单链表，当具有相同映射位置时将它们串成一个链表链接到一起。每一个子集称为一个桶，各个桶(单链表)的头结点存放在哈希表中。
每个桶中存放的都是发生哈希冲突的元素。
结点定义
template<class K, class V>//结点的结构体里面存放一个指针struct HashNode{pair<K, V> _kv;HashNode* _next;HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}};由于哈希表每个位置放的是一个哈希桶，因此结点中应该定义一个_next用来遍历每个哈希桶中的数据。
释放桶(析构函数)
~HashTable(){for (size_t i = 0; i < _tables.size(); i++){//释放桶~HashTable()Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] == nullptr;}}遍历并释放每个桶中的每个结点，最后将每个桶的头结点置空。
扩容
大小
当我们去看源码的时候发现源码中为扩容后哈希表的大小给了特定了一些值。这些值均为素数，由于素数具有特殊的性质因此一定条件下可以减小哈希冲突。因此我将源码中的这个数组应用于我写的这个扩容。
注意：并且在开散列中负载因子不将遵循小于0.7的限制走，而是负载因子等于1的时候就扩容。
方式
在以下代码中是有两种方式的:
第一种：建立新表，新表的大小开到我们所定义数组中的下一个素数的位置。
遍历旧表，将遍历的值挨个插入到新表中。然后交换两个表，此时新表会由于是局部对象，调用默认的析构函数将其释放空间。
第二种：直接使用旧表中的结点链接到新表中，通过遍历旧表完成。
第二种的优点：第一种每次遍历旧表插入到新表的时候都会挨个创建每个结点的值，到最后还是会调用析构函数进行销毁，那这些结点创建的意义就非常小。
然而第二种方法，并不用创建新的结点，提高了效率，倘若我们需要插入10000个数据，那么就少创建了10000个结点，效率较高，因此我们在这里选择第二种。
//负载因子控制在1，超过1就扩容if (_tables.size() == _n){第一种情况，创建一个新的哈希表是为了使用哈希表中的insert函数// //创建一个新的哈希表// // //创建新表// //局部对象出作用域销毁// // //这一步会调用我们所给的构造函数去对newHT里面的成员变量进行初始化// HashTable<K, V, Hash> newHT;// newHT._tables.resize(_tables.size() * 2);// //将旧表数据插入到新表中// for (auto& cur : _tables)//&减少拷贝// {// //遍历旧表的数据// while (cur)// {// newHT.Insert(cur->_kv);// cur = cur->_next;// }// }// //最后交换旧表与新表，由于新表是局部对象，出作用域自动销毁// _tables.swap(newHT._tables);vector<Node*> newTables;//newTables.resize(2 * _tables.size(), nullptr);// 遍历旧表将旧表中的结点头插到新表中。// 这样就不用创建新的结点。 newTables.resize(__stl_next_prime(_tables.size()), nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = Hash()(cur->_kv.first) % newTables.size();//头插到新表cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}//移动玩一个桶之后，将旧表此结点的位置置空_tables[i] = nullptr;}_tables.swap(newTables);}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, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};for (int i = 0; i < __stl_num_primes; i++){if (__stl_prime_list[i] > n){return __stl_prime_list[i];}}return __stl_prime_list[__stl_num_primes - 1];}插入
扩容解决后插入就很简单了，遍历哈希表，找到该数据对应的桶。然后通过我们之前学习单链表的方式进行链接操作。
bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;//负载因子控制在1，超过1就扩容if (_tables.size() == _n){第一种情况，创建一个新的哈希表是为了使用哈希表中的insert函数// //创建一个新的哈希表// // //创建新表// //局部对象出作用域销毁// // //这一步会调用我们所给的构造函数去对newHT里面的成员变量进行初始化// HashTable<K, V, Hash> newHT;// newHT._tables.resize(__stl_next_prime(_tables.size());// //将旧表数据插入到新表中// for (auto& cur : _tables)//&减少拷贝// {// //遍历旧表的数据// while (cur)// {// newHT.Insert(cur->_kv);// cur = cur->_next;// }// }// //最后交换旧表与新表，由于新表是局部对象，出作用域自动销毁// _tables.swap(newHT._tables);vector<Node*> newTables;//newTables.resize(2 * _tables.size(), nullptr);// 遍历旧表将旧表中的结点头插到新表中。// 这样就不用创建新的结点。 newTables.resize(__stl_next_prime(_tables.size()), nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = Hash()(cur->_kv.first) % newTables.size();//头插到新表cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}//移动玩一个桶之后，将旧表此结点的位置置空_tables[i] = nullptr;}_tables.swap(newTables);}//Hash hf;//用仿函数进行转换然后取模size_t hashi = Hash()(kv.first) % _tables.size();//定义一个新结点//这一步会调用构造函数对kv和_next进行初始化Node* newnode = new Node(kv);//链接--头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return true;}查找
遍历，返回。
Node* Find(const K& key){size_t hashi = Hash()(key) % _tables.size();//cur定义为映射后hashi映射位置哈希桶的头结点Node* cur = _tables[hashi];//遍历桶里面的每个结点，看是否与key相同while (cur){if (cur->_kv.first == key){return cur;}else{cur = cur->_next;}}return nullptr;}删除
复用查找。
注意：当我们需要删除一个节点的时候我们需要将它的前驱结点与后继结点进行链接，因此我们需要定义一个前驱指针。
bool Erase(const K& key){size_t hashi = Hash()(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){//找到了if (cur->_kv.first == key){//准备删除//如果需要删除的就是头结点if (cur == _tables[hashi]){_tables[hashi] = cur->_next;}//需要删除的非头结点else{//将自己的前驱指针指向自己的后继指针 prev->_next = cur->_next;}delete cur;_n--;//元素-1return true;}else{prev = cur;cur = cur->_next;}}return false;}开散列完整代码
#pragma once
//仿函数
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
//模板的特化
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;//BKDRhashfor (auto ch : key){hash *= 131;hash += ch;}return hash;/*size_t hash = 0;for (auto ch : key){hash += ch;}return hash;*/}
};
namespace closehash
{//状态enum State{EMPTY,//0EXIST,//1DELETE,//2};////struct HashFuncString//{// size_t operator()(const string& key)// {// size_t hash = 0;// for (auto ch : key)// {// hash += ch;// }// return hash;// //return key[0];// }//};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;//自定义类型会调用他的默认构造，内置类型不处理};template<class K, class V, class Hash = HashFunc<K>>//并且给个缺省的class HashTable{typedef HashData<K, V> Data;public://构造函数用于初始化HashTable():_n(0){_tables.resize(10);}bool Insert(const pair<K, V>& kv)//传引用减少拷贝{//如果已经存在我们需要插入的值，则直接返回falseif (Find(kv.first))return false;//注意判断载荷因子的时候类型需要转换if (_n * 1.0 / _tables.size() >= 0.7){//扩容之后映射位置发生改变，不能直接把数据给拷贝袭来//因此需要搞一个新表，重新去算映射的位置//这里还是线性探测，如果遇到位置有值，就向后探测// //旧表数据，重新计算，映射到新表/*vector<Data> newTable;newTable.resize(2 * _tables.size());for (){}*///创建新表HashTable<K, V, Hash> newHT;//局部对象出作用域销毁//大小扩容二倍newHT._tables.resize(_tables.size() * 2);//将旧表数据插入到新表中for (auto& e : _tables)//&减少拷贝{//旧表中位置存在才插入if (e._state == EXIST){//复用了旧表的插入 newHT.Insert(e._kv);}}//最后交换旧表与新表，由于新表是局部对象，出作用域自动销毁_tables.swap(newHT._tables);}Hash hf;//hashi为存入的数据对表长进行取模size_t hashi = hf(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){//线性探测hashi++;//探测完之后需要再次模sizehashi %= _tables.size();}//将该结点赋给hashi位置_tables[hashi]._kv = kv;//改变状态_tables[hashi]._state = EXIST;//表中的有效数据++_n++;return true;}//这里返回所找到结点的地址是为了便于删除操作Data* Find(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];//返回这个位置的地址}hashi++;hashi %= _tables.size();}return nullptr;}bool Erase(const K& key){Data* ret = Find(key);//如果找到了返回找到的地址if (ret->_state != EMPTY)//检查状态是否存在{ret->_state = DELETE;_n--;//把有效数据数量-1}elsereturn false;/*删除失败返回false*/}private://该vector里面存的是结点的值vector<Data> _tables;size_t _n = 0; //表中存储的有效数据的个数};void TestHT1(){HashTable<int, int> ht;int a[] = { 18,8,7,27,57,38 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(17, 17));ht.Insert(make_pair(18, 18));ht.Insert(make_pair(5, 5));ht.Insert(make_pair(2, 2));ht.Insert(make_pair(1, 1));ht.Erase(1);cout << "Find(1)：" << ht.Find(1) << endl;/*for (auto e : ht){cout << e << " ";}cout << endl;*/}void TestHT2(){//这里是为了统计水果的次数//但是有一个致命的问题就是我们的key是一个string类型的//在通过key找该结点在哈希表中的位置的时候需要取模//我们忽略了一个问题，string对int取模，很明显是行不通的string arr[] = { "苹果","梨","桃子" };//countHT只是一个哈希表//HashTable<string, int, HashFuncString> countHT;HashTable<string, int> countHT;//我们要对结点里面的对象进行操作的话//需要定义一个结点的对象来接受Find返回的指针for (auto& e : arr){HashData<string, int>* ret = countHT.Find(e);if (ret)//如果条件为真，就是找到了//ret是指向结点的指针{//通过ret找到_kv再找到secondret->_kv.second++;}elsecountHT.Insert(make_pair(e, 1));}HashFunc<string> hf;cout << hf("abc") << endl;cout << hf("bac") << endl;cout << hf("acb") << endl;cout << hf("add") << endl;}
}namespace buckethash
{template<class K, class V>//结点的结构体里面存放一个指针struct HashNode{pair<K, V> _kv;HashNode* _next;HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}};template<class K, class V, class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:HashTable():_n(0){_tables.resize(__stl_next_prime(0));}~HashTable(){for (size_t i = 0; i < _tables.size(); i++){//释放桶~HashTable()Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] == nullptr;}}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;//负载因子控制在1，超过1就扩容if (_tables.size() == _n){第一种情况，创建一个新的哈希表是为了使用哈希表中的insert函数// //创建一个新的哈希表// // //创建新表// //局部对象出作用域销毁// // //这一步会调用我们所给的构造函数去对newHT里面的成员变量进行初始化// HashTable<K, V, Hash> newHT;// newHT._tables.resize(__stl_next_prime(_tables.size());// //将旧表数据插入到新表中// for (auto& cur : _tables)//&减少拷贝// {// //遍历旧表的数据// while (cur)// {// newHT.Insert(cur->_kv);// cur = cur->_next;// }// }// //最后交换旧表与新表，由于新表是局部对象，出作用域自动销毁// _tables.swap(newHT._tables);vector<Node*> newTables;//newTables.resize(2 * _tables.size(), nullptr);// 遍历旧表将旧表中的结点头插到新表中。// 这样就不用创建新的结点。 newTables.resize(__stl_next_prime(_tables.size()), nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = Hash()(cur->_kv.first) % newTables.size();//头插到新表cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}//移动玩一个桶之后，将旧表此结点的位置置空_tables[i] = nullptr;}_tables.swap(newTables);}//Hash hf;//用仿函数进行转换然后取模size_t hashi = Hash()(kv.first) % _tables.size();//定义一个新结点//这一步会调用构造函数对kv和_next进行初始化Node* newnode = new Node(kv);//链接--头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return true;}Node* Find(const K& key){size_t hashi = Hash()(key) % _tables.size();//cur定义为映射后hashi映射位置哈希桶的头结点Node* cur = _tables[hashi];//遍历桶里面的每个结点，看是否与key相同while (cur){if (cur->_kv.first == key){return cur;}else{cur = cur->_next;}}return nullptr;}bool Erase(const K& key){size_t hashi = Hash()(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){//找到了if (cur->_kv.first == key){//准备删除//如果需要删除的就是头结点if (cur == _tables[hashi]){_tables[hashi] = cur->_next;}//需要删除的非头结点else{//将自己的前驱指针指向自己的后继指针 prev->_next = cur->_next;}delete cur;_n--;//元素-1return true;}else{prev = cur;cur = cur->_next;}}return false;}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, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};for (int i = 0; i < __stl_num_primes; i++){if (__stl_prime_list[i] > n){return __stl_prime_list[i];}}return __stl_prime_list[__stl_num_primes - 1];}private://指针数组 数组的每一个元素是一个指针vector<Node*> _tables;//指针数组size_t _n = 0;};void TestHT1(){HashTable<int, int> ht;int a[] = { 18,8,7,27,57,3,38,18,17,88,38,28 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(5, 5));ht.Erase(17);ht.Erase(57);}void TestHT2(){string arr[] = { "苹果","梨","桃子" };HashTable<string, int> countHT;for (auto& e : arr){HashNode<string, int >* ret = countHT.Find(e);//auto ret = countHT.Find(e);if (ret){ret->_kv.second++;}elsecountHT.Insert(make_pair(e, 1));}}
}用开散列哈希表封装unordered系列容器
仅为了解，并包含迭代器。
HashTable.h
#pragma once
//仿函数
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
//模板的特化
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;//BKDRhashfor (auto ch : key){hash *= 131;hash += ch;}return hash;}
};
namespace closehash
{//状态enum State{EMPTY,//0EXIST,//1DELETE,//2};////struct HashFuncString//{// size_t operator()(const string& key)// {// size_t hash = 0;// for (auto ch : key)// {// hash += ch;// }// return hash;// //return key[0];// }//};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;//自定义类型会调用他的默认构造，内置类型不处理};template<class K, class V, class Hash = HashFunc<K>>//并且给个缺省的class HashTable{typedef HashData<K, V> Data;public://构造函数用于初始化HashTable():_n(0){_tables.resize(10);}bool Insert(const pair<K, V>& kv)//传引用减少拷贝{//如果已经存在我们需要插入的值，则直接返回falseif (Find(kv.first))return false;//注意判断载荷因子的时候类型需要转换if (_n * 1.0 / _tables.size() >= 0.7){//扩容之后映射位置发生改变，不能直接把数据给拷贝进来//因此需要搞一个新表，重新去算映射的位置//这里还是线性探测，如果遇到位置有值，就向后探测// //旧表数据，重新计算，映射到新表/*vector<Data> newTable;newTable.resize(2 * _tables.size());for (){}*///创建新表HashTable<K, V, Hash> newHT;//局部对象出作用域销毁//大小扩容二倍newHT._tables.resize(_tables.size() * 2);//将旧表数据插入到新表中for (auto& e : _tables)//&减少拷贝{//旧表中位置存在才插入if (e._state == EXIST){//复用了旧表的插入 newHT.Insert(e._kv);}}//最后交换旧表与新表，由于新表是局部对象，出作用域自动销毁_tables.swap(newHT._tables);}Hash hf;//hashi为存入的数据对表长进行取模size_t hashi = hf(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){//线性探测hashi++;//探测完之后需要再次模sizehashi %= _tables.size();}//将该结点赋给hashi位置_tables[hashi]._kv = kv;//改变状态_tables[hashi]._state = EXIST;//表中的有效数据++_n++;return true;}//这里返回所找到结点的地址是为了便于删除操作Data* Find(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();size_t starti = hashi;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];//返回这个位置的地址}hashi++;hashi %= _tables.size();//极端情况下：哈希表中没有空的，全是存在或者删除状态if (hashi == starti){break;}}return nullptr;}bool Erase(const K& key){Data* ret = Find(key);//如果找到了返回找到的地址if (ret->_state != EMPTY)//检查状态是否存在{ret->_state = DELETE;_n--;//把有效数据数量-1return true;}elsereturn false;/*删除失败返回false*/}private://该vector里面存的是结点的值vector<Data> _tables;size_t _n = 0; //表中存储的有效数据的个数};void TestHT1(){HashTable<int, int> ht;int a[] = { 18,8,7,27,57,38 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(17, 17));ht.Insert(make_pair(18, 18));ht.Insert(make_pair(5, 5));ht.Insert(make_pair(2, 2));ht.Insert(make_pair(1, 1));ht.Erase(1);cout << "Find(1)：" << ht.Find(1) << endl;/*for (auto e : ht){cout << e << " ";}cout << endl;*/}void TestHT2(){//这里是为了统计水果的次数//但是有一个致命的问题就是我们的key是一个string类型的//在通过key找该结点在哈希表中的位置的时候需要取模//我们忽略了一个问题，string对int取模，很明显是行不通的string arr[] = { "苹果","梨","桃子" };//countHT只是一个哈希表//HashTable<string, int, HashFuncString> countHT;HashTable<string, int> countHT;//我们要对结点里面的对象进行操作的话//需要定义一个结点的对象来接受Find返回的指针for (auto& e : arr){HashData<string, int>* ret = countHT.Find(e);if (ret)//如果条件为真，就是找到了//ret是指向结点的指针{//通过ret找到_kv再找到secondret->_kv.second++;}elsecountHT.Insert(make_pair(e, 1));}HashFunc<string> hf;cout << hf("abc") << endl;cout << hf("bac") << endl;cout << hf("acb") << endl;cout << hf("add") << endl;}
}namespace buckethash
{template<class T>//结点的结构体里面存放一个指针struct HashNode{//pair<K, V> _kv;T _data;HashNode<T>* _next;//HashNode(const pair<K, T>& kv)// :_kv(kv)// , _next(nullptr)//{}HashNode(const T& data):_data(data), _next(nullptr){}};//迭代器用哈希表 —— 哈希表用迭代器//所以要使用前置声明//前置声明template<class K, class T, class Hash, class KeyOfT>class HashTable;//为什么const迭代器没有复用普通迭代器template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>struct __HTIterator{typedef HashNode<T> Node;typedef __HTIterator<K, T, Ref, Ptr, Hash, KeyOfT> Self;typedef HashTable<K, T, Hash, KeyOfT> HT;Node* _node;HT* _ht;__HTIterator(Node* node, HT* ht):_node(node), _ht(ht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s)const{return _node != s._node;}Self& operator++(){if (_node->_next){_node = _node->_next;}//当前桶走完了，要找下一个桶的第一个else{KeyOfT kot;Hash hash;//记录当前的位置size_t hashi = hash(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;}};template<class K, class T, class Hash, class KeyOfT>class HashTable{typedef HashNode<T> Node;template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>friend struct __HTIterator;public:typedef __HTIterator<K, T, T&, T*, Hash, KeyOfT> iterator;typedef __HTIterator<K, T, const T&, const T*, Hash, KeyOfT> const_iterator;iterator begin(){for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]){return iterator(_tables[i], this);}}return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}const_iterator begin() const{for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]){return const_iterator(_tables[i], this);}}return const_iterator(nullptr, this);}const_iterator end() const{return const_iterator(nullptr, this);}HashTable():_n(0){_tables.resize(__stl_next_prime(0));}~HashTable(){for (size_t i = 0; i < _tables.size(); i++){//释放桶~HashTable()Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}pair<iterator, bool> Insert(const T& data){KeyOfT kot;iterator it = Find(kot(data));if (it != end())return make_pair(it, false);//负载因子控制在1，超过1就扩容if (_tables.size() == _n){第一种情况，创建一个新的哈希表是为了使用哈希表中的insert函数// //创建一个新的哈希表// // //创建新表// //局部对象出作用域销毁// // //这一步会调用我们所给的构造函数去对newHT里面的成员变量进行初始化// HashTable<K, V, Hash> newHT;// //大小扩容二倍// newHT._tables.resize(_tables.size() * 2);// //将旧表数据插入到新表中// for (auto& cur : _tables)//&减少拷贝// {// //遍历旧表的数据// while (cur)// {// newHT.Insert(cur->_kv);// cur = cur->_next;// }// }// //最后交换旧表与新表，由于新表是局部对象，出作用域自动销毁// _tables.swap(newHT._tables);vector<Node*> newTables;//newTables.resize(2 * _tables.size(), nullptr);// 遍历旧表将旧表中的结点头插到新表中。// 这样就不用创建新的结点。 newTables.resize(__stl_next_prime(_tables.size()), nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = Hash()(kot(cur->_data)) % newTables.size();//头插到新表cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}//移动玩一个桶之后，将旧表此结点的位置置空_tables[i] = nullptr;}_tables.swap(newTables);}//Hash hf;//用仿函数进行转换然后取模//TODOsize_t hashi = Hash()(kot(data)) % _tables.size();//定义一个新结点//这一步会调用构造函数对kv和_next进行初始化Node* newnode = new Node(data);//链接--头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return make_pair(iterator(newnode, this), true);}iterator Find(const K& key){KeyOfT kot;size_t hashi = Hash()(key) % _tables.size();//cur定义为映射后hashi映射位置哈希桶的头结点Node* cur = _tables[hashi];//遍历桶里面的每个结点，看是否与key相同while (cur){if (kot(cur->_data) == key){return iterator(cur, this);}else{cur = cur->_next;}}return end();}bool Erase(const K& key){size_t hashi = Hash()(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){//找到了if (cur->_kv.first == key){//准备删除//如果需要删除的就是头结点if (cur == _tables[hashi]){_tables[hashi] = cur->_next;}//需要删除的非头结点else{//将自己的前驱指针指向自己的后继指针 prev->_next = cur->_next;}delete cur;_n--;//元素-1return true;}else{prev = cur;cur = cur->_next;}}return false;}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, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};for (int i = 0; i < __stl_num_primes; i++){if (__stl_prime_list[i] > n){return __stl_prime_list[i];}}return __stl_prime_list[__stl_num_primes - 1];}private://指针数组 数组的每一个元素是一个指针vector<Node*> _tables;//指针数组size_t _n = 0;};//void TestHT1()//{// HashTable<int, int> ht;// int a[] = { 18,8,7,27,57,3,38,18,17,88,38,28 };// for (auto e : a)// {// ht.Insert(make_pair(e, e));// }// ht.Insert(make_pair(5, 5));// ht.Erase(17);// ht.Erase(57);//}//void TestHT2()//{// string arr[] = { "苹果","梨","桃子" };// HashTable<string, int> countHT;// for (auto& e : arr)// {// HashNode<string, int >* ret = countHT.Find(e);// //auto ret = countHT.Find(e);// if (ret)// {// ret->_kv.second++;// }// else// countHT.Insert(make_pair(e, 1));// }//}
}UnorderSet.h
#pragma once
#include"HashTable.h"namespace bit
{template<class K, class Hash = HashFunc<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename buckethash::HashTable<K, K, Hash, SetKeyOfT>::iterator iterator;typedef typename buckethash::HashTable<K, K, Hash, SetKeyOfT>::iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}pair<iterator, bool> insert(const K& key){return _ht.Insert(key);}private:buckethash::HashTable<K, K, Hash, SetKeyOfT> _ht;};/*void Func(const unordered_set<int>& us){unordered_set<int>::const_iterator it = us.begin();while (it != us.end()){cout << *it << " ";++it;}cout << endl;}*/void test_unordered_set(){unordered_set<int> us;us.insert(13);us.insert(3);us.insert(666);us.insert(23);us.insert(5);us.insert(5);us.insert(60);us.insert(15);unordered_set<int>::iterator it = us.begin();while (it != us.end()){cout << *it << " ";++it;}cout << endl;for (auto e : us){cout << e << " ";}cout << endl;//Func(us);}
}UnorderMap.h
#pragma once
#include"HashTable.h"namespace bit
{template<class K, class V, class Hash = HashFunc<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<const K, V>& kv){return kv.first;}};public:typedef typename buckethash::HashTable<K, pair<const K, V>, Hash,MapKeyOfT>::iterator iterator;typedef typename buckethash::HashTable<K, pair<const K, V>, Hash,MapKeyOfT>::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}pair<iterator,bool> insert(const pair<K, V>& data){return _ht.Insert(data);}iterator find(const K& key){return _ht.Find(key);}V& operator[](const K& key){pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));return ret.first->second;}private:buckethash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht;};void test_unordered_map(){string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };unordered_map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (const auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}}
}