哈希概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较，顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(logN),搜索的效率取决于搜索过程种元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到想要的搜索元素。如果构造一种存储结构，通过某种函数（）HashFunc）使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：
1.插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
2.搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。
该方式即为哈希（散列）方法，哈希方法中使用的转换函数称为哈希（散列）函数，构造出来的结构称为哈希表（Hash Table）或者散列表。
例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为hash(key) = key % capacity capacity为存储元素底层空间总的大小。
用同该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
哈希冲突
对于：4、14这两个元素的关键字，在上述的哈希函数中计算的哈希值都为4，此时就会存在哈希冲突，即：不同关键字通过相同的哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
哈希函数
引发哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数设计原则：
1.哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址是，其值域必须在0到m-1之间
2.哈希函数计算出来的地址能均匀分布在整个空间
3.哈希函数应该比较简单
常见的哈希函数：
1.直接定值法（常用）
取关键字的某个线性函数为散列地址：Hash(key) = A*key +B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
2.除留余数法（常用）
设散列表允许的地址数为m，取一个不大于m，但是接近或等于m的质数p作为除数。
按照哈希函数：Hash(key) = key % p(p<=m)，将关键码转换成哈希地址
优点：使用场景广泛，不受限制。
缺点：存在哈希冲突，需要解决哈希冲突，哈希冲突越多，效率下降越厉害。
3.平方取中法
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址。
使用场景：不知道关键字的分布，而位数又不是很大的情况。
4.折叠法
折叠法是将关键字从左到右侧分割成位数相等的几部分（最后一部分可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
5.随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H a s h ( K e y ) = r a n d o m ( K e y ) Hash(Key)=random(Key)Hash(Key)=random(Key)，其中random为随机数函数。
使用场景：通常应用于关键字长度不等时。
6.数学分析法
设有n个d位数，每一位可能有r种不同的符号，这r中不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，而在某些位上分布不均匀，只有几种符号经常出现。此时，我们可根据哈希表的大小，选择其中各种符号分布均匀的若干位作为哈希地址。
假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是相同的，那么我们可以选择后面的四位作为哈希地址。
如果这样的抽取方式还容易出现冲突，还可以对抽取出来的数字进行反转（如1234改成4321）、右环位移（如1234改成4123）、左环位移（如1234改成2341）、前两数与后两数叠加（如1234改成12+34=46）等操作。
数字分析法通常适合处理关键字位数比较大的情况，或事先知道关键字的分布且关键字的若干位分布较均匀的情况。
注意：哈希函数设计的越精妙，产生哈希冲突的可能性越低，但是无法避免哈希冲突。
哈希冲突解决
闭散列（开放定址法）
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被填满，说明在哈希表中必然还有空的位置，那么可以把key存放在冲突位置中的“下一个”空位置去。那么如何寻找下一个空位置呢？
1.线性探测
比如下图的场景中：需要插入44，先计算哈希地址，为4，因此应该插入在4的位置，但是该地方已经放入了元素为4的值，此时发生了哈希冲突
线性探测：从发生冲突的位置开始，依次向后探测，知道寻找到下一个空位置为止。
一：插入步骤：
1.通过哈希函数获取待插入元素在哈希表的位置
2.如果该位置没有元素则直接插入新元素，如果该位置中已经有元素（发生哈希冲突），那么使用线性探测找到下一个空位置，插入新元素。
二：删除步骤：
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
2.二次探测
二次探测：i的2次方，i为查找次数，例如下图：
第一次为1，第二次为4，第三次为9，依次类推
所以下图的44是在第二次查找中找到了空位置并插入
开散列 （链地址法）
开散列又叫链地址法，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子合集，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中，例如下图：
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。
负载因子
负载因子 = 表中有效数据个数 / 空间的大小
负载因子越大，产出冲突的概率越高，增删查改的效率越低。
负载因子越小，产出冲突的概率越低，增删查改的效率越高。
负载因子越小，也就意味着空间的利用率越低，此时大量的空间实际上都被浪费了。对于闭散列（开放定址法）来说，负载因子是特别重要的因素，一般控制在0.7~0.8以下，超过0.8会导致在查表时CPU缓存不命中（cache missing）按照指数曲线上升。
因此，一些采用开放定址法的hash库，如JAVA的系统库限制了负载因子为0.75，当超过该值时，会对哈希表进行增容。
一但负载因子超出设定值，那么该表需要扩容处理。
一般来说，在闭散列中负载因子设置为0.7，在开散列中负载因子设置为1
哈希表模拟实现
哈希表的结构
首先，我们得存储该位置的状态信息，定义一个枚举变量，状态分别为：
1.EMPTY
2.EXIST
3.DELEDE
许多同学会想，我们为什么要多定义一个DELEDE的状态呢？
我们在前面的学习中发现，在搜索元素的时候，找到空位置即停止，那么假设在搜索过程中，原本存在的数据被删除了，那么此时还要不要继续搜索呢？原本应该搜索到的元素，在中途因为某一个元素的删除而判定空，该怎么办呢？
所以就有了DELETE的状态。
在删除的时候将状态更改为DELETE，停止条件为遇到EMPTY则停止，那么就能顺利搜索了。
//状态
enum Status
{
EMPTY,//空
EXIST,//存在
DELETE//删除
};每个哈希值结构除了存在键值对，还需要存在状态变量来存储状态，初始化都为空。
//哈希值结构
template<class K,class V>
struct HashData
{
pair<K, V> _kv;//键值对
Status _s = EMPTY;//状态
};在哈希类中，为了在插入元素时好计算当前哈希表的负载因子，我们还应该时刻存储整个哈希表中的有效元素个数，当负载因子过大时就应该进行哈希表的增容。
//哈希类
template<class K, class V>
class HashTable
{
public:
//构造函数
HashTables()//构造函数初始化空间为10
{
_tables.resize(10);
}
//析构函数
~HashTables()
//...
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;//存储关键字的格个数
};哈希表的插入
插入步骤：
1.检查是否存在插入的值
这里我们按照Find函数进行直接查找即可，如果不为空，那么就说明有了，返回false，如果没查找到，那么说明该值不存在，进入下一步骤。
2.检查负载因子是否超过0.7，超过需要扩容
如果负载因子超过0.7，那么该表就需要扩容了
扩容又分为三步：
1.new一个新表出来
2.将旧表中的数据一一重新inser进新表，注意此时哈希函数也会发生变化。
3.将新旧表交换，因为新表才是我们需要的
如果负载因子没有超过设定值，那么开始寻找插入位置并插入
3.线性探测插入
先计算好该元素对应的哈希值，然后从该哈希值对应的位置开始，如果该位置已经存在，存在哈希冲突，那么按照线性探测往前寻找，如果遇到EXIST就继续往前，遇到EMPTY和DELETE那么就可以插入了。
//插入函数
bool Insert(const pair<K, V>& kv)
{
//用find判断是否已经有了
if (Find(kv.first))
{
return false;
}
//负载因子
if (_n * 10 / _tables.size() >= 7)//如果负载因子＞0.7，那么需要扩容
{
//开新表
size_t newsize = _tables.size() * 2;
HashTable<K, V> newht;
newht._tables.resize(newsize);
//遍历旧表
for (size_t i = 0; i < _tables.size(); ++i)
{
if (_tables[i]._s == EXIST)
{
newht.Insert(_tables[i]._kv);
}
}
//交换新旧表
_tables.swap(newht._tables);
}
size_t hash = kv.first % _tables.size();//计算哈希值
//开始寻找可插入位置
while (_tables[hash]._s == EXIST)//如果该位置已经有值，那么线性向前探测
{
hash++;//线性探测，每次往前一位探测
hash %= _tables.size();//防止探测越界
}
//开始插入
_tables[hash]._kv = kv;
_tables[hash]._s = EXIST;
++_n;
return true;
}哈希表的查找
查找的方式很简单
1.计算哈希值
2. 从哈希值对应的位置开始查找
这里只要遇到不为空的都继续查找，因为插入的时候是线性探测，只要存在哈希冲突，那么往前查找到为空的就插入，也就是说只要遇到空就一定找不到。
//查找函数
HashData<K, V>* Find(const K& key)
{
size_t hash = key % _tables.size();//计算哈希值
while (_tables[hash]._s != EMPTY)//找到位置为空的就停止寻找
{
if (_tables[hash]._kv.first == key && _tables[hash]._s == EMPTY)//找到了
{
return &_tables[hash];//返回地址
}
//如果没找到，线性往前探测
hash++;
hash %= _tables.size();//防止探测越界
}
//出了循环
return NULL;//返回空
}哈希表的删除
哈希表的删除也很简单
1.通过find函数查找到元素对应的地址
2.将该地址的状态改为DELETE即可，也就是伪删除，最后删除成功
3.如果地址为空，说明要删除的元素不存在，删除失败
//删除函数
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);//先获取key的地址
if (ret != NULL)//如果地址不为空，说明存在
{
ret->_s = DELETE;//状态改为删除
--_n;//空间-1
return true;
}
else//如果地址为空
{
return false;//删除失败
}
}哈希桶模拟实现
哈希桶的结构
在开散列的哈希表中，哈希表的每个位置存储的实际上是某个单链表的头结点，即每个哈希桶中存储的数据实际上是一个结点类型，该结点类型除了存储所给数据之外，还需要存储一个结点指针用于指向下一个结点。
template<class K,class V>
struct HashNode
{
HashNode* _next;
pair<K, V> _kv;
HashNode(const pair<K, V>& kv)
:_kv(kv)
,_next(nullptr)
{}
};与闭散列的哈希表不同的是，在实现开散列的哈希表时，我们不用为哈希表中的每个位置设置一个状态字段，因为在开散列的哈希表中，我们将哈希地址相同的元素都放到了同一个哈希桶中，并不需要经过探测寻找所谓的“下一个位置”。
哈希表的开散列实现方式，在插入数据时也需要根据负载因子判断是否需要增容，所以我们也应该时刻存储整个哈希表中的有效元素个数，当负载因子过大时就应该进行哈希表的增容。
template<class K,class V>
class HashTables
{
typedef HashNode<K, V> Node;
public:
//构造函数
HashTables()//构造函数初始化空间为10
{
_tables.resize(10);
}
//析构函数
~HashTables();
//...
private:
vector<Node*> _tables;
size_t _n = 0;
};哈希桶的插入
插入的步骤和哈希表类似
1.通过find函数判断该元素是否存在
2. 检查负载因子是否超出设定值，超出则需要扩容
扩容的步骤如下：
1.开新表。
2.遍历旧表，将结点逐一挪到新表并将旧表置空。
3. 交换新旧表，因为新表才是我们需要的。
//插入函数
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
//负载因子
if (_n == _tables.size())//因子到1开始扩容
{
//开新表
vector<Node*> newtables;
newtables.resize(_tables.size() * 2, nullptr);
//遍历旧表
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;//记录下一个的地址
size_t hash = cur->_kv.first % newtables.size();//计算哈希值
//头插
cur->_next = newtables[i];
newtables[i] = cur;
//更新下一个位置
cur = next;
}
//将表置空
_tables[i] = nullptr;
}
//交换新旧表
_tables.swap(newtables);
}
size_t hash = kv.first % _tables.size();//计算哈希值
Node* newnode = new Node(kv);//创建结点
//头插
newnode->_next = _tables[hash];
_tables[hash] = newnode;
++_n;
return true;
}哈希桶的查找
在哈希表中查找数据的步骤如下：
1.计算哈希值
2.通过哈希值寻找位置
3.从该位置开始循环查找
循环的步骤如下：
1.判断是否相同，相同则返回找到的地址
2.不相同则判断下一个
3.出了循环还没找到那么返回空
//查找函数
Node* Find(const K& key)
{
size_t hash = key % _tables.size();//计算哈希值
Node* cur = _tables[hash];//寻找位置
while (cur)//cur不为空则继续寻找
{
if (cur->_kv.first == key)//相同则找到
{
return cur;//返回找到的地址
}
//不相同则判断下一个
cur = cur->_next;
}
//出循环还没找到则返回空
return NULL;
}哈希桶的删除
删除的步骤如下：
1.计算哈希值，并记录哈希值对应当前位置和前一个结点的地址（NULL）
2.进入循环，判断是否相同，相同则删除，然后将前一个结点连接下一个结点。不相同则继续判断下一个，更改cur和prev的地址
3.出了循环还没找到则删除失败
//删除函数
bool Erase(const K& key)
{
size_t hash = key % _tables.size();//计算哈希值
Node* prev = nullptr;//记录前地址
Node* cur = _tables[hash];//记录当前地址
while (cur)//不为空则继续寻找
{
if (cur->_kv.first == key)//相同则找到
{
if (prev == nullptr)//如果为头删
{
_tables[hash] = cur->_next;//将下一个结点地址放到指针数组上
}
else
{
prev->_next = cur->_next;//将前一个结点连接后一个地址
}
delete cur;//删除找到的结点
return true;
}
prev = cur;
cur = cur->_next;
}
//出循环还没找到则删除失败
return false;
}
