[数据结构与算法]哈希表的使用

一、开放寻址法
代码实现

import java.util.Arrays;
import java.util.Scanner;
public class Main {
	static int n,u;
	static String s;
	static int N=200003,INF=0x3f3f3f3f;
	static int[] h=new int[N];
	public static int find(int x) {
		int k=(x%N+N)%N;
		while(h[k]!=INF&&h[k]!=x) {
			k++;
			if(k==N) k=0;
		}
		return k;
	}
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		Arrays.fill(h, INF);
		while(n--!=0) {
			s=sc.next();
			u=sc.nextInt();
			int t=find(u);
			if(s.equals("I")) {
				h[t]=u;
			}else {
				if(h[t]!=INF)
					System.out.println("Yes");
				else
					System.out.println("No");
			}
		}
	}
}

二、拉链法
代码实现

import java.util.Scanner;
import java.util.Arrays;
public class Main {
	static int N=100003;  
	static int n,u,idx=1;
	static String s;
	static int[] h=new int[N],e=new int[N],ne=new int[N];
	public static void insert(int x) {
		int k=(x%N+N)%N;
		e[idx]=x;
		ne[idx]=h[k];
		h[k]=idx++;
	}
	public static boolean query(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;
	}
	public static void main(String[] args) {	
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		Arrays.fill(h, -1);
		while(n--!=0) {
			s=sc.next();
			u=sc.nextInt();
			if(s.equals("I")) {
				insert(u);
			}else {
				System.out.println(query(u)?"Yes":"No");
			}
		}
	}
}

三、字符串哈希
代码实现

import java.io.*;
public class Main {
	static int n,m;
	static int l1,r1,l2,r2;
	static int N=100010,P=131;
	static String s;
	static long[] h=new long[N],p=new long[N];
	public static long get(int l,int r) {
		return h[r]-h[l-1]*p[r-l+1];
	}
	public static void main(String[] args) throws IOException{
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out=new BufferedWriter(new OutputStreamWriter(System.out));
		String[] a=in.readLine().split(" ");
		n=Integer.parseInt(a[0]);
		m=Integer.parseInt(a[1]);
		s=in.readLine();
		p[0]=1;
		for(int i=1;i<=n;i++) {
			p[i]=p[i-1]*P;
			h[i]=h[i-1]*P+s.charAt(i-1);
		}
		while(m--!=0) {
			a=in.readLine().split(" ");
			l1=Integer.parseInt(a[0]);
			r1=Integer.parseInt(a[1]);
			l2=Integer.parseInt(a[2]);
			r2=Integer.parseInt(a[3]);
			System.out.println(get(l1,r1)==get(l2,r2)?"Yes":"No");
		}
	}
}