AcWing 840. 模拟散列表(Java)
原题链接
简单
作者:
Wonion
,
2021-01-18 13:59:58
,
所有人可见
,
阅读 306
拉链法
import java.util.Scanner;
public class Main{
static int N = 100003;
static int[] h = new int[N]; //表示某个节点下有几个节点,以哈希值为索引,值是插入了几个数 01234
static int[] e = new int[N]; //存储链表的值
static int[] ne = new int[N]; //存储指向下一个节点的指针
static int idx = 0; //idx表示要操作节点的索引
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for(int i = 0; i < N; i++) h[i] = -1; //清空h数组,-1代表空节点
while(n-- > 0)
{
String a = in.next();
int b = in.nextInt();
if(a.equals("I")) insert(b);
else if(a.equals("Q"))
{
if(find(b)) System.out.println("Yes");
else System.out.println("No");
}
}
}
private static void insert(int x)
{
int k = (x % N + N) % N; //为了把负数变成正数
e[idx] = x;
ne[idx] = h[k];
h[k] = idx;
idx++;
}
private static boolean find(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;
}
}
开放寻址法
import java.util.Scanner;
public class Main{
static int N = 100003;
static int nul = 100010;
static int[] h = new int[N]; //以哈希值为索引,存储值
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for(int i = 0; i < N; i++) h[i] = nul;
while(n-- >0)
{
String a = in.next();
int x = in.nextInt();
int k = find(x);
if(a.equals("I")) h[k] = x;
else if(a.equals("Q"))
{
if(h[k] == x) System.out.println("Yes");
else System.out.println("No");
}
}
}
//如果当前位置为空,就直接返回映射后的索引,如果值相同,就返回当前位置的索引
//如果不为空并且值不同,就继续向右走,直到找到空位置
private static int find(int x) //返回值为x的索引
{
int k = (x % N + N) % N;
while(h[k] != nul && h[k] != x)
{
k++;
if(k == N) k = 0; //如果走到尾了,就从0开始寻找
}
return k;
}
}
兄弟,h[]数组表示的不是某个节点下有几个节点吧,h【】存的是所有的hash值为k的所有节点组成的单链表的第一个节点的位置吧