世界的尽头

哈希表

哈希表用于维护“键”与存储位置之间的映射。它通过哈希函数把范围很大的键映射到一个有限的下标范围，从而快速完成插入、查询等操作。

例如，要判断整数 x 是否已经出现，可以使用取模构造哈希函数：

int k = (x % N + N) % N;

其中，k 是 x 对应的桶编号，范围为 $[0,N-1]$ 。

在 C++ 中，负数取模的结果可能为负数。例如：

-3 % 5 = -3

因此不能直接把 x % N 当作数组下标。先加上 N，再对 N 取模，可以把结果统一转换到合法下标范围内。

哈希冲突

哈希表把大量可能的键映射到数量有限的桶中，不同的数可能得到同一个桶编号。例如，当 N = 5 时，2 和 7 都会被映射到编号为 2 的桶中。

这种情况称为哈希冲突。常见的冲突处理方法有：

拉链法：每个桶维护一条链表，把映射到同一个桶的元素存入同一条链表；
开放寻址法：发生冲突后，继续寻找下一个可用位置。

本题使用拉链法。

拉链法的数组模拟

可以把每个哈希桶看作一条单链表，并使用数组模拟所有链表：

const int N = 100003;
 
int h[N], e[N], ne[N], idx;

各数组的含义如下：

h[k]：编号为 k 的桶中，第一个节点的编号；
e[i]：编号为 i 的节点存储的整数；
ne[i]：编号为 i 的节点的下一个节点编号；
idx：下一个可以使用的新节点编号。

这里所有桶共用 e 和 ne 两个节点数组。h[k] 只保存对应链表的头节点编号。

节点编号从 0 开始，因此不能再用 0 表示空指针。初始化时需要把所有桶头设为 -1：

memset(h, -1, sizeof h);

为什么桶数取 `100003`

题目最多执行 $10^5$ 次操作，所以桶数取一个略大于 $10^5$ 的质数 100003。取模数为质数通常能让常见输入在桶中的分布更均匀，降低冲突概率。

这只能改善平均表现，不能从理论上消除冲突；真正保证查询正确的是拉链法保留了桶中的所有元素。

插入

插入整数 x 时，先计算它所属的桶，再使用头插法把它加入对应链表：

void insert(int x) {
  int k = (x % N + N) % N;
 
  e[idx] = x;
  ne[idx] = h[k];
  h[k] = idx++;
}

操作顺序为：

e[idx] = x：在新节点中保存 x；
ne[idx] = h[k]：让新节点指向原来的链表头；
h[k] = idx++：把新节点设为新的链表头，并移动 idx。

头插法不需要遍历链表，所以单次插入的时间复杂度为 $O(1)$ 。

如果同一个数被插入多次，链表中会保存多个相同节点，但不会影响“这个数是否存在”的查询结果。本题总插入次数不会超过操作次数，因此数组空间仍然足够。

查询

查询整数 x 时，只需要遍历它所属桶的链表：

bool query(int x) {
  int k = (x % N + N) % N;
 
  for (int i = h[k]; i != -1; i = ne[i]) {
    if (e[i] == x) {
      return true;
    }
  }
 
  return false;
}

哈希值不同的整数一定不在同一个桶中，因此不需要检查其他桶。哈希值相同的整数可能只是发生了冲突，所以还必须通过 e[i] == x 比较原值，不能只根据桶是否为空判断元素存在。

正确性说明

插入 x 时，算法根据哈希函数计算唯一的桶编号 k，再把一个存储 x 的新节点连接到 h[k] 所表示链表的头部。原链表中的所有节点仍然可以沿 ne 访问，因此插入不会丢失已经保存的元素。

查询 x 时，算法使用同一个哈希函数得到桶编号 k。如果 x 曾经被插入，它对应的节点一定被加入桶 k 的链表，遍历该链表时必然能够找到 e[i] == x 的节点并返回 true。

如果遍历完整条链表仍未找到 x，则桶 k 中不存在值为 x 的节点。由于每次插入 x 都只能进入桶 k，其他桶中也不可能保存由该次插入产生的 x，所以返回 false。

因此，查询结果为 true 当且仅当 x 曾经被插入。

AcWing 840：模拟散列表

题意

维护一个整数集合，依次执行 $n$ 个操作：

I x：插入整数 x；
Q x：询问整数 x 是否在集合中出现过。

对于每次查询，如果 x 出现过，输出 Yes；否则输出 No。

解题思路

使用拉链法实现哈希表：

把所有桶头初始化为 -1；
插入时计算 x 所属的桶，并使用头插法加入桶内链表；
查询时只遍历对应桶的链表，逐个比较节点中保存的原值。

哈希函数必须同时用于插入和查询，并通过 (x % N + N) % N 正确处理负数。

完整代码

#include <cstring>
#include <iostream>
#include <string>
 
using namespace std;
 
// 100003 是略大于 10^5 的质数，可以降低常见输入下的冲突概率。
const int N = 100003;
 
int h[N], ne[N], e[N], idx;
 
void insert(int x) {
  int k = (x % N + N) % N;
  e[idx] = x;
  ne[idx] = h[k];
  h[k] = idx++;
}
 
bool query(int x) {
  int k = (x % N + N) % N;
 
  for (int i = h[k]; i != -1; i = ne[i]) {
    if (e[i] == x) {
      return true;
    }
  }
 
  return false;
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  memset(h, -1, sizeof h);
 
  int n;
  cin >> n;
 
  while (n--) {
    string op;
    int x;
    cin >> op >> x;
 
    if (op == "I") {
      insert(x);
    } else {
      cout << (query(x) ? "Yes" : "No") << '\n';
    }
  }
 
  return 0;
}

样例

输入：

5
I 1
I 2
Q 3
Q 1
Q 2

输出：

No
Yes
Yes

插入 1 和 2 后，集合中不存在 3，但存在 1 和 2。

复杂度分析

设一共执行 $n$ 次操作。

插入使用头插法，单次时间复杂度为 $O(1)$ ；
在哈希分布较均匀时，查询的期望时间复杂度为 $O(1)$ ；
$n$ 次操作的期望总时间复杂度为 $O(n)$ ；
h、e 和 ne 数组的空间复杂度为 $O(N)$ ，其中本题的 $N$ 与操作数同阶。

极端情况下，所有元素都发生冲突并进入同一个桶，单次查询会退化为 $O(n)$ 。因此，不能把拉链法查询的最坏时间复杂度写成 $O(1)$ 。

常见错误

没有初始化桶头：全局数组默认值为 0，但节点编号 0 是有效节点。必须使用 memset(h, -1, sizeof h) 把空链表标记为 -1。
负数直接取模：x % N 可能为负数，作为数组下标会越界。应使用 (x % N + N) % N。
只判断桶是否为空：同一个桶中可能存有其他发生冲突的整数，必须遍历链表并比较 e[i] == x。
插入时覆盖原链表：更新 h[k] 前，必须先令 ne[idx] = h[k]，否则会丢失桶中原有节点。
数组空间不足：每次插入都会创建一个节点，e 和 ne 至少要容纳题目允许的最大插入次数。
混淆桶编号和节点编号：k 是 h 数组的桶编号，i 和 idx 是 e、ne 数组的节点编号，二者不是同一类下标。
误写复杂度：插入是严格的 $O(1)$ ，查询只是期望 $O(1)$ ，最坏情况下会退化为线性扫描。

参考资料

AcWing：数据结构（二）—— 单调栈、单调队列、KMP、Trie、并查集、堆、哈希表，作者：yxc（非商业转载请注明出处）。

8-哈希表

哈希表