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;
 }
}