1. 首頁 > 生活百科 > >

HashMap底層原理及jdk1.8源碼解讀( 三 )

生活百科

4、resize方法解讀看不清查看原鏈接：高清圖鏈接

HashMap底層原理及jdk1.8源碼解讀

文章插圖
/** * 初始化或者是將table大小加倍,如果為空，則按threshold分配空間，* 否則加倍后，每個容器中的元素在新table中要么呆在原索引處，要么有一個2的次冪的位移 */final Node<K,V>[] resize() { // 原來的數據Node<K,V>[] oldTab = table;// 獲取原來的數組大小int oldCap = (oldTab == null) ? 0 : oldTab.length;// 舊數組的擴容閾值，注意看，這里取的是當前對象的 threshold 值，下邊的第2種情況會用到 。int oldThr = threshold;// 初始化新數組的容量和閾值int newCap, newThr = 0;// 1.當舊數組的容量大于0時，說明在這之前肯定調用過 resize擴容過一次，才會導致舊容量不為0 。if (oldCap > 0) {// 容量達到最大if (oldCap >= MAXIMUM_CAPACITY) {// 擴容的大小設置為上限threshold = Integer.MAX_VALUE;// 直接返回默認原來的，無法在擴了return oldTab;}// 如果舊容量是在16到上限之間else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 新數組的容量和閾值都擴大原來的2倍newThr = oldThr << 1; // double threshold}// 2. 到這里 oldCap <= 0，oldThr(threshold) > 0，這就是 map 初始化的時候，// 第一次調用 resize的情況else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;// 3. 到這里 ， 說明 oldCap 和 oldThr 都是小于等于0的 。也說明我們的map是通過默認無參構造來創建的else {// zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;// 16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);// 12}// 只有經過2.才會進入if (newThr == 0) {float ft = (float)newCap * loadFactor;// 把計算后的ft符合大?。?則賦值newThrnewThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 最后得到要擴容的大小threshold = newThr;// 用于抑制編譯器產生警告信息@SuppressWarnings({"rawtypes","unchecked"})// 在構造函數時，并沒有創建數組，在第一次調用put方法，導致resize的時候 ， 才會把數組創建出來 。// 這是為了延遲加載 ， 提高效率 。Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;// 判斷原來的數組有沒有值，如果沒有則把剛剛創建的數組進行返回if (oldTab != null) {// 便利舊數組for (int j = 0; j < oldCap; ++j) {Node<K,V> e;// 判斷當前元素是否為空if ((e = oldTab[j]) != null) {oldTab[j] = null;// 如果第一個元素的下一個元素為null，說明鏈表只有一個if (e.next == null)// 則直接用它的hash值和新數組的容量取模就行(這樣運算效率高)，得到新的下標位置newTab[e.hash & (newCap - 1)] = e;// 如果是紅黑樹else if (e instanceof TreeNode)// 則拆分紅黑樹，這個小編就不帶著往下深究了,感興趣可以自己點進去看看((TreeNode<K,V>)e).split(this, newTab, j, oldCap);// 說明是鏈表且長度大于1else { // preserve order// 鏈表舊位置的頭尾節點Node<K,V> loHead = null, loTail = null;// 鏈表新位置的頭尾節點Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;// 這里小編不太明白了，只能參考大佬的講解 ， 還是有點懵逼，等有時間懂了再來重新梳理do {next = e.next;// 如果當前元素的hash值和oldCap做與運算為0，則原位置不變if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}// 不為0則把數據移動到新位置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;}5、get和containsKey方法解讀/*** 根據key獲取對應的value*/public V get(Object key) {Node<K,V> e;// 調用后存在就獲取元素的value返回return (e = getNode(hash(key), key)) == null ? null : e.value;}/*** 判斷key是否在map中存在*/public boolean containsKey(Object key) { // 調用方法存在及不為nullreturn getNode(hash(key), key) != null;}/*** 我們發現底層都是getNode來進行干活的*/final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// 判斷數組不能為空 ， 然后取到當前hash值計算出來的下標位置的第一個元素if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 如果hash值和key都相等并不為null，則說明我們要找的就是第一個元素if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))// 返回第一個元素return first;// 如果不是第一個就接著往下找if ((e = first.next) != null) {// 如果是紅黑樹if (first instanceof TreeNode)// 則以紅黑樹的查找方式進行獲取到我們想要的key對應的值return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 這里說明為普通鏈表，我們依次往下找即可do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}// 找不到key對應的值，返回nullreturn null;}

推薦閱讀