HashMap解析(主要JDK1.8,附帶1.7出現的問題以及區別)

按問題的形式來吧,這些大多是我自己總結的,如有錯誤請及時指正謝謝

1.你了解HashMap么,可以說說么?

  首先,HashMap是一種數據結構,可以快速的幫我們存取數據。它的底層數據結構在1.7和1.8有了一些變化,1.7版本及以前他是數組+鏈表的形式,1.8及以後數組+鏈表+紅黑樹,如果鏈表長度大於等於8就會轉化為紅黑樹,如果長度降至6紅黑樹會轉化為鏈表紅黑樹的出現解決了因為鏈表過長導致查詢速度變慢的問題,因為鏈表的查詢時間複雜度是O(n),而紅黑樹的查詢時間複雜度是O(logn)。

2.它的數組+鏈表是怎麼實現的?

  

 

 

 這個代碼是1.8的(1.7是Entry,就是名字不一樣),其實我們每一個放進去的(key,value)到最後都會封裝成這樣的Node對象。Hashmap的數組就是以一系列這樣的Node對象構成的數組,鏈表就是把next指向下一個Node對象。

 

 

3.為什麼要有鏈表,紅黑樹?只有數組不可以么?

首先我們要知道什麼是Hash算法。

這裏放出一段官方的話:

 

Hash,一般翻譯做散列、雜湊,或音譯為哈希,是把任意長度的輸入(又叫做預映射pre-image)通過散列算法變換成固定長度的輸出,該輸出就是散列值。這種轉換是一種壓縮映射,也就是,散列值的空間通常遠小於輸入的空間,不同的輸入可能會散列成相同的輸出,所以不可能從散列值來確定唯一的輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

 

簡單點來說:就是把一個大数字經過運算變為固定範圍的輸出,最簡單的算法就是對你的數組長度取模。

但是這樣就會出現一個問題,你這麼算難免會出現算出來的数字是一樣的:

比如數組長度為16,我們要放入数字1和17,那麼他們經過對數組長度取模后位置是一樣的,這樣就產生了Hash衝突。我們就可以在數組下拉出一個鏈表去存儲這個数字

4.知道哪些常見的解決hash衝突算法么?

1、開放定址法(就是往下找空餘地方)
     用開放定址法解決衝突的做法是:當衝突發生時,使用某種探查(亦稱探測)技術在散列表中形成一個探查(測)序列。沿此序列逐個單元地查找,直到找到給定 的關鍵字,或者碰到一個開放的地址(即該地址單元為空)為止(若要插入,在探查到開放的地址,則可將待插入的新結點存人該地址單元)。查找時探查到開放的 地址則表明表中無待查的關鍵字,即查找失敗。

2、 再哈希法(再進行hash直到無衝突)
再哈希法又叫雙哈希法,有多個不同的Hash函數,當發生衝突時,使用第二個,第三個,….,等哈希函數
計算地址,直到無衝突。雖然不易發生聚集,但是增加了計算時間。

3、拉鏈法(hashmap用的)

鏈地址法的基本思想是:每個哈希表節點都有一個next指針,多個哈希表節點可以用next指針構成一個單向鏈表,被分配到同一個索引上的多個結點用單向鏈表連接起來

4、建立公共溢出區: 
這種方法的基本思想是:將哈希表分為基本表和溢出表兩部分,凡是和基本表發生衝突的元素,一律填入溢出表

5.為什麼閾值就是8和6呢?中間的7是有什麼作用的呢?直接就是紅黑樹不可以么?

HashMap中有這樣一段註釋(主要看数字):

/* * Because TreeNodes are about twice the size of regular nodes, we * use them only when 鏈表s 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 鏈表s. In * usages with well-distributed user hashCodes, tree 鏈表s are * rarely used. Ideally, under random hashCodes, the frequency of * nodes in 鏈表s 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 */

TreeNodes佔用空間是普通Nodes的兩倍(相較於鏈表結構,鏈表只有指向下一個節點的指針,二叉樹則需要左右指針,分別指向左節點和右節點),所以只有當鏈表包含足夠多的節點時才會轉成TreeNodes(考慮到時間和空間的權衡),而是否足夠多就是由TREEIFY_THRESHOLD的值決定的。當紅黑樹中節點數變少時,又會轉成普通的鏈表。並且我們查看源碼的時候發現,鏈表長度達到8就轉成紅黑樹,當長度降到6就轉成普通鏈表。

這樣就解釋了為什麼不是一開始就將其轉換為TreeNodes,而是需要一定節點數才轉為TreeNodes,說白了就是trade-off,空間和時間的權衡。

當hashCode離散性很好的時候,樹型鏈表用到的概率非常小,因為數據均勻分佈在每個鏈表中,幾乎不會有鏈表中鏈表長度會達到閾值。但是在隨機hashCode下,離散性可能會變差,然而JDK又不能阻止用戶實現這種不好的hash算法,因此就可能導致不均勻的數據分佈。不過理想情況下隨機hashCode算法下所有鏈表中節點的分佈頻率會遵循泊松分佈,我們可以看到,一個鏈表中鏈表長度達到8個元素的概率為0.00000006,幾乎是不可能事件。這種不可能事件都發生了,說明鏈表中的節點數很多,查找起來效率不高。至於7,是為了作為緩衝,可以有效防止鏈表和樹頻繁轉換。

之所以選擇8,不是拍拍屁股決定的,而是根據概率統計決定的。由此可見,發展30年的Java每一項改動和優化都是非常嚴謹和科學的。

泊松分佈適合於描述單位時間(或空間)內隨機事件發生的次數。如某一服務設施在一定時間內到達的人數,電話交換機接到呼叫的次數,汽車站台的候客人數,機器出現的故障數,自然災害發生的次數,一塊產品上的缺陷數,顯微鏡下單位分區內的細菌分佈數等等。如果有興趣的,可以研究一下,概率是怎麼算出來的!

個人總結:

  1. 選擇8是因為空間和時間的權衡,再一個是因為鏈表中節點的分佈頻率會遵循泊松分佈,達到8的概率很小
  2. 選擇7是為了作為緩衝,可以有效防止鏈表和樹頻繁轉換
  3. 你的紅黑樹查詢時間複雜度低,但你的維持平衡的操作代價是大的,所以不會直接是紅黑樹(這一點是個人理解)

6.HashMap的初始容量,加載因子,擴容增量是多少?如果加載因子變大變小會怎麼樣?

HashMap的初始容量16,加載因子為0.75,擴容增量是原容量的1倍。如果HashMap的容量為16,一次擴容后容量為32。HashMap擴容是指元素個數(包括數組和鏈表+紅黑樹中)超過了16*0.75=12(容量×加載因子)之後開始擴容。

這個就是源碼里的聲明

//默認初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //最大容量
static final int MAXIMUM_CAPACITY = 1 << 30; //加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

加載因子越大,填滿的元素越多,空間利用率越高,但衝突的機會加大了。
反之,加載因子越小,填滿的元素越少,衝突的機會減小,但空間浪費多了(因為需要經常擴容)。

所以這是一個時間和空間的均衡。

7. 如果我默認初始大小為100,那麼元素個數到達75會擴容么?

這個問題我以前見到過,所以拿出來說一下。

首先HashMap的構造方法有四個

    public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
  
  public HashMap(Map<!--? extends K, ? extends V--> m) {       this.loadFactor = DEFAULT_LOAD_FACTOR;       putMapEntries(m, false);   }  

簡單點來說就是你可以自定義加載因子和初始容量。但是這個初始容量不是說你設置多少就是多少,他是會有個計算的,到最後Hashmap的容量一定是2的n次方

 

 

 簡單說一下putMapEntries

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { //獲取該map的實際長度
        int s = m.size(); if (s > 0) { //判斷table是否初始化,如果沒有初始化
            if (table == null) { // pre-size
                /**求出需要的容量,因為實際使用的長度=容量*0.75得來的,+1是因為小數相除,基本都不會是整數,容量大小不能為小數的,後面轉換為int,多餘的小數就要被丟掉,所以+1,例如,map實際長度22,22/0.75=29.3,所需要的容量肯定為30,有人會問如果剛剛好除得整數呢,除得整數的話,容量大小多1也沒什麼影響**/
                float ft = ((float)s / loadFactor) + 1.0F; //判斷該容量大小是否超出上限。
                int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); /**對臨界值進行初始化,tableSizeFor(t)這個方法會返回大於t值的,且離其最近的2次冪,例如t為29,則返回的值是32**/
                if (t > threshold) threshold = tableSizeFor(t); } //如果table已經初始化,則進行擴容操作,resize()就是擴容。
            else if (s > threshold) resize(); //遍歷,把map中的數據轉到hashMap中。
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } }

 

所以說這個答案就是不會擴容的,因為你初始它的容量是100,tableSizeFor也會自動變成128,128×0.75是93遠遠大於75.

8. HashMap中為什麼數組的長度為2的冪次方?

主要是為了計算hash值時散列性更好。

我們看一下HashMap的數組下標如何計算的

 

// 將(數組的長度-1)和hash值進行按位與操作:
i = (n - 1) & hash  // i為數組對應位置的索引 n為當前數組的大小

假定HashMap的長度為默認的16,則n – 1為15,也就是二進制的01111

可以說,Hash算法最終得到的index結果完全取決於hashCode的最後幾位。

那麼說為什麼別的数字不行呢?

假設,HashMap的長度為10,則n-1為9,也就是二進制的1001

我們來試一個hashCode:1110時,通過Hash算法得到的最終的index是8

 

再比如說:1000得到的index也是8。

也就是說,即使我們把倒數第二、三位的0、1變換,得到的index仍舊是8,說明有些index結果出現的幾率變大!

這樣,顯然不符合Hash算法均勻分佈的要求。

反觀,長度16或其他2的冪次方,Length – 1的值的二進制所有的位均為1,這種情況下,Index的結果等於hashCode的最後幾位。只要輸入的hashCode本身符合均勻分佈,Hash算法的結果就是均勻的。

一句話,HashMap的長度為2的冪次方的原因是為了減少Hash碰撞,盡量使Hash算法的結果均勻分佈。

9.put方法

在講解put方法之前,先看看hash方法,看怎麼計算哈希值的。

    static final int hash(Object key) { int h; /**先獲取到key的hashCode,然後進行移位再進行異或運算,為什麼這麼複雜,不用想肯定是為了減少hash衝突**/
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

put方法實際調用了putVal方法

    public V put(K key, V value) { /**四個參數,第一個hash值,第四個參數表示如果該key存在值,如果為null的話,則插入新的value,最後一個參數,在hashMap中沒有用,可以不用管,使用默認的即可**/
        return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //tab 哈希數組,p 該哈希桶的首節點,n hashMap的長度,i 計算出的數組下標
        Node<K,V>[] tab; Node<K,V> p; int n, i; //獲取長度並進行擴容,使用的是懶加載,table一開始是沒有加載的,等put后才開始加載
        if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; /**如果計算出的該哈希桶的位置沒有值,則把新插入的key-value放到此處,此處就算沒有插入成功,也就是發生哈希衝突時也會把哈希桶的首節點賦予p**/
        if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //發生哈希衝突的幾種情況
        else { // e 臨時節點的作用, k 存放該當前節點的key 
            Node<K,V> e; K k; //第一種,插入的key-value的hash值,key都與當前節點的相等,e = p,則表示為首節點
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //第二種,hash值不等於首節點,判斷該p是否屬於紅黑樹的節點
            else if (p instanceof TreeNode) /**為紅黑樹的節點,則在紅黑樹中進行添加,如果該節點已經存在,則返回該節點(不為null),該值很重要,用來判斷put操作是否成功,如果添加成功返回null**/ e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //第三種,hash值不等於首節點,不為紅黑樹的節點,則為鏈表的節點
            else { //遍歷該鏈表
                for (int binCount = 0; ; ++binCount) { //如果找到尾部,則表明添加的key-value沒有重複,在尾部進行添加
                    if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //判斷是否要轉換為紅黑樹結構
                        if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } //如果鏈表中有重複的key,e則為當前重複的節點,結束循環
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //有重複的key,則用待插入值進行覆蓋,返回舊值。
            if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } //到了此步驟,則表明待插入的key-value是沒有key的重複,因為插入成功e節點的值為null //修改次數+1
        ++modCount; //實際長度+1,判斷是否大於臨界值,大於則擴容
        if (++size > threshold) resize(); afterNodeInsertion(evict); //添加成功
        return null; }

大概如下幾步:

①. 判斷鍵值對數組table[i]是否為空或為null,否則執行resize()進行擴容,初始容量是16;

②. 根據鍵值key計算hash值得到插入的數組索引i,如果table[i]==null,直接新建節點添加,轉向⑥,如果table[i]不為空,轉向③;

③. 判斷table[i]的首個元素是否和key一樣,如果相同直接覆蓋value,否則轉向④,這裏的相同指的是hashCode以及equals;

④. 判斷table[i] 是否為TreeNode,即table[i] 是否是紅黑樹,如果是紅黑樹,遍歷發現該key不存在  則直接在樹中插入鍵值對;遍歷發現key已經存在直接覆蓋value即可;

⑤. 如果table[i] 不是TreeNode則是鏈表節點,遍歷發現該key不存在,則先添加在鏈表結尾, 判斷鏈表長度是否大於8,大於8的話把鏈錶轉換為紅黑樹;遍歷發現key已經存在直接覆蓋value即可;

⑥. 插入成功后,判斷實際存在的鍵值對數量size是否超多了最大容量threshold,如果超過,進行擴容。

10.resize方法

何時進行擴容?

HashMap使用的是懶加載,構造完HashMap對象后,只要不進行put 方法插入元素之前,HashMap並不會去初始化或者擴容table。

當首次調用put方法時,HashMap會發現table為空然後調用resize方法進行初始化
,當添加完元素后,如果HashMap發現size(元素總數)大於threshold(閾值),則會調用resize方法進行擴容

    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table; //old的長度
        int oldCap = (oldTab == null) ? 0 : oldTab.length; //old的臨界值
        int oldThr = threshold; //初始化new的長度和臨界值
        int newCap, newThr = 0; //oldCap > 0也就是說不是首次初始化,因為hashMap用的是懶加載
        if (oldCap > 0) { //大於最大值
            if (oldCap >= MAXIMUM_CAPACITY) { //臨界值為整數的最大值
                threshold = Integer.MAX_VALUE; return oldTab; } //標記##,其它情況,擴容兩倍,並且擴容后的長度要小於最大值,old長度也要大於16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //臨界值也擴容為old的臨界值2倍
                newThr = oldThr << 1; } /**如果oldCap<0,但是已經初始化了,像把元素刪除完之後的情況,那麼它的臨界值肯定還存在, 如果是首次初始化,它的臨界值則為0 **/
        else if (oldThr > 0) newCap = oldThr; //首次初始化,給與默認的值
        else { newCap = DEFAULT_INITIAL_CAPACITY; //臨界值等於容量*加載因子
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //此處的if為上面標記##的補充,也就是初始化時容量小於默認值16的,此時newThr沒有賦值
        if (newThr == 0) { //new的臨界值
            float ft = (float)newCap * loadFactor; //判斷是否new容量是否大於最大值,臨界值是否大於最大值
            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
        table = newTab; //此處自然是把old中的元素,遍歷到new中
        if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { //臨時變量
                Node<K,V> e; //當前哈希桶的位置值不為null,也就是數組下標處有值,因為有值表示可能會發生衝突
                if ((e = oldTab[j]) != null) { //把已經賦值之後的變量置位null,當然是為了好回收,釋放內存
                    oldTab[j] = null; //如果下標處的節點沒有下一個元素
                    if (e.next == null) //把該變量的值存入newCap中,e.hash & (newCap - 1)並不等於j
                        newTab[e.hash & (newCap - 1)] = e; //該節點為紅黑樹結構,也就是存在哈希衝突,該哈希桶中有多個元素
                    else if (e instanceof TreeNode) //把此樹進行轉移到newCap中
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { /**此處表示為鏈表結構,同樣把鏈錶轉移到newCap中,就是把鏈表遍歷后,把值轉過去,在置位null**/ 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; } } } } } //返回擴容后的hashMap
        return newTab; }

其實主要就是兩步:1.創建新的數組 2.複製元素

但是在新的下標位置計算上1.8做了很大的優化,後面會說到。

11.get方法

    public V get(Object key) { Node<K,V> e; 9 //調用getNode方法來完成的
        return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { //first 頭結點,e 臨時變量,n 長度,k key
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //頭結點也就是數組下標的節點
        if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //如果是頭結點,則直接返回頭結點
            if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) return first; //不是頭結點
            if ((e = first.next) != null) { //判斷是否是紅黑樹結構
                if (first instanceof TreeNode) //去紅黑樹中找,然後返回
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { //鏈表節點,一樣遍歷鏈表,找到該節點並返回
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } //找不到,表示不存在該節點
        return null; }

主要就是利用equals和hashcode方法找到並返回

12.HashMap在JDK1.7和1.8除了數據結構的區別

(1)插入數據方式不同:

JDK1.7用的是頭插法,而JDK1.8及之後使用的都是尾插法,那麼他們為什麼要這樣做呢?因為JDK1.7認為最新插入的應該會先被用到,所以用了頭插法,但當採用頭插法時會容易出現逆序且環形鏈表死循環問題。但是在JDK1.8之後是因為加入了紅黑樹使用尾插法,能夠避免出現逆序且鏈表死循環的問題。

  說一下為什麼會產生死循環問題:

  問題出現在了這個移動元素的transfer方法里

  

 主要問題就出在了這行代碼上

Entry<K,V> next = e.next

如果兩個線程A,B都要對這個map進行擴容

A和B都已經創建了新的數組,假設線程A在執行到Entry < K,V > next = e.next之後,cpu時間片用完了,這時變量e指向節點a,變量next指向節點b。

此時A的狀態:e=a ,next=b

線程B繼續執行,很不巧,a、b、c節點rehash之後又是在同一個位置,開始移動節點, 因為頭插法,複製后順序是反的,結束后B的狀態:

 

 

 此時A開始執行,此時變量e指向節點a,變量next指向節點b,開始執行循環體的剩餘邏輯

if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next;

執行到

newTable[i] = e;

此時A的狀態

 

執行到

e = next;

 

此時e=b

再執行一波循環,Entry<K,V> next = e.next 但是此時b的next是a,就出現了死循環問題

 

 

(2)擴容后數據存儲位置的計算方式也不一樣:

在JDK1.7的時候是重新計算數組下標

而在JDK1.8的時候直接用了JDK1.7的時候計算的規律,也就是擴容前的原始位置+擴容的大小值=JDK1.8的計算方式,而不再是JDK1.7的那種異或的方法。但是這種方式就相當於只需要判斷Hash值的新增參与運算的位是0還是1就直接迅速計算出了擴容后的儲存方式。

就比如說:數組大小是4,hash算法是對長度取模

 

 擴容后是這樣的

我們可以把這三個數的二進制和擴容后的length-1進行按位與,可以看到只有数字5新增位為1

 

 

 

 因此,我們在擴充HashMap的時候,不需要像JDK1.7的實現那樣重新計算hash,只需要看看原來的hash值新增的那個bit是1還是0就好了,是0的話索引沒變,是1的話索引變成“原索引+oldCap”

(3)擴容的條件不同,1.7需要容量超過閾值且發生hash衝突,1.8超過閾值即會擴容

(4)JDK1.7的時候是先進行擴容後進行插入,而在JDK1.8的時候則是先插入後進行擴容

(5)1.8中沒有區分鍵為null的情況,而1.7版本中對於鍵為null的情況調用putForNullKey()方法。但是兩個版本中如果鍵為null,那麼調用hash()方法得到的都將是0,所以鍵為null的元素都始終位於哈希表table【0】中。

(6)jdk1.7中當哈希表為空時,會先調用inflateTable()初始化一個數組;而1.8則是直接調用resize()擴容

(7)jdk1.7中的hash函數對哈希值的計算直接使用key的hashCode值,而1.8中則是採用key的hashCode異或上key的hashCode進行無符號右移16位的結果,避免了只靠低位數據來計算哈希時導致的衝突,計算結果由高低位結合決定,使元素分佈更均勻

13、HashMap是線程安全的么?如果想線程安全怎麼辦?

不是線程安全的,多線程下會出現死循環和put操作時可能導致元素丟失

死循環原因:上邊已經分析過了

丟失原因:當多個線程同時執行addEntry(hash,key ,value,i)時,如果產生哈希碰撞,導致兩個線程得到同樣的bucketIndex去存儲,就可能會發生元素覆蓋丟失的情況

 

想實現線程安全的解決方法:

1.使用Hashtable 類,Hashtable 是線程安全的(不建議用,就是利用了synchronized進行加鎖);

2.使用併發包下的java.util.concurrent.ConcurrentHashMap,ConcurrentHashMap實現了更高級的線程安全;

3.或者使用synchronizedMap() 同步方法包裝 HashMap object,得到線程安全的Map,並在此Map上進行操作。

 

參考:

https://blog.csdn.net/m0_37914588/article/details/82287191

https://www.jianshu.com/p/7cf2d6f1096b

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※教你寫出一流的銷售文案?

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※回頭車貨運收費標準

※別再煩惱如何寫文案,掌握八大原則!

※超省錢租車方案

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※推薦台中搬家公司優質服務,可到府估價

您可能也會喜歡…