36.Acwing基础课第840题-简单-模拟散列表

36.Acwing基础课第840题-简单-模拟散列表

题目描述

维护一个集合，支持如下几种操作：

1. I x，插入一个整数 x；
2. Q x，询问整数 x 是否在集合中出现过；

现在要进行 N 次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 N，表示操作数量。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式

对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤N≤10⁵

-10⁹≤x≤10⁹

输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

问题

问题1：为什么要找第一个比空间大的质数，const int N = 200003;

1.1开放寻址操作过程中会出现冲突的情况，一般会开成两倍的空间，减少数据的冲突

1.2 如果使用%来计算索引， 把哈希表的长度设计为素数（质数）可以大大减小哈希冲突

比如

10%8 = 2      10%7 = 3
20%8 = 4      20%7 = 6
30%8 = 6      30%7 = 2
40%8 = 0      40%7 = 5
50%8 = 2      50%7 = 1
60%8 = 4      60%7 = 4
70%8 = 6      70%7 = 0

这就是为什么要找第一个比空间大的质数

问题2：const int null = 0x3f3f3f3f 和 memset(h, 0x3f, sizeof h)之间的关系;

核心关系：值的精准匹配

const int null = 0x3f3f3f3f; 定义的常量值，恰好是 memset(h, 0x3f, sizeof h) 对 int 类型数组 h 初始化后，每个数组元素的最终值。

这一匹配的本质是：利用 memset 按字节填充 的特性，将 int 类型的 4 个字节全部填充为 0x3f，拼接后就得到了 0x3f3f3f3f。

分步拆解原理

1. 先明确 memset 的核心规则

memset(void *_Dst, int _Val, size_t _Size) 的工作逻辑是：

• _Dst：待初始化内存的起始地址（比如数组 h 的首地址）；
• _Val：单字节填充值（仅取低 8 位，即 0~0xff）；
• _Size：要填充的总字节数（不是元素个数）；
• 核心：把从 _Dst 开始的 _Size 个字节，每个字节 都设置为 _Val 的低 8 位值。

2. int 类型的字节构成

在绝大多数系统中，int 占 4 个字节（32 位）。比如一个 int 变量在内存中是 4 个连续的字节空间：

地址： 0x00  0x01  0x02  0x03
字节： [ ]   [ ]   [ ]   [ ]  （共4字节，对应1个int）

3. memset(h, 0x3f, sizeof h) 的填充过程

• sizeof h：计算数组 h 的总字节数（比如 h 是 int h[10]，则 sizeof h = 10*4 = 40 字节）；

• memset 会把 h 对应的 40 个字节，每个字节 都填入 0x3f（单字节值）；

• 对于其中任意一个 int 元素（4 字节），填充后内存布局为：

  地址： 0x00  0x01  0x02  0x03
  字节： 0x3f  0x3f  0x3f  0x3f
  

• 4 个 0x3f 拼接成 32 位整数，就是 0x3f3f3f3f，和 const int null 的值完全一致。

4. 为什么不直接用 memset 填 1、2 这类常见值？

以填 1 为例：

• memset(h, 1, sizeof h) 会把每个字节填为 0x01，一个 int 元素就变成 0x01010101（十进制 16843009），而非整数 1；
• 只有 -1和 0是特例：
  • -1 的补码是全 1（0xff），memset(h, -1, sizeof h) 会让每个 int 元素都是 -1；
  • 0 的字节是 0x00，填充后每个 int 元素都是 0。

问题3：为什么要取0x3f3f3f,为什么不直接定义无穷大INF = 0x7fffffff,即32个1来初始化呢？

核心结论

选择 0x3f3f3f3f 而非 0x7fffffff 作为 “无穷大（INF）” 初始化值，核心是兼顾数值安全性和初始化效率——0x7fffffff 仅满足 “数值大”，但易溢出且无法高效初始化；0x3f3f3f3f 既适配 “无穷大” 的语义，又能利用 memset 快速赋值。

分维度解析原因

1. 数值特性：避免溢出，符合 “无穷大” 的数学逻辑

0x7fffffff 是 32 位有符号 int 的最大值（十进制 2147483647），看似是 “无穷大”，但存在致命缺陷：

• 溢出风险：只要对 0x7fffffff做加法（比如 INF + 5），就会触发整数溢出，根据补码规则，结果会变成负数（例如 0x7fffffff + 1 = 0x80000000，对应十进制 - 2147483648），直接破坏 “无穷大” 的语义。

  典型场景：图论最短路算法（Dijkstra/Floyd）中，松弛操作 dist[i] = min(dist[i], dist[j] + w)，若 dist[j] 是 0x7fffffff，加 w后变成负数，会导致算法逻辑完全错误。

而 0x3f3f3f3f 完美规避这个问题：

• 数值足够大：十进制 1061109567（10⁹级别），远大于常规业务 / 算法场景中的数据范围（比如路径长度、权值等），满足 “无穷大” 的基本要求；
• 加法不溢出：0x3f3f3f3f + 0x3f3f3f3f = 2122219134，仍小于 int 最大值（2147483647），实现 “无穷大加无穷大还是无穷大” 的逻辑；
• 减法 / 赋值安全：即使做减法（比如 0x3f3f3f3f - 100），结果仍远大于常规数据，不会影响判断。

2. 初始化效率：完美适配 memset，告别循环赋值

0x7fffffff 的字节结构是 0x7f 0xff 0xff 0xff（4 个字节不一致），而 memset 是按字节填充的，因此无法用 memset 初始化：

• 若用 memset(a, 0x7f, sizeof(a))，每个 int 元素会被填充为 0x7f7f7f7f（不是 0x7fffffff）；
• 若用 memset(a, 0xff, sizeof(a))，每个 int 元素会变成 0xffffffff（即 - 1）；
• 最终只能写循环 for (int i=0; i<n; i++) a[i] = 0x7fffffff;，对大数组（如 1e5 长度）效率极低。

而 0x3f3f3f3f 的字节结构是 0x3f 0x3f 0x3f 0x3f（4 个字节完全相同），刚好适配 memset：

• 一行代码 memset(a, 0x3f, sizeof(a)) 就能将整个数组的每个字节填充为 0x3f，最终每个 int 元素都是 0x3f3f3f3f；
• memset 是内存级别的操作，比循环赋值快 1~2 个数量级，尤其适合算法题中 “邻接矩阵、距离数组” 等大数组的初始化。

3. 额外优势：兼容性强

0x3f3f3f3f 的单字节值是 0x3f，不仅适配 int 类型：

• 对 char 类型：memset 后值为 0x3f（十进制 63），可作为字符数组的 “小无穷大”；
• 对 short 类型：memset 后值为 0x3f3f（十进制 16191），也适配短整型的 “无穷大” 场景。

总结

1. memset 按字节填充，0x3f 是单字节值，填充 4 字节 int 后得到 0x3f3f3f3f；
2. const int null = 0x3f3f3f3f 是对这一填充结果的常量封装，方便代码中直接引用；
3. memset 仅对 -1、0 能填充出对应整数值，其他值需结合字节特性理解最终结果。

代码：

#include <iostream>
#include <cstring>
using namespace std;const int N = 100003;//h[k]是指针，指向所映射数值下挂的第一个数，e[idx]当前节点存储的值
//ne[idx]是指向序号idx指向的下一个序号结点的指针，idx表示当前用到的位置序号
int h[N], e[N], ne[N], idx;void insert(int x)
{int k = (x % N + N) % N;e[idx] = x;ne[idx] = h[k];h[k] = idx++;
}bool find(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()
{int n;scanf("%d", &n);memset(h, -1, sizeof h);while(n--){char op[2];int x;scanf("%s%d", op, &x);if(*op == 'I') insert(x);else{if(find(x)) puts("Yes");else puts("No");}}return 0;
}

开放寻址法

#include <cstring>
#include <iostream>using namespace std;const int N = 200003, null = 0x3f3f3f3f;
int h[N];int find(int x)
{int t = (x % N + N) % N;while(h[t] != null && h[t] != x){t++;if(t == N) t = 0;}return t;
}int main()
{memset(h, 0x3f, sizeof h);int n;cin >> n;while(n--){char op[2];int x;cin >> op >> x;int k = find(x);if(*op == 'I'){h[k] = x;}else{if(h[k] != null)  puts("Yes");else  puts("No");}}return 0;
}

拉链法

#include <cstring>
#include <iostream>using namespace std;const int N = 100003;
int h[N], e[N], ne[N], idx;void insert(int x)
{int k = (x % N + N) % N;e[idx] = x;ne[idx] = h[k];h[k] = idx++;
}bool find(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()
{int n;cin >> n;memset(h, -1, sizeof h);while(n--){char op[2];int x;cin >> op >> x;if(*op == 'I')  insert(x);else{if(find(x))  puts("Yes");else  puts("No");}}return 0;
}