【第8条】改写equals时总是要改写hashCode

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

    可能有人会问：什么是hash？它是干什么用的？

    的确，一开始我也没有在意到hashCode。翻了一下底层API的代码，我自己的类确实也犯了这个错误，而且还发现其他项目组的API也是。那个项目是从Java1.0版本就做起的，直到现在使用的是1.5，但是他们说了：我们改写了equals的类只是一些JavaBean，他们很少有机会（不太严谨的说是从不会）被放到HashMap、HashSet、Hashtable中，就更不会放进去而且还当Key用了。

    那么，还是回答一下刚才的问题吧，什么是hash？它是干什么用的？如果违反了此条到底在什么情况下，会有怎样的后果？

    hash是一个散列值，或者叫“杂乱编码”，对一个对象做hashCode()运算，简单地说就是给这个对象算出一个无规则的ID。我们知道，数组的优势在于遍历，而HashMap等的优势在于快速查找。当我们在HashMap中放入了一些Key-Vaule的值对后，可以通过Key值很快地检索出它所对应的Value（很像对数据库表的查询），关键的是这个检索的时间耗费是固定的（严谨地说应该是与容量无关的），而非与内容多少线性的。很明显它不是像数组一样循环遍历、比较来做查找的，而是直达目标。那么它是如何做到的呢？

    这里再多啰嗦几句，HashMap的原理：当你初始化一个HashMap时，系统会预先开创一些空间用于放置将要被放入的对象，之后随着对象的放入，当容量不够用的时候就将容积扩倍。但是，什么时候叫“不够用”呢？并不是现有的“格子”都被放满了，而是75%（这个百分比叫loadFactor，Java用的是0.75，其它系统可能不一样，微软好像是0.72）。这是为什么呢？其实这个百分比是可以自己指定的，但是如果没有特别的情况，建议你不要这么做，相信很多数学专家已经经过大量的计算和论证才选用的0.75这个值的。再多说一句，其实所谓“扩倍”也是不严格的说法，各个系统在选择容量上都有自己的策略，比如Java是不小于扩倍数的一个奇数，而微软好像是用质数。再有就是容量的初始值各系统也不相同，Java是11。

    当一个Key-Value值对被put进来时，首先计算Key的hashCode，然后对容量取余，这个余数就是这个值对将要被存放的位置。get的时候，也是首先对Key算hashCode，然后对容量取余数，之后直接到余数的位置就找的目标了（那么如果在set和get之间，这个HashMap扩容过，那么该如何呢？这就不在这里详细讨论了）。这就是为什么检索的时间耗费是与容量无关的了。但是，两个不同的对象也可能具有相同的hashCode，或者两个具有不同hashCode的对象恰巧它们的HashCode之差是容量的整数倍，这样都会导致它们得到的余数是相同的，就又怎么办呢？HashMap会在每个位置上其实都是一个链表，如果有两个以上的对象落在了相同的位置上，那么就让链表上第一个元素的next指向下一个元素即可（如果某位置上仅有一个元素，那它的next就是null），这就是为什么严谨地说不能是“时间耗费是固定的”，在链表上查找还是需要时间一个一个的遍历比较的。现在我们知道了吧，即使约定并不要求通过equals方法判断是不相等的两个对象的hashCode也一定不能相同，但是最好还是让他们不同的好。如果这样一个hashCode()算法：

 

public int hashCode(){ 
    return 42; 
}

 
    虽然不是错误的，也满足约定，但它是从来不该出现的，如果采用这样的hashCode()方法的类的对象被装入HashMap的话，它们的位置会都在一处，也就是成了一个链表了。
   
    现在知道了为什么一定要改写hashCode，该将如何改写了。书上又给出了一个“处方”：
    1）int result = 17;
    2）对每个关键域（我觉得就是那些影响equals的域）如下处理：
      2.1）int c; 并根据该域的类型：
       2.1.1）如果该域f是boolean型，c = (f ? 0 : 1);
       2.1.2）如果该域f是byte、char、short、int型，c = (int)f;
       2.1.3）如果该域f是long型，c = (f ^ (f >>> 32));
       2.1.4）如果该域f是float型，c = Float.floatToIntBits(f);
       2.1.5）如果该域f是double型，c = (int)Double.doubleToLongBits(f);
       2.1.6）如果该域f是一个对象，c = f.hashCode();
       2.1.7）如果该域f是一个数组，遍历数组的每个元素，并按2.2）中的做法吧这些散列值组合起来;
      2.2）result = 37 * result + c
    3）return result
   
    例子：
    我们还是看在【第1条】出现的那个复数的例子，如果该类没有改写hashCode方法，不能满足Object的规范：
    如果两个对象根据equals(Object)方法是相等的，那么调用其中任一个对象的hashCode方法必须产生同样的整数结果。
    则会出现这样的尴尬：

    Complex c1 = new Complex(15.5,10.2);
    Map hm = new HashMap();
    hm.put(c1, "c1");

      

    之后如果你想检查某一个用户输入的复数，是否在这个HashMap中，而恰巧用户输入的re和im值正好是15.5和10.2

    String cName = hm.get(new Complex(re, im));  //返回null

 

    却返回的是null，而并非所设想的"c1"。原因就是两次new Complex(15.5,10.2)的hashCode不是同一个整数。虽然在这个例子中，可以通过两次都用 Complex.valueOf(15.5,10.2) 来代替 new Complex(15.5,10.2)，或者将Complex类做成非可变类，从而得到正确的结果（为什么？如果不清楚，请看【第1条】和【第13条】），但这个例子还是要告诉你改写hashCode的必要性。
   
    那么Complex类的hashCode方法按照“处方”应该写成这样：

    public int hashCode(){
      int result = 17;
      result = 37 * result + Float.floatToIntBits(this.re);
      result = 37 * result + Float.floatToIntBits(this.im);
      return result;
    }

 

 

 

【Effective Java 学习笔记】系列连载专题请见:
http://tonylian.iteye.com/categories/64208

 

评论

1 楼 lxh2002 2009-05-12  

写得不错，分析都挺详细的。