simplehashtable.java

中国移动定位引擎的客户端

package ffcs.lbp.common;

import java.util.Iterator;

/**
 * <p>
 * Title: 智能短信系统接口程序
 * </p>
 * <p>简单Hashtable 类</p>
 * <p>Copyright: 2007 福建福富软件技术股份有限公司 </p>
 * <p>Company: 福建福富软件技术股份有限公司</p>
 * @author chenxin
 * @version 1.0 $Date:2007-06-30
 */
public class SimpleHashtable {

	protected DataItem[] hashArray;

	private int arraySize;

	private int dataSize;

	/**
	 * 构造函数
	 * @param size　Hashtable容量
	 */
	public SimpleHashtable(int size) // constructor
	{
		arraySize = size;
		hashArray = new DataItem[arraySize];
	}

	/**
	 * 显示Hashtable中的值
	 */
	public void displayTable() {
		System.out.print("Table: ");
		for (int j = 0; j < arraySize; j++) {
			if (hashArray[j] != null)
				System.out.print(((DataItem) hashArray[j]).key + " ");
			else
				System.out.print("** ");
		}
		System.out.println("");
	}

	public int hashFunc(int key) {
		return key % arraySize; // hash function
	}

	public void put(int key, Object data) {
		put(new DataItem(key, data));
	}

	/**
	 * 添加数据项到Hashtable
	 * @param item
	 */
	protected void put(DataItem item) // insert a DataItem
	{
		int key = item.getKey(); // extract key
		int hashVal = hashFunc(key); // hash the key
		// until empty cell or -1,
		while (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
			if (hashArray[hashVal].key == item.key) {
				break;
			}
			++hashVal; // go to next cell
			hashVal %= arraySize; // wraparound if necessary

		}
		if (hashArray[hashVal] == null) {
			dataSize++;
		}
		hashArray[hashVal] = item; // insert item
	}

	/**
	 * 根据KEY删除Hashtable中的数据项
	 * @param key　要删除的KEY
	 * @return　DataItem　返回删除的数据项
	 */
	public DataItem delete(int key) // delete a DataItem
	{
		int hashVal = hashFunc(key); // hash the key

		while (hashArray[hashVal] != null) // until empty cell,
		{ // found the key?
			if (hashArray[hashVal].getKey() == key) {
				DataItem temp = hashArray[hashVal]; // save item
				hashArray[hashVal] = null; // delete item
				dataSize--;
				return temp; // return item
			}
			++hashVal; // go to next cell
			hashVal %= arraySize; // wraparound if necessary
		}
		return null; // can't find item
	}

	/**
	 * 根据KEY提到数据项
	 * @param key　Hashtable中的key
	 * @return
	 */
	public Object get(int key) // find item with key
	{
		int hashVal = hashFunc(key); // hash the key

		while (hashArray[hashVal] != null) // until empty cell,
		{ // found the key?
			if (hashArray[hashVal].getKey() == key) {
				return ((DataItem) hashArray[hashVal]).getData(); // yes,
				// return
				// item
			}
			++hashVal; // go to next cell
			hashVal %= arraySize; // wraparound if necessary
		}
		return null; // can't find item
	}

	public int getSize() {
		return dataSize;
	}

	public int getCapacity() {
		return arraySize;
	}

	public Iterator keyIterator(){
		return new SimpleIterator();
	}
	/**
	 * Hashtable内部存储数据对象
	 * @author chenxin
	 */
	class DataItem {
		Object data; // array holds hash table
		int key;
		DataItem(int pKey, Object pData) {
			data = pData;
			key = pKey;
		}
		Object getData() {
			return data;
		}
		int getKey() {
			return key;
		}
	}
	class SimpleIterator implements Iterator {
		int postion = 0;
		DataItem next = null;
		DataItem current = null;
		public SimpleIterator() {
			for (int i = 0; i < hashArray.length; i++) {
				if (hashArray[i] != null &&  next==null) {
					next = hashArray[i];
					current =next;
					postion=i;
					break;
				}
			}
		}
		public boolean hasNext() {
			return next != null;
		}
		public Object next() {
			if(postion>=hashArray.length || next==null){
				return null;
			}
			current = next ;
			postion++;
			while(postion<=(hashArray.length-1) && hashArray[postion]==null ){
				postion++;
			}
			if(postion<hashArray.length){
				next = hashArray[postion];
			}else{
				next=null;
			}
			return new Integer(current.key);
		}

		public void remove() {
			if (current != null) {
				SimpleHashtable.this.delete(current.key);
			}
		}
	}
	
	/*class SimpleIterator implements Iterator {
		int postion = 0;
		List list = new LinkedList();
		DataItem next = null;
		DataItem current = null;
		public SimpleIterator() {
			for (int i = 0; i < hashArray.length; i++) {
				if (hashArray[i] != null) {
					list.add((hashArray[i]));
				}
			}
			if (list.size() > 0) {
				next = (DataItem) list.get(0);
				current =next;
			}
		}
		public boolean hasNext() {
			return next != null;
		}
		public Object next() {
			if(postion>=list.size()){
				return null;
			}
			current = next ;
			if((++postion)<list.size()){
				next = (DataItem)list.get(postion);
			}else{
				next=null;
			}
			return new Integer(current.key);
		}

		public void remove() {
			if (current != null) {
				SimpleHashtable.this.delete(current.key);
			}
		}
	}*/
	
	
	public void clear(){
		
		for (int j = 0; j < arraySize; j++) {
			if (hashArray[j] != null)
				hashArray[j]=null;
		}
		
		dataSize=0;
		
	}
	
	
	
	
	/**
	 * 测试
	 * @param args
	 * @throws Exception
	 */
	public static void main(String[] args)throws Exception{
		SimpleHashtable sh = new SimpleHashtable(11);
		System.out.println(sh.getSize());
		sh.put(100,"100");
		sh.put(101,"101");
		sh.put(104,"104");
		sh.put(107,"107");
		
		Iterator key  = sh.keyIterator();
		while(key.hasNext()){
			Integer i =(Integer)key.next();
			key.remove();
			System.out.println(i);
		}
		System.out.println(sh.getSize());
	}
}