Acwing算法基础课——数据结构 840.模拟散列表

题目维护一个集合支持如下几种操作I x插入一个整数 xQ x询问整数 x 是否在集合中出现过现在要进行 N 次操作对于每个询问操作输出对应的结果。输入格式第一行包含整数 N表示操作数量。接下来 N 行每行包含一个操作指令操作指令为I xQ x中的一种。输出格式对于每个询问指令Q x输出一个询问结果如果 x 在集合中出现过则输出Yes否则输出No。每个结果占一行。数据范围1≤N≤10^5−10^9≤x≤10^9输入样例5 I 1 I 2 I 3 Q 2 Q 5输出样例Yes No答案开放寻址法#includeiostream #includecstring using namespace std; const int N200003;//哈希表大小通常取一个质数且是N值的2-3倍降低冲突概率 const int null0x3f3f3f3f;//选择一个数据范围之外的值作为空标记 int h[N]; //查找 x 的位置如果 x 存在则返回下标否则返回可插入的位置 int find(int x){ int k(x%NN)%N;//哈希函数 为什么要N%N C 中对负数取模为负加 N 再取模即可让哈希值k都是正数。 while(h[k]!nullh[k]!x){ k; if(kN) k0; } return k; } int main(){ memset(h,0x3f,sizeof h);//初始化为null int n; cinn; while(n--){ char op; int x; cinopx; int kfind(x); if(opI) { h[k]x;} else if(opQ){ if(h[k]!null) coutYesendl; else coutNoendl; } } }要点1.哈希表大小的选择const int N200003; 哈希表大小通常取一个质数且是N值的2-3倍降低冲突概率。2.const int null0x3f3f3f3f; 选择一个数据范围之外的值作为空标记3.哈希函数的选择int k(x%NN)%N;为什么要N%N C 中对负数取模为负加 N 再取模即可让哈希值k都是正数。4.memset(h,0x3f,sizeof h);//将数组全部初始化为null memset是按字节设置的int有4个字节会把每个字节都变成0x3f 即3f3f3f3f