AcWing 840. 模拟散列表Java
原题链接
简单
作者:
w972314191
,
2022-12-09 18:52:34
,
所有人可见
,
阅读 143
拉链法
import java.util.*;
import java.io.*;
public class Main{
static int N = 100003, idx = -1;
static int[] hash = new int[N], node = new int[N], ne = new int[N];
static void insert(int v){
int k = (v % N + N) % N;
node[++idx] = v;
ne[idx] = hash[k];
hash[k] = idx;
}
static boolean find(int v){
int k = (v % N + N) % N;
for(int i = hash[k]; i != -1; i = ne[i]){
if(node[i] == v){
return true;
}
}
return false;
}
public static void main(String[] args) throws IOException{
Scanner scanner = new Scanner(System.in);
Arrays.fill(hash, -1);
int m = scanner.nextInt();
while(m-- > 0){
String opt = scanner.next();
int x = scanner.nextInt();
if("I".equals(opt)){
insert(x);
}else{
System.out.println(find(x) ? "Yes" : "No");
}
}
}
}
开放寻址法
import java.util.*;
import java.io.*;
public class Main{
static int N = 200003, idx = -1;
static Integer[] hash = new Integer[N];
static int find(int v){
int k = (v % N + N) % N;
while(hash[k] != null && hash[k] != v){
k++;
if(k == N) k = 0;
}
return k;
}
public static void main(String[] args) throws IOException{
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)){
hash[find(x)] = x;
}else{
System.out.println(hash[find(x)] != null ? "Yes" : "No");
}
}
}
}