$\Huge\color{orchid}{点击此处获取更多干货}$
查找与查找表
“查找”指的是在数据集合中选出某些符合特定条件的元素，这个用于查找的数据集合叫做“查找表”，可以分为静态查找表和动态查找表，前者只关心查找，后者还要关心元素的增删。之前遇到过的顺序查找和折半（二分）查找，都是基于静态查找表的算法。动态查找表除了此前的顺序表，链表，字典树以外，还有二叉查找树，B树，B+树，散列表等多种自带查找算法的查找表。前面那些各种各样的“树”以后再说，这次的主角是最后提到的“散列表”。
哈希表
哈希表是散列表的另一个名字，来源于英语单词“散列”($\text{hash}$)的音译，表中元素的一个很重要的特性是其存储地址与其值高度关联，这种关联性要通过一个“哈希函数”来实现，即$Addr = H(key)$
哈希表自身需要借助数组实现，哈希函数的值和数组的下标一一对应，当哈希表满了之后需要自动扩容。另外，不同数据元素的哈希函数值可能相同，这属于“冲突”现象，而哈希表也需要有冲突处理机制。下面将结合代码一同介绍哈希表存储结构，哈希函数，插入，查询和扩容
哈希表类定义
STL中在关联式容器map,multimap,set,multiset前面加上unordered_就成为哈希容器，代码中以unordered_set为例，先给出哈希表类定义：
template<class Elem>
class UnorderedSet {
private:
vector<Elem> base;//存储元素用的数组
size_t size = 0;//容器大小，即存入元素的个数
const size_t primeList[13] = {
53, 97, 193, 389, 769, 1543,
3079, 6151, 12289, 24593,
49157, 98317, 196613
};//可供选择的表长，idx与此对应
size_t idx = 0;
//哈希函数
size_t hashCode(Elem e);
//扩容时重新计算哈希值
void rehash();
public:
//构造函数
UnorderedSet();
//插入
void insert(Elem e);
//查找
bool find(Elem e);
};
哈希函数
哈希表是通用型的查找表，对元素类型无特殊要求，这里以整数型(int)为例。常见的哈希函数有以下几种：
1. 直接定址法：$H(key)=a*key+b$。对于均匀连续分布的元素，这种方式有奇效，但元素的离散程度如果稍微高一点，那就会造成存储空间的严重浪费。如班级内学生的学号，假设为$170601 \sim 170648$，那么就可以取$H(key) = 1 * key - 170601$，把所有元素集中在下标$0 \sim 47$之间的数组中
2. 除留余数法：$H(key)=key~MOD~p$，其中$p$一般取不大于表长的质数，这样可以一定程度上减少冲突。这是最常用的哈希函数，STL中给出了一些可选的质数，这里选取了其中靠前的13个作为类内的$primeList$，供初始化和扩容时选择表长，哈希函数也是用元素本身与表长取模
template<class Elem>
UnorderedSet<Elem>::UnorderedSet()
{
//选择第一个质数53作为初始表长
base.resize(primeList[idx], Elem(INT_MIN));
}
template<class Elem>
size_t UnorderedSet<Elem>::hashCode(Elem e)
{
//size_t是unsigned long long类型，有无符号不影响整数的存储
return (size_t)e % primeList[idx];
}
————————————
3. 数字分析法：选取数字分布较为均匀的几位为关键字，适用于已知的关键字集合，比如11位的手机号码，选取最后4位为关键字
4. 平方取中法：在元素的平方构成的数位中选取中间的几位为关键字
冲突处理
在介绍冲突前，首先介绍“同义词”概念：不同的表项求得的哈希函数值对应到了同一个地址，那么这些表项都是该地址的“同义词”。某表项在存入哈希表前发现它所在地址已经存在了同义词，这就是所谓的“冲突”现象。处理冲突的思想主要有三种：
1. 开放定址法：表中空闲地址同时对该地址的同义词和非同义词开放，也就是把产生冲突的表项存入表中另一个槽位中，而不另外申请空间，又称“闭散列”
2. 链地址法：在表外申请新的空间，存放某地址的所有同义词，并将这些表项按照链表或树的方式关联起来，又称“开散列”
3. 再散列法：准备多个哈希函数，当某个哈希函数冲突时，换另一个哈希函数重算地址，直到不冲突为止
本帖中先介绍考研热点“开放定址法”，链地址法过后填坑（哈希函数都为除留余数法）。再散列法由于实现较为麻烦，还需进一步查阅资料，暂时不补
插入
下面的示例中，表长取了一个更小的质数13，依次将$\left \{17,40,23,71,26,90 \right \}$插入哈希表，挨个计算哈希函数值，得到以下的元素位置：
如果还想继续往里插入$\left \{ 19,6,32 \right \}$，由于它们的哈希值都是6，而地址6上已经有了元素71，此时就发生了冲突。对于开放定址法，冲突的处理主要就是在原来的值上添加一个增量$d_i$之后重算哈希函数值，统一格式为$H_i = (H(key)+d_i)~MOD~p$。根据增量序列的不同，又分为3种方法：
1. 线性探测：$d_i=1,2,3,4,…,p-1$
2. 二次探测：$d_i=+1^2,-1^2,+2^2,-2^2,…,+k^2,-k^2(k<m/2)$
3. 伪随机数探测：$d_i$从伪随机序列中取得
下面给出线性探测（代码中的方法，红色表示）和二次探测（绿色表示）处理冲突之后，上述三个元素的位置：
实际上，线性探测方法对于同义词较多的情况，会出现很明显的聚集现象，二次探测和伪随机数探测就可以有效减少聚集（示例过后填坑）
扩容
哈希表有一个装填因子概念，定义为表内元素的数量与表长的比值，当表长确定时，表内元素数量也就有了一个阈值，超过这个阈值，哈希表就会自动扩容，STL中默认的装填因子为1.0，也就是当哈希表满了的时候才扩容。扩容总共分为三个步骤：
1. 确定哈希表的新长度（这里是在质数列表中选择下一个更大的），构造一条更长的数组
2. 重新计算原表中每个元素的哈希值
3. 将它们依次移动到新的数组中，并替换原来的数组
扩容函数如下：
template<class Elem>
void UnorderedSet<Elem>::rehash()
{
idx++;//准备选择下一个质数
vector<Elem> newBase(primeList[idx], Elem(INT_MIN));
//重算每个元素的哈希值（除留余数+线性探测）
for (auto& e : base) {
size_t pos = hashCode(e);
while (newBase[pos] != Elem(INT_MIN)) {
pos = hashCode(Elem(pos + 1));
}
//放进新表中
newBase[pos] = e;
}
//替换原表
base = newBase;
}
加上扩容之后的插入函数：
template<class Elem>
void UnorderedSet<Elem>::insert(Elem e)
{
//已经在表中，不用插入
if (find(e)) {
return;
}
//装满了，扩容
if (size == primeList[idx]) {
rehash();
}
//计算哈希值（除留余数+线性探测）
size_t pos = hashCode(e);
while (base[pos] != Elem(INT_MIN)) {
pos = hashCode(Elem(pos + 1));
}
base[pos] = e;
size++;
}
查找
查找元素，首先计算待查元素的哈希值，然后保持和插入时相同的冲突处理策略，依次重算哈希值（插入时使用除留余数+线性探测，那么查找时也用除留余数+线性探测）并查看该地址上的元素是否为待查元素，是则查找成功，查找到空槽位或者遍历全表仍未查找到，则查找失败
查找函数如下：
template<class Elem>
bool UnorderedSet<Elem>::find(Elem e)
{
size_t pos = hashCode(e);
for (int i = 0; i < primeList[idx]; i++) {
//当前地址上是待查元素，直接成功
if (base[pos] == e) {
return true;
}
//空槽位，直接失败
if (base[pos] == Elem(INT_MIN)) {
return false;
}
//和插入时使用相同的冲突处理策略
pos = hashCode(Elem(pos + 1));
}
//遍历完了仍未成功，自动失败
return false;
}
