hashtable.java

java 实现常用数据结构（链表

/**
 *
 *
 *
 */
 
 package dreamer.util;
 
 public class HashTable<T>
 {
 	private final int INIT_SIZE = 2047;
 	private HashNode [] table;
 	private int size;
 	private int length;
 	
 	class HashNode<T>
 	{
 		private T data;
 		private String key;
 		private HashNode next;
 	}
 
 	public HashTable()
 	{
 		table = new HashNode[INIT_SIZE];
 		size = INIT_SIZE;
 		for(int i=0;i<size;i++)
 		{
 			table[i] = new HashNode();
 		} 		
 		length = 0;
 	}
 	
 	private int hash(String key)
 	{
 		char [] chars = key.toCharArray();
 		int addr = 0;
 		for(char ch:chars)
 		{
 			addr = addr<<3;
 			addr = addr+ch;
 		}
 		return addr%size;
 	}
 	
 	public boolean put(String key,T elem)
 	{
 		if(key==null)
 			return false;
 		int addr = hash(key);
 		HashNode head = table[addr];
 		HashNode node = new HashNode();
 		node.key = key;
 		node.data = elem;
 		if(head.next==null)
 		{
 			head.next = node;
 			length++;
 			return true;
 		}
 		HashNode cursor = head.next;
 		while(cursor!=null)
 		{
 			if(cursor.key.equals(key))
 				return false;
 			cursor = cursor.next;
 		}
 		cursor = node;
 		return true;
 	}
 	
 	public T remove(String key)
 	{
 		if(key==null)
 			return null;
 		int addr = hash(key);
 		HashNode previous = table[addr];
 		HashNode cursor = table[addr].next;
 		while(cursor!=null)
 		{
 			if(cursor.key.equals(key))
 			{
 				T elem = (T)cursor.data;
 				previous.next = cursor.next;
 				length--;
 				return elem;
 			}
 			previous = cursor;
 			cursor = cursor.next;
 		}	
 		return null;
 	}
 	
 	public T get(String key)
 	{
 		if(key==null)
 			return null;
 		int addr = hash(key);
 		HashNode cursor = table[addr].next;
 		while(cursor!=null)
 		{
 			if(cursor.key.equals(key))
 				return (T)cursor.data;
 			cursor = cursor.next;
 		}
 		return null;
 	}
 	
 	public boolean set(String key, T value)
 	{
 		if(key==null)
 			return false;
 		int addr = hash(key);
 		HashNode cursor = table[addr].next;
 		while(cursor!=null)
 		{
 			if(cursor.key.equals(key))
 			{
 				cursor.data = value;
 				return true;
 			}
 			cursor = cursor.next;
 		}
 		return false;
 	}
 	
 	public boolean contains(T elem)
 	{
 		for(int i=0;i<size;i++)
 		{
 			HashNode cursor = table[i].next;
 			while(cursor!=null)
 			{
 				if(cursor.data.equals(elem))
 					return true;
 				cursor = cursor.next;
 			}
 		}
 		return false;
 	}
 	
 	public boolean containskey(String key)
 	{
 		if(key==null)
 			return false;
 		int addr = hash(key);
 		HashNode cursor = table[addr].next;
 		while(cursor!=null)
 		{
 			if(cursor.key.equals(key))
 				return true;
 			cursor = cursor.next;
 		}
 		return false;
 	}
 
 	public Set keySet()
 	{
 		if(length==0)
 			return null;
 		Set keys = new ArraySet<String>();
 		for(int i=0;i<size;i++)
 		{
 			HashNode cursor = table[i].next;
 			while(cursor!=null)
 			{
 				keys.add(cursor.key);
 				cursor = cursor.next;
 			}
 		}
 		return keys;
 	}
 	
 	public Object [] toArray()
 	{
 		if(length==0)
 			return null;
 		Object [] elements = new Object[length];
 		int i = -1;
 		for(int j=0;j<size;j++)
 		{
 			HashNode cursor = table[j].next;
 			while(cursor!=null)
 			{
 				i++;
 				elements[i] = cursor.data; 				
 				cursor = cursor.next;
 			}
 			continue;
 		}
 		return elements;
 	}
 	
 	public boolean isEmpty()
 	{
 		if(length==0)
 			return true;
 		return false;
 	}
 	
 	public int size()
 	{
 		return length;
 	}
 
    public void clear()
    {
    	table = new HashNode[INIT_SIZE];
 		size = INIT_SIZE;
 		for(int i=0;i<size;i++)
 		{
 			table[i] = new HashNode();
 		} 		
 		length = 0;
    }
 }