菜鸡的理解–java
拉链法
y总代码写的很好,但是进行插入操作的时候想起来会很迷,就比如说h[e],ne[e]的关系
我学起来就很迷,然后自己拒了一个例子,慢慢推了一遍就理解了
这是我模拟的样例,然后就可以看出:
e[idx]=x;//储存元素
ne[idx]=h[k];//储存上一个mod值相同元素的坐标,用ne坐标其实不如用pre形象
//而且第一个插入的ne[]=he[k]=-1,就直接停止了,
//当然,也可以不用-1做标记,但是为了避免冲突,idx要从1开始遍历
h[k]=idx++;//h[k]存的是mod N =k的最后一个元素的坐标,ne[idx]=x;
java代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N=100003;
static int h[]=new int [N],ne[]=new int [N];
static int e[]=new int [N],idx=1;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
StringBuilder st=new StringBuilder();
while(n--!=0) {
String s=sc.next();
int x=sc.nextInt();
if(s.charAt(0)=='I') insert(x);
else {
if(find(x))st.append("Yes").append('\n');
else st.append("No").append('\n');
}
}
System.out.print(st);
}
static void insert(int x) {
int k=((x%N)+N)%N;
e[idx]=x;
ne[idx]=h[k];//上一个元素的坐标,用ne坐标其实不如用pre形象
h[k]=idx++;//h[k]存的是mod=k的最后一个元素的坐标,ne[idx]=x;
}
static boolean find(int x) {
int k=((x%N)+N)%N;
for (int i = h[k]; i !=0;i=ne[i]) {
if(e[i]==x) return true;
}
return false;
}
}
开放寻址法
开放寻址法的思想很简单,就是如果mod之后得到的k有冲突的,就直接往后走一位
而且空间开的大,避讳出现空间都占用的情况
代码如下
package _2数据结构;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import javax.imageio.IIOException;
public class 开放寻址法哈希 {
static int N=300007;
static int temp=0x3f3f3f3f;//不在数据范围值之内的数字即可
static int h[]=new int [N];
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Exception
{
StringBuilder st=new StringBuilder();
Arrays.fill(h, temp);
int n=Integer.parseInt(br.readLine());
while(n--!=0) {
String s[]=br.readLine().split(" ");
int x=Integer.parseInt(s[1]);
int k=find(x);
if('I'==s[0].charAt(0)) {
h[k]=x;
}else {
if(h[k]!=temp) st.append("Yes\n");
else st.append("No\n");
}
}
bw.write(st.toString());
bw.close();
br.close();
}
static int find(int x) {
int k=((x%N)+N)%N;
while(h[k]!=temp&&h[k]!=x) {
k++;
if(k==N) k=0;
}
return k;
}
}