前言

總是覺(jué)得對(duì)HashMap很熟悉，但最近連續(xù)被問(wèn)到幾個(gè)關(guān)于它的問(wèn)題，才發(fā)現(xiàn)它其實(shí)并不簡(jiǎn)單。這里對(duì)關(guān)于它的一些問(wèn)題做個(gè)總結(jié)，也希望能夠大家一個(gè)參考。

hash值沖突該怎么處理

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

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)//沒(méi)有初始化，則要初始化，初始化調(diào)用的也是resize（）方法
            n = (tab = resize()).length; 
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);//這個(gè)位置沒(méi)有值，直接插入，重寫(xiě)hash方法的作用體現(xiàn)在這里
        else {//出現(xiàn)了沖突
            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)//事樹(shù)節(jié)點(diǎn)，插入到樹(shù)里。jdk8沖突節(jié)點(diǎn)數(shù)目達(dá)到一定值后，使用樹(shù)結(jié)構(gòu)存儲(chǔ)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {//一直找到鏈表的結(jié)尾，將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);//是否需要改成樹(shù)存儲(chǔ)
                        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重寫(xiě)equal的作用。HashMap以key的value來(lái)獲取值，所以一定要確保同一個(gè)key的hashcode在任何時(shí)候都不能改變。這也是為什么建議key是不可變對(duì)象，如string對(duì)象。如果key是對(duì)象，運(yùn)行過(guò)程中key的hashcode因?yàn)閮?nèi)部值的改變而發(fā)生了改變，那么map中的value將永遠(yuǎn)丟失。

非線程安全體現(xiàn)

以上是關(guān)于kv的討論，接下來(lái)是關(guān)于HashMap的另外的一個(gè)常見(jiàn)話題——線程安全問(wèn)題。多數(shù)人都知道它是非線程安全的。但是如果問(wèn)你它非線程安全體現(xiàn)在哪里，恐怕會(huì)難住一批人。

首先容易想到的是多線程插入時(shí)出現(xiàn)了沖突的情況，多個(gè)線程同時(shí)插入，但是這其中有些值又出現(xiàn)了沖突。插入時(shí)大家都看到這個(gè)位置沒(méi)有值，于是都進(jìn)行插入，這樣肯定會(huì)出現(xiàn)值覆蓋，對(duì)外的表現(xiàn)就是值丟失。如果開(kāi)始插入時(shí)，這個(gè)位置已經(jīng)有了值，那么在插入鏈表過(guò)程中還是會(huì)出現(xiàn)值覆蓋。

另外就是同時(shí)擴(kuò)容問(wèn)題。因?yàn)镠ashMap會(huì)在空間不足時(shí)自動(dòng)擴(kuò)容，大小變成之前的兩倍。同時(shí)復(fù)制之前的值到新的數(shù)組中。沖突鏈也會(huì)進(jìn)行復(fù)制。如果多個(gè)線程插入后同時(shí)看到容量需要調(diào)整，就都會(huì)調(diào)用resize方法。那么底層到達(dá)會(huì)出現(xiàn)什么問(wèn)題就難以預(yù)測(cè)了。

所以這也是HashMap非線程安全的第二點(diǎn)體現(xiàn)。當(dāng)然同時(shí)讀寫(xiě)一個(gè)值也可能會(huì)存在數(shù)據(jù)跟期望不一致的情況。這也是非線程安全的表現(xiàn)。

以上就是HashMap的一些相關(guān)問(wèn)題。個(gè)人體會(huì)還是需要注重細(xì)節(jié)，自己看源碼，才會(huì)有更深入的體會(huì)。

更多關(guān)于Hashmap非線程安全的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論