package Search;
/*
* 哈希查找(线性探测法)：位置=存数（即要存的数据）%p //p取小于等于长度的最大素数
* 解决冲突时往下移一个位置
* 即(存数+1)%p....直至找到位置
*
* 能存储的元素个数=p
*
* 补充知识点：
* 1、&&和||是短路运算符（&&：当第一个条件为false，不用判断第二个条件）
* （||：当第一个条件为true，不用判断第二个条件）
* 2、%和|是非短路运算符：两个条件都需要判断
*/
public class HashSearch {
public static void entry(int hash[],int key) { //存元素方法
int p=getMaxPrime(hash); //获得小于等于长度的最大素数
int i=0;
int pos=(key+i)%p;
int t=pos;
while (hash[t]!=0) { //判断该位置是否为空，不为空接着查下一位置
i++;
t=(key+i)%p; //进入下一位置
if (t==pos) { //下一位置已回到原点（pos），表已满
System.out.println("表已满"+t);
return;
}
}
hash[t]=key;
}
public static int getMaxPrime(int[] hash) { //获得小于等于长度的最大素数
int maxPrime=hash.length;
if (maxPrime<=1) { //当数组长度为1时p取1
return 1;
}
while (isPrime(maxPrime)==false) { //判断当前值是否为素数
maxPrime--;
}
return maxPrime;
}
public static boolean isPrime(int prime) { //判断数是否是素数（传入数必须>=2）
boolean judge=true; //默认为真
for (int i = 2; i < prime; i++) {
if (prime%i==0) {
judge=false;
break;
}
}
return judge;
}
/*
* 第一种查找方法：
* （1）hash[t]（即当前判断元素为空）：在查找过程中出现hash[t]为空，元素从未插入
* （因为元素插入过程如果有空，应立即插在该位置上，返回-1）
* （2）hash[t]（即当前判断元素不为空）：第一种==key(查找成功，返回位置t)
* 第二种!=key(不匹配，移至下一位置继续查找)
* 属于（2）情况且必须在移至下一位置后执行：位置移动后的判断（t==pos）,已查找表中所有元素
* ，未找到返回-1
*/
public static int HashSearchOne(int[] hash,int key) {
int p=getMaxPrime(hash);
int i=0;
int pos=(key+i)%p;
int t=pos;
while (hash[t]!=0) { //当前位置非空
if (hash[t]==key) {
return t;
}else {
i++;
t=(t+i)%p;
}
if (t==pos)return -1; //查找失败，表已全部查完
}
return -1; //当前位置为空，查找失败
}
/*
* 第二种查找方法：
* （1）hash[t]==key：查找成功
* （2）hash[t]!=key:第一种为空：查找失败
* 第二种不为空：移至下一元素继续匹配
* 属于（2）需要在移动至下一元素语句后判断：t==pos，表已走位，查找失败
*/
public static int HashSearchTwo(int[] hash,int key) {
int p=getMaxPrime(hash);
int pos=key%p;
int t=pos;
while (hash[t]!=key) {
if (hash[t]==0) { //为空，查找失败
return -1;
}else { //不为空，移至下一位置
t=(t+1)%p;
}
if(t==pos) return -1; //表已走完，未找到元素
}
return t; //查找成功
}
}
package Search;
public class test {
public static void main(String[] args) {
int[] hash=new int[5];
int[] key=new int[]{2,1,5,3,4};
for (int i = 0; i < key.length; i++) {
HashSearch.entry(hash, key[i]);
}
System.out.println("hash表的存储结构：");
for (int i = 0; i < HashSearch.getMaxPrime(hash); i++) {
System.out.println(hash[i]);
}
System.out.println("5的索引："+HashSearch.HashSearchOne(hash, 5));
System.out.println("2的索引："+HashSearch.HashSearchOne(hash, 2));
System.out.println("5的索引："+HashSearch.HashSearchTwo(hash, 5));
System.out.println("2的索引："+HashSearch.HashSearchTwo(hash, 2));
}
}
