HashMap到底是怎么put 的？

這是我的專欄的第一篇，有任何錯誤，希望大家不吝賜教，共同學習。

寫這個專欄主要是自己學習源碼的過程，如果對別人能有所幫助，不勝開心~

Put的流程：

resize流程圖：

關于HashMap中的紅黑樹這里不做討論，后續可能會進行源碼分析

直接上源碼，jdk1.8 put

代碼片段一

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {// putVal(hash(key), key, value, false, true);// hash是key的hash值，具體算法見方法，key是put時的key，value是put的value,onlyIfAbSent = false,evict = true;Node<K,V>[] tab; Node<K,V> p; int n, i;// 如果為該Map為空尚未初始化，則調用resize進行初始化，n = 初始化后table的大小16。//==========================resize過程見代碼片段二===================================if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 如果在計算出來的table數組的第i個位置上，p = null 還沒有節點，則創建一個節點即可。（i = (n - 1) & hash）,這個計算方法是完成了類似%的操作，并且因為n-1始終是2進制的1111...,所以在table數組上的位置均分。// p = table[i];if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// 如果在第i個位置上已有節點，即p!=null則進入else方法塊。else {Node<K,V> e; K k;// 數組table第i個元素的第一個節點 的hash值 = 要put的key的hash值，要put的key如果等于在這個節點上的key（包括null情況，這也就說明，hashMap的key可以為null，但是只能有一個）。// 在這種情況下則將當前節點用e指代if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 如果p（table第i個元素的第一個節點 的hash值 ） 為 TreeNode，則將新節點放入HashMap里自定義的紅黑樹。putTreeVal方法會自己完成樹的平衡else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// table第i個元素的第一個節點 不滿足上述情況（第一個節點和put進來的key不一樣 + 不為TreeNode），則進入這個方法塊。else {//遍歷table第i個元素上的鏈表，從頭開始遍歷，見第一行e = p.next 和for循環最后一行p = e。for (int binCount = 0; ; ++binCount) {//遍歷到p 的next節點為null的時候，則 p.next指向新節點。（所以hashMap的鏈表上有新節點時都是在鏈表尾部插入。）//e = p.next ；p.next = newNode 這句則是將當前節點記錄，用e指代。if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//插入到binCount到7的時候，即鏈表上的元素為第八個，插入了第九個的時候，則將這個鏈表轉變為紅黑樹，使用treeifyBin方法。if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}//如果循環到一個節點，且滿足 【hash值 = 要put的key的hash值，要put的key如果等于在這個節點上的key（包括null情況，這也就說明，hashMap的key可以為null，但是只能有一個）】// 則將當前節點記錄，用e指代。if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//由上面的代碼執行完，則e肯定是指代了一個當前節點，key與要put的key一致，如果已有值，則value 是oldValue,如果沒有，則是新的value// 下面的代碼執行結束，則返回一個value（如果已有則為old,否則為插入的）可以使用map.put(k,v) == v 來判斷hashMap以前有沒有存儲過這個key。//并返回。if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;//預留方法，LinkedList使用afterNodeAccess(e);return oldValue;}}// 如果是【在第i個位置上已有節點，即p!=null則進入else方法塊。】這個條件，則會在上面return，所以在這里的代碼都是第i個節點上沒有數據的情況才會執行，即resize這個方法只會在往數組的一個新位置上插入數據的時候才會觸發（其實是廢話，resize就是table的size不夠的情況）。++modCount;//size為table數組上有數據的數量，如果size大于threshold時則擴容。if (++size > threshold)//=====================================這里擴容時的resize見代碼片段三====================================resize();//預留方法，LinkedList使用afterNodeInsertion(evict);//返回null。return null; }

代碼片段二

// 在初始化的時候的調用場景 final Node<K,V>[] resize() {//空Node<K,V>[] oldTab = table;// 0int oldCap = (oldTab == null) ? 0 : oldTab.length;//0int oldThr = threshold;int newCap, newThr = 0;//不進去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}//不進去else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;//進去，設置容量為默認容量為16 ，threshold = 12else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//不進去，已被賦值if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//繼續賦值，threshold是成員變量threshold = newThr;//創建出一個newTab，數組大小為 newCap = 16@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//將變量 table 設置為剛才創建出來的newTab。 table 是成員變量。//總結一下，這個方法在初始化的時候只是將table設置為初始化的大小為16的數組，threshold =12。table = newTab;//不進去if (oldTab != null) {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 orderNode<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;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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; }

代碼片段三

final Node<K,V>[] resize() {//將要擴容的table，容量到達0.75*capacityNode<K,V>[] oldTab = table;//當前的capacityint oldCap = (oldTab == null) ? 0 : oldTab.length;//當前的thresholdint oldThr = threshold;//設置新的容量和thresholdint newCap, newThr = 0;//擴容時進入if (oldCap > 0) {//如果已經到達int最大值，則只能這樣了...直接返回不擴容（所以，也不是到了就擴容，畢竟有上限）。if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//如果還沒到，則新的容量設置為老的容量的2倍，threshold也變成以前的兩倍（16->32...）else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//不進去，已被賦值if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;//創建一個新的數組，容量為新容量（2倍老容量）@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//這里將成員變量設置為新的數組（在這時候如果put，則可能會有問題，想想）table = newTab;//擴容時進入if (oldTab != null) {//遍歷舊的數組for (int j = 0; j < oldCap; ++j) {Node<K,V> e;//用e指向舊數組的遍歷到的位置，如果不為空，則進入，為空則不用管。if ((e = oldTab[j]) != null) {oldTab[j] = null;//如果e.next==null,則是只有一個元素，則只需要將這個元素 e 平移到新數組上即可。newTab[e.hash & (newCap - 1)] = eif (e.next == null)newTab[e.hash & (newCap - 1)] = e;//如果這個位置上的存儲結構是樹結構，則進行分割這個樹結構到新數組上，與下面的else情況類似，分為在新數組的老位置還是新位置。else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);//除此的情況，不是只有1個元素，且不是樹結構（鏈表大小小于8），則進入。else { // preserve order//這里的處理我第一次看到的時候覺得很是佩服。//定義兩個Node,一個低位Node loHead ，一個高位Node hiNode，為什么高，為什么低下面說。Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;// 循環遍歷e開頭的鏈表,直到 e 的最后一個節點do {next = e.next;//遍歷過程中，如果 e 滿足 (e.hash & oldCap) == 0 則將這個節點放到 loHead鏈表。//這里這么處理的原因是 oldCap 一定是2的冪次方，在2進制下為10000....這種，所以當e.hash如果滿足(e.hash & oldCap) == 0 時則說明，e的高位也為0。而newCap-1 的二進制是1111111...（與oldCap的長度一樣）//比如16擴容后變成32 ，則oldCap = 10000，newCap -1 = 11111;//在這種情況下，前面說過e的高位為0。其實e.hash &（newCap -1）實際上的最高位肯定 =0 ，而如果高位等于0，則e.hash &（newCap -1） == e.hash &（oldCap -1）,這個元素則新舊數組table中的位置肯定是一個。// 所以還在第j 個位置。//如果不為0 ，則高位為1，則e.hash &（newCap -1） = e.hash &（oldCap -1） + 10000...（oldCap的二進制）if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}// 不滿足的 (e.hash & oldCap) != 0 則將這個節點放到 hiTail 鏈表。else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);//遍歷完畢，if滿足部分進入數組的原有位置 j ，else 滿足部分進入 數組新位置 j+oldCap 。if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}//返回新數組，結束擴容。return newTab; }

總結

以上是生活随笔為你收集整理的源码学习【HashMap第一篇】HashMap到底是怎么put的？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。