好了，上一篇我们了解到了关于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;
}好了，本次就先分享到这里了，后面我们再继续更新哈希桶的内容。
希望你我共进步！
最后，到了本次鸡汤环节：
文字共勉！
