HashMap實作原理

面試高頻問題，這裡提供下參考。

HashMap結構圖

我覺得HashMap的實作方式不夠好，關鍵的幾個方法裡面包含的情況太多了，閱讀起來是有難度的，而寫程式的目的之一不就是讓其他開發者閱讀嗎？一個方法内部做了太多的事情，違反了代碼整潔的規則，一個函數做要盡量少的事情。

解析

之前稍微介紹了一些HashMap的特性，

HashMap初探

。這裡接着深入。

先挑最簡單的說...

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
}

先從數組下标，找到對應的Node
如果Node裡的第一個節點命中，直接傳回
如果有沖突，則通過key.equals(k)去查找對應的entry

若為樹，則在樹中通過key.equals(k)查找，O(logn)；
若為連結清單，則在連結清單中通過key.equals(k)查找，O(n)。

// hash值為hash(key),key
final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //table不為空，并且tab[(n-1) & hash] != null的時候。
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            
            //判斷取出Node的hash值是否相等。key值相等，那麼直接傳回。
            //想一想什麼情況下，if語句不成立？
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            
            //也就是取出的第一個Node的hash值與key計算的hash不等。    
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                
                    //從樹中取節點。
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    
                do {
                    //判斷hash值與key值是否相等，一直判斷到相等或到節點末端為止。
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

這個中間涉及的邏輯多一些，方法需要分不同的步驟看。

思路：

對key的hashCode()做hash，然後再計算index;
如果沒碰撞直接放到bucket裡；
如果碰撞了，以連結清單的形式存在buckets後；
- 如果節點已經存在就替換old value(保證key的唯一性)
- 如果碰撞導緻連結清單過長(大于等于TREEIFY_THRESHOLD)，就把連結清單轉換成紅黑樹；
如果Node的容量滿了(超過load factor*current capacity)，就要resize。

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為空，就重新建立table
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果tab[(n-1) & hash]為空的話，就在tab[(n-1) & hash]位置存儲節點。
        // newNode = new Node<>(hash, key, value, next);    
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        
            //當tab[(n-1)&hash]位置已經存在Node的時候。
            Node<K,V> e; K k;

            //如果已經存在的Node與即将要存的key值一樣
            // e為存在的Node
            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 {
                //不滿足以上的情況，一直把Node往後插入。
                //如果插入的節點數量多于TREEIFY_THRESHOLD-1個，變為樹形節點
                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;
                    }
                    //如果再周遊的時候，發現key值相同的時候，就跳出循環。e = p.next，
                    // 這時已經記錄e的Node值了
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            
            // 存在對應的Node時
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        
        // HashMap内部修改的初始
        ++modCount;
        
        //如果存儲的節點數，大于臨界值，重新配置設定大小
        if (++size > threshold)
            resize();

        //抽象方法，當節點執行插入操作的時候如何處理    
        afterNodeInsertion(evict);
        return null;
    }

一般不發生碰撞的時候，相對簡單，資料量較小的情況下。

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)
            n = (tab = resize()).length;
        
        // 留意 i = (n-1)&hash，是以取的時候也這樣取
      // newNode = new Node<>(hash, key, value, next);
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
}

發生碰撞後，有個紅黑樹的處理，因為紅黑樹相對知識點較多，下次單獨詳細解釋。這裡可以參考以下，

從JDK源碼研究紅黑樹

。我解釋下關于碰撞沖的循環。

檢視是否存在相同的key，存在相同的key跳出循環，覆寫key的value
如果不存在相同的key，在連結清單末尾插入新的Node
- 如果連結清單節點過長，轉換為樹。

for (int binCount = 0; ; ++binCount) {
                    // p.next為null的時候，走到了連結清單的末端，然後建立一個節點，如果連結清單的長度太長，轉換為樹存儲。
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
              
                    // 如果連結清單中存在于要put的key值相同的時候，存儲key值，也就是e ,(e = p.next)。
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }

紅黑樹的部分，我們下次單獨解析

這個涉及的内容，有不少線需要捋一捋。首先看申明時候會resize()。它們都在調用put的時候執行的。

table == null的時候

if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

鍵值映射的的數目大于臨界值的時候。

if (++size > threshold)
            resize();

resize具體方法

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        
        // 之前的容量可能為0或者為之前的大小
        // threshold可能為null或者為2的n次方
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;

        //新的容量，新的臨界目前都為0
        int newCap, newThr = 0;

        // 第二次resize的時候。
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        //第一次resize()的時候，初始化的操作。
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        
        //第一次resize()，會進入
        if (newThr == 0) {
            //負載因子 * 初始容量
            float ft = (float)newCap * loadFactor;
            
            //保證臨界值不超過最大值。
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        
        //真正初始化的操作，建立newCap個數組，臨界值初始化。
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        
        // 非 第一次reizie()時
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    
                    // 重新計算了一次hash
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                        
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // 如果e.next ！= null 存在hash的Node 鍊子
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        
                        do {
                            next = e.next;
                            // 原索引
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            // 原索引+ oldCap
                            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;
                        }
                    }
                }
            }
        }
        return newTab;
    }

如果是第一次resize，我們抽出來會執行到的語句。

初始化容量
初始化threshold，也就是初始化臨界值，決定了table的鍵值對數目到什麼時候會再次resize()

final Node<K,V>[] resize() {
      //第一次的時候table為null
        Node<K,V>[] oldTab = table;
      // oldCap 為 0,threshod為null
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;

        int newCap, newThr = 0;

// 不會走
        if (oldCap > 0) {
             ....
// 從這裡執行
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
     
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        return newTab;
}

第二次及後續的resize執行流程

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        // oldCap為目前table的長度,  oldThr為上次的table臨界值
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;

        int newCap, newThr = 0;
        if (oldCap > 0) {
            // 這個if語句保證容量不超過hashmap的容量上限值。
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 如果擴容之後，不超過容量上限，
           //  那麼表的大小加倍。臨界值加倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
   
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;

        //第二次擴容的時候，對上次的table如何處理。
        if (oldTab != null) {

            // 周遊之前的table，重新hash排序
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //隻對存在的索引操作
                if ((e = oldTab[j]) != null) {
                    //銷毀目前索引的内容
                    oldTab[j] = null;
                    //重新計算位置并指派
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                   //樹的操作，下次再說
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

                    //連結清單的操作
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            // oldCap 為 16也就是 10000，
                            //oldCap為16的倍數，這裡是hash值為低數字的時候

                            if ((e.hash & oldCap) == 0) {
                                //第一次
                                if (loTail == null)
                                    loHead = e;
                                //計算新的next
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            //同理
                            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;
                        }
                    }
                }
            }
        }
        return newTab;
    }

resize中對有碰撞的連結清單的操作寫的很有意思，再叙述一下。在重新配置設定索引的時候，有重新組建連結清單的操作。

舉個比較誇張的例子，讀者就明白了。

e.hash < 2，那麼 e.hash&oldCap就等于0，索引為小于之前hash表大小以内的索引。也就是當初的索引不變。
e.hash > 2的時候，e.hash&old不等于0，那麼它的索引就為目前表的索引再加上新擴容的大小。

案例圖

這個圖說的是，當hashmap的表大小為2擴充到4的時候，原本挂載在1位置的連結清單，重新配置設定之後的樣子。

Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            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;
                        }

最後

篇幅有限，我這裡僅僅介紹了get方法，put方法，resize方法的具體原理，文章就已經非常長了，不利于閱讀。

下次再補充一下HashMap的hash方法原理，其餘的相關注意事項。

HashMap實作原理

目錄

解析

最後

參考

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method