HashMap源碼分析 —— put與get（四）

鏈接

上一節(jié) : HashMap源碼分析 —— put與get（三）

2.6 resize()擴(kuò)容操作

    Node<K,V> loHead = null, loTail = null;
    Node<K,V> hiHead = null, hiTail = null;
    Node<K,V> next;
    do {
        next = e.next;
        // 還是原來(lái)的索引值
        if ((e.hash & oldCap) == 0) {
            if (loTail == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
        }
        // 不是原來(lái)的索引值了 需要遷移
        else {
            if (hiTail == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
        }
    } while ((e = next) != null);
    if (loTail != null) {
      loTail.next = null;
      newTab[j] = loHead;
    }
    if (hiTail != null) {
      hiTail.next = null;
      newTab[j + oldCap] = hiHead;
    }

不難看出，loHead和loTail兩個(gè)節(jié)點(diǎn)分別記錄不需要移動(dòng)的鏈表的頭部和尾部，hiHead和hiTail分別記錄需要移動(dòng)的鏈表頭部和尾部.

假設(shè)在擴(kuò)容的時(shí)候某個(gè)數(shù)組下有這樣一個(gè)鏈表 :

image

其中，假設(shè)天藍(lán)色部分的不需要挪動(dòng)，紅色部分的需要挪動(dòng)

第一步 : 建立loHead loTail hiHead hiTail四個(gè)節(jié)點(diǎn)

第二步 ：

image

第三步 :

image

...

第N步 :

image

最后一步 :

把以loHead為首的鏈表放到數(shù)組的原位置，把以hiHead為首的鏈表放到原位置+oldCap的位置，這就是鏈表的擴(kuò)容操作

下面圖片是美團(tuán)技術(shù)團(tuán)隊(duì)的put函數(shù)的流程總結(jié) :

image

2.7 腳步加快 —— get()函數(shù)

相對(duì)于put()函數(shù) get()函數(shù)要簡(jiǎn)單的多 ：

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

首先看下條件 :

// 數(shù)組不能是空的 數(shù)組的長(zhǎng)度必須要大于0 數(shù)組當(dāng)前索引有節(jié)點(diǎn)存在
if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
    // ...           
}

然后，如果第一個(gè)節(jié)點(diǎn)正好就是要找的，那就直接返回吧 :

if (first.hash == hash && // always check first node
    ((k = first.key) == key || (key != null && key.equals(k))))
    return first;

if ((e = first.next) != null) {
    // 如果是紅黑樹(shù)
    if (first instanceof TreeNode)
        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
   // 如果是鏈表 就循環(huán) 直到最后一個(gè)節(jié)點(diǎn)
   do {
       if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
           return e;
    } while ((e = e.next) != null);

}

2.8 HashMap的最后一個(gè)構(gòu)造函數(shù)

最后一個(gè)構(gòu)造函數(shù)如下 ：

public HashMap(Map<? extends K, ? extends V> m) {
   // 加載因子直接設(shè)置成默認(rèn)的
   this.loadFactor = DEFAULT_LOAD_FACTOR;
   putMapEntries(m, false);
}

注意形式參數(shù)中的泛型

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            // 其實(shí)構(gòu)造函數(shù)時(shí) table是null
            if (table == null) { // pre-size
                // 初始化數(shù)據(jù)的容量
                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();
            // 遍歷要插入的map中的每一個(gè)節(jié)點(diǎn) 并把它們插入到調(diào)用它的map中
            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);
            }
        }
    }

其實(shí)除了構(gòu)造器中調(diào)用了putMapEntries函數(shù)之外，還有putAll()函數(shù)調(diào)用了它

下一節(jié) ： HashMap源碼分析 —— put與get（總）