JDK源代码学习系列一---java.util（2）

前一篇 JDK源代码学习系列一---java.util（1）：[url]http://www.iteye.com/topic/905329[/url]

就目前看来，上一篇有点标题党的味道，源代码学习却没有一句JDK源代码，把大家都骗进来了，为了改过自新，哥现在开始要贴源代码了。我相信我要讲的，我所看到的，很多jer都知道的比我深刻，有同学已经在回复中贴出了部分源码，但是我的学习我得自己过一遍。所以我们接下去是讨论，我说我的，各位大大们觉得我理解有误的地方可以用砖头拍我。
继续来学习HashMap。
首先，我们来看下什么叫hash。百度有如下解释，参考性拿来使用：
“Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，[color=red]不同的输入可能会散列成相同的输出[/color]，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。”
接着，我们来看一下HashMap的一些结构。HashMap是存储key-value键值对的，即Entry。宏观上来说它底层是一个Entry的数组。

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry[] table;

但是，Entry并不是简单纯粹的键值对，它的结构如下：

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
...

重点请关注Entry<K,V> next;，这个让人想到的是链表。
为了能形象的看到整个HashMap的结构，哥从百度上找了张HashMap的结构图（如有侵权行为，请通知本人，请勿直接投隐藏...）:

[img]http://dl.iteye.com/upload/attachment/417783/cffa20f1-310c-3a3f-80dd-cfe77b19c0c4.jpg[/img]

可见table这个数组存储的并非是单纯的键值对，实际存储的是链表，而每一个Entry的next将指向该链表的下一个元素。那为什么在这个地方需要链表的结构呢？
我们来看一下HashMap的put方法：

     /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        //如果key为null,则调用putForNullKey(value)，由此可见HashMap支持null为key
        if (key == null)
            return putForNullKey(value);
        //获取key的hash值
        int hash = hash(key.hashCode());
        //由此可见新元素插入HashMap的位置将由其hash值决定，所以通过hash值和table长
        //度算出该key的hash值所对应的table数组索引i。
        int i = indexFor(hash, table.length);
        //遍历table[i]这个位置的链表
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //如果hash值与key都相同，表明该链表中已存在该key的entry,则更新该entry的value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //若程序走到这里，table[i]处尚没有该key对应的entry，插入entry
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

    ......

     /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }
    ......

    /**
     * Adds a new entry with the specified key, value and hash code to
     * the specified bucket.  It is the responsibility of this
     * method to resize the table if appropriate.
     *
     * Subclass overrides this to alter the behavior of put method.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        //插入链表头部
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

获取hash值需要使用哈希算法，但是通过上文Hash解释的红色字体部分“不同的输入可能会散列成相同的输出”可以得知，哈希算法可能会出现不同的key得到重复的hash值，这就是hash冲突。这样的entry都会被插入到table的i处，为了不覆盖不同的key的entry，多个hash值相同的key的entry就会被按照链表的结构串接起来。
到这里，我希望我讲清楚了HashMap的结构与其成因。

现在，我们来看看上一篇中留下的问题。

首次插入p1，p2的时候，p1与p2的hash值不同，所以插入后的结构应该如下：
[img]http://dl.iteye.com/upload/attachment/418697/7c49a67b-cf66-348a-a2e3-14beee086a64.jpg[/img]
可见key为p1,p2的hash值得到分别为x,y,根据indexFor方法得到该插入table的索引值分别为m,n。因此entry分别被插入到table的索引m,n处。但是后来p2的id被修改了，因为entry中的key虽然是final的，但它只是一个引用，实例对象还是可以被修改的。一旦p2的id被修改，根据Person类重写的hashcode方法，其重新计算得到的hash值也将改变。因为将p2的id改为了与p1相同，所以重新计算得到p2的hash值与p1相同，都为x。我们来看一下HashMap的get方法：

    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        //重新计算key的hash值，此时p2与p1的hash值相同
        int hash = hash(key.hashCode());
        //此处的循环并不是一key对应多个value的循环，而是通过重新计算得到key的hash值
        //找出该key所对应的entry在table数组中的链表所在的索引，然后遍历相同hash的
        //entry链表找到目标key，并返回该key对应的value
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

因为此时在n位置的p2对应的entry中的hash是final字段，在插入时就已经固定，所以重新计算得到hash并不会更新，且该链表结构也不会改变。p2对应的entry还在老位置，但是通过get(p2)等效于get(p1)，因为他们的hash值相同。所以虽然出现了一键对应多个value的情况，但实际上不论通过get(p1)还是get(p2)只能找到m处的entry了。
那么现在你会想到，既然p2对应的entry还在老位置，我有什么方法可以重新找到这个entry呢。如果我给你两种方案：
1.将p2的id改回去，然后通过m.get(p2):

 ......

 p2.setId("2");

 ......

2.新建一个p3，把p3的id设为"2",即跟原来的p2相同，然后直接通过m.get(p3):

      ......
      Person p3 = new Person();
      p3.setName("name3");
      ......
      System.out.println("Map m 通过get方法用key p3:"+p3+"时,获取的value:"+m.get(p3));

大家觉得两种结果分别会怎样呢？原因又是什么？