從去年畢業(yè)到現(xiàn)在工作中一直使用的都是Jdk1.8，今天在看HashMap的源碼的時候發(fā)現(xiàn)和曾經(jīng)的版本有很明顯的改進。

一 、大體區(qū)別:

之前的版本是通過數(shù)據(jù)+鏈表實現(xiàn)的，而現(xiàn)在是通過數(shù)組+鏈表/紅黑數(shù)。當數(shù)組上的某一串鏈表bucket數(shù)量大于8個的時候，就會變?yōu)榧t黑樹結(jié)構(gòu)，以提高遍歷鏈表的效率(之前的時間復雜度是O(n),現(xiàn)在是O(logn))。

數(shù)據(jù)結(jié)構(gòu)的變化

二、HashMap的實現(xiàn)

* @author  Doug Lea
 * @author  Josh Bloch
 * @author  Arthur van Hoff
 * @author  Neal Gafter
 * @see     Object#hashCode()
 * @see     Collection
 * @see     Map
 * @see     TreeMap
 * @see     Hashtable
 * @since   1.2
 */
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

HashMap繼承AbstractMap,實現(xiàn)了Map<K，V>、克隆Cloneable，序列化Serializable接口。Map接口幾乎沒有變定義了基本操作的方法，為AbstractMap減輕負擔。

三、屬性

 private static final long serialVersionUID = 362498820763181265L;
  
    //默認的初始化數(shù)組大小16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //默認的最大數(shù)組長度2的30次方
    static final int MAXIMUM_CAPACITY = 1 << 30;
     //默認的負載因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
     //鏈表轉(zhuǎn)紅黑樹的閥值
    static final int TREEIFY_THRESHOLD = 8;
    //紅黑樹轉(zhuǎn)鏈表的閥值
    static final int UNTREEIFY_THRESHOLD = 6;
     //哈希表的最小樹形化容量
    //當哈希表中的容量大于這個值時，表中的桶才能進行樹形化
    //否則桶內(nèi)元素太多時會擴容，而不是樹形化
    //為了避免進行擴容、樹形化選擇的沖突，這個值不能小于 4 * TREEIFY_THRESHOLD
    static final int MIN_TREEIFY_CAPACITY = 64;
    //是一個實現(xiàn)了Map.Entry的內(nèi)部類
    static class Node<K,V> implements Map.Entry<K,V> {
        //哈希值
        final int hash;
        //鍵值對的鍵
        final K key;
        //鍵值對的值
        V value;
         //下一個節(jié)點
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

    // 1.8升級了hash方法，將原來的int類型參數(shù)變?yōu)榱薕bject，省去了接下來很多判斷，如果是null直接返回0。
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

   
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
     //數(shù)組
    transient Node<K,V>[] table;
    //所有元素的Set集合
    transient Set<Map.Entry<K,V>> entrySet;
    //所有元素的大小，不是數(shù)組的長度
    transient int size;
     //計數(shù)器
     transient int modCount;
    // 臨界值 當實際大小(容量*填充因子)超過臨界值時，會進行擴容
    int threshold;  
    //負載因子
    final float loadFactor;

四、構(gòu)造方法:

構(gòu)造方法

 public HashMap(int initialCapacity, float loadFactor) {
     //如果數(shù)組長度小于0報錯
     if (initialCapacity < 0)
         throw new IllegalArgumentException("Illegal initial capacity: " +
                                            initialCapacity);
     //如果數(shù)組長度大于最大值賦值為最大值
     if (initialCapacity > MAXIMUM_CAPACITY)
         initialCapacity = MAXIMUM_CAPACITY;
     //如果負載因子小于0
     if (loadFactor <= 0 || Float.isNaN(loadFactor))
         throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor);
    //初始化負載因子
     this.loadFactor = loadFactor;
   //初始化容量
     this.threshold = tableSizeFor(initialCapacity);
 }
//直接調(diào)用
public HashMap(int initialCapacity) {
     this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }
public HashMap() {
     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
 }
//直接傳入一個map類型的值，將這個map的值全部put到新的hashMap中
public HashMap(Map<? extends K, ? extends V> m) {
     this.loadFactor = DEFAULT_LOAD_FACTOR;
     putMapEntries(m, false);
 }

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
     int s = m.size();
     if (s > 0) {
         if (table == null) { // pre-size
             float ft = ((float)s / loadFactor) + 1.0F;
             int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                      (int)ft : MAXIMUM_CAPACITY);
             if (t > threshold)
                 threshold = tableSizeFor(t);
         }
         else if (s > threshold)
             resize();
         for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
             K key = e.getKey();
             V value = e.getValue();
             putVal(hash(key), key, value, false, evict);
         }
     }
 }

五、主要方法
1.put方法

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
         //table未初始化或者長度為0，進行擴容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //如果桶是空的，那么在數(shù)組的這個位置創(chuàng)建一個node放在桶的第一位
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
          //否則如果key相同，value也相同，啊那么替換一下值。
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
              //如果是樹節(jié)點，那么調(diào)用紅黑樹的插入方法
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                //否則鏈表進行遍歷，在尾部插入節(jié)點
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //如果數(shù)量大于閥值，轉(zhuǎn)換成紅黑樹。
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }