自己动手写数据结构之散列表

【散列表】

它是用一个散列函数把关键字 映射到散列表中的特定位置。
在理想情况下，如果元素e 的关键字为k，散列函 数为f，那么e 在散列表中的位置为f (k)。要搜索关键字为k
的元素，首先要计算出f (k)，然后看 表中f (k)处是否有元素。如果有，便找到了该元素。如果没有，说明该字典中不包含该元素。
在前一种情况中，如果要删除该元素，只需把表中f (k)位置置为空即可。在后一种情况中，可 以通过把元素放在f (k)位置以实现插入。
此例是一个理想情况下的散列表，不考虑关键字重复的情况

 

public class HashList {	
	
	private String[] table;

	private int size;

	private int threshold;

	private static final int INITIAL_CAPACITY = 10;

	private static final int SIZE_INCREASE = 10;

	private static final float DEFAULT_LOAD_FACTOR = 0.75f;
	
	
	
	public HashList(){
		threshold = (int)(INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR);
		table = new String[INITIAL_CAPACITY];
	}
	
	
	
	public HashList(String[] table){
		this.table = table;
	}
	
	
	
	
	/**
	 * Get the actual size of the list
	 * @return
	 */
	public int size(){
		return size;
	}
	
	/**
	 * for test
	 * @return
	 */
	public String[] getElements(){
		return table;
	}
	
	public boolean contains(String element) {
		if (element == null) {
			return false;
		}
		if (element.equals(table[getIndex(element)])) {
			return true;
		}
		return false;
	}
	
	public void add(String element){
		int index = getIndex(element);
		if(size>threshold){
			resize();
		}
		table[index] = element;
		size++;
	}
	
	
	
	//private methods
	/**
	 * resize the array
	 */
	private void resize(){
		String[] newArray = new String[table.length+SIZE_INCREASE];
		for(int i=0;i<table.length;i++){
			newArray[i] = table[i];
		}
		table = newArray;
		threshold = (int)(table.length*DEFAULT_LOAD_FACTOR);
	}
	
	/**
	 * get the index of the element
	 * @param element
	 * @return
	 */
	public int getIndex(String element) {
		return (element.hashCode() & 0x7FFFFFFF) % table.length;
	}	
}