HashMap

介紹

HashMap是一個以鍵值對形式保存數(shù)據(jù)的結構，實現(xiàn)了Map接口搭综，可以接受null的鍵值，內(nèi)部沒有做同步處理划栓，內(nèi)部將key的hash值兑巾，key，hash忠荞，next(下一個結點)蒋歌，包裹在一個對象中進行保存；

HashMap的工作原理

我們使用put(key,value)方法往HashMap中添加元素時钻洒，先計算得到key的Hash值奋姿，然后通過Key高16位與低16位相異或（高16位不變），然后與數(shù)組大小-1相與素标，得到了該元素在數(shù)組中的位置称诗；

如果數(shù)組中該位置為空，則直接放入头遭，如果不為空（出現(xiàn)了Hash沖突）寓免，則接到以數(shù)組該位置為鏈頭的鏈表中；

在Java8中计维，鏈表的長度超過8袜香，則使用紅黑樹來替換鏈表，以提高查找速度鲫惶；

使用get從HashMap中讀取元素時蜈首，先通過同樣的方法計算Key在數(shù)組中的下標，再通過key的equals()方法來查找對應的元素欠母；如果該位置是一個鏈表欢策，則查找的速度為O(n)，如果該位置是紅黑樹赏淌，查找的時間復雜度為O(logN)踩寇；

如果HashMap的數(shù)組使用量超過了一個閾值（負載因子，默認0.75）六水，HashMap將會resize俺孙，即重新開辟一個原來數(shù)組長度兩倍的HashMap，并重新計算位置掷贾；

相關問題

1. 為什么在resize的時候是擴展為原數(shù)組大小的兩倍睛榄？

   擴展為兩倍是為了方便重新確定元素在數(shù)組中的位置，當擴展為兩倍時想帅，數(shù)組的大小在二進制中就相當于在高位多了一位懈费，重新得到的位置要不就是在原位置，要不就是原位置加上原數(shù)組大小的位置博脑；

   因為index的計算是通過元素的hash與數(shù)組大小-1相與憎乙，數(shù)組大小-1在高位多了一位，則只需要在原來的hash的高位多取一位就是元素的index叉趣，這一位有可能是0泞边，有可能是1，是0的時候元素的位置不變疗杉，是1的時候位置相當于加了原始數(shù)組大小的位置阵谚；

   同時可以認為新增的那一位的值是隨機的，也就是可以均勻地把元素分布在新的數(shù)組中烟具；

   舉例：

   數(shù)組的大小是16： 0000 0000 0000 0000 0000 0000 0001 0000

   則數(shù)組大小減一是：0000 0000 0000 0000 0000 0000 0000 1111

   擴容后數(shù)組大小是：0000 0000 0000 0000 0000 0000 0010 0000

   數(shù)組大小減一是： 0000 0000 0000 0000 0000 0000 0001 1111

   假設元素的hash是：1111 1111 1111 1111 0000 1111 0001 0101

   原始的元素位置為：0101梢什，即為5

   擴容后的位置是：1 0101，為5 + 16 = 21

   以下是擴容的代碼（僅截取了為鏈表的部分）：

   if (oldTab != null) {
       for (int j = 0; j < oldCap; ++j) {
           Node<K,V> e;
           if ((e = oldTab[j]) != null) {
               //從原始數(shù)組中取出頭結點
               oldTab[j] = null;
               //如果只有一個元素朝聋，計算出新的位置并放置
               if (e.next == null)
                   newTab[e.hash & (newCap - 1)] = e;
               //結點是樹的情況    
               else if (e instanceof TreeNode)
                   ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
               else { // preserve order
                   //將該位置的元素分成兩部分嗡午，一部分為增加的一位是1的(hi)，一部分為增加的一位是0的(lo)
                   Node<K,V> loHead = null, loTail = null;
                   Node<K,V> hiHead = null, hiTail = null;
                   Node<K,V> next;
                   do {
                       next = e.next;   // mark
                       //增加的一位是0
                       if ((e.hash & oldCap) == 0) {
                           //構造鏈表
                           if (loTail == null)
                               loHead = e;
                           else
                               loTail.next = e;
                           loTail = e;
                       }
                       //增加的一位是1
                       else {
                           if (hiTail == null)
                               hiHead = e;
                           else
                               hiTail.next = e;
                           hiTail = e;
                       }
                   } while ((e = next) != null);
                   //對增加的一位是0的元素進行處理
                   if (loTail != null) {
                       loTail.next = null;
                       //放置的位置為原始位置
                       newTab[j] = loHead;
                   }
                   //對增加的一位是1的元素進行處理
                   if (hiTail != null) {
                       hiTail.next = null;
                       //放置的位置為原始位置加上原始數(shù)組大小
                       newTab[j + oldCap] = hiHead;
                   }
               }
           }
       }
   }
   

2. 在計算index時為什么要高16位與低16位異或冀痕？

   設計者為了提高在計算index時的效率荔睹，沒有采用取余（%）的方式計算index，而是采用了位運算言蛇，通過hash與數(shù)組大小-1（數(shù)組大小總是為 ）相與(&)得到僻他；

   但是這樣在數(shù)組較小的情況下容易產(chǎn)生Hash沖突，數(shù)組大小為16時腊尚，參與運算的只有hash的末尾4位吨拗，一共就只有15個值；

   所以在綜合考慮了速度和質(zhì)量的情況下讓高16位也參與運算婿斥，在保證效率的同時一定程度上降低了Hash沖突出現(xiàn)的可能性劝篷；

3. HashMap是線程安全的嗎？

   不是受扳，在兩個線程同時put時會出現(xiàn)線程A的元素覆蓋線程B元素的問題;

   假設根據(jù)線程A携龟，B想要插入的元素的Key，計算得到的在數(shù)組中的index相同勘高；A線程先拿到了在那個index的鏈尾元素的引用峡蟋，這時線程A的時間片用完；線程B執(zhí)行华望，并成功地插入了元素蕊蝗，之后線程A繼續(xù)執(zhí)行，于是將鏈尾元素的引用指向了自己的元素赖舟，線程B的元素就被拋棄掉了蓬戚，造成了線程A對線程B結果的覆蓋；