HashMap源碼分析——put和get（二）

鏈接

上一節(jié) ：HashMap源碼分析——put和get（一）

2.3 tableSizeFor函數(shù)

先來看tableSizeFor函數(shù)的構(gòu)成 :

    /**
     * Returns a power of two size for the given target capacity.
     */
    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;
    }

    private static final int MAXIMUM_CAPACITY = 1 << 30;

    public static void main(String[] args) {
        int cap = 18;
        int n = cap - 1; // 17
        System.out.println("n |= n >>> 1 --> " + (n |= n >>> 1));
        System.out.println("n |= n >>> 2 --> " + (n |= n >>> 2));
        System.out.println("n |= n >>> 4 --> " + (n |= n >>> 4));
        System.out.println("n |= n >>> 8 --> " + (n |= n >>> 8));
        System.out.println("n |= n >>> 16 --> " + (n |= n >>> 16));
        int result = (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        System.out.println(result);
    }

結(jié)果打印為32 那這些代碼是怎樣將18轉(zhuǎn)換成為了一個(gè)比他大有離他最近的一個(gè)二次冪整數(shù)呢？

0000 0000 0001 0001 (17)
0000 0000 0000 1000 (17 >>> 1)
-----------------------
0000 0000 0001 1001
0000 0000 0000 0110 ( >>> 2)
-----------------------
0000 0000 0001 1111
0000 0000 0000 0001 ( >>> 4)
-----------------------
0000 0000 0001 1111
.... .... .... .... ( >>> 8)
-----------------------
0000 0000 0001 1111
.... .... .... .... ....

我們發(fā)現(xiàn)當(dāng)?shù)竭\(yùn)行至第二行后骄瓣，就已經(jīng)定下了解決侣集，不管之后再怎樣做或運(yùn)算漱逸，結(jié)果會(huì)成為0001 1111正勒，最會(huì)在加一就會(huì)成為0010 0000也就是32

那若果n = 01000 0000 0000 0000 0000 0000 0000 0000呢？也就是說 cap = (1 >> 30) + 1票编，雖然在構(gòu)造函數(shù)中有這樣一句話 ：

public HashMap(int initialCapacity, float loadFactor) {
    // ...
  if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
    // ...
}

但是為什么要這樣迄埃？

0100 0000 0000 0000 || 0000 0000 0000 0000
0010 0000 0000 0000 || 0000 0000 0000 0000 ( >>> 1)
---------------------------------------------------
0110 0000 0000 0000 || 0000 0000 0000 0000
0001 1000 0000 0000 || 0000 0000 0000 0000 ( >>> 2)
---------------------------------------------------
0111 1000 0000 0000 || 0000 0000 0000 0000
0000 0111 1000 0000 || 0000 0000 0000 0000 ( >>> 4)
---------------------------------------------------
0111 1111 1000 0000 || 0000 0000 0000 0000
0000 0000 0111 1111 || 1000 0000 0000 0000 ( >>> 8)
---------------------------------------------------
0111 1111 1111 1111 || 1000 0000 0000 0000
0000 0000 0000 0000 || 0111 1111 1111 1111 ( >>> 16)
---------------------------------------------------
0111 1111 1111 1111 || 1111 1111 1111 1111

int result = (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

如果沒有判斷的話 n+1就成了負(fù)數(shù)。所以說 1 >>> 30 是int類型中最大的二次冪整數(shù)寝蹈，如果在構(gòu)造函數(shù)中聲名了比他還大的一個(gè)數(shù)并且沒有任何約束條件的話李命，最后會(huì)變成一個(gè)悲劇（也就會(huì)成為負(fù)數(shù)）箫老。

通過上面兩個(gè)異或操作 不難看出tableSizeFor()函數(shù)就是找到二進(jìn)制中的第一個(gè)1封字，并把這個(gè)1后面的0全部變成1。

2.4 數(shù)組的初始化

我們看數(shù)組的初始化其實(shí)是在做put()中進(jìn)行的(put函數(shù)直接調(diào)用了putVal())：

    transient Node<K,V>[] table;
    // ...
    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;
        if ((tab = table) == null || (n = tab.length) == 0)
            // 數(shù)組的初始化
            n = (tab = resize()).length;
    }
    // ...

其實(shí)putVal()是一個(gè)很長的函數(shù)耍鬓，但是數(shù)組的初始化只有這幾行阔籽。

具體再來看resize()函數(shù)是怎樣初始化的 :

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        // ...
        else if (oldThr > 0)
          // 如果你定義了初始容量就走這里了
          newCap = oldThr;
        else {               
            // 無參構(gòu)造函數(shù)就會(huì)到這里進(jìn)行初始化
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            // 在這里計(jì)算閾值
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            // ... 一段昂長的代碼    
        }
        return newTab;
    }

總的來說，在初始化階段牲蜀，先計(jì)算數(shù)組的容量笆制，再計(jì)算數(shù)組的閾值涣达。

2.5 HashMap的put操作

下面代碼才是putVal()的原身 ：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 對(duì)數(shù)組進(jìn)行初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 接下來我們要分析以下代碼
        // ------>
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            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)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        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;
    }

先看這兩行 :

// ...
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // ...
  // 如果數(shù)組有位置 就把節(jié)點(diǎn)放在這個(gè)位置上
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  // ...
}

2.5.1 判斷索引位置以及擾動(dòng)函數(shù)

如何判斷某個(gè)元素在哪個(gè)位置呢在辆？

p = tab[i = (n-1) & hash]

判斷元素在數(shù)組的哪個(gè)位置位置其實(shí)就是 (length - 1) & hash

那么 hash又是怎么來的证薇？

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

當(dāng)key時(shí)null的時(shí)候，hash值就是0匆篓；如果不是null浑度，就計(jì)算key的hashCode()，并把結(jié)果右移16位鸦概，然后把兩個(gè)做異或處理俺泣。這就是最后的hash()值

那為何要這么做？知乎某位大佬給出了如下解釋 ：

[JDK 源碼中 HashMap 的 hash 方法原理是什么完残？](JDK 源碼中 HashMap 的 hash 方法原理是什么伏钠？ - 知乎
https://www.zhihu.com/question/20733617/answer/32513376)

就是說，在確定數(shù)組的索引位置時(shí)候谨设，如果直接計(jì)算hash(key)的話熟掂，代價(jià)是比較大的。因?yàn)閔ash(key)的取值范圍是整個(gè)int范圍扎拣，而HashMap默認(rèn)的數(shù)組容量只有16赴肚。所以我們可以將hash(key)做取模處理，也就是 hash(key) & (length - 1)二蓝。但是誉券，這些又會(huì)引發(fā)很多的”碰撞”（這個(gè)結(jié)果很可能將很多的節(jié)點(diǎn)放到0號(hào)位置）。

 0000 0000 0000 0000 || 0000 0000 0000 1111
&0... .... .... .... || .... .... .... 0000
--------------------------------------------
 0000 0000 0000 0000 || 0000 0000 0000 0000

我們發(fā)現(xiàn)刊愚，不管...是0還是1踊跟，只要最后四位是0的話，結(jié)果都會(huì)成為0鸥诽，這就會(huì)造成很多碰撞

根據(jù)這個(gè)情況商玫，擾動(dòng)函數(shù)出來了：

擾動(dòng)函數(shù)

將hash()結(jié)果的高半部分和低半部分做異或處理，這樣就很大程度上減少了碰撞牡借。

好了拳昌，知道了元素存放到數(shù)組哪個(gè)索引下面了，代碼就開始判斷這個(gè)索引是不是空的钠龙，如果是空的炬藤，元素就是頭頭了。

image

假設(shè)某個(gè)節(jié)點(diǎn)要進(jìn)行put操作碴里，這個(gè)節(jié)點(diǎn)的

value="老古董",key="CN-Z17-18-00139",index(hash)=7

然后它就開始判斷table[7]是不是有元素占著沈矿，如果沒有，他就成為了第一張"唱片"（老古董是尋寶游戲的第一張單曲）

image

我們?cè)倩仡^看put函數(shù)的其他情況 ：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 數(shù)組初始化
        // ...
        // 如果當(dāng)前索引是空的 占位
        // ...
        // 如果當(dāng)前有位置 走這里
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // ...
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        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;
            }
        }
        // ...
}

2.5.2 HashMap什么時(shí)候會(huì)發(fā)生替換

先來看這一段代碼 ：

Node < K, V > e; K k;
// ...
// 如果待插入的節(jié)點(diǎn)和待在數(shù)組上的節(jié)點(diǎn)重了 就做替換
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;
// ...
if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        // 目前沒有意義的一句話
        afterNodeAccess(e);
    return oldValue;
}

所以什么時(shí)候HashMap會(huì)進(jìn)行節(jié)點(diǎn)的替換呢并闲？必須滿足以下條件：

• 待插入的和將要被替換的節(jié)點(diǎn)必須hash值相等细睡。當(dāng)然這里的hash值并不是簡單的hash(key)，而是經(jīng)過擾動(dòng)算法“摧殘”過的hash值帝火。
• 待插入的節(jié)點(diǎn)的key必須要等于將要被替換的key || 待插入的節(jié)點(diǎn)的key不能是null并且待插入和代替換的key的equals()要為true

上面兩個(gè)條件必須同時(shí)滿足才可以發(fā)生節(jié)點(diǎn)的替換溜徙。

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