public class HashTable{
   private String[] name;    //關鍵字
   private int sum;    //容量
   public static void main(String[] args){    //測試
        HashTable ht = new HashTable();
        ht.add("chenhaitao");
        ht.add("zhongcheng");
        ht.add("baiyudong");
        ht.add("huangshiyao");
        ht.add("djflkd");
        ht.add("gg");
        System.out.println(ht.contains("baiyudong"));
        ht.remove("huangshiyao");
        System.out.println(ht.contains("huangshiyao"));
        ht.print();
   }
  public HashTable(){             //初始化，初始容量是10個
      name = new String[10];
      sum = 0;
  }
  public int hash1(String s){                                       //哈希函數
        return Math.abs(s.hashCode())%name.length;
  }
  public int hash2(String s){                                     //處理沖突的哈希函數
      int result = Math.abs(s.hashCode())%(name.length-1);
      System.out.println(s+"--"+result);
      if(result%2==0){
          return result + 1;
      }
   return result;
  }
  public boolean contains(String s){                  //哈希表里面是否包含字符串s
      int start = hash1(s);
      int i = start;
      while (name[i] != null){
           if(name[i].equals(s)){
               return true;
           }
        i = (i + hash2(s))%name.length;
        if(i == start){
             return false;
        }
      }
   return false;
  }
  public void add(String s){
       if(sum>=name.length/2){
            this.rehash();
       }
      int start = hash1(s);
      int i = start;
     while(name[i] != null){
         if(s.equals(name[i])){
              return;
         }
       i = (i + hash2(s))%name.length;
      if(i == start){
          return;
       }
     }
    name[i] = s;
    sum ++;
  }
   public void rehash(){                              //擴建一個哈希表為原表的兩倍，把原來的哈希表添加到新表中
       HashTable ht = new HashTable();
       ht.name = new String[this.name.length * 2];
       for(int i = 0; i < this.name.length; i ++){
               if((this.name[i] != null)){
                   ht.add(this.name[i]);
              }
       }
     this.name = ht.name;
     this.sum = ht.sum;
   }
  public void remove(String s){                     //刪除某個元素
         if(this.contains(s)){
              int i = this.getValue(s);
              this.name[i] = null;
         }
  }
  public int getValue(String s){                //得到s在哈希表中的位置
    int start = this.hash1(s);
    int i = start;
    while(this.name[i] != null){
       if(this.name[i].equals(s)){
           return i;
       }
     i = (i + this.hash2(s))%this.name.length;
    if(i == start){
      return -1;
     }
   }
  return -1;
  }
  public void print(){                       //輸出哈希表中所有元素
     for(int i = 0; i < name.length; i ++){
        System.out.println(i+":"+name[i]);
    }
  }
public int size(){          //哈希表存儲元素的個數
   return this.sum;
 }
public int length(){            //哈希表的長度
    return this.name.length;
 }
}