哈希表与哈希桶的模拟实现
unordered系列关联式容器介绍
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到$log_2 N$，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好 的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个 unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是 其底层结构不同，例如， unordered_multimap和unordered_multiset
==但是unordered系列的底层是哈希==！——其实是应该叫做hash_map,hash_set会比较合理的！但是之所以叫做unordered是为了在功能上进行区分！==因为map与set的底层是二叉搜索树！是有序的！但是以哈希为底层的unordered_map和unordered_set是无序的！所以这就是为什么叫unordered！==
==有一些区别就是unordered系列的容器不支持反向迭代器！==
除了这两点之外unordered系列的容器和由二叉树作为底层的容器几乎没有区别！
那么究竟为什么需要unordered系列的容器呢？
==我们看如下的测试==
#include <iostream> #include <unordered_set> #include <set> #include <vector> using namespace std; int main() { const size_t N = 100000; unordered_set<int> us; set<int> s; vector<int> v; v.reserve(N); srand(time(0)); for(size_t i = 0; i < N; ++i) { v.push_back(i);//大量数据不同 //v.push_back(rand());//大量数据相同 //v.push_back(rand()+i);//部分数据相同 } size_t begin = clock(); for(size_t i = 0; i < N; ++i) { us.insert(v[i]); } size_t end = clock(); cout << "unordered_set: " << end - begin << endl; begin = clock(); for(size_t i = 0; i < N; ++i) { s.insert(v[i]); } end = clock(); cout << "set: " << end - begin << endl; size_t begin2 = clock(); for(auto e:v) { s.find(e); } size_t end2 = clock(); cout << "set find:" << end2 - begin2 << endl; size_t begin3 = clock(); for(auto e:v) { us.find(e); } size_t end3 = clock(); cout << "unordered_set find :" << end3 - begin3 << endl; size_t begin4 = clock(); for(auto& e:v) { s.erase(e); } size_t end4 = clock(); cout << "set: erase :" << end4 - begin4 << endl; size_t begin5 = clock(); for(auto& e:v) { us.erase(e); } size_t end5 = clock(); cout << "unordered_set: erase :" << end5 - begin5 << endl; return 0; }insert性能对比
在大量的重复数据的情况下！
在大量不重复的数据的情况下
我们发现了在大批量的有重复的进行插入的时候！unordered系列容器快了好几倍！——rand只能产生3w多个随机值！所以就会造成大量的重复！
如果是不同的的数据进行插入，那么set就会比会比unordered系列的快一点
find效率对比！
==而且我们发现unordered系列的查找非常的快！这是由unordered的底层哈希决定的！无论是大量的数据重复还是大量的数据不重复！unordered系列的find都更加的快！==
erase效率对比
在有大量的数据不同的情况下
在部分或者少量数据相同的情况下
在大量数据相同的情况下！
在数据量重复的情况比较多的时候我们会发现unordered系列会更加的占优势！在大量不重复的时候非unordered版本会更好一点！不过也不一定，在不同的编译器下面实现的可能会有不同的结果！
==但是我们综上我们可以发现，unordered系列的find效率极高！无论是什么场景！unordered系列的find性能都是高于非unordered系列的！所以如果对于查找性能要求比较高的！我们可以使用unordered版本！==
哈希的概念
unordered系列的容器的底层是哈希表！
什么是哈希？哈希就是一种映射！==我们一般叫做哈希映射==——key值跟存储位置建立一种关联关系！
只要知道了key就找到了存储位置！
我们一般会映射到表里面（在C++里面，数组，链表我们都可以叫做表！）
哈希是一种思想！
- 直接定址法--(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：==适合查找比较小且连续的情况（范围集中！）==
为了解决上面的缺陷，所以有了另一种方法！
- 除留余数法
- 设散列表中==允许的地址数为m==，取一个不大于m，==但最接近或者等于m的质数p作为除数==， 按照哈希函数：==Hash(key) = key% p(p<=m)==，将关键码转换成哈希地址
==模出来的余数是几就在那个位置！这样子就和范围不相干！==
但是这样子又引入了另一个问题！
万一模出来的数是相同的应该怎么办？这样子就会映射在相同的位置上！
我们将不同的值映射在相同位置的情况——称之为==哈希冲突/碰撞==
直接定址法——是不会有这个问题的！因为每一个值都会对应一个唯一的位置！
那么我们应该如何解决哈希冲突呢？
==下面我将介绍常见的两种解决办法——闭散列和开散列！==
闭散列——开放定址法
思路就是——映射的位置已经有存在值了，就按照一定的规则找到其他的位置
规则1——线性探测——如果这个位置已经发生了冲突了，那么就往下面继续找！直到找到空为止！
就是一直++下标！——这就是线性探测
但是这个方法也有问题！
- 查找效率低下
- 导致相互冲突
==找到最后，要从头开始寻找！不是要扩容！==
规则2——二次探测
二次探测——不是探测两次的意思！
关于哈希表数据应该如何删除
==所以我们既不应该将数据置空！也不应该以位置空为结束条件！——我们应该弄一个状态标识符来标记每一个位置的状态！==
状态标识符——应该有三种状态
- 该位置为空
- 该位置不为空，但是已经删除
- 该位置不为空，没有删除！
==遇到状态为删除的是不能停下来的！要遇到状态为空的的才能停下来！==
有的读者可能会有另一种想法！挪动行不行？删除一个然后向前挪动？
这是不可以的！首先这样子删除效率低下！其次这会导致映射位置造成偏差！比如有的数值明明映射在正确的位置上！但是一挪动就错了！这样子可能会影响查找效率！
闭散列的代码实现——线性探测的实现
哈希数据类
namespace MySTL { enum State { EMPTY, EXIST, DELETE };//设定三种状态 template<class K,class V> struct HashData { std::pair<K, V> _kv; State _state; }; }
哈希数据类的构造
namespace MySTL { enum State { EMPTY, EXIST, DELETE }; template<class K,class V> struct HashData { HashData(const std::pair<K,V>& kv = std::pair<K,V>()) :_kv(kv) ,_state(EMPTY) {} std::pair<K, V> _kv; State _state; }; }
哈希类的成员变量
#pragma once #include<iostream> #include<vector> namespace MySTL { template<class K, class V> class Hashtable { typedef HashData<K,V> Data; private: std::vector<Data> _table; size_t _n;//有效元素个数 }; }
构造函数
#pragma once #include<iostream> #include<vector> namespace MySTL { template<class K, class V> class Hashtable { typedef HashData<K,V> Data; public: Hashtable(size_t size = 10)//开始就要给表一个值！防止出现空表导致插入出问题！ :_table(size) ,_n(0) {} private: std::vector<Data> _table; size_t _n;//有效元素个数 }; }
Insert
#pragma once #include<iostream> #include<vector> namespace MySTL { template<class K, class V> class Hashtable { typedef HashData<K,V> Data; public: bool Insert(const std::pair<K,V>& kv) { //大于标定的负载因 子就需要进行扩容！ //不要使用if(_n/_table.size() > 0.7)因为_n是size_t，_table.size()是size_t //_n/_table.size()的结果是不会是一个浮点数的！ if(_n*10/_table.size() >= 7) { //方法一 /* size_t newsize = _table.size() * 2; std::vector<Data> newtable(newsize);//创建一个新的表！ for(auto& e:_table)//一个个的拷贝！ { if(e._state != EXIST)//只有存在的才需要拷贝！一定要判断！ continue; size_t hashi = e._kv.first%newsize; while(newtable[hashi]._state == EXIST) { ++hashi; if(hashi == newsize) hashi = 0; } newtable[hashi] = e; } _table.swap(newtable); */ //方法二 Hashtable<K,V> NEWHT(_table.size()*2); for(auto& e:_table) { if(e._state == EXIST) NEWHT.Insert(e._kv); } //我们可以直接创建一个新的哈希表！ //然后调用新的哈希表的插入函数！ //复用代码！因为新表的负载因子一定是不会超过0.7的！ //所以不会再次进行扩容！ //那么就会调用下面的代码！ //这样就不用再写一遍插入的代码了！ //然后交换一下就好了！ _table.swap(NEWHT._table); } size_t hashi = kv.first% _table.size();//先算要映射的位置！ //要模上表的大小，因为可能会超出表的大小！ //而不是capacity，因为capacity是表的容量，可能会比表的大小大！ while(_table[hashi]._state == EXIST)//循环结束的条件就是遇到空，或者遇到删除！ { if(_table[hashi]._kv.first == kv.first)//如果已经存在 return false; //线性探测就是++ ++hashi; if(hashi == _table.size()) hashi = 0; } _table[hashi]._kv = kv; _table[hashi]._state = EXIST; ++_n;//有效元素个数加一！ } private: std::vector<Data> _table; size_t _n;//有效元素个数 }; }
负载因子
==insert的时候！是完全不用担心是满的！为什么？==
假如有一个哈希表！表的大小是1000，里面已经有了999个值！那么假如我们这时候去插入！冲突的概率是极大的！且插入效率很低！==所以对于闭散列的哈希表我们是不可能让它满的！==
所以这里就有提出来一个新的概念负载因子！W
==负载因子/载荷因子 == 表中有效数据的个数/表的大小==
所以闭散列的负载因子是不可能达到1的！1就是意味着满了！
==一般我们认为负载因子控制在 0.7-0.8这个区间是最好的！==
所以一旦负载因子到了0.7-0.8左右的时候就要进行扩容的！
负载因子就是一种空间换时间的手段！
负载因子越小，冲突的概率越小，消耗空间越多
负载因子越大，冲突概率越大，空间利用率越高
哈希表如何进行扩容
哈希表的扩容能不能直接单纯的将数据拷贝下来呢？——答案是否定的！
为什么呢？——因为==进行了扩容之后表的大小已经发生了改变！映射关系也已经发生了改变！==
==我们必须重新计算映射关系！==
扩容的时候，不要去使用reserve或者reszie，因为这样子我们相当于是在原表上进行处理！——会很麻烦！
因为如果我们重新算映射关系的时候，将还没计算映射关系的值给覆盖了！那就很不妙了！
==所以最好是弄一个新表！然后重新映射完后交换一下==
Find
#pragma once #include<iostream> #include<vector> namespace MySTL { template<class K, class V> class Hashtable { typedef HashData<K,V> Data; public: Data* Find(const K& key) { //查找和插入的逻辑是一致的！就是线性探测的过程！ size_t hashi = key%_table.size(); size_t starti = hashi; while(_table[hashi]._state != EMPTY)//找到空才能停 { if(_table[hashi]._state == EXIST && _table[hashi]._kv.first == key)//要判断是否存在！而不是删除！ return &_table[hashi]; ++hashi; if(hashi == _table.size()) hashi = 0; if(starti == hashi)//极端场景下面不存在空！全是存在或者删除！ { break; } } return nullptr; } private: std::vector<Data> _table; size_t _n;//有效元素个数 }; }==我们使用Data* 作为返回值有一个好处！——就是可以方便进行复用！==
erase
#pragma once #include<iostream> #include<vector> namespace MySTL { template<class K, class V> class Hashtable { typedef HashData<K,V> Data; public: bool erase(const K& key) { Data* ret = Find(key);//直接复用Find我们就可以不用自己去写查找逻辑了！ if(ret == nullptr) return false; else { ret->_state = DELETE;//这种就是伪删除！ --_n;//减去有效数据次数 return true; } } private: std::vector<Data> _table; size_t _n;//有效元素个数 }; }
双重映射——哈希函数
上面的映射一个问题！——那就是只能映射整形！
我们想要插入一个string类型的时候！就会发生报错！
那这时候应该怎么办？——答案就是双重映射！
==先将string映射为整形！然后再对整形取模！==——这个算法要是一个稳定的算法！让一个字符串尽可能的对应一个唯一的数字！
例如：我们可以去字符串的第一个字母（char类型的变量）——但是这样子有很大的概率就会发生冲突！因为只要第一个字母相同那么就会发生冲突！
所以我们就必须==写一个哈希函数——一个仿函数！==用来进行转换！
这个哈希函数的的作用就是将key转换为一个整形类型！
namespace MySTL { enum State { EMPTY, EXIST, DELETE }; template<class K,class V> struct HashData { HashData(const std::pair<K,V>& kv = std::pair<K,V>()) :_kv(kv) ,_state(EMPTY) {} std::pair<K, V> _kv; State _state; }; //写一个哈希函数！ template<class K> struct HashFunc//这就是我们默认的哈希函数！但是这个哈希函数是不能将string类转换为size_t的！ { size_t operator()(const K& key) { return (size_t)key; } }; //多加一个模板参数！——仿函数！ template<class K, class V,class Hash = HashFunc<K>> class Hashtable { typedef HashData<K,V> Data; public: Hashtable(size_t size = 10) :_table(size) ,_n(0) {} bool Insert(const std::pair<K,V>& kv) { if(_n*10/_table.size() >= 7) { Hashtable<K,V,Hash> NEWHT(_table.size()*2); for(auto& e:_table) { if(e._state == EXIST) NEWHT.Insert(e._kv); } _table.swap(NEWHT._table); } Hash hf; size_t hashi = hf(kv.first) % _table.size(); while(_table[hashi]._state == EXIST) { if(_table[hashi]._kv.first == kv.first) return false; ++hashi; if(hashi == _table.size()) hashi = 0; } _table[hashi]._kv = kv; _table[hashi]._state = EXIST; ++_n; return true; } Data* Find(const K& key) { Hash hf; size_t hashi = hf(key)%_table.size(); while(_table[hashi]._state != EMPTY) { if(_table[hashi]._state == EXIST && _table[hashi]._kv.first == key) return &_table[hashi]; ++hashi; if(hashi == _table.size()) hashi = 0; } return nullptr; } bool erase(const K& key) { Data* ret = Find(key); if(ret == nullptr) return false; else { ret->_state = DELETE; --_n; return true; } } private: std::vector<Data> _table; size_t _n;//有效元素个数 }; }//将string类转换为size_t的一个哈希函数！ namespace MySTL { struct HashFuncstring { size_t operator()(const std::string& key) { size_t hash = 0; for(auto& e:key) { hash = hash*131 + e;//不一定要使用这个算法，也可以自己写一个算法 } return hash; } } //或者我们也可以将模版进行偏特化！ //将上面的写的hash仿函数偏特化一下！ template<> struct HashFunc<std::string> { size_t operator()(const std::string& key) { size_t hash = 0; for(auto& e:key) { hash = hash*131 + e; } return hash; } }; } namespace MySTL { void testHash() { std::vector<std::string> fruit = {"apple","banana","orange","apple","banana","apple"}; //使用我们自己写的这个hash函数！ Hashtable<std::string,int,HashFuncstring> HT2; for(auto& e:fruit) { HashData<std::string,int>* ret = HT2.Find(e); if(ret == nullptr) HT2.Insert(std::make_pair(e,1)); else ++(ret->_kv.second); } } //我们要针对这个类型写一个特定的仿函数！ //哈希的用法就是这样的！ }
我们可以看到我们成功的统计了水果的数量！
==不过我们哈希表一般要么是使用整形作为key，要么就是字符串作为key！其实很少用自定义类型作为key==
我们可以看一下官方接口也是如此实现的！
我们也可以自己去传哈希函数！
字符串转整形是一种常见的情况！
有兴趣可以看看各种字符串Hash函数 这篇文章里面介绍了各种的字符串转整形的哈希算法！
==但是无论是怎么样的哈希算法，都是无法避免冲突的！因为字符串是无限的！但是整形是有限的！但是可以极大的避免冲突！==
我们想要插入一个string类型的时候！就会发生报错！
这个哈希表是不用写拷贝构造，赋值重装和析构的！对于自定义类型，哈希会自己去调用vector的拷贝/构造/赋值重装！
开散列——哈希桶介绍
相比哈希表（由闭散列实现！）——闭散列无论如何，占用别的数据的位置是不可避免的！
但是由开散列实现的哈希桶就没有这个问题！
==但是哈希桶有一个问题！那就是如果大量的数据发生了冲突！甚至最极端的情况！所有数据都冲突了！（就是全都挂在了同一个的单链表上！）那么就会从哈希桶退化为单链表！==
==一般哈希桶都是使用单链表作为它的子结构！==
这就是为什么unordered系列的容器只支持单向迭代器！——而不支持双向迭代器！
哈希桶的实现
哈希桶节点类
namespace MySTL { template<class K,class V> struct HashNode { HashNode(const std::pair<K,V> kv = std::pair<K,V>()) :_kv(kv) ,_next(nullptr) {} std::pair<K,V> _kv; HashNode<K,V>* _next; }; }
哈希桶
成员变量
#pragma once #include <iostream> #include <vector> namespace MySTL { template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } };//默认哈希函数！ template<class K,class V,class Hash = HashFunc<K>> class HashBucket { typedef HashNode<K, V> Node; public: HashBucket() :_n(0) ,_Bucket(10, nullptr) {} private: std::vector<Node> _Bucket; size_t _n; }; }==如果不想自己写链表可以去使用STL库里面的list或者forward_list这两个容器==
构造函数
#pragma once #include <iostream> #include <vector> namespace MySTL { template<class K> struct Hash { size_t operator()(const K& key) { return (size_t)key; } }; template<class K,class V,class Hash = HashFunc<K>> class HashBucket { typedef HashNode<K, V> Node; public: HashBucket(size_t n = 10) :_n(0) { _Bucket.resize(n); } private: std::vector<Node> _Bucket; size_t _n; }; }
析构函数
#pragma once #include <iostream> #include <vector> namespace MySTL { template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<class K,class V,class Hash = HashFunc<K>> class HashBucket { typedef HashNode<K, V> Node; public: ~HashBucket() { for(auto cur : _Bucket) { while(cur) { Node* next = cur->_next; delete cur; cur = next; } } } private: std::vector<Node*> _Bucket; size_t _n; }; }==闭散列是不需要写析构函数的！但是开散列是需要的！如果不写析构函数！因为_Bucket只会释放每个桶的头节点！而不会释放每个桶的所有节点！会造成存泄露！==
Find
#pragma once #include <iostream> #include <vector> namespace MySTL { template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<class K,class V,class Hash = HashFunc<K>> class HashBucket { typedef HashNode<K, V> Node; public: Node* Find(const K& key) { size_t hashi = Hash()(key) % _Bucket.size(); Node cur = _Bucket[hashi]; while(cur) { if(cur->_kv.first == key) return cur; cur = cur->_next; } return nullptr; } private: std::vector<Node> _Bucket; size_t _n; }; }
Insert
#include <iostream> #include <vector> namespace MySTL { template<class K,class V,class Hash = HashFunc<K>> class HashBucket { typedef HashNode<K, V> Node; public: bool Insert(const std::pair<K,V> &kv) { if(Find(kv.first)) return false; //还要考虑扩容！要考虑一下负载因子 //闭散列的负载因子是不会大于一的，但是开散列的负载因子是可以大于一的，因为理论上开散列可以无限挂 //一般的负载因子控制在1 if(_n == _Bucket.size())//我们这边就简单写死 { //方法一 //像闭散列一样创建一个新的哈希表，然后把旧的哈希表的元素全部插入到新的哈希表中 //然后交换一下根节点就结束！ //这样子的前提是要写析构函数保证旧的哈希表的元素都能被释放！ //因为vector只会只会去释放每个位置的根节点元素！但是根节点后面的元素都不会被释放！ //HashBucket<K,V,Hash> newHT; //newHT._Bucket.resize(_Bucket.size()*2); //for(auto cur :_Bucket) //{ // while(cur) // { // newHT.Insert(cur->_kv); // cur = cur->_next; // } //} //_Bucket.swap(newHT._Bucket); //方法二,将旧表的节点全部拿出来，然后重新插入到新表中 std::vector<Node*> newBucket; newBucket.resize(_Bucket.size()*2, nullptr); for(int i = 0;i< _Bucket.size();i++) { Node* cur = _Bucket[i]; while(cur) { Node* next = cur->_next; size_t hashi = Hash()(cur->_kv.first) % newBucket.size(); //cur是新插入的节点！要进行头插！变成新的头结点 //nweBucket[hashi]是原来的头结点！要变成新的头结点的next cur->_next = newBucket[hashi]; //不用担心第一次是空的，即使第一次是nullptr，也不会出错！ newBucket[hashi] = cur;//变成新的头结点 cur = next; } _Bucket[i] = nullptr; } _Bucket.swap(newBucket);//交换两个表 } size_t hashi = Hash()(kv.first) % _Bucket.size(); //要放在扩容的后面！否则会导致扩容之后用的是扩容前的映射！ //哈希桶和哈希表不一样！哈希桶不用担心哈希冲突，因为哈希桶的每个位置都是一个链表 //直接进行头插 //不用判断开始是不是空！ Node* newhead = new Node(kv); newhead->_next = _Bucket[hashi]; _Bucket[hashi] = newhead; ++_n; return true; } private: std::vector<Node*> _Bucket; size_t _n; }; }**闭散列的负载因子不能大于一！**但是==开散列可以！==因为理论上来说，开散列是可以无限挂下去的！
==但是一般我们会将负载因子控制在1左右！==
在STL库的unordered系列的容器中给我们提供了一个接口！
==这个接口允许我们控制负载因子的大小！==
开链表如何进行扩容
if(_n == _Bucket.size())//我们这边就简单写死 { //方法一 //像闭散列一样创建一个新的哈希表，然后把旧的哈希表的元素全部插入到新的哈希表中 //然后交换一下根节点就结束！ //这样子的前提是要写析构函数保证旧的哈希表的元素都能被释放！ //因为vector只会只会去释放每个位置的根节点元素！但是根节点后面的元素都不会被释放！ HashBucket<K,V,Hash> newHT; newHT._Bucket.resize(_Bucket.size()*2); for(auto cur :_Bucket) { while(cur) { newHT.Insert(cur->_kv); cur = cur->_next; } } _Bucket.swap(newHT._Bucket); }==但是这种方法扩容的消耗十分的大！因为我们要去new新的节点！然后再调用析构函数去释放所有旧表的节点！==
==所以我们可以想办法利用一下旧的节点！——但是绝不是像上面的一样！直接将新表指向桶！这样子旧导致一个桶被指向连词，如果不将旧表置空还会导致节点析构两次！==
if(_n == _Bucket.size())//我们这边就简单写死 { //方法二,将旧表的节点全部拿出来，然后重新插入到新表中 std::vector<Node*> newBucket; newBucket.resize(_Bucket.size()*2, nullptr); for(int i = 0;i< _Bucket.size();i++) { Node* cur = _Bucket[i]; while(cur) { Node* next = cur->_next; size_t hashi = Hash()(cur->_kv.first) % newBucket.size(); //cur是新插入的节点！要进行头插！变成新的头结点 //nweBucket[hashi]是原来的头结点！要变成新的头结点的next cur->_next = newBucket[hashi]; //不用担心第一次是空的，即使第一次是nullptr，也不会出错！ newBucket[hashi] = cur;//变成新的头结点 cur = next; } _Bucket[i] = nullptr; } _Bucket.swap(newBucket); }==这样我们既避免了重新new新的节点！也避免了去调用哈希表的析构函数！==
关于表扩容的大小
有一个说法，就是如果表的大小是一个素数，那么就可以在取模的时候让数据更加的分散
而在STL库的早期实现中也确实采用了这个说法
==我们可以看到因为每一次扩容如果要算下一个素数很麻烦！所以STL库干脆给了一个素数表！然后通过lower_bound每次去找到比n更大的素数然后返回，而到最后如果到最大值了，就不再进行扩容！而是返回最大值！==
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];//如果已经最大了就返回最后的值！ }==也不用担心到了最大了但是不扩容的问题！因为最大了有42亿9千万多个数据！即使我们按最小的字节来计算也就是42亿9千万多个字节——也就是 4G==——而如果每个数据是整形（4字节）那么就是16G的数据！——而且不止有这个这个16G的数据还有每个节点还有一个指针！（我们按32位来计算）——那么就是**(4+4)*4 = 32G**的数据！那么光是节点的数据就是非常的恐怖了，何况还有挂节点的数组的大小
所以几乎不用担心，哈希表可能会怎么大！
#include <iostream> #include <vector> namespace MySTL { template<class K,class V,class Hash = HashFunc<K>> class HashBucket { typedef HashNode<K, V> Node; public: bool Insert(const std::pair<K,V> &kv) { if(Find(kv.first)) return false; size_t hashi = Hash()(kv.first) % _Bucket.size(); if(_n == _Bucket.size())//我们这边就简单写死 { std::vector<Node*> newBucket; //然后就简单的修一下一下扩容 newBucket.resize( __stl_next_prime(_Bucket.size()), nullptr); for(int i = 0;i< _Bucket.size();i++) { Node* cur = _Bucket[i]; while(cur) { //..... } } _Bucket.swap(newBucket);//交换两个表 } //...... } private: std::vector<Node*> _Bucket; size_t _n; }; }如果实在害怕链表挂的太长了！情况过于极端！还可以在超过一定长度之后将链表改成红黑树！我们既然可以挂单链表，自然也是可以挂红黑树的！（像是java的处理就是在链表长度超过8就将链表改成红黑树！）这样子就是最极端的情况就是退化为log2(N)
拷贝构造
#pragma once #include <iostream> #include <vector> namespace MySTL { template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<class K,class V,class Hash = HashFunc<K>> class HashBucket { typedef HashNode<K, V> Node; public: HashBucket(const HashBucket<K,V,Hash>& ht)//拷贝构造 { _Bucket.resize(ht._Bucket.size()); for(size_t i = 0;i < ht._Bucket.size();++i) { Node* cur = ht._Bucket[i]; while(cur)//不断插入的这个链表的节点！ { Insert(cur->_kv); cur = cur->_next; } } } private: std::vector<Node*> _Bucket; size_t _n; }; }
Erase
#pragma once #include <iostream> #include <vector> namespace MySTL { template<class K,class V,class Hash = HashFunc<K>> class HashBucket { typedef HashNode<K, V> Node; public: bool Erase(const K& key) { //开散列不能像闭散列一样Find然后删除！因为这是一个单链表！要找到前一个节点才能删除！ size_t hashi = Hash()(key) % _Bucket.size(); Node* cur = _Bucket[hashi]; Node* curprev = nullptr; while(cur) { //找到后开始准备删除 if(cur->_kv.first == key) { if(cur == _Bucket[hashi]) //如果删除的是头结点！ { _Bucket[hashi] = cur->_next; } else { curprev->_next = cur->_next; } delete cur; _n--; return true; } cur = cur->_next; curprev = cur; } return false; } private: std::vector<Node*> _Bucket; size_t _n; }; }
12
