public class DataItem {
private int iData;
public DataItem(int i){
iData = i;
}
public int getkey(){
return iData;
}
}
public class HashTable {
/**
* 完成哈希存储的查找的功能
* 开放地址法之线性探测
* 线性探测就是按照当前的位置冲突,它会按照数组的下标一步步的查找空白的单元
* 缺点:当哈希表越来越满的时候,聚集会变的越来越严重,这会导致产生非常长的探测长度
* 意味着存储序列的最会单元会非常耗时
*/
private DataItem [] hashArray;
private int arraySize;
private DataItem nonItem;
//hashtabe 的初始化
public HashTable(int size){
arraySize = size;
hashArray = new DataItem[arraySize];
nonItem = new DataItem(-1);
}
//用来遍历整个哈希表
public void displayTable(){
System.out.println("table: ");
for(int i=0;i<hashArray.length;i++){
if(hashArray[i]!=null){
System.out.println(hashArray[i].getkey()+" ");
}else{
System.out.println("** ");
}
}
}
//hash映射函数
public int hashFun(int key){
return key%arraySize;
}
//哈希插入
public void insert(DataItem item){
int key = item.getkey(); //将存储对象的数据的键值传递给映射函数,得到数字的下标
int hashVal= hashFun(key);
while(hashArray[hashVal] !=null && hashArray[hashVal].getkey() !=-1){ //判断得到的位置上有没有数据,如果有数据就执行此循环
++hashVal;
hashVal %=arraySize;
}
hashArray[hashVal] = item;
}
//哈希删除
public DataItem delete(int key){
int hashVal = hashFun(key);
while(hashArray[hashVal] != null ){ //如果key的位置有数据
if(hashArray[hashVal].getkey() == key){
DataItem temp = hashArray[hashVal]; //取走数据以后将这个位置上的数据设置为空
hashArray[hashVal] = nonItem;
return temp; //返回key位置的数据
}
++hashVal; //如果这个位置上数据不是要找的数据,就向前遍历这个数据
hashVal%=arraySize;
}
return null;
}
//哈希查找
public DataItem find(int key){
int hashVal = hashFun(key);
while(hashArray[hashVal]!=null){
if(hashArray[hashVal].getkey() == key){
return hashArray[hashVal];
}
++hashVal;
hashVal%=arraySize;
}
return null;
}
//测试
public static void main(String[] args) {
HashTable hs = new HashTable(5);
DataItem i1 = new DataItem(2);
hs.insert(i1);
DataItem i2 = new DataItem(1);
hs.insert(i2);
DataItem i3 = new DataItem(4);
hs.insert(i3);
DataItem i4 = new DataItem(3);
hs.insert(i4);
hs.displayTable();
System.out.println(hs.delete(0));
}
}