By

文章目录

一个很常见的错误源于没有改写hashCode方法。在每个改写了equals方法的类中，你必须也要改写hashCode方法。如果不这样做到话，就会违反Object.hashCode的通用约定，从而导致该类无法与所有基于散列值(hash)的集合类结合在一起正常运作，这样的集合类包括hashMap、HashSet和Hashtable。

下面是hashcode约定的内容，来自java.lang.Object的规范:

  • 在一个应用程序执行期间，如果一个对象的equals方法比较所用到的信息没有被修改的话，那么，对该对象调用hashCode方法多次，它必须始终如一地返回一个整数。在同一个应用程序的多次执行过程中，这个整数可以不同，即这个应用程序这次执行返回的整数与下一次执行返回的整数可以不一致。

  • 如果两个对象根据equals(Object)方法是相等的，那么调用这两个对象中任意一个对象的hashCode方法必须产生同样的整数结果。

  • 如果两个对象根据equals(Object)方法是不相等的，那么调用这两个对象中任意一个对象的hashCode方法，不要求必须产生不同的整数结果。然而，程序员应该意识到这样的事实，对于不相等的对象产生截然不同的整数结果，有可能提高散列表的性能。

因为没有改写hashCode而违反的关键约定是第二条:相等的对象必须有相等的hash code。根据一个类的equals方法，两个截然不同的实例有可能在逻辑上是相等的，但是，根据Object类的hashCode方法，它们仅仅是两个对象，没有其他共同的地方。因此，对象hashCode方法返回两个看起来是随机的整数，而不是根据第二个约定要求的那样，返回两个相等的整数。

例如，考虑下面极为简单的PhoneNumber类

public final class PhoneNumber {
	private final short areaCode;
	private final short exchange;
	private final short extension;

	private static void rangeCheck(int arg, int max, String name) {
		if (arg < 0 || arg > max)
			throw new IllegalArgumentException(name + ":" + arg);
	}

	public PhoneNumber(int areaCode, int exchange, int extension) {
		rangeCheck(areaCode, 999, "area code");
		rangeCheck(exchange, 999, "exchange");
		rangeCheck(extension, 9999, "extension");
		this.areaCode = (short) areaCode;
		this.exchange = (short) exchange;
		this.extension = (short) extension;
	}

	public boolean equals(Object o) {
		if (o == this)
			return true;
		if (!(o instanceof PhoneNumber))
			return false;
		PhoneNumber pn = (PhoneNumber) o;
		return pn.extension == extension && pn.exchange == exchange
				&& pn.areaCode == areaCode;
	}
}

假设你企图将这个类与HashMap一起使用：

Map m = new HashMap();
m.put(new PhoneNumber(408,867,5309),"Jenny");

这时候，你可能会期望m.get(new PhoneNumber(408,867,5309))会返回”Jenny”，但是它实际上返回null。注意，这里涉及到两个PhoneNumber实例:第一个被用于插入到HashMap中，第二个实例与第一个相等，被用于检索。由于PhoneNumber类没有改写hashCode方法，从而导致两个相等的实例具有不相等的散列码,违反了hashCode的约定。因此，put方法把Jenny的电话号码对象存放在以散列桶中，而get方法会在另一个散列通中查找她的电话号码对象。要想修正这个问题非常简单，只需为PhoneNumber类提供一个适当的hashCode方法即可。
编写一个合法但并不好用的hashcode方法没有任何价值，例如下面这个方法合法但永远不应该被正式使用:

public int hashCode(){return 42;}

上面这个hashCode方法是合法的，因为相等的对象总是有同样的散列码。但它也极为恶劣，因为它使得每一个对象都具有同样的散列码。因此，每个对象都被映射到同一个散列桶中，从而散列表被退化为链表(linked list)。它使得本该线性时间运行的程序变成了平方运行时间，对于规模很大的散列表而言，这关系到列表能否正常工作。

一个好的散列函数通常倾向于”为不相等的对象产生不相等的散列码”。这正是hashCode约定中第三条的含义。理想情况下，一个散列函数应该把一个集合中不相等的实例均匀地分布到所有可能的散列值上。要想完全达到这种理想的情形是非常困难的，幸运的是，相对于这种理想情形并不太困难。下面给出一种简单的”处方“:
1.把某个非零常数值，保存在一个叫result的int类型的变量中。

2.对于对象中每一个关键域f，完成以下步骤:

a.为该域计算int类型的散列码c:

i.如果该域是boolean类型，则计算(f?0:1)。

ii.如果该域是byte、char、short或int类型，则计算(int)f。

iii.如果该域是long类型，则计算(int)(f^(f>>32))。

iv.如果该域是float类型，则计算Float.floatToIntBits(f)。

v.如果该域是double类型，则计算Double.doubleToLongBits(f)得到一个long类型的值，然后按照步骤,2.a.iii，对该long型值计算散列值。

vi.如果该域是一个对象引用，并且该类的equals方法通过递归调用equals的方式来比较这个域，则同样对这个域递归调用hashCode。如果要求一个更为复杂的比较，则为这个域计算一个”规范表示”，然后针对这个范式表示调用hashCode。如果这个域的值为null，则返回0

vii.如果该域是一个数组，则把每一个元素当做单独的域来处理。也就是说，递归地应用上述规则，对每个重要的元素计算一个散列码，然后根据步骤2.b中的做法把这些散列值组合起来。

b.按照下面的公式，把步骤a中计算得到的散列码c组合到result中:

result = 37*result+c;

3.返回result。
4.写完了hashCode方法之后，问自己”是否相等的实例具有相等的散列码”。如果不是的话，找出原因，并修正错误。

在散列码的计算过程中，把冗余域排除在外是可以接受的。换句话说，如果一个域的值可以根据参与计算的其他域值计算出来，则把这样的与排除在外是可以接受的。对于在相等比较计算中没有被用到的任何域，你要把它们排除在外，这是一个要求。如果不这样做的话，可能会导致违反hashCode约定的第二条。

上面步骤1中用到了一个非零的初始值，对于步骤2.a中计算的散列值为0的那些初始域，它们会影响到散列值。如果步骤1中的初始值为0，则整个散列值将不受这些初始域的影响，从而会增加冲突的可能性。值17是任选的。

步骤2.b中的乘法部分使得散列值依赖于域的顺序，如果一个类包含多个相似的域，那么这样的乘法运算会产生一个更好的散列函数。例如，如果String类也根据上面的步骤来建立散列函数，并且把乘法部分省去，则那些仅仅是字母顺序不同的所有字符串，都会有同样的散列码。之所以选择37，是因为它是一个奇素数。如果乘数是偶数，并且乘法溢出的话，则信息会丢失，因为与2相乘等价于移位运算，使用素数的好处并不是很明显，但是习惯上使用素数来计算散列结果。
现在我们把这种方法用到PhoneNumber类中，它有三个关键域，都是short类型。根据上面的步骤，很直接地会得到下面的散列函数:

public int hashCode()
{
    int result = 17;
    result = 37 * result + areaCode;
    result = 37 * result + exchange;
    result = 37 * result + extension;
    return result;
}

因为这个方法返回结果是一个简单的、确定的计算结果，它的输入只是PhoneNumber实例中的三个关键域，所以，很清楚，相等的PhoneNumber会有相等的散列码。实际上，对于PhoneNumber的hashcode实现而言，上面这个方法是非常合理的，等同于Java平台库1.4版本中的实现。它的做法非常简单，速度也非常快，恰当地把不相等的电话号码分散到不同的散列桶中。

如果一个类是非可变的，并且计算散列码的代价也比较大，那么你应该考虑把散列码缓存在对象内部，而不是每次请求的时候都重新计算散列码。如果你觉得这种类型的大多数对象会被用做散列键，那么你应该在实例被创建的时候就计算散列码。否则的话，你可以选择“迟缓初始化”散列码，一直到hashCode被第一次调用的时候才初始化。现在尚不清楚我们的PhoneNumber类是否值得这样处理，但可以通过它来说明这种方法如何实现:

private volatile int hashCode = 0;
public int hashCode()
{
    if(hashCode == 0)
    {
        int result = 17;
        result = 37 * result + areaCode;
        result = 37 * result + exchange;
        result = 37 * result + extension;
        hashCode = result;
    }
    return hashCode;

}

虽然本条目中前面给出的hashCode实现方法能够获得相对比较好的散列函数，但是它并不能产生最新的散列函数。不要试图从散列码计算中排除掉一个对象的关键部分以提高性能。虽然这样得到的散列函数运行起来可能非常快，但是它的效果不见得会好，可能会导致散列表慢的根本不可用。特别是在实践中，散列函数可能会面临大量的实例，而且，在你选择可以忽略掉的区域之中，这些实例仍然区别非常大。如果这样的话，散列函数会把所有这些实例映射到非常少量的散列码上，基于散列的集合将会表现出平方级的性能指标。

Java性能优化
文章目录