小白也能看懂的JDK1.8前_HashMap的擴容機制原理
- 2020 年 10 月 8 日
- 筆記
最近在研究hashmap的擴容機制，作為一個小白，相信我的理解，對於一些同樣是剛剛接觸hashmap的白白是有很很大的幫助，畢竟你去看一些已經對數據結構了解透徹的大神談hashmap的原理等，人家說的很高大上，時不時會夾着稍許的英文你也看不懂是吧，不過這樣顯得比較有逼格哈哈。在正文之前，我非常有必要給剛剛接觸hashmap以及沒有學過數據結構（其實數據結構我了解也不多哈哈）的小夥伴普及幾個知識，你記住就行了：
1. 對於剛接觸hashmap，hashmap你就暫時理解為哈希表(hash表)，結構為「數組+鏈表」；如果說到表的長度，那指的是數組長度。
2. 「數組+鏈表」的結構專業術語叫「鏈表散列」，說簡單點，一個數組上的每個位置存儲的一個單鏈表；實際上數組的每個位置記錄著是單鏈表的第一個節點，有了第一個節點後面不就串起來了嘛
3. hashmap在jdk1.8前的結構是「數組+(單)鏈表」，在jdk1.8，結構就引入了「數組+鏈表+紅黑樹」，不過在這裡我們只討論1.8之前
4. hashmap在添加元素時使用的是「尾插法」，而在擴容時轉移數據使用的是「頭插法」；後半句話給我重點記着，後面的源碼就涉及到這個
5.hashmap擴容的本質是重新創建一個原有數組長度2倍的新數組。
6. 新表的節點分佈 並不一定 跟 舊錶 一致。比如說舊錶的oldTable[0]上有key(0)->key(1)->key(2)，而到新表這裡newTable[0]就可能變成了key(2)->key(0)【頭插法】，而key(1)在其他位置了。
好了，開始進入正題！我們來研究jdk1.8前的hashmap的擴容原理（為什麼沒有1.8呢？因為我還沒去看哈哈）；它擴容最核心的方法就是resize()，源碼如下：
//hashmap的擴容方法 void resize(int newCapacity) { Entry[] oldTable = table; //把當前的hash表賦值給一個臨時數組，這個臨時數組代表 舊hash表 int oldCapacity = oldTable.length; //得到舊hash表的長度 if (oldCapacity == MAXIMUM_CAPACITY) { //如果判斷舊hash表的長度（其實是數組長度）等於最大容量值 threshold = Integer.MAX_VALUE; //把Integer.MAX_VALUE賦值給當前的閾值，它的意思就是不再擴容了 return; } Entry[] newTable = new Entry[newCapacity]; //創建一個新的hash表 transfer(newTable, initHashSeedAsNeeded(newCapacity)); //這個是重點，這個方法實現將舊hash表的數據放到新的hash表中 table = newTable; //當前的hash表換成新的hash表了 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); // 有新表後，閾值是需要重新計算的 }
上面代碼中，我們真正要關注的是transfer（），你看它方法名就取得很明顯，轉移的意思是吧，源碼如下：
/** * 把 舊錶 的 數據 往新表上挪 */ void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; //得到新表的長度 for (Entry<K,V> e : table) { //這裡table是舊錶，這裡是遍歷舊錶，把舊錶的數據往新表上轉移 while(null != e) { //如果當前節點不為空 Entry<K,V> next = e.next; //next是一個臨時變量，用來引用或保存當前節點指向的下一節點，比如說當前節點是key(3)，key(3)->key(5)，
那next就暫時保存key(5) if (rehash) { //重新計算hash e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); //這個挺重要的，它是重新計算我們當前的(舊)節點應該放到新表的哪個位置上 e.next = newTable[i]; //超級重點，它的作用是斷開當前節點與舊錶的聯繫，啥意思呢？ 還是剛才的例子當前節點是key(3)，key(3)->key(5)，
key(3)現在不指向key(5)了，已經投奔(指向)新表上的某個位置了
newTable[i] = e; //超級重點+，頭插法來了，把當前的節點賦值給新表的某個位置，作用就是舊節點複製到新表上了；意思是每輪循環的當前節點都會
插入到新數組上的某個單鏈表的第一個位置，作為單鏈表的頭節點
e = next; //把剛才保存的下一節點 作為下一輪循環的當前節點 } } }
我盡量把解釋都放到了源碼上面，方便大家查看，減少不必要的頁面上下滾動帶來的眼睛疲勞（我真是活雷鋒哈哈），後面我會去看jdk1.8的源碼，會再次為大家分享。
如果覺得說的勉強還行的話，點個推薦唄！
