一、哈希表的映射方法
1、直接定址法（值的分布范围集中）
比如统计字符串中字符出现的次数，字符范围集中。
2、除留余数法（值的分布范围分散)
hashi = key % n
但是这种方法会导致，哈希冲突：不同的值映射到相同的位置
不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞 。
解决哈希冲突的方案
闭散列的---开放定址法：当前位置被占用了，按规则找下一个位置（占用别人的位置）
1、线性探测
2、二次探测
.
二、查找的时候可以找的到，但是这个值在空的后面
查找逻辑：遇到空就停止查找。
可以使用状态来标记
1、EXIST
2、EMPTY
3、DELETE
查找的时候，遇到状态EMPTY才能停止。
三、哈希表什么时候扩容
散列表的载荷因子定义为 ：填入表中的元素个数 /散列表的长度
负载因子越大，冲突概率越大，空间利用率越高
负载因子越小，冲突概率越小，空间利用率越低。空间浪费越多。
哈希表不能满了扩容，控制负载因子到一定值就扩容。负载因子可以限制在0.7~0.8之间。
四、扩容以后我们的映射关系就变了，需要重新映射。
解决方案：
1、 重新开一个vector，把旧的的值直接插入到新的vector里面中去。遍历旧表重新映射到新表。
2、我们可以重新搞一个hash表，把空间提前开好，遍历旧表插入到新表里。然后旧表和新表进行交换。
bool Insert(const pair<K, V>& kv)
{
// 扩容
//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;
}二次探测
hashi = key%n
hashi = key%i^2
开放定址法的缺点：冲突会互相影响。
哈希桶：
第二种方法为哈希桶
插入：
bool Insert(const T& data)
{
// 负载因子到1就扩容
if (_n == _table.size())
{
// 16:03继续
size_t newSize = _table.size()*2;
vector<Node*> newTable;
newTable.resize(newSize, nullptr);
// 遍历旧表，顺手牵羊，把节点牵下来挂到新表
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = cur->_data % newSize;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
size_t hashi = data % _table.size();
// 头插
Node* newnode = new Node(data);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return true;
}删除：
bool Erase(const K& key)
{
size_t hashi = key % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
{
_table[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
