一、题目
https://www.acwing.com/problem/content/842/
二、思路
拉链法
开放寻址法采用hash函数找到在hash数组中对应的位置，如果该位置上有值，并且这个值不是寻址的值，则出现冲突碰撞，需要解决冲突方案，该算法采用链表的形式，一直往下拉
开放寻址法
开放寻址法采用hash函数找到在hash数组中对应的位置，如果该位置上有值，并且这个值不是寻址的值，则出现冲突碰撞，需要解决冲突方案，该算法采用简单的向右继续寻址来解决问题。
三、代码
拉链法
import java.util.Scanner; public class Main { //N:操作数量 , h[N]:拉链数组 , e[N]:地址为N的数值 , ne[N]:地址为N的下一个节点地址，index:节点地址 static int N=100003; static int index=1; static int []h=new int[N]; static int []e=new int[N]; static int []ne=new int[N]; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n= sc.nextInt(); while (n-->0) { String s=sc.next(); int c=sc.nextInt(); if(s.equals("I")){ insert(c); }else { if(query(c)){ System.out.println("Yes"); }else System.out.println("No"); } } } private static void insert(int x) { int n=(x%N+N)%N; //+N余N是为了防止取余的结果为负数 e[index]=x; ne[index]=h[n]; h[n]=index++; } private static boolean query(int x) { int n=(x%N+N)%N; for(int i=h[n];i!=0;i=ne[i]){ if(e[i]==x) return true; } return false; } }
开放寻址法
import java.util.*; public class Main{ private static int N = 200003; //因为要用null标识节点空，所以类型为Integer private static Integer[] a = new Integer[N]; public static int find(int x){ int k = (x % N + N) % N; //别忘了第二个已存在的条件 while(a[k] != null && a[k] != x){ k++; if(k == N){ k = 0; } } return k; } public static void main(String[] args){ //先将所有位置设为null，标识为空 Arrays.fill(a,null); Scanner scanner = new Scanner(System.in); int m = scanner.nextInt(); while(m-- > 0){ String opt = scanner.next(); int x = scanner.nextInt(); if("I".equals(opt)){ a[find(x)] = x; }else{ //这是比较的是a[find(x)] System.out.println(a[find(x)] == null ? "No" : "Yes"); } } } }
