package Hash;

public class HashTable {
	private DataItem[] hashArray;
	private int arraySize;
	private DataItem nonItem;
	
	public HashTable(int size) {
		this.arraySize = size;
		this.hashArray = new DataItem[this.arraySize];
		this.nonItem = new DataItem(-1);
	}
	
	public void displayTable() {
		System.out.print("Table:");
		
		for(int j=0;j<this.arraySize;j++) {
			if(this.hashArray[j] != null) {
				System.out.print(this.hashArray[j].getKey()+" ");
			}else {
				System.out.print("*");
			}
			System.out.print("/");
		}
	}
	
	/**
	 * 哈希函数 - 线性探测哈希表
	 * @return
	 */
	public int hashFunc(int key) {
		return key % this.arraySize;
	}
	
	/**
	 * 再哈希函数
	 * @param key
	 * @return
	 */
	public int hashFunc2(int key) {
		return 5-(key%5);
	}
	
	public void insert(int i) {
		DataItem newItem = new DataItem(i);
		int hashVal = this.hashFunc(i);
		int stepSize = this.hashFunc2(i);
		
		while(this.hashArray[hashVal] != null && this.hashArray[hashVal].getKey() != -1) {
			hashVal += stepSize;
			hashVal %= this.arraySize;
		}
		
		this.hashArray[hashVal] = newItem;
	}
	
	public DataItem delete(int key) {
		int hashVal = this.hashFunc(key);
		int stepSize = this.hashFunc2(key);
		
		while(this.hashArray[hashVal] != null) {
			if(this.hashArray[hashVal].getKey() == key) {
				DataItem temp = this.hashArray[hashVal];
				this.hashArray[hashVal] = this.nonItem;
				return temp;
			}
			
			hashVal += stepSize;
			hashVal %= this.arraySize;
		}
		
		return null;
	}
	
	public boolean find(int key) {
		int hashVal = this.hashFunc(key);
		int stepSize = this.hashFunc2(key);
		
		while(this.hashArray[hashVal] != null) {
			if(this.hashArray[hashVal].getKey() == key) {
				return true;
			}
			
			hashVal += stepSize;
			hashVal %= this.arraySize;
		}
		
		return false;
	}
}