哈希表——線性探測

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));
		
	}
}