小菜毛毛技术分享

与大家共同成长

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  164 Posts :: 141 Stories :: 94 Comments :: 0 Trackbacks
经常在论坛上面看到覆写hashCode函数的问题,很多情况下是一些开发者不了解hash code,或者和equals一起用的时候不太清楚为啥一定要复写hashCode。

    对于hash code的理论我不想多说,这个话题太大。我只想说用hash code的原因只有一个:效率。理论的说法它的复杂度只有O(1)。试想我们把元素放在线性表里面,每次要找一个元素必须从头一个一个的找它的复杂度有O(n)。如果放在平衡二叉树,复杂度也有O(log n)。

   为啥很多地方说“覆写equals的时候一定要覆写hashCode”。说到这里我知道很多人知道有个原则:如果a.equals(b)那么要确保a.hashCode()==b.hashCode()。为什么?hashCode和我写的程序的业务逻辑毫无关系,为啥我要override? 要我说如果你的class永远不可能放在hash code为基础的容器内,不必劳神,您真的不必override hashCode() :)

    说得准确一点放在HashMap和Hashtable里面如果是作为value而不是作为key的话也是不必override hashCode了。至于HashSet,实际上它只是忽略value的HashMap,每次HashSet.add(o)其实就是 HashMap.put(o, dummyObject)。

    那为什么放到Hash容器里面要overide hashCode呢?因为每次get的时候HashMap既要看equals是不是true也要看hash code是不是一致,put的时候也是要看equals和hash code。

    如果说到这里您还是不太明白,咱就举个例子:

    譬如把一个自己定义的class Foo{...}放到HashMap。实际上HashMap也是把数据存在一个数组里面,所以在put函数里面,HashMap会调 Foo.hashCode()算出作为这个元素在数组里面的下标,然后把key和value封装成一个对象放到数组。等一下,万一2个对象算出来的 hash code一样怎么办?会不会冲掉?先回答第2个问题,会不会冲掉就要看Foo.equals()了,如果equals()也是true那就要冲掉了。万一 是false,就是所谓的collision了。当2个元素hashCode一样但是equals为false的时候,那个HashMap里面的数组的这 个元素就变成了链表。也就是hash code一样的元素在一个链表里面,链表的头在那个数组里面。

回过来说get的时候,HashMap也先调key.hashCode()算出数组下标,然后看equals是不是true,所以就涉及了equals。

    反观假设如果a.equals(b)但是a.hashCode()!=b.hashCode()的话,在put元素a之后,我们又用一个 a.equals(b)但是b.hashCode()!=a.hashCode()的b元素作为key来get的时候就找不到a了。如果 a.hashCode()==b.hashCode()但是!a.equals(b)倒是不要紧,这2个元素会collision然后被放到链表,只是效 率变差。

  这里有个非常简化版的HashMap实现帮助大家理解。

  1. /* 
  2.  * Just to demonstrate hash map mechanism,  
  3.  * Please do not use it in your commercial product. 
  4.  * 
  5.  * @author Shengyuan Lu 卢声远 <michaellufhl@yahoo.com.cn> 
  6.  */  
  7. public class SimpleHashMap {  
  8.     ArrayList<LinkedList<Entry>> entries = new ArrayList<LinkedList<Entry>>();  
  9.       
  10.     /** 
  11.      * Each key-value is encapsulated by Entry. 
  12.      */  
  13.     static class Entry {  
  14.         Object key;  
  15.         Object value;  
  16.         public Entry(Object key, Object value) {  
  17.             this.key = key;  
  18.             this.value = value;  
  19.         }  
  20.     }  
  21.     void put(Object key, Object value) {  
  22.         LinkedList<Entry> e = entries.get(key.hashCode());  
  23.         if (e != null) {  
  24.             for (Entry entry : e) {  
  25.                 if (entry.key.equals(key)) {  
  26.                     entry.value = value;// Match in lined list  
  27.                     return;  
  28.                 }  
  29.             }  
  30.             e.addFirst(new Entry(key, value));// Add the entry to the list  
  31.         } else {  
  32.             // Put the new entry in array  
  33.             LinkedList<Entry> newEntry = new LinkedList<Entry>();  
  34.             newEntry.add(new Entry(key, value));  
  35.             entries.add(key.hashCode(), newEntry);  
  36.         }  
  37.     }  
  38.     Object get(Object key) {  
  39.         LinkedList<Entry> e = entries.get(key.hashCode());  
  40.         if (e != null) {  
  41.             for (Entry entry : e) {  
  42.                 if (entry.key.equals(key)) {  
  43.                     return entry.value;  
  44.                 }  
  45.             }  
  46.         }  
  47.         return null;  
  48.     }  
  49.       
  50.     /** 
  51.      * Do we need to override equals() and hashCode() for SimpleHashMap itself?  
  52.      * I don't know either:) 
  53.      */  
  54. }  


这个问题的权威阐释可以参考Bloch的<Effective Java>的 Item 9: Always override hashCode when you override equals

posted on 2010-08-27 09:51 小菜毛毛 阅读(385) 评论(0)  编辑  收藏 所属分类: 面试

只有注册用户登录后才能发表评论。


网站导航: