<input id="ohw05"></input>
  • <table id="ohw05"><menu id="ohw05"></menu></table>
  • <var id="ohw05"></var>
  • <code id="ohw05"><cite id="ohw05"></cite></code>
    <label id="ohw05"></label>
    <var id="ohw05"></var>
  • 一文精通HashMap靈魂七問,你學還是不學

    如果讓你看一篇文章,就可以精通HashMap,成為硬剛才面試官的高手,你學還是不學?

    別著急,開始之前不如先嘗試回來下面幾個問題吧:

    HashMap的底層結構是什么?

    什么時候HashMap中的鏈表會轉化為紅黑樹?

    為什么當鏈表長度超過8個時候會轉化成紅黑樹?這為什么是8個而不是3個呢?

    HashMap是線程安全的嘛?

    HashMap為什么是線程不安全的?有哪些具體體現?

    ConcurrentHashMap和HashTable是如何實現線程安全的呢?有何不同呢?

    一、HashMap底層結構是什么樣的?

    HashMap底層是數組+鏈表+紅黑樹組成的復合結構。

    數組被分為一個個的桶(bucket),通過哈希值決定鍵值對在數組中存儲的位置;

    當鍵值對的哈希值相同,則以鏈表形式存儲;

    當鏈表長度大于或等于閾值(默認為 8)的時候,如果同時還滿足容量大于或等于 MIN_TREEIFY_CAPACITY(默認為 64)的要求,就會把鏈表轉換為紅黑樹。同樣,后續如果刪除了元素,當紅黑樹的節點小于或等于 6 個以后,又會恢復為鏈表。

    HashMap 的結構示意圖:

    二、為什么需要將鏈表轉化為紅黑樹呢?

    因為紅黑樹有和鏈表不一樣的查找性能。從鏈表中查找一個元素,時間復雜度是 O(n)。而從紅黑樹查找,由于紅黑樹有自平衡的特點,可以防止不平衡情況的發生,所以時間復雜是 O(log(n))。如果鏈表長度較短,O(n) 和 O(log(n)) 的區別不大,但是如果鏈表較長,那么這種差異就會很明顯了。所以為了提升HashMap查找性能,在鏈表長度超過閾值的時候將鏈表轉化為紅黑樹進行存儲。

    三、既然紅黑樹查找性能優于鏈表,那為什么不在一開始就使用紅黑樹呢?而是要經歷一個轉換的過程呢?

    世上本沒有“銀彈”,紅黑樹也不是“銀彈”。單個 TreeNode 需要占用的空間大約是普通鏈表Node 的兩倍,所以只有當包含足夠多的 Nodes 時才會轉成 TreeNodes,而是否足夠多就是由 TREEIFY_THRESHOLD 的值決定的。而當桶中節點數由于移除或者 resize 變少后,又會變回普通的鏈表的形式,以便節省空間。

    這其實是一種tradeoff,指的是一種取舍、一種權衡,最后達成折中平衡。在HashMap里面,如果要性能就需要犧牲空間,要空間就要犧牲性能,魚與熊掌不可兼得,最后達成折中方案:鏈表加紅黑樹,在適當情況下進行轉化。

    四、為什么鏈表轉化為紅黑樹的這個閾值要默認設置為 8 呢?

    如果 hashCode 分布良好,也就是哈希算法足夠好,計算出來的哈希值散離散程度高,那么很少出現哈希沖突和鏈表很長的情況,紅黑樹這種形式也就很少會被用到。在理想情況下,鏈表長度符合泊松分布,各個長度的命中概率依次遞減,當長度為 8 的時候,概率僅為 0.00000006。這是一個小于千萬分之一的概率,通常我們的 Map 里面是不會存儲這么多的數據的,所以通常情況下,并不會發生從鏈表向紅黑樹的轉換。請看源碼(本文源碼均為Java8版本)注釋:

    * Because TreeNodes are about twice the size of regular nodes, we
    * use them only when bins contain enough nodes to warrant use
    * (see TREEIFY_THRESHOLD). And when they become too small (due to
    * removal or resizing) they are converted back to plain bins.  In
    * usages with well-distributed user hashCodes, tree bins are
    * rarely used.  Ideally, under random hashCodes, the frequency of
    * nodes in bins follows a Poisson distribution
    * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
    * parameter of about 0.5 on average for the default resizing
    * threshold of 0.75, although with a large variance because of
    * resizing granularity. Ignoring variance, the expected
    * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
    * factorial(k)). The first values are:
    *
    * 0:    0.60653066
    * 1:    0.30326533
    * 2:    0.07581633
    * 3:    0.01263606
    * 4:    0.00157952
    * 5:    0.00015795
    * 6:    0.00001316
    * 7:    0.00000094
    * 8:    0.00000006
    * more: less than 1 in ten million
    

    如果在調試過程中發現HashMap中的鏈表結構經常轉換為紅黑樹進行存儲,那么這時候應該注意下哈希函數是不是出現問題了。

    五、對比一下Hashtable、HashMap、TreeMap 有什么不同?

    Hashtable、HashMap、TreeMap 都是最常見的Map實現,是以鍵值對的形式存儲和操作數據的容器類型。

    Hashtable 是早期 Java 類庫提供的一個哈希表實現,本身是同步的,不支持 null 鍵和值,由于同步導致的性能開銷,所以已經不建議使用。

    HashMap 是目前最常用的哈希表實現,與 HashTable 的主要區別在于: HashMap 不是同步的,支持 null 鍵和值等。通常情況下,HashMap 進行 put 或者 get 操作,可以達到常數時間的性能,所以它是絕大部分利用鍵值對存取場景的首選。

    TreeMap 則是基于紅黑樹的一種提供順序訪問的 Map,和 HashMap 不同,它的 get、put、remove 之類操作都是 O(log(n))的時間復雜度,如果有排序的訴求可以選擇使用。

    六、HashMap為什么是線程不安全的?具體有哪些體現?

    put方法中的++modCount

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    /**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    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)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            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);
                        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;
    }
    

    ++modCount ++size看似一行代碼,但是該操作并不能保證原子性,實際上是分三個步驟執行的,會存在并發問題。modCount這個參數在HashMap中表述HashMap內部結果改變的次數,例如rehash。如果++modCount發生并發問題,會拋出ConcurrentModificationException。

    在put方法中,通過比較++size和threshold的大小判斷是否進行擴容操作,如果++size發生并發問題,可能使得HashMap在應該擴容的時候未進行擴容,導致put操作的時候元素插入失敗或者丟失。

    /**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     */
    transient int modCount;
    

    擴容期間取出來值不準確

    HashMap 默認初始容量為16,如果不停地往 map 中添加新的數據,當元素個數大于負載因子容量大小的時候,會進行擴容,擴至原來的2倍。
    newThr = oldThr << 1

    在擴容期間,它會新建一個新的空數組,并且將老數組中的元素重新放置到新數組中。那么,在這個填充的過程中,如果有線程獲取值,很可能會取到 null 值。

    同時put導致數據丟失

    比如,有多個線程同時使用 put 方法來添加元素,而且恰好兩個 put 的 key 的哈希值是一樣的,計算出來的 bucket 位置一樣,并且兩個線程又同時判斷該位置是空的,可以寫入,所以這兩個線程的兩個不同的 value 便會添加到數組的同一個位置,這樣最終就只會保留一個數據,丟失一個數據。

    死循環造成CPU100%

    該問題是多線程同時擴容的時候鏈表死循環而引起的CPU100%問題。可參考:https://coolshell.cn/articles/9606.html

    七、同樣是線程安全的,ConcurrentHashMap和Hashtable有什么區別?ConcurrentHashMap在Java7 和Java8又有何不同?

    雖然 ConcurrentHashMap 和 Hashtable 它們兩個都是線程安全的,但是從原理上分析,Hashtable 實現并發安全的原理是通過 synchronized 關鍵字實現的。

    ConcurrentHashMap在Java7中是通過Segment實現線程安全的,在Java8是通過Node + CAS + synchronized實現的。

    Java7中的ConcurrentHashMap最外層是多個Segment,每個Segment的底層數據結構與HashMap類似,仍然是數組加鏈表組成。

    Java8中的ConcurrentHashMap依然是數組+ 鏈表+ 紅黑樹的方式實現的,結構和HashMap一致。

    ConcurrentHashMap在Java7 和Java8的對比如下:

    Java7 Java8
    數據結構 Segment + 數組+鏈表 數組+鏈表+紅黑樹
    并發原理 Segment Node + CAS + synchronized
    并發度 Segment個數,默認16 數組長度
    Hash沖突 拉鏈法 拉鏈法+紅黑樹

    如果看完有幫忙,能不能幫我點個贊呢?

    posted @ 2022-06-26 12:24  James_Shangguan  閱讀(177)  評論(0編輯  收藏  舉報
    国产美女a做受大片观看