散列表分离链接法

/*
 *分离链接散列表类架构
 */
 public class SeparateChainingHashTable<AnyType>{
	 private static final int DEFAULT_TABLE_SIZE=101;
	 private List<AnyType>[] theLists;
	 private int currentSize;
	 public SeparateChainingHashTable(){
		 this.SeparateChainingHashTable(DEFAULT_TABLE_SIZE);
	 }
	 public SeparateChainingHashTable(Int size){
		 theLists=new LinkedList[nextPrime(theLists.length)];
		 for(int i=0;i<theLists.length;i++){
			 theLists[i]=new LinkedList<AnyType>();
		 }
	 }
	 /*
	  *插入元素
	  * @param x is the item to insert
	  */
	 public void insert(AnyType x){
		 List<AnyType> list=theLists[myhash(x)];
		 if(!list.contains(x)){
			 list.add(x);
		 
		 if(++curentSize>theLists.length){
			 rehash();
		 }	
		 }		 
	 }
	 /*
	  * @param x is the item to remove
	  */
	 public void remove(AnyType x){
		 List<AnyType> list=theLists[myhash(x)];
		 if(list.contains(x){
			 list.remove(x);
			 currentSize--;
		 }
	 }
	 public boolean contains(AnyType x){
		 List<AnyType> list=theLists[myhash(x)];
		 return list.contains(x);
	 }
	 public void makeEmpty(){
		 for(int i=0;i<theLists.length;i++){
			 theLists[i].clear();
		 }
		 curentSize=0;
	 }
	 /*
	  * 散列
	  * @return hash值
	  */
	 private int myhash(AnyType x){
		 int hashVal=x.hashCode();//应当是关键字求值
		 hashVal%=theLists.length;
		 if(hashVal<0){
			 hashVal+=theLists.length;
		 }
		 return hashVal;
	 }
	 /*
	  *分离链接散列法再散列
	  */
	 private void rehash(){
		 List<AnyType>[]oldLists=theLists;
		 theLists=new List<AnyType>[nextPrime(2*oldLists.length)];
		 for(int j=0;j<oldLists.length;j++){
			 theLists[i]=new ArrayList<AnyType>();
		 }
		 currentSize=0;
		 for(int i=0;i<oldLists.length;i++){
			 for(int j=0;j<oldLists[i].size;j++){
				 insert(oldLists[i].get(j))
			 }
		 }
	 }
	 private static int nextPrime(int n){
		 while(!isPrime(n)){
			 ++n;
		 }
		 return n;
	 }
	 private static boolean isPrime(int n){
		 for(int i=2;i<sqrt(n);i++){
			 int k=n%i;
			 if(k==0){
				 return false;
			 }
		 }
		 return true;
	 }
 }