AcWing 840. 模拟散列表

题目描述

---

餐前小菜：

在讨论本题目之前先看一个简单的问题：给出 $N$ 个正整数 $(a_1,a_2,...,a_n)$，再给出 $M$ 个正整数 $(x_1,x_2,...,x_m)$，问这 $M$ 个数中的每个数是否在 $N$ 个数中出现过，其中 $N,M\le 10^5$，且所有正整数均不超过 $10^5$。比较容易想到的思路是：对每个欲查询的数 $x_i$，遍历 $N$ 看看是否存在。该算法时间复杂度为 $O(NM)$，是有很多的优化空间的。
经典思想为用空间换时间，设有一个 hashTable[N]，其中 hashTable[$x_i$] == true 表示正整数 $x_i$ 在 $N$ 个正整数 $(a_1,a_2,...,a_n)$ 中找到了与之相等的数，若为 false 表示没有出现过。我们该怎么做呢？初始时 hashTable 全为 false，对读入的 $N$ 个数 $(a_1,a_2,...,a_n)$，进行预处理将 hashTable[$a_i$] 设置为 true，接着对 $M$ 个欲查正整数，直接查看 hashTable[$x_i$] 为 true/false 来判断出现/没出现过。在许多算法里都用到了这样一种方案：把输入的数作为数组下标来进行查询。将查询的时间复杂度降低至 $O(1)$。

---

分析：

但注意本题中，我们每个数的范围是 $[-10^9,10^9]$ 这是没有办法作为数组下标进行查询的！因此我们希望能将一些不合适的下标（负数或过大）转换为我们期望的一个范围内。
因此我们引入哈希（散列、hash）的思想，将元素(element, e)通过一个函数转换为整数，使得该整数可以尽量地代表这个元素。该函数称为哈希函数 $h()$。即对 $e$，求 $h(e)$。
看看这道题 $-10^9\le e\le 10^9$ 为整数，可以使用哪些常用的哈希函数呢？

1. 直接定址法（简单，常用于映射要求不高的题目）： $h(e)=e$。餐前小菜中对于需要查找的 $x_i$，其实就是使用了该方案，有一个隐式的$h(x_i)=x_i$，将要查询的数作为数组下标。
2. 平方取中法（基本不使用该方法，可忽略）：将 $e$ 的平方的中间若干位作为 hash 值。
3. 除留余数法（重要，常用）：$h(e)=e$ $mod$ $k$。通过该哈希函数，可以把很大的数转换为一个不超过 $k$ 的数，这样就可以作为可行的数组下标。这里 TableSize（即可 hash 映射的总长度必须大于等于 $k$，不然会产生越界），当 $k$ 是一个素数时，$h(e)$ 能尽可能覆盖 $[0,k)$ 范围内的每一个数。这里将 TableSize与 $k$ 都设置为相同的素数。但本题远没有这么简单，有两点需要注意：
   ① e 的取值可能为负，在人类世界里负数的模有各种各样的计算方法，但总归会得到一个在现有规则下“正确的”一个非负数解，同理根据高级程序语言的不同计算的方式也不同，但结果却不尽相同，在C/C++中，若对负数求模运算，会得到一个负的解，这显然是与模运算的定义所违背的，因此需要对运算结果进行加工：ans = (e % TableSize + TableSize) % TableSize，这样不论是正数还是负数都能得到正确的解，具体的细节不多做解释，可以将它看作是与加减乘除相类似的算法。
   ② TableSize 该如何选取呢？这是很重要的一点，同时也决定了哈希函数（与 k 有关）的设计。按照上文分析， TableSize 又应该大于等于输入总数 $N$ 的质数且根据上文需要大于等于 $k$，而 k 应为一个质数，我们得到一下关系：$TableSize=k\ge N$，而 $N$ 不是质数，因此不使用它，我们可以使用比 $N$ 大的第一个质数。

   // 求比 N 大的第一个质数
   N = 100000
   for (int i = N; ; i ++)
   {bool flag = false;for (int j = 2; j * j <= i; j ++){if (i % j == 0){flag = true;break;}}if (flag){cout << i << endl;break;}
   }>_: 100003
   

以我们对求余运算的了解，对于两不同的数 $e_1,e_2$，他们的 hash值可能是相同的，当 $e_1$ 将表中下标为 $h(e_1)$ 的单元占据时，$e_2$ 便不能再使用这个位置了，此时发生了冲突。

为解决冲突，将介绍一下三种方法，其中第一、二种都计算了新的 hash 值，又称为开放寻址法：

1. 线性探测法(Linear Probing)：当得到 $e$ 的 $hash值h(e)$ 后，观察到 hashTable 中下标为 $h(e)$ 的位置已经被其他元素占用，那么就检查下个位置 $h(e)+1$ 是否被占用，如果没有，就使用这个位置；如果还是被占用就继续向后检查，当检查长度超出 TableSize 时，就回到表头继续向后查找，知道找到能使用的位置或表中所有位置均被使用过为止。这种做法容易扎堆。同时，由于线性探测法有向后检查的特征，因此 hashTable 的设置至少要为 N 的 2 倍，又根据我们在除留余数法中的分析，TableSize 为 200003。而具体实现中，用一个极大值$(0x3f3f3f3f)$来标识一个位置是否被占用，如被占用，则 $hashTable[h(e)]=e$，否则 $hashTable[h(e)]=0x3f3f3f3f$。
2. 平方探测法(Quadratic probing)：在平方探测法中，为了尽可能避免扎堆现象，当表中 $h(e)$ 的位置被占用时，将按下面的顺序检查表中的位置：$h(e)+1^2、h(e)-1^2、h(e)+2^2、h(e)-2^2、h(e)+3^2...$。①如果检查过程中 $h(e)+i^2＞TableSize$ 时（下个位置超出表尾），就把 $h(e)+i^2$ 对 TableSize 取模；②如果检查过程中 $h(e)-i^2＜0$时（下个位置超出表头），就将$((h(e)-i^2)modTableSize+TableSize)modTableSize$ 作为结果，如果为避免出现负数的麻烦可以只进行正方向的平方探测。有结论证明，如果 $e$ 在 $[0,TableSize]$ 范围内都无法找到位置，当 $i\ge TableSize$ 时，也一定无法找到位置。
3. 链地址法(拉链法)：拉链法不计算新的 hash值，而是把所有 $h(e)$ 相同的 $e$ 连接成一条单链表。，若 $e_1,e_2$ 有相同 hash值，则可以形成这样一个单链表：
   可以看到，线性探测法比较直观而拉链法操作比较多，因此对其进行模拟一下，请结合代码理解！
   

---

代码(C++)

线性探测法

#include <iostream>using namespace std;// TS: TableSize
const int TS = 200003, null = 0x3f3f3f3f;
int hashtable[TS];// 哈希函数，输入元素返回哈希值用于初步定位 hashtable
// h(e) 返回的是未经线性探测的位置
int h(int e)
{return (e % TS + TS) % TS;
}// find(e) 返回经过线性探测的位置
int find(int e)
{int he = h(e);while (hashtable[he] != null && hashtable[he] != e){he ++;if (he == TS) he = 0;}return he;
}int main()
{int n;cin >> n;// 初始化时，每一位都没有被占用，即没有出现过for (int i = 0; i < TS; i ++) hashtable[i] = null;while (n --){char op;int e;cin >> op >> e;// 找到最终位置后进行插入if (op == 'I') hashtable[find(e)] = e;else{// 通过经过线性探测的位置来判断 e 的性质//而不能通过计算一次哈希函数就去hashtable看if (hashtable[find(e)] == null) cout << "No" << endl;else cout << "Yes" << endl;}}
}

拉链法

#include <iostream>using namespace std;const int TS = 100003;
// TS: TableSize, no: node, ne: next
int hashtable[TS], no[TS], ne[TS], idx;int h(int e)
{// 哈希函数，输入元素返回哈希值用于初步定位 hashtablereturn (e % TS + TS) % TS;
}void insert(int e)
{int he = h(e);no[idx] = e;ne[idx] = hashtable[he];hashtable[he] = idx ++;
}int find(int e)
{int he = h(e);// 通过 hashtable[he] 可以查询到最后一个被连接到 h(e) 位置的元素// 再顺着该元素往前查看，看 e 是否在此链中出现过for (int i = hashtable[he]; i != -1; i = ne[i]){// i 实际上为 idxif (no[i] == e) return true;}return false;
}int main()
{int n;cin >> n;// 每个位置的链没有连接元素for (int i = 0; i < TS; i ++) hashtable[i] = -1;while (n --){char op;int e;cin >> op >> e;if (op == 'I') insert(e);else{if (find(e)) cout << "Yes" << endl;else cout << "No" << endl;}}
}

---