hashCode乱谈

 

今天翻“Effective Java”的时候看到了改写hashCode()方法的三条约定，突然想到了某些问题，故记录之。

1.在每个改写了equasl方法的类中，你也必须要改写hashCode方法。

2.如果equals相等，两个对象的hashCode必须相等。

3.不相等的对象倾向于产生 不相等的散列码，但是不相等的对象可以有相等的散列码。

我在写代码的时候曾遇到过如下情况：

    class Person {    
          String name ;
          int age ;   
          public Person (String name , int age ){
                this . name = name ;
                this . age = age ;
          }    
          public boolean equals (Object o ){        
                if (o instanceof Person ){
                      Person p=( Person )o ;
                      return name . equals (p. name ) && age == p. age ;
                }
                else return false ;
          }
    }

    public class Test {    
          public static void main (String ... s){
                HashSet < Person > s = new HashSet < Person >();  
                s . add (new Person ("hello" , 23 ));       
                System.out.println(
                       s.contains(new Person("hello" , 23 )));                  
          }
    }

这段代码很simple很naive，但是当看到结果的时候依然迷惑了~因为我所期望的结果是输出true，但很不幸的是这段代码的结果输出为false。更让我感到困惑的是，如果对这两个对象调用equals方法比较，他们必然是相等的。

于是我便去参阅jdk中HashSet类的源码，才知道原来HashSet其实就是一个HashMap。众所周知HashMap中存放的是键值对， 因此所有的键都必须是唯一的，在HashMap中不可能同时存在两个相同的键。所以HashSet便是利用这个特性，将add进这个Set的对象都当做是 Map的某个key。下面是HashSet实现类的代码片段：

    public class HashSet < E >{
        private transient HashMap < E , Object > map ;
        private static final Object PRESENT = new Object ();
        public HashSet () {
              map = new HashMap < E , Object >();
        }
        public boolean add (E e ) {
              return map . put (e , PRESENT )== null ;
        }
        public boolean contains (Object o ) {
              return map . containsKey (o );
        }
        ……

    }


    public boolean add (E e ) {  
           return map . put (e , PRESENT )== null ;
    }

    // 首次调用add方法添加元素e的时候，map中会建立 e--->PRESENT 的键值对。
    // 由于此前map中不存在e作为key，因此会返回一个null值，此时add方法调用成功，返回true。
    // 首次调用add方法添加元素e的时候，map中已存在 e--->PRESENT ，因此会把这个PRESENT
    // 当成是旧值返回，由于PRESENT!=null，故add方法返回false。 

 

可以清楚的看出来，HashSet类中包含了一个map，而且是HashMap，同时还保存了一个空对象PRESENT 。每当我们调用add方法的时候，实质上就是在hashMap中插入一对键值。此时充当键值的是我们想插入Set的元素E，而充当值的，正是PRESENT 。其实这个结构挺囧的，因为HashMap中存放的所有值，都是这个PRESENT 的引用。

参阅javaAPI手册，HashMap.put方法有一个返回值V。这个V是与key关联的旧值，如果key没有任何映射关系，则返回null。

 

现在回归最开始的问题，这个问题可以归结如下。

    public class Test {    
        public static void main (String ... s){
            Person p1 = new Person ("hello" , 23 );
            Person p2 = new Person ("hello" , 23 );
            System . out . println (p1 . equals (p2 ));        //输出true
           
            HashSet < Person > s = new HashSet < Person >();  
            s . add (p1 );
            System . out . println (s. contains (p2 ));       //输出false
        }
    }

 

第一个输出true很好理解，第二个输出false有点费解。 

 

当执行完 s . add (p1 ) 之后，s中的map里已经包含了 P1 --->PRESENT 的键值对。然后对这个map进行查询，发现不含有p2键。这说明有两个equals相等的对象，正在一个hashMap中充当着不同的键，这很不合理！那么HashMap中的键究竟是根据什么来判断他们是否相同呢？不妨来研究一下HashMap类：

public class HashMap < K , V >{

    transient Entry [] table ;    //这是一个Entry数组，注意Entry其实是一个链表

    public V put (K key , V value ) {
        if (key == null )
            return putForNullKey (value ); //key是null的情况
 
        // 如果key不是null，首先调用hash方法进一步散列。然后通过indexFor 函数将
        // 所得的hash码映射到 [0,table.length-1] 区间，得到的映射值为i。
        // 遍历table[i]这个链表，如果已经有某个Entry 结点的key与所要插入的key相等，
        // 那么修改这个Entry结点，用value替换掉原来的旧值
        // 如果table[i]链表中尚不存在这样键为key的Entry，则生成一个这样的结点，
        // 插入到table[i]的首个结点之前        
        int hash = hash (key . hashCode ());
        int i = indexFor (hash , table . length );
        for (Entry < K , V > e = table [ i ]; e != null ; e = e . next ) {
            Object k ;
            if (e . hash == hash && ((k = e . key ) == key || key . equals (k ))) {
                V oldValue = e . value ;
                e . value = value ;
                e . recordAccess (this );
                return oldValue ;
            }
        }  
        modCount ++;
        addEntry (hash , key , value , i );
        return null ;
    }  
 
    /**
     * 如果key是null，那么这个value一定是放在table [ 0 ] 所在的链表里的
     * 如果table [ 0 ] 这个链表中本来就存在Entry，那么会遍历这个链表，直到找到key是null的
     * 结点，用新的value替换掉旧的，返回旧值
     * 如果table [ 0 ] 这个链表中为空，或者不存在key为null的Entry结点，那么会调用addEntry
     * 方法，该方法创建一个结点，插入到table [ 0 ] 链表的首个结点之前
     */
    private V putForNullKey (V value ) {
        for (Entry < K , V > e = table [ 0 ]; e != null ; e = e . next ) {
            if (e . key == null ) {
                V oldValue = e . value ;
                e . value = value ;
                e . recordAccess (this );
                return oldValue ;
            }
        }
        modCount ++;
        addEntry (0 , null , value , 0 );
        return null ;
    }  
 
    //h ash方法用于将对象的hashCode进一步散列，具体的算法看不懂
    static int hash (int h ) {
        h ^= (h >>> 20 ) ^ (h >>> 12 );
        return h ^ (h >>> 7 ) ^ (h >>> 4 );
    }

    static int indexFor (int h , int length ) {
        return h & (length - 1 );
    }
} 

 

阅读完HashMap的代码片段，至少能够确定一点，用对象A作为键去关联另一个对象B，可以说其实是建立了对象的A的散列码和对象B之间的映射。因此在上面一个set的例子中，两个Person对象P1与P2虽然用equals方法相等，但是由于没有覆写hashCode方法，所以P1和P2返回的散列码并不一样。故P1与P2可以在hashMap中充当不同的键。

 

回到刚开始的三点建议~当我们改写了equals方法的时候，还需要改写hashCode方法。并且需要保证如果equals方法相等，那么hashCode也一定要相等。这两条建议其实是强制保证我们代码的语义与真正执行结果之间的一致性。因为很多时候，equals方法并不简单比较引用是否相等，我们更需要的是一个能够进行对象内容比较的equals方法。所以如果我们认为两个对象相等了，正如P1和P2，那么我们要确保 s . add (p1 )后s. contains (p2 )一定能够返回true.

 

至于第三点建议，如果不相等对象产生了相同的散列码也没有问题。用不同散列码的好处就在于可以将键散列到Entry数组的不同位置，我们下次访问的时候，仅仅是访问数组的某一个单元，消耗的是单位时间。但是如果在hashMap中用这些相同散列码的对象作为键值，那么生成的键值对肯定在数组某个单元包含的同一串链表上，查找或者修改这样一个链表是很费时的。

 

 

 

评论

1 楼 yznxing 2010-05-05  

哈哈，跟我前两天遇到的差不多问题。
我也记录了下这个。。。

额~~~~