public class HashTable{
private String[] name; //The keyword
private int sum; //capacity
public static void main(String[] args){ //test
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(){ // Initialization, initialization capacity is 10 a
name = new String[10];
sum = 0;
}
public int hash1(String s){ //The hash function
return Math.abs(s.hashCode())%name.length;
}
public int hash2(String s){ // conflict-handling The hash function
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){ //Does the hash table contain the string 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(){ //Expand a hash table to double the original table and add the original hash table to the new table
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){ //Delete an element
if(this.contains(s)){
int i = this.getValue(s);
this.name[i] = null;
}
}
public int getValue(String s){ //I get the position of s in the hash table
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(){ //Output all elements in the hash table
for(int i = 0; i < name.length; i ++){
System.out.println(i+":"+name[i]);
}
}
public int size(){ //The hash table stores the number of elements
return this.sum;
}
public int length(){ //The length of the hash table
return this.name.length;
}
}