HashMap的性能瓶頸

今天問到了 HashMap

沒回答好

再總結一下

隻總結我沒有注意的部分

并不完整

解決哈希沖突

開放定址法、再哈希函數法和鍊位址法

我隻想起來 hashMap 預設的 鍊位址法 不過還好 沒把這個忘了 基本牌還是有的

開放定址

開放定址法很簡單，當發生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那麼可以把 key 存放到沖突位置後面的空位置上去。這種方法存在着很多缺點，例如，查找、擴容等，是以我不建議你作為解決哈希沖突的首選。

再哈希

再哈希法顧名思義就是在同義詞産生位址沖突時再計算另一個哈希函數位址，直到沖突不再發生，這種方法不易産生 “聚集”，但卻增加了計算時間。如果我們不考慮添加元素的時間成本，且對查詢元素的要求極高，就可以考慮使用這種算法設計。

鍊位址法

HashMap 則是綜合考慮了所有因素，采用鍊位址法解決哈希沖突問題。這種方法是采用了數組（哈希表）+ 連結清單的資料結構，當發生哈希沖突時，就用一個連結清單結構存儲相同 Hash 值的資料。

HashMap 引入了紅黑樹資料

這是因為連結清單的長度超過 8 後，紅黑樹的查詢效率要比連結清單高，是以當連結清單超過 8 時，HashMap 就會将連結清單轉換為紅黑樹，這裡值得注意的一點是，這時的新增由于存在左旋、右旋效率會降低。

講到這裡，我前面我提到的 “因連結清單過長而導緻的查詢時間複雜度高” 的問題，也就迎刃而解了。

新增由于存在左旋、右旋效率會降低。 這個點 沒有注意到 以後要記得講

PUT源碼

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)
//1、判斷當table為null或者tab的長度為0時，即table尚未初始化，此時通過resize()方法得到初始化的table
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
//1.1、此處通過（n - 1） & hash 計算出的值作為tab的下标i，并另p表示tab[i]，也就是該連結清單第一個節點的位置。并判斷p是否為null
            tab[i] = newNode(hash, key, value, null);
//1.1.1、當p為null時，表明tab[i]上沒有任何元素，那麼接下來就new第一個Node節點，調用newNode方法傳回新節點指派給tab[i]
        else {
//2.1下面進入p不為null的情況，有三種情況：p為連結清單節點；p為紅黑樹節點；p是連結清單節點但長度為臨界長度TREEIFY_THRESHOLD，再插入任何元素就要變成紅黑樹了。
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
//2.1.1HashMap中判斷key相同的條件是key的hash相同，并且符合equals方法。這裡判斷了p.key是否和插入的key相等，如果相等，則将p的引用賦給e

                e = p;
            else if (p instanceof TreeNode)
//2.1.2現在開始了第一種情況，p是紅黑樹節點，那麼肯定插入後仍然是紅黑樹節點，是以我們直接強制轉型p後調用TreeNode.putTreeVal方法，傳回的引用賦給e
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
//2.1.3接下裡就是p為連結清單節點的情形，也就是上述說的另外兩類情況：插入後還是連結清單/插入後轉紅黑樹。另外，上行轉型代碼也說明了TreeNode是Node的一個子類
                for (int binCount = 0; ; ++binCount) {
//我們需要一個計數器來計算目前連結清單的元素個數，并周遊連結清單，binCount就是這個計數器

                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) 
// 插入成功後，要判斷是否需要轉換為紅黑樹，因為插入後連結清單長度加1，而binCount并不包含新節點，是以判斷時要将臨界門檻值減1
                            treeifyBin(tab, hash);
//當新長度滿足轉換條件時，調用treeifyBin方法，将該連結清單轉換為紅黑樹
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
           

編碼優化點 這個 好像答出來了 我說 hashcode 需要占cpu資源

在編碼中也可以優化 HashMap 的性能，例如，重寫 key 值的 hashCode() 方法，降低哈希沖突，進而減少連結清單的産生，高效利用哈希表，達到提高性能的效果。

擴容優化

這個點 忘了 應該 注意 這個是重點

1.7采用數組+單連結清單，1.8在單連結清單超過一定長度後改成紅黑樹存儲

1.7擴容時需要重新計算哈希值和索引位置，1.8并不重新計算哈希值，巧妙地采用和擴容後容量進行&操作來計算新的索引位置。

1.7插入元素到單連結清單中采用頭插入法，1.8采用的是尾插入法。

循環連結清單問題

HashMap在jdk1.7中采用頭插入法，在擴容時會改變連結清單中元素原本的順序，以至于在并發場景下導緻連結清單成環的問題。而在jdk1.8中采用尾插入法，在擴容時會保持連結清單元素原本的順序，就不會出現連結清單成環的問題了。

JDK1.7 頭插法 容易出循環連結清單問題

在 JDK1.7 中，HashMap 整個擴容過程就是分别取出數組元素，一般該元素是最後一個放傳入連結表中的元素，然後周遊以該元素為頭的單向連結清單元素，依據每個被周遊元素的 hash 值計算其在新數組中的下标，然後進行交換。這樣的擴容方式會将原來哈希沖突的單向連結清單尾部變成擴容後單向連結清單的頭部。

JDK1.8 尾插發不會出現