在每个覆盖equals方法的类中,也必须覆盖hashCode方法。如果不这样做,就违反了Object.hasCode的通用约定,从而导致该类无法结合所有基于散列的集合一起正常运行,这样的集合包括HashMap、HashSet和HashTable。
下面的约定内容,摘自Object规范
在应用程序的执行期间,只要对象的equals方法的比较操作所用到的信息没有被修改,那么对这同一对象调用多次,hashCode方法都必须始终如一地返回同一个正数。在同一个应用程序的多次执行过程中,每次执行所返回的整数可以不一致。
如果两个对象根据equals(Object)方法比较是相等的,那么调用这两个对象中任意一个对象的hashCode方法都必须产生同样的整数结果。
如果两个对象根据equals(Object)方法比较是不相等的,那么调用这两个对象中任意一个对象的hashCode方法,则不一定要产生不同的整数结果。但是程序员应该知道,给不相等的对象产生截然不同的整数结果,有可能提高散列表(hash table)的性能。
public final class PhoneNumber { private final short areaCode; private final short prefix; private final short lineNumber; public PhoneNumber (int areaCode,int prefix,int lineNumber) { this.areaCode=(short)areaCode; this.prefix=(short)prefix; this.lineNumber=(short)lineNumber; } private static void rangeCheck( int arg,int max,String name){ if( arg < 0 || arg > max ){ throw new IllegalArgumentException(name+": "+arg); } } @Override public boolean equals(Object obj) { if (obj == this) return true; if(!(obj instanceof PhoneNumber)) return false; PhoneNumber pn= (PhoneNumber) obj; return pn.lineNumber == this.lineNumber && pn.prefix==this.prefix && pn.areaCode ==this.areaCode } }
将这个类与HashMap一起使用
public class PhoneNumberTest extends TestCase { public void testPhoneNumber(){ Map<PhoneNumber,String> map=new HashMap<PhoneNumber, String>(); map.put(new PhoneNumber(707,867,5309),"Jenny"); System.out.println(map.get(new PhoneNumber(707,867,5309))); } }这个时候,可能希望能够输出"Jenny",但事实是范围一个null。
导致这个错误的原因是PhoneNumber类没有覆盖hashCode方法,从而导致两个相等的实例具有不相等的散列码,违反了hashCode的约定。因此put方法把数据存到了一个散列桶中(Hash bucket)而get方法却从另一个散列桶中取出,那么必定返回null值了。
其实修改这个错误很简单,只需要在PhoneNumber中覆盖hashCode方法即可
@Override public int hashCode() { return 42; }
这个代码总是合法的,但是永远都不应该被正式使用。
因为它确保了相等的对象总是具有相同的散列码,但是,每个对象的散列码都是同样的散列码。每个对象都被映射到同一个散列桶(Hash Bucket)中,使得散列表退化成了链表(Linked list)。它使得本该线性时间运行的程序变成了平方时间运行。对于规模很大的散列表而言,这会关系到散列表能否正常运行。
理想的情况下,散列函数应该把集合中不相等的实例均匀地分布到所有可能的散列值上。要想完全达到这种理想的情形是非常困难的,但是接近理想状态还是有办法的。
1.把某个非零的常数值,比如说17,保存在一个名为result的int类型的变量中。
2.对于对象中每个关键域f(指equals方法中涉及的每个域),完成以下步骤:
a.为该域计算int类型的散列码c:
i. 如果该域是boolean类型,则计算(f?1:0)
ii.如果该域是byte、char、short或者int类型,则计算(int)f。
iii. 如果该域是long,则计算(int)(f^(f>>32))。
iv.如果该域是flaot,则计算Float.floatToLongBits(f)。
v.如果该域是double,则计算Double.doubleToLongBits(f),然后按照步骤iii,为得到的long类型值计算散列值。
vi.如果该域是一个对象引用,并且该类的equals方法通过递归地调用equals的方式来比较这个域,则同样为这个域递归地调用hashCode。如果需要更复杂的比较,则为这个域计算一个“范式(canonical representation)”,然后针对这个范式调用hashCode。如果这个域的值为null,则返回0(或者其他某个常数,但通常是0)。
vii.如果该域是一个数组,则要把每一个元素当做单独的域来处理。也就是说,递归地应用上述规则,对每个重要的元素计算一个散列码,然后根据步骤2.b中的做法把这些散列值组合起来。如果数组域中的每个元素都很重要,可以利用发行版本1.5中增加的Arrays.hashCode方法。
b.按照下面的公式,把步骤2.a中计算得到的散列码c合并到result中
result = 31 * result +c
3.返回result
4.编写单元测试来验证hashCode方法。
提示:
计算散列码的过程,可以把冗余域排除在外(域的值可以根据参与计算的其他域值计算出来)。必须排除equals比较计算没有用到的任何域。否则很可能违反hashCode约定的第二条。
现在把PhoneNumber的hashCode方法根据上述规则修改一下。
@Override public int hashCode() { int result=17; result=31*result+areaCode; result=31*result+prefix; result=31*result+lineNumber; return result; }这样就可以将不相等的电话号码分散到不同的散列桶中。
如果一个类是不可变的,并且计算散列码的开销也较大,就应该考虑把散列码缓存在对象内部,而不是每次请求的时候都重新计算散列码。如果你觉得这种类型的大多数对象会被用作散列键(hash keys),就应该在创建实例的时候计算散列码。否则,可以选择“延迟初始化(lazily initialize)”散列码,一直到hashCode被第一次调用的时候才初始化。我们可以这样修改一下PhoneNumber(在这里不一定是必须的,为了试验)。
public final class PhoneNumber { private volatile int result; @Override public int hashCode() { if (result == 0) { result = 17; result = 31 * result + areaCode; result = 31 * result + prefix; result = 31 * result + lineNumber; } return result; } }
不要试图从散列码计算中排除掉一个对象的关键部分来提高性能。虽然这样得到的散列函数运行起来可能更快,但是它的效果不见得好,可能会导致散列表慢到根本无法使用。