java hashtable实现代码
程序员文章站
2024-02-12 22:04:22
复制代码 代码如下:public class hashtable{ private string[] name; ...
复制代码 代码如下:
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;
}
}
上一篇: iOS开发笔记--详解UILabel的相关属性设置
下一篇: java登录验证码实现代码