Java中的散列表

任何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()方法里使用的变量保持一致或是其子集

评论

1 楼 柚子叔叔 2011-08-17  

文章一般