hash表的模拟--开放定址法
好了，上一篇我们了解到了关于hash的基础知识，现在我们来了解一下如何解决hash冲突的问题。
接上篇：
对于hash冲突的问题，我们采用的解决方案：
开放定址法
闭散列（也叫开放定址法）：当前位置被占用了，就按规则找下一个位置（占用别人的位置）。
ps：当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，此时就可以将它放到空位置上。
那么我们又该怎么去找呢？
两种方法：1.线性探测 2.二次探测 3.…………
什么是线性探测？
从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止
举个例子：
查找：线性：走到空/存在就可停下来。
补充：（开放定址法的缺点：冲突会相互影响，4，5，6这几个值会相互影响）
解决了查找问题后，我们再来看一下关于删除的操作：
如上图的：删去6.
问题1：把6删除了，那个位置总得填一个值：填什么呢？0？随机值？
显然这些做法都是不可取的，你若填了这些无效值，但如果它本身就是无效值呢？eg：它本身就是0，你还能再填一个0吗？
问题2：把6删掉了，现在去查找44，又会出现什么问题？
我们想一下，我们线性：走到空/存在就可停下来，现在这个它6为空了，还能不能找到44这个位置？明显不能，对吧？
所以，针对上面的两种情况，我们采取的措施：利用状态标志法：
定义：1.EXIST（存在） 2.EMPTY（空） 3.DELETE（删除）
来标记该位置属于那种状态，来判断执行哪种操作。
eg：你要删除6，就不用真正去删除，把6等等状态改成DELETE，遇到DELETE不能停,遇到EMPTY才能停止。
enum STATE{EXIST,EMPTY,DELETE};接下来我们来定义一下成员变量，来实现一下开放定址法的模拟代码：
namespace open_adress
{enum STATE{EXIST,EMPTY,DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;STATE state = EMPTY;}; template<class K, class V, class HashFunc = DefaultFunc<K>>class HashTable{public:private:vector<HashData<K, V>> _table;size_t _n = 0;};
}解释：
通过上面的了解，知道我们需要一个数组，所以我们直接使用vector容器。
问题来了：有人可能会疑惑，这里既然用了vector容器，而vector容器不是有size的函数接口吗，你为什么还要定义n成员变量？
原因：物理上是数组，逻辑上哈希表，反列表（值存储的是按一定规则存的，并不是一个一个挨着的），所以它其实已经不是一个顺序表了。就像堆中，物理上是数组，逻辑上是完全二叉树。
所以，我们这里定义了一个n变量，而n存储的是有效数据的个数。
再来思考一下：hashi=key%（capacity？还是size)?
我们不妨来假设一下选capacity：
那么，如果有以下代码：
_table[hashi].kv=_kv; _table[hashi]._state=EXIST;我们回顾以下：vector[]的检查方式？
顺序表数据存储的是连续的：0~size-1。所以访问到size后面的数就不可以再访问了。虽然空间确实开出来了，但是[]有检查，而且，你放数据，你绝对是用[]去访问的，又加上vector只能访问0~size-1。所以不可以使用capacity。
2.最好让size与capacity相等，这样节省空间。因为无论是搜索树还是哈希表：存储规则都只跟key有关，vector只是附带的。
3.关于负载因子(a)设置：
a=元素个数/长度，比例代表的是装满的程度。负载因子越大，冲突概率越大（空间利用率越高），反之相反，空间利用率低，有空间浪费。
哈希表不能满了再扩容，控制负载因子到一定值就扩容。而对于开放定址法：一般控制到0.7~0.8
此时，_n这个成员变量就发挥作用了：
class HashTable{public:HashTable(){_table.resize(10);}bool insert(const pair<K, V>& kv){//扩容if (10 * _n / _table.size() == 7){size_t newsize = _table.size() * 2;//新表HashTable<K, V, HashFunc> NHT;NHT._table.resize(newsize);for (size_t i = 0; i < _table.size(); i++){NHT.insert(_table[i]._kv);}_table.swap(NHT._table);}private:vector<HashData<K, V>> _table;size_t _n = 0;};解释：
1.n的个数==0。写构造函数，一上来就开空间。
2.细节：在扩容那句里面：如果不按照我上面这样写的话，就要自行去强转。若不想强转，可以写成上面那样。
if ((double)_n / _table.size() == 0.7)3.不要直接扩成2倍。否则会出现问题：
因为扩容后，映射关系就变了，需要重新映射。
原来冲突的：现在不一定冲突。
原来不冲突的：现在可能冲突。
那么我们该怎么去解决这种问题呢？
法一：扩容时，弄一个newnode,开好空间。（ps:但是这个方法太拙了，就不考虑这种方法）
法二：直接在原来的基础上开辟空间：
1.开辟空间
2.遍历旧表的数据插到新表即可。
如果存在：就递归插入。那么会不会死循环呢？不会的，因为：这里我是把空间开好的，10时开到20了，/去除肯定不会满
3.交换
哈希表扩容时，注定是性能会降低的，但是整体上是没有很大的影响的，因为它是指数级的。
Insert部分
bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}// 扩容//if ((double)_n / (double)_table.size() >= 0.7)if (_n * 10 / _table.size() >= 7){size_t newSize = _table.size() * 2;// 遍历旧表，重新映射到新表HashTable<K, 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;
其中_table是vector<int>,vector中的交换成本不高，从之前我们的vector的模拟实现中知道，
本质上是start，finish，endofstage的交换。
而旧表出了作用域会调用析构函数，所以不用担心释放的问题
注意：上图中不能写成pair<const K,V> kv:当你把const放到K里，会出现报错情况，你赋值会赋不上去（find那个函数），所以我们采取在返回的时候加const。
那么，为什么红黑树的时候就可以加const呢？
因为红黑树那里并不会修改那里的值，插入的时候，它是插入一个新节点，而现在它是开好的空间。
若想要摆脱，就别用vector，自己开数组，开空间时也不要用new，而用malloc，相当于它没有初始化，这时候就搞定位new
问题来了，我们上面的
size_t hashi = kv.first % _table.size();有时并不能%，因为它只适合整形才可以，所以我们就得使用两层映射，如果不是整形，就想办法让他变成整形。
1.有人可能会想到那就去它的ASCALL码，
size_t hashi=key[0]%_table.size();但是，K不一定是string呀，它是一个模板。
2.有人又可能会想到，取地址？
eg： …………&…………
但是如果是下面的情况呢？
string d1("aaaa"); string d2("aaaa");按理说是一样的，但是地址不一样啊。
所以我们还是得拿出 我们的 仿函数！！
template<class K>struct DefaultFunc{size_t operator()(const K& key){return (size_t)key;}};template<>struct DefaultFunc<string>{size_t operator()(const string& str){size_t hash = 0;for (auto e : str){hash *= 131;hash += e;}return hash;}};
解释：
1.一个默认的HashFunc(),你给整形，它本身就能%（整形，指针，浮点都能转化为整形）里面都要走这个仿函数，因为你本身不知道它是什么类型的。
2.而为什么要弄成size_t呢？本来负数不可以%的，但是现在弄成size_t就可以了。
3.接下来，string无法转整形的问题：
法一：写仿函数，默认是整形，若是string，就自己去调显示。
法二：不传仿函数，写类模板的特化，template<>
如果用string的第一个ASCALL码值去模好不好？
不好，因为第一个字母相同的话，就全部冲突了。
改进：可以考虑把全部的ASCALL码值全部加起来。
但是仍然避免不了：“abcd” "abbe"ASCALL值相等，所以大佬经过了大量实验用了一种方法。
得出乘以131时，它的冲突概率最小。
find函数
（1）HashData<const K, V>* find(const K& key){size_t hashi = key % _table.size();while (_table[hashi].state != EMPTY){if (_table[hashi].state == EXIST&& _table[hashi]._kv.first == key){（2）return (HashData<const K, V>*) & _table[hashi];}hashi++;hashi %= _table.size();}return nullptr;}注意：这里（1）的返回函数能不能改成pair<K,V>呢？然后（2）的return &_table[hashi]._kv?
答案是不能的，因为它可能会被别人改掉状态，eg：在Erase函数部分
HashData<K,V>*ret=find(key);：虽然这样写的话有时没有报错！为啥呢？
因为:C++编译会根据按需编译（针对模板）。比如说：这模板写了10个函数，但并不是是每个函数都会去编译，实际上是你不用我就不会把它实例化。
而且这里还需要把K变为const K,因为如果K可以改的话，你把哈希表都改乱了。
另外，因为有的地方返回时直接转是不支持的，所以最好返回时建议强转一下。
Erase函数部分
bool erase(const K& key){HashData<const K, V>* ret = find(key);if (ret){ret->state = DELETE;_n--;return true;}return false;}好了，本次就先分享到这里了，后面我们再继续更新哈希桶的内容。
希望你我共进步！
最后，到了本次鸡汤环节：
文字共勉！
