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