首页 > 代码库 > 容器深入研究 --- 散列与散列码(三)

容器深入研究 --- 散列与散列码(三)

如何覆盖hashCode():

明白了如何散列之后,编写自己的hashCode()就更有意义了。

首先,你无法控制bucket数组的下标值的产生。这个值依赖于具体的HashMap对象的容量,而容量的改变与容器的充满程度和负载因子有关。hashCode()生成的结果,经过处理后称为桶位的下标。

设计hashCode()时最重要的因素就是:无论何时,对同一个对象调用hashCode()都应该产生同样的值。如果在将一个对象用put()添加进HashMap时产生一个hashCode()值,而用get()去除时却产生了另外一个hashCode()值,那么就无法重新取得该对象了(也会造成内存泄露)。

所以,如果你的hashCode()方法依赖于对象中易变的数据,用户就要当心了,因为数据发生变化时,hashCode()就会生成一个不同的散列码,相当于产生了一个不同的键。

此外,也不应该使hashCode()依赖于具有唯一性的对象信息,尤其是使用this的值,这只能产生很糟糕的hashCode()。因为这样做无法生成一个新的键,使之与put()中原始的键值对中的键相同。

下面以String类为例。String有个特点:如果程序中有多个String对象,都包含相同的字符串序列,那么这些String对象都映射到同一块内存区域。所以new String("hello");生成的两个实例,虽然是相互独立的,但是对它们使用hashCode()应该生成同样的结果。

public static void main(String[] args) {
		String[] hellos = "Hello Hello".split(" ");
		System.out.println(hellos[0].hashCode());
		System.out.println(hellos[1].hashCode());
		//69609650
		//69609650
}

对于String而言,hashCode()明显是基于String内容的。

因此,要想使hashCode()实用,它必须速度快,并且必须有意义。也就是说必须基于对象的内容生成散列码。记得吗,散列码不必是独一无二的(应该更关注生成速度,而不是一致性),但是通过hashCode()和equals(),必须能够完全确定对象的身份。

因为在生成桶的下标前,hashCode()还需要做进一步的处理,所以散列码的生成范围并不重要,只要是int即可。

还有另一个因素影响:好的hashCode()应该产生均匀分布的散列码。如果散列码都集中在一块,那么HashMap或者HashSet在某些区域的负载会很重,这样就不如分布均匀的散列函数快。

写出一个像样的hashCode()的基本指导:

1,给int变量result赋予某个非零值常量。

2,为对象内每个意义的域f计算出一个int散列码c。

* -------------------------------------------------------------
 * 域类型		计算
 * boolean		c = (f ? 0 : 1 );
 * byte/char/short/int c = (int)f;
 * long 		c = (int)(f ^ f>>>32)
 * float 		c = Float.floatToInBits(f);
 * double		long l = Double.doubleToLongBits(f); c = (int)(l ^ (l>>>32));
 * Object		c = f.hashCode();
 * 数组			对每个元素应用应用以上规则

3,合并计算得到的散列码:result = 37 * result + c;

4,返回result

5,检查hashCode()最后生成的结果,确保相同的对象有相同的散列码。

例如:

public int hashCode() {
	int reuslt = 17;
	result = 37 * result + s.hashCode();
	result = 37 * result + (int)id;
	return result;
}