Hashmap非線程安全關于hash值沖突怎么處理

本篇內容主要講解“Hashmap非線程安全關于hash值沖突怎么處理”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Hashmap非線程安全關于hash值沖突怎么處理”吧!

hash值沖突該怎么處理

都知道它是基于hash值，可以進行常量時間消化的存儲結構。廣泛用于各種情況下的高效key-value存儲。這里有幾個問題。首先，如果出現hash值沖突該怎么處理？相信很多人都不用思考就能說出，通過鏈表來解決沖突。就是將hash值相同值存儲到一個掛載在該位置的鏈表里面去。但是這就又引出了新的問題，給一個key，它的hash值有沖突的情況下，它是如何在鏈表上取到你所期望的value的？這個就要去看hashmap的存儲結構了。每一個key-value會被封裝到一個entity中，map中存儲的其實是這個entity。這樣既存儲了value，又存儲了key。所有在鏈表上取值只需要比較key是否equal。這里又出現了一個問題，為什么建議重寫key的equal和hash方法。重寫hash方法能夠保證不同對象用于不同的hash值，從而減少沖突，重寫equal則可以在出現沖突的情況下，保證不出現錯誤覆蓋的情況。

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)//沒有初始化，則要初始化，初始化調用的也是resize（）方法
            n = (tab = resize()).length; 
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);//這個位置沒有值，直接插入，重寫hash方法的作用體現在這里
        else {//出現了沖突
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))//找到了如該key equal的value
                e = p;
            else if (p instanceof TreeNode)//事樹節點，插入到樹里。jdk8沖突節點數目達到一定值后，使用樹結構存儲
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {//一直找到鏈表的結尾，將k-v插入
                    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;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

上面的代碼充分表明了key重寫equal的作用。HashMap以key的value來獲取值，所以一定要確保同一個key的hashcode在任何時候都不能改變。這也是為什么建議key是不可變對象，如string對象。如果key是對象，運行過程中key的hashcode因為內部值的改變而發生了改變，那么map中的value將永遠丟失。

非線程安全體現

以上是關于kv的討論，接下來是關于HashMap的另外的一個常見話題——線程安全問題。多數人都知道它是非線程安全的。但是如果問你它非線程安全體現在哪里，恐怕會難住一批人。

首先容易想到的是多線程插入時出現了沖突的情況，多個線程同時插入，但是這其中有些值又出現了沖突。插入時大家都看到這個位置沒有值，于是都進行插入，這樣肯定會出現值覆蓋，對外的表現就是值丟失。如果開始插入時，這個位置已經有了值，那么在插入鏈表過程中還是會出現值覆蓋。

另外就是同時擴容問題。因為HashMap會在空間不足時自動擴容，大小變成之前的兩倍。同時復制之前的值到新的數組中。沖突鏈也會進行復制。如果多個線程插入后同時看到容量需要調整，就都會調用resize方法。那么底層到達會出現什么問題就難以預測了。

所以這也是HashMap非線程安全的第二點體現。當然同時讀寫一個值也可能會存在數據跟期望不一致的情況。這也是非線程安全的表現。

到此，相信大家對“Hashmap非線程安全關于hash值沖突怎么處理”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！