1. 首頁 > 生活百科 > >

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

生活百科

五、源碼分析之常用方法解讀1、tableSizeFor方法解讀/** * 返回給定目標容量的 2 次方 。*/static final int tableSizeFor(int cap) { // cap = 10int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;// 小于0就是1，如果大于0在判斷是不是超過最大容量就是n=15+1 = 16，超過就按最大容量return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}以cap為10為例：（右移規則為：無符號位右移）
10的二進制為：0000 0000 0000 0000 0000 0000 0000 1010
執行int n = cap - 1;
二進制結果為：0000 0000 0000 0000 0000 0000 0000 1001
執行n |= n >>> 1;（先進行右移，結果和原來的數進行或運算[==有1則1==]）
0000 0000 0000 0000 0000 0000 0000 10010000 0000 0000 0000 0000 0000 0000 0100n>>1結果————————————————————0000 0000 0000 0000 0000 0000 0000 1101n |= n >> 1 結果
二進制結果為：0000 0000 0000 0000 0000 0000 0000 1101
執行n |= n >>> 2;
0000 0000 0000 0000 0000 0000 0000 1101
0000 0000 0000 0000 0000 0000 0000 0011n>>2結果
————————————————————0000 0000 0000 0000 0000 0000 0000 1111n |= n >> 2 結果
二進制結果為：0000 0000 0000 0000 0000 0000 0000 1111
執行n |= n >>> 4;
0000 0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0000 0000n>>4結果
————————————————————0000 0000 0000 0000 0000 0000 0000 1111n |= n >> 4 結果
二進制結果為：0000 0000 0000 0000 0000 0000 0000 1111
執行n |= n >>> 8;
0000 0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0000 0000n>>8結果
————————————————————0000 0000 0000 0000 0000 0000 0000 1111n |= n >> 8 結果
二進制結果為：0000 0000 0000 0000 0000 0000 0000 1111
執行n |= n >>> 16;
0000 0000 0000 0000 0000 0000 0000 1111
0000 0000 0000 0000 0000 0000 0000 0000n>>16結果
————————————————————0000 0000 0000 0000 0000 0000 0000 1111n |= n >> 16 結果
二進制結果為：0000 0000 0000 0000 0000 0000 0000 1111
我們會發現，當數小的的時候進行到4時就不會變了我們得到的值為15 ， 即輸入10 ， 經過此方法后得到15 。遇到大的數才會明顯，大家可以找個大的數字進行試試就是先右移在進行或運算 。最后進行三門運算進行+1操作，最后結果為16=2^4
2、hash方法解讀static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}先判斷key是否為空 ， 若為空則返回0 。上面說了HashMap僅支持一個key為null的 。若非空 ， 則先計算key的hashCode值 ， 賦值給h ， 然后把h右移16位，并與原來的h進行異或處理（相同為1，不同為0） 。注釋進行谷歌翻譯：計算 key.hashCode() 并傳播（XOR）更高位的哈希降低 。由于該表使用二次冪掩碼，因此僅在當前掩碼之上位變化的散列集將始終發生沖突 。（已知的例子是在小表中保存連續整數的 Float 鍵集 。）因此，我們應用了一種變換，將高位的影響向下傳播 。在位擴展的速度、實用性和質量之間存在折衷 。因為許多常見的散列集已經合理分布（所以不要從傳播中受益），并且因為我們使用樹來處理 bin 中的大量沖突，我們只是以最簡單的方式對一些移位的位進行異或，以減少系統損失， 以及合并最高位的影響 ， 否則由于表邊界，這些最高位將永遠不會用于索引計算 。
總結：使用最簡易的方式，及減少系統損失又減少了hash碰撞 。
3、put方法解讀

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

文章插圖
/*** 將指定的值與此映射中的指定鍵相關聯 。即當前key應該存放在數組的哪個下標位置* 如果映射先前包含鍵的映射，則替換舊的值 。*/public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}/*** 這才是真正的保存方法* @param hash經過hash運算后的key* @param key你要添加的key* @param value你要添加的value* @param onlyIfAbsent如果為真，則不要更改現有值，本次為FALSE，可以替換更改* @param evict如果為 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是否為空if ((tab = table) == null || (n = tab.length) == 0)// 如果空的話 ， 會先調用resize擴容,resize我們后面展開講解n = (tab = resize()).length;// 把通過hash得到的值與數組大小-1進行與運算，這個運算就可以實現取模運算，而且位運算還有個好處，就是速度比較快 。// 得到key所對應的數組的節點，然后把該數組節點賦值給p,然后判斷這個位置是不是有元素if ((p = tab[i = (n - 1) & hash]) == null)// key、value包裝成newNode節點，直接添加到此位置 。tab[i] = newNode(hash, key, value, null);// 如果當前數組下標位置已經有元素了，又分為三種情況 。else {Node<K,V> e; K k;// 當前位置元素的hash值等于傳過來的hash，并且他們的key值也相等if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// 則把p賦值給e，后續需要新值把舊值替換e = p;// 來到這里說明該節點的key與原來的key不同，則看該節點是紅黑樹 ， 還是鏈表else if (p instanceof TreeNode)// 如果是紅黑樹 ， 則通過紅黑樹的方式，把key-value存到紅黑樹中 。后面再講解這個方法e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {// 來到這里說明結構為鏈表，把key-value使用尾插法插到鏈表尾 。// jdk1.7 鏈表是頭插入法，在并發擴容時會造成死循環// jdk1.8 就把頭插入法換成了尾插入法，雖然效率上有點稍微降低一些，但是不會出現死循環for (int binCount = 0; ; ++binCount) {// 遍歷該鏈表，知道知道下一個節點為null 。if ((e = p.next) == null) {// 說明到鏈表尾部，然后把尾部的next指向新生成的對象p.next = newNode(hash, key, value, null);// 如果鏈表的長度大于等于8if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st// 則鏈表轉化成為紅黑樹 后面再補充treeifyBin(tab, hash);break;}// 如果在鏈表中找到了相同key的話，直接退出循環if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 說明發生了碰撞，e代表的是舊值，需要替換為新值if (e != null) { // existing mapping for keyV oldValue = https://www.huyubaike.com/biancheng/e.value;// 判斷是不是允許覆蓋舊值 ， 和舊值是否為空if (!onlyIfAbsent || oldValue == null)// 把舊值替換e.value = value;// hashmap沒有任何實現 ， 我們先不考慮afterNodeAccess(e);// 返回新值return oldValue;}}// fail-fast機制每次對結構改變進行+1++modCount;// 判斷HashMap中的存的數據大?。?如果大于數組長度*0.75 ， 就要進行擴容if (++size > threshold)resize();// 也是一個空的實現afterNodeInsertion(evict);return null;}

推薦閱讀