/*
*分離連結散清單類架構
*/
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;
}
}