Java中HashMap的案例分析

這篇文章給大家分享的是有關Java中HashMap的案例分析的內容。小編覺得挺實用的，因此分享給大家做個參考。一起跟隨小編過來看看吧。

HashMap 是數組和鏈表組合組成的復雜結構，哈希值決定了鍵值在數組的位置，當哈希值相同時則以鏈表形式存儲，當鏈表長度到達設定的閾值則會對其進行樹化，這樣做是為了保證數據安全和數據相關操作的效率

HashMap 性能表現取決于哈希碼的有效性，所以 hashCode 和 equals 的基本約定規則尤為重要，如：equals 相等，hashCode 一定要相等；重寫了 hashCode 也要重寫 equals；hashCode 需要保持一致性，狀態改變返回的哈希值仍然要一致；equals 的對稱、反射、傳遞等特性

HashMap 與 Hashtable、TreeMap 的區別

HashMap：基于數組的非同步哈希表，支持 null 鍵或值，是鍵值對存取數據場景的首選

Hashtable：基于數組的同步哈希表，不支持null鍵或值，因為同步導致性能影響，很少被使用

TreeMap：基于紅黑樹提供順序訪問的 Map，比 HashMap 節省空間，但它的數據操作（查、增、刪）時間復雜度均為：O（log(n)），這點與 HashMap 不同。支持空值，當鍵為空時且未實現 Comparator 接口，會出現 NullPointerException ，實現了 Comparator 接口并對 null 對象進行判斷可實現正常存入

HashMap、Hashtable、TreeMap 均以鍵值對形式存儲或操作數據元素。HashMap、TreeMap 繼承自 AbstractMap 類，Hashtable 繼承自 Dictionary 類，三者均實現 Map 接口

HashMap 源碼解析

HashMap()

public HashMap(int initialCapacity, float loadFactor){  
    // ... 
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

初始化 HashMap 時僅設置了一些初始值，但在開始處理數據時，如 .put() 方法內漸漸開始復雜起來

HashMap.put()

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    	// 定義新tab數組及node對象
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 如果原table是空的或者未存儲任何元素則需要先初始化進行tab的初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 當數組中對應位置為null時，將新元素放入數組中
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        // 若對應位置不為空時處理哈希沖突
        else {
            Node<K,V> e; K k;
            // 1 - 普通元素判斷： 更新數組中對應位置數據
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 2 - 紅黑樹判斷：當p為樹的節點時，向樹內插入節點
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 3 - 鏈表判斷：插入節點
            else {
                for (int binCount = 0; ; ++binCount) {
                	// 找到尾結點并插入
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 判斷鏈表長度是否達到樹化閾值，達到就對鏈表進行樹化
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        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;
                // 判斷是否允許覆蓋，并且value是否為空
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 回調以允許LinkedHashMap后置操作
                afterNodeAccess(e); 
                return oldValue;
            }
        }
        // 更新修改次數
        ++modCount;
        // 檢查數組是否需要進行擴容
        if (++size > threshold)
            resize();
        // 回調以允許LinkedHashMap后置操作
        afterNodeInsertion(evict);
        return null;
    }

當 table 為 null，會通過 resize() 初始化，且 resize() 有兩個作用，一是創建并初始化 table ，二是在 table 容量不滿足需求時進行擴容：

        if (++size > threshold)
            resize();

具體的鍵值對存儲位置計算方法為：

        if ((p = tab[i = (n - 1) & hash]) == null)
            // 向數組賦值新元素
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            // 如果新插入的結點和table中p結點的hash值，key值相同的話
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 如果是紅黑樹結點的話，進行紅黑樹插入
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    // 代表這個單鏈表只有一個頭部結點，則直接新建一個結點即可
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 鏈表長度大于8時，將鏈表轉紅黑樹
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 及時更新p
                    p = e;
                }
            }
            // 如果存在這個映射就覆蓋
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                // 判斷是否允許覆蓋，并且value是否為空
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);     // 回調以允許LinkedHashMap后置操作
                return oldValue;
            }
        }

留意 .put() 方法中的 hash 計算，它并不是 key 的 hashCode ，而是將 key 的 hashCode 高位數據移位到低位進行異或運算，這樣一些計算出來的哈希值主要差異在高位時的數據，就不會因 HashMap 里哈希尋址時被忽略容量以上的高位，那么即可有效避免此類情況下的哈希碰撞

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

HashMap.resize()

    final Node<K,V>[] resize() {
    	// 把當前底層數組賦值給oldTab，為數據遷移工作做準備
        Node<K,V>[] oldTab = table;
        // 獲取當前數組的大小，等于或小于0表示需要初始化數組，大于0表示需要擴容數組
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 獲取擴容的閾值（容量*負載系數）
        int oldThr = threshold;
        // 定義并初始化新數組長度和目標閾值
        int newCap, newThr = 0;
        // 判斷是初始化數組還是擴容，等于或小于0表示需要初始化數組，大于0表示需要擴容數組。若  if(oldCap > 0)=true 表示需擴容而非初始化
        if (oldCap > 0) {
        	// 判斷數組長度是否已經是最大，MAXIMUM_CAPACITY =（2^30）
            if (oldCap >= MAXIMUM_CAPACITY) {
            	// 閾值設置為最大
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)            	
            	// 目標閾值擴展2倍，數組長度擴展2倍
                newThr = oldThr << 1; // double threshold
        }
        // 表示需要初始化數組而不是擴容
        else if (oldThr > 0) 
        	// 說明調用的是HashMap的有參構造函數，因為無參構造函數并沒有對threshold進行初始化
            newCap = oldThr;
        // 表示需要初始化數組而不是擴容，零初始閾值表示使用默認值
        else {	
        	// 說明調用的是HashMap的無參構造函數
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 計算目標閾值
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 當目標閾值為0時需重新計算，公式：容量（newCap）*負載系數（loadFactor）
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 根據以上計算結果將閾值更新
        threshold = newThr;
        // 將新數組賦值給底層數組
        @SuppressWarnings({"rawtypes","unchecked"})
            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;
                // 將數組內此下標中的數據賦值給Node類型的變量e，并判斷非空
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 1 - 普通元素判斷：判斷數組內此下標中是否只存儲了一個元素，是的話表示這是一個普通元素，并開始轉移
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    // 2 - 紅黑樹判斷：判斷此下標內是否是一顆紅黑樹，是的話進行數據遷移
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // 3 -  鏈表判斷：若此下標內包含的數據既不是普通元素又不是紅黑樹，則它只能是一個鏈表，進行數據轉移
                    else { // preserve order
                        Node<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;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.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;
    }

容量和負載系數決定了數組容量，空余太多會造成空間浪費，使用太滿會影響操作性能

如果能夠明確知道 HashMap 將要存取的鍵值對的數量，可以考慮預先設置合適的容量大小。具體數值我們可以根據擴容發生的條件來做簡單預估，根據前面的代碼分析，我們知道它需要符合計算條件：負載因子 * 容量 > 元素數量

所以，預先設置的容量需要滿足，大于 預估元素數量 / 負載因子，同時它是 2 的冪數

但需要注意的是：

如果沒有特別需求，不要輕易進行更改，因為 JDK 自身的默認負載因子是非常符合通用場景的需求的。如果確實需要調整，建議不要設置超過 0.75 的數值，因為會顯著增加沖突，降低 HashMap 的性能。如果使用太小的負載因子，按照上面的公式，預設容量值也進行調整，否則可能會導致更加頻繁的擴容，增加無謂的開銷，本身訪問性能也會受影響。

HashMap.get()

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 將table賦值給變量tab并判斷非空 && tab 的廠部大于0 && 通過位運算得到求模結果確定鏈表的首節點賦值并判斷非空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
        	// 判斷首節點hash值 && 判斷key的hash值（地址相同 || equals相等）均為true則表示first即為目標節點直接返回
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 若首節點非目標節點，且還有后續節點時，則繼續向后尋找
            if ((e = first.next) != null) {
            	// 1 - 樹：判斷此節點是否為樹的節點，是的話遍歷樹結構查找節點，查找結果可能為null
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 2 - 鏈表：若此節點非樹節點，說明它是鏈表，遍歷鏈表查找節點，查找結果可能為null
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

HashMap 為什么會被樹化

為了保證數據安全及相關操作效率

因為在元素放置過程中，如果一個對象哈希沖突，都被放置到同一個桶里，則會形成一個鏈表，我們知道鏈表查詢是線性的，會嚴重影響存取的性能

而在現實世界，構造哈希沖突的數據并不是非常復雜的事情，惡意代碼就可以利用這些數據大量與服務器端交互，導致服務器端 CPU 大量占用，這就構成了哈希碰撞拒絕服務攻擊，國內一線互聯網公司就發生過類似攻擊事件

感謝各位的閱讀！關于Java中HashMap的案例分析就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！