本文是在觀看 Java HashMap 工作原理及實現(xiàn) 后,雖然大致了解了 HashMap 的工作原理及實現(xiàn),但是對實現(xiàn)的具體過程,思路尚未貫通,所以對于其中的幾個核心方法按照每個步驟進行研究,注釋

源碼版本為jdk1.8.0_91

put(K key, V value)

public V put(K key, V value) {
    // 調(diào)用 putVal 方法
    return putVal(hash(key), key, value, false, true);
}
// 對 key 進行 hash 操作
static final int hash(Object key) {
    int h;
    // 如果 key 為 null,返回0,否則調(diào)用 hashCode() 方法,然后對 hashCode 高16bit不變，低16bit和高16bit做了一個異或處理
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)

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 為 null,或者 table 的長度為0,進行初始化操作
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 根據(jù) (table長度-1) 與 hash 計算得出該 hash 在table中的索引
    // 根據(jù)索引獲取對應的值,如果該值為 null,在此位置插入一個 Node 對象
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 判斷該值的 hash,key 與要插入的 hash,key 是否相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 如果相等,表明該key為當前節(jié)點的第一個,將原值設(shè)置為當前 e 對象
            e = p;
        else if (p instanceof TreeNode)
            // 判斷當前節(jié)點是否為 TreeNode 類型
            // 如果是 TreeNode 類型,使用紅黑樹的方式找出對應節(jié)點或新增節(jié)點并返回
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 如果是鏈表類型
            for (int binCount = 0; ; ++binCount) {
                // 如果下一個節(jié)點為 null,進行節(jié)點追加操作
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 如果當前節(jié)點的數(shù)量大于等于 8,將鏈表轉(zhuǎn)換為 TreeNode
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果鏈表中存在該 key,因為已經(jīng)將該節(jié)點賦值給 e,所以直接結(jié)束循環(huán),等待下面的方法對值進行更新
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果 e 不等于 null,證明存在舊節(jié)點
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 更新原本舊值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 空實現(xiàn)
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 操作數(shù)加1
    ++modCount;
    // 如果總數(shù)加1大于threshold,進行擴容
    if (++size > threshold)
        resize();
    // 空實現(xiàn)
    afterNodeInsertion(evict);
    return null;
}

get(K key)

public V get(Object key) {
    Node<K,V> e;
    // 調(diào)用 getNode 方法進行獲取 Node 對象
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode(int hash, Object key)

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 如果 table 為 null 或 table 的長度為0 或 根據(jù) hash 計算的節(jié)點為 null,返回null,否則進行查找
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 檢查第一個節(jié)點是否為當前 key
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 如果第二個節(jié)點不是 null
        if ((e = first.next) != null) {
            // 如果是 TreeNode 類型
            if (first instanceof TreeNode)
                // 使用紅黑樹的查找方法進行查找
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 循環(huán)判斷 hash,key是否相等,如果相等,返回否則一直到鏈表結(jié)束
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

remove(Object key)

public V remove(Object key) {
    Node<K,V> e;
    // 調(diào)用 removeNode 方法
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 如果 table 為 null 或 table 的長度為0 或 根據(jù) hash 計算的節(jié)點為 null,返回null,否則進行查找
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 檢查第一個節(jié)點是否為當前 key,如果是將其賦值給 node 變量
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 如果第二個節(jié)點不為空
        else if ((e = p.next) != null) {
            // 如果是 TreeNode 類型
            if (p instanceof TreeNode)
                // 使用紅黑樹的查找方法進行查找
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 循環(huán)判斷 hash,key 是否相等,如果相等,賦值給 node 變量
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 如果根據(jù) key 找到對應節(jié)點
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 根據(jù)該節(jié)點的類型進行對應的刪除操作
            if (node instanceof TreeNode)
                // 如果是 TreeNode 類型,按照紅黑樹的方式刪除
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                // 如果是第一個,將table中的該索引指向第二個節(jié)點
                tab[index] = node.next;
            else
                //如果是在鏈表中,將 node 的前一個節(jié)點的 next 指向 node 的節(jié)點的 next
                p.next = node.next;
            // 操作數(shù)加1
            ++modCount;
            // 總數(shù)減1
            --size;
            // 空實現(xiàn)
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

resize()

final Node<K,V>[] resize() {
    // 原數(shù)組
    Node<K,V>[] oldTab = table;
    // 原容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 原threshold值(容量*負載因子)
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果原容量大于 0
    if (oldCap > 0) {
        // 如果數(shù)組長度達到最大上限,更新 threshold,不進行擴容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 否則容量*2 threshold*2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 如果在構(gòu)造函數(shù)中設(shè)置了初始 threshold 使用 HashMap(int initialCapacity, float loadFactor)創(chuàng)建 Map
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
    // 如果原容量且原threshold 都為0,進行初始化操作
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果 newThr == 0 ( oldThr > 0 為 true 時該判斷才會為 true)
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        // 計算新的 threshold
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 更新 threshold
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 根據(jù)newCap 構(gòu)造一個新數(shù)組
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 更顯table引用
    table = newTab;
    // 如果 oldTab 不為 null,表明為擴容操作,否則為table初始化操作
    if (oldTab != null) {
        // 遍歷原數(shù)組中的元素
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 如果該元素不為 null
            if ((e = oldTab[j]) != null) {
                // 將原數(shù)組該索引設(shè)置為null,方便回收
                oldTab[j] = null;
                // 如果該節(jié)點下一個元素為null,表明該節(jié)點只存在一個元素
                if (e.next == null)
                    // 將該節(jié)點設(shè)置到新數(shù)組中去
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 如果節(jié)點為 TreeNode 類型,按照對應方式設(shè)置到新數(shù)組中
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 如果是數(shù)量大于1的鏈表
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 此處操作跟hash計算索引有關(guān)
                        // 在 HashMap 中,索引的計算方法為 (n - 1) & hash
                        // 所以,在進行擴容操作 (n*2) 后,該計算結(jié)果可能導致變更
                        // 例如
                        // 有一個值為 111001 的 hash
                        // 擴容前  n=16(10000)  n-1=15(1111)  (n - 1) & hash = 1111 & 111001= 001001
                        // 擴容后 n=32(100000) n-1=31(11111)  (n - 1) & hash = 11111 & 111001= 011001
                        // 假如 hash 值為 101001
                        // 那么會發(fā)現(xiàn)擴容前  1111 & 101001 = 001001
                        //           擴容后 11111 & 101001 = 001001
                        // 所以可知,在進行擴容操作時,主要按照 hash 與 原數(shù)組長度中1的對應位置有關(guān)
                        // 如果 hash 中對應的位置為0,擴容后索引結(jié)果不變
                        // 不為0,表示索引結(jié)果為原結(jié)果+原數(shù)組長度
                        // 而 hash 中該對應位置的值只存在倆種可能 0,1
                        // 所以在該節(jié)點中的數(shù)據(jù)大約有一半索引不變,一半為原索引+原數(shù)組長度
                        // 通過 e.hash & oldCap 的方式可以得知 hash 在 oldCap 1對應的位置是否為0或1
                        if ((e.hash & oldCap) == 0) {
                            // 如果為0,證明擴容后索引的計算依然與擴容前一致
                            // 組裝鏈表
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            //如果不為0,則表明擴容后索引的計算依然與擴容不一致,所以需要移動到新索引,新索引的位置為舊索引加oldCap
                            // 組裝鏈表
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 如果鏈表不為 null,設(shè)置到新數(shù)組中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}