Java中的散列表
程序员文章站
2022-07-15 14:21:24
...
任何Java对象都有一个继承自Object类的hashcode()方法用来返回这个对象对应的散列值。
散列值最常见的使用是会被用来在散列表中查找索引值的用到。
不同索引值在节点会处在不同的散列表的不同节点上;相同散列值的节点以一个单向链表相连。
查找过程大致如下:
int hashcode = key.hashCode();
int index = (hashcode & 0x7FFFFFFF) % hashMap.length;
for(Entry e = hashMap[index]; e != null ; e = e.next){
if((e.hashCode()==hashcode) && key.equals(e.key))
return e.value;
}
return null;
从中可以看到,如果散列值和键都相等,则键对应的值就会被返回。如果我们有一个自定义的类,类的hashCode()方法和equals()方法设计的不好,可能会有不期望的结果返回,例如我们有一个以下的类:
public class Personal {
private int age;
private String name;
private String national;
public Personal(int age, String name, String national) {
super();
this.age = age;
this.name = name;
this.national = national;
}
public int hashCode() {
return age | name.hashCode();
}
public int getAge() {
return age;
}
public String getName() {
return name;
}
public String getNational() {
return national;
}
public boolean equals(Object obj) {
if(this == obj) return true;
if (obj instanceof Personal) {
return age == ((Personal) obj).age
&& name.equals(((Personal) obj).name);
}
return false;
}
}
有以下测试类:
public class HashcodeTest {
public static void main(String[] args) {
Map<Personal, String> map = new HashMap<Personal, String>();
Personal model1 = new Personal(32, "name", "China");
Personal model2 = new Personal(32, "name", "USA");
map.put(model2, "USA");
map.put(model1, "China");
System.out.println(map.get(model2));
System.out.println(map.get(model1));
}
}
我这里看到运行结果为:
China
China
我们期望的是:
USA
China
之所以会出现这种情况,就是因为我们的hashCode()和equals()方法设计的不好,只考虑了age和name的信息。如果把national的信息也加上,这个问题就容易解决了。可以修改hashCode()方法加上national.hashCode(),也可以修改equals()方法,加上national的信息;或者两者都修改。不过建议在hashCode()方法和equals()方法里使用的变量保持一致或是其子集
上一篇: shellcode分段执行