如何用散列表模拟解决Acwing第840题？

36.Acwing基础课第840题-简单-模拟散列表 题目描述 维护一个集合，支持如下几种操作： I x，插入一个整数 x； Q x，询问整数 x 是否在集合中出现过； 现在要进行 N 次操作，对于每个询问操作输出对应的结果。 输入格式 第一行包含整数 N，表示操作数量。 接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。 输出格式 对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。 每个结果占一行。 数据范围 1≤N≤105 -109≤x≤109 输入样例： 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），也适配短整型的 “无穷大” 场景。 总结 memset 按字节填充，0x3f 是单字节值，填充 4 字节 int 后得到 0x3f3f3f3f； const int null = 0x3f3f3f3f 是对这一填充结果的常量封装，方便代码中直接引用； 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; }