如何用散列表模拟解决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 快速赋值。