本篇內(nèi)容介紹了“HashMap底層原理是什么”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

包河網(wǎng)站制作公司哪家好，找成都創(chuàng)新互聯(lián)！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、APP開(kāi)發(fā)、響應(yīng)式網(wǎng)站設(shè)計(jì)等網(wǎng)站項(xiàng)目制作，到程序開(kāi)發(fā)，運(yùn)營(yíng)維護(hù)。成都創(chuàng)新互聯(lián)成立與2013年到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來(lái)保證我們的工作的順利進(jìn)行。專(zhuān)注于網(wǎng)站建設(shè)就選成都創(chuàng)新互聯(lián)。

HashMap存儲(chǔ)結(jié)構(gòu)

這里需要區(qū)分一下，JDK1.7和 JDK1.8之后的 HashMap 存儲(chǔ)結(jié)構(gòu)。在JDK1.7及之前，是用數(shù)組加鏈表的方式存儲(chǔ)的。

但是，眾所周知，當(dāng)鏈表的長(zhǎng)度特別長(zhǎng)的時(shí)候，查詢效率將直線下降，查詢的時(shí)間復(fù)雜度為 O(n)。因此，JDK1.8  把它設(shè)計(jì)為達(dá)到一個(gè)特定的閾值之后，就將鏈表轉(zhuǎn)化為紅黑樹(shù)。

這里簡(jiǎn)單說(shuō)下紅黑樹(shù)的特點(diǎn)：

• 每個(gè)節(jié)點(diǎn)只有兩種顏色：紅色或者黑色

• 根節(jié)點(diǎn)必須是黑色

• 每個(gè)葉子節(jié)點(diǎn)(NIL)都是黑色的空節(jié)點(diǎn)

• 從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，不能出現(xiàn)兩個(gè)連續(xù)的紅色節(jié)點(diǎn)

• 從任一節(jié)點(diǎn)出發(fā)，到它下邊的子節(jié)點(diǎn)的路徑包含的黑色節(jié)點(diǎn)數(shù)目都相同

由于紅黑樹(shù)，是一個(gè)自平衡的二叉搜索樹(shù)，因此可以使查詢的時(shí)間復(fù)雜度降為O(logn)。(紅黑樹(shù)不是本文重點(diǎn)，不了解的童鞋可自行查閱相關(guān)資料哈)

HashMap 結(jié)構(gòu)示意圖：

常用的變量

在 HashMap源碼中，比較重要的常用變量，主要有以下這些。還有兩個(gè)內(nèi)部類(lèi)來(lái)表示普通鏈表的節(jié)點(diǎn)和紅黑樹(shù)節(jié)點(diǎn)。

//默認(rèn)的初始化容量為16，必須是2的n次冪 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16  //最大容量為 2^30 static final int MAXIMUM_CAPACITY = 1 << 30;  //默認(rèn)的加載因子0.75，乘以數(shù)組容量得到的值，用來(lái)表示元素個(gè)數(shù)達(dá)到多少時(shí)，需要擴(kuò)容。 //為什么設(shè)置 0.75 這個(gè)值呢，簡(jiǎn)單來(lái)說(shuō)就是時(shí)間和空間的權(quán)衡。 //若小于0.75如0.5，則數(shù)組長(zhǎng)度達(dá)到一半大小就需要擴(kuò)容，空間使用率大大降低， //若大于0.75如0.8，則會(huì)增大hash沖突的概率，影響查詢效率。 static final float DEFAULT_LOAD_FACTOR = 0.75f;  //剛才提到了當(dāng)鏈表長(zhǎng)度過(guò)長(zhǎng)時(shí)，會(huì)有一個(gè)閾值，超過(guò)這個(gè)閾值8就會(huì)轉(zhuǎn)化為紅黑樹(shù) static final int TREEIFY_THRESHOLD = 8;  //當(dāng)紅黑樹(shù)上的元素個(gè)數(shù)，減少到6個(gè)時(shí)，就退化為鏈表 static final int UNTREEIFY_THRESHOLD = 6;  //鏈表轉(zhuǎn)化為紅黑樹(shù)，除了有閾值的限制，還有另外一個(gè)限制，需要數(shù)組容量至少達(dá)到64，才會(huì)樹(shù)化。 //這是為了避免，數(shù)組擴(kuò)容和樹(shù)化閾值之間的沖突。 static final int MIN_TREEIFY_CAPACITY = 64;  //存放所有Node節(jié)點(diǎn)的數(shù)組 transient Node[] table;  //存放所有的鍵值對(duì) transient Set> entrySet;  //map中的實(shí)際鍵值對(duì)個(gè)數(shù)，即數(shù)組中元素個(gè)數(shù) transient int size;  //每次結(jié)構(gòu)改變時(shí)，都會(huì)自增，fail-fast機(jī)制，這是一種錯(cuò)誤檢測(cè)機(jī)制。 //當(dāng)?shù)系臅r(shí)候，如果結(jié)構(gòu)發(fā)生改變，則會(huì)發(fā)生 fail-fast，拋出異常。 transient int modCount;  //數(shù)組擴(kuò)容閾值 int threshold;  //加載因子 final float loadFactor;                   //普通單向鏈表節(jié)點(diǎn)類(lèi) static class Node implements Map.Entry {     //key的hash值，put和get的時(shí)候都需要用到它來(lái)確定元素在數(shù)組中的位置     final int hash;     final K key;     V value;     //指向單鏈表的下一個(gè)節(jié)點(diǎn)     Node next;      Node(int hash, K key, V value, Node next) {         this.hash = hash;         this.key = key;         this.value = value;         this.next = next;     } }  //轉(zhuǎn)化為紅黑樹(shù)的節(jié)點(diǎn)類(lèi) static final class TreeNode extends LinkedHashMap.Entry {     //當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)     TreeNode parent;     //左孩子節(jié)點(diǎn)     TreeNode left;     //右孩子節(jié)點(diǎn)     TreeNode right;     //指向前一個(gè)節(jié)點(diǎn)     TreeNode prev;    // needed to unlink next upon deletion     //當(dāng)前節(jié)點(diǎn)是紅色或者黑色的標(biāo)識(shí)     boolean red;     TreeNode(int hash, K key, V val, Node next) {         super(hash, key, val, next);     } }

HashMap 構(gòu)造函數(shù)

HashMap有四個(gè)構(gòu)造函數(shù)可供我們使用，一起來(lái)看下：

//默認(rèn)無(wú)參構(gòu)造，指定一個(gè)默認(rèn)的加載因子 public HashMap() {     this.loadFactor = DEFAULT_LOAD_FACTOR; }  //可指定容量的有參構(gòu)造，但是需要注意當(dāng)前我們指定的容量并不一定就是實(shí)際的容量，下面會(huì)說(shuō) public HashMap(int initialCapacity) {     //同樣使用默認(rèn)加載因子     this(initialCapacity, DEFAULT_LOAD_FACTOR); }  //可指定容量和加載因子，但是筆者不建議自己手動(dòng)指定非0.75的加載因子 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;     //這里就是把我們指定的容量改為一個(gè)大于它的的最小的2次冪值，如傳過(guò)來(lái)的容量是14，則返回16     //注意這里，按理說(shuō)返回的值應(yīng)該賦值給 capacity，即保證數(shù)組容量總是2的n次冪，為什么這里賦值給了 threshold 呢？     //先賣(mài)個(gè)關(guān)子，等到 resize 的時(shí)候再說(shuō)     this.threshold = tableSizeFor(initialCapacity); }  //可傳入一個(gè)已有的map public HashMap(Map m) {     this.loadFactor = DEFAULT_LOAD_FACTOR;     putMapEntries(m, false); }  //把傳入的map里邊的元素都加載到當(dāng)前map final void putMapEntries(Map m, boolean evict) {     int s = m.size();     if (s > 0) {         if (table == null) { // pre-size             float ft = ((float)s / loadFactor) + 1.0F;             int t = ((ft < (float)MAXIMUM_CAPACITY) ?                      (int)ft : MAXIMUM_CAPACITY);             if (t > threshold)                 threshold = tableSizeFor(t);         }         else if (s > threshold)             resize();         for (Map.Entry e : m.entrySet()) {             K key = e.getKey();             V value = e.getValue();             //put方法的具體實(shí)現(xiàn)，后邊講             putVal(hash(key), key, value, false, evict);         }     } }

tableSizeFor()

上邊的第三個(gè)構(gòu)造函數(shù)中，調(diào)用了 tableSizeFor 方法，這個(gè)方法是怎么實(shí)現(xiàn)的呢?

static final int tableSizeFor(int cap) {     int n = cap - 1;     n |= n >>> 1;     n |= n >>> 2;     n |= n >>> 4;     n |= n >>> 8;     n |= n >>> 16;     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

我們以傳入?yún)?shù)為14 來(lái)舉例，計(jì)算這個(gè)過(guò)程。

首先，14傳進(jìn)去之后先減1，n此時(shí)為13。然后是一系列的無(wú)符號(hào)右移運(yùn)算。

//13的二進(jìn)制 0000 0000 0000 0000 0000 0000 0000 1101 //無(wú)右移1位，高位補(bǔ)0 0000 0000 0000 0000 0000 0000 0000 0110 //然后把它和原來(lái)的13做或運(yùn)算得到，此時(shí)的n值 0000 0000 0000 0000 0000 0000 0000 1111 //再以上邊的值，右移2位 0000 0000 0000 0000 0000 0000 0000 0011 //然后和第一次或運(yùn)算之后的 n 值再做或運(yùn)算，此時(shí)得到的n值 0000 0000 0000 0000 0000 0000 0000 1111 ... //我們會(huì)發(fā)現(xiàn)，再執(zhí)行右移 4,8,16位，同樣n的值不變 //當(dāng)n小于0時(shí)，返回1，否則判斷是否大于最大容量，是的話返回最大容量，否則返回 n+1 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; //很明顯我們這里返回的是 n+1 的值， 0000 0000 0000 0000 0000 0000 0000 1111 +                                     1 0000 0000 0000 0000 0000 0000 0001 0000

將它轉(zhuǎn)為十進(jìn)制，就是 2^4 = 16 。我們會(huì)發(fā)現(xiàn)一個(gè)規(guī)律，以上的右移運(yùn)算，最終會(huì)把最低位的值都轉(zhuǎn)化為 1111 這樣的結(jié)構(gòu)，然后再加1，就是1  0000 這樣的結(jié)構(gòu)，它一定是 2的n次冪。因此，這個(gè)方法返回的就是大于當(dāng)前傳入值的最小(最接近當(dāng)前值)的一個(gè)2的n次冪的值。

put()方法詳解

//put方法，會(huì)先調(diào)用一個(gè)hash()方法，得到當(dāng)前key的一個(gè)hash值， //用于確定當(dāng)前key應(yīng)該存放在數(shù)組的哪個(gè)下標(biāo)位置 //這里的 hash方法，我們姑且先認(rèn)為是key.hashCode()，其實(shí)不是的，一會(huì)兒細(xì)講 public V put(K key, V value) {     return putVal(hash(key), key, value, false, true); }  //把hash值和當(dāng)前的key，value傳入進(jìn)來(lái) //這里onlyIfAbsent如果為true，表明不能修改已經(jīng)存在的值，因此我們傳入false //evict只有在方法 afterNodeInsertion(boolean evict) { }用到，可以看到它是一個(gè)空實(shí)現(xiàn)，因此不用關(guān)注這個(gè)參數(shù) final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                boolean evict) {     Node[] tab; Node p; int n, i;     //判斷table是否為空，如果空的話，會(huì)先調(diào)用resize擴(kuò)容     if ((tab = table) == null || (n = tab.length) == 0)         n = (tab = resize()).length;     //根據(jù)當(dāng)前key的hash值找到它在數(shù)組中的下標(biāo)，判斷當(dāng)前下標(biāo)位置是否已經(jīng)存在元素，     //若沒(méi)有，則把key、value包裝成Node節(jié)點(diǎn)，直接添加到此位置。     // i = (n - 1) & hash 是計(jì)算下標(biāo)位置的，為什么這樣算，后邊講     if ((p = tab[i = (n - 1) & hash]) == null)         tab[i] = newNode(hash, key, value, null);     else {         //如果當(dāng)前位置已經(jīng)有元素了，分為三種情況。         Node e; K k;         //1.當(dāng)前位置元素的hash值等于傳過(guò)來(lái)的hash，并且他們的key值也相等，         //則把p賦值給e，跳轉(zhuǎn)到①處，后續(xù)需要做值的覆蓋處理         if (p.hash == hash &&             ((k = p.key) == key || (key != null && key.equals(k))))             e = p;         //2.如果當(dāng)前是紅黑樹(shù)結(jié)構(gòu)，則把它加入到紅黑樹(shù)         else if (p instanceof TreeNode)             e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);         else {         //3.說(shuō)明此位置已存在元素，并且是普通鏈表結(jié)構(gòu)，則采用尾插法，把新節(jié)點(diǎn)加入到鏈表尾部             for (int binCount = 0; ; ++binCount) {                 if ((e = p.next) == null) {                     //如果頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為空，則插入新節(jié)點(diǎn)                     p.next = newNode(hash, key, value, null);                     //如果在插入的過(guò)程中，鏈表長(zhǎng)度超過(guò)了8，則轉(zhuǎn)化為紅黑樹(shù)                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                         treeifyBin(tab, hash);                     //插入成功之后，跳出循環(huán)，跳轉(zhuǎn)到①處                     break;                 }                 //若在鏈表中找到了相同key的話，直接退出循環(huán)，跳轉(zhuǎn)到①處                 if (e.hash == hash &&                     ((k = e.key) == key || (key != null && key.equals(k))))                     break;                 p = e;             }         }         //① 此時(shí)e有兩種情況         //1.說(shuō)明發(fā)生了碰撞，e代表的是舊值，因此節(jié)點(diǎn)位置不變，但是需要替換為新值         //2.說(shuō)明e是插入鏈表或者紅黑樹(shù)，成功后的新節(jié)點(diǎn)         if (e != null) { // existing mapping for key             V oldValue = e.value;             //用新值替換舊值，并返回舊值。             //oldValue為空，說(shuō)明e是新增的節(jié)點(diǎn)或者也有可能舊值本來(lái)就是空的，因?yàn)閔ashmap可存空值             if (!onlyIfAbsent || oldValue == null)                 e.value = value;             //看方法名字即可知，這是在node被訪問(wèn)之后需要做的操作。其實(shí)此處是一個(gè)空實(shí)現(xiàn)，             //只有在 LinkedHashMap才會(huì)實(shí)現(xiàn)，用于實(shí)現(xiàn)根據(jù)訪問(wèn)先后順序?qū)υ剡M(jìn)行排序，hashmap不提供排序功能             // Callbacks to allow LinkedHashMap post-actions             //void afterNodeAccess(Node p) { }             afterNodeAccess(e);             return oldValue;         }     }     //fail-fast機(jī)制     ++modCount;     //如果當(dāng)前數(shù)組中的元素個(gè)數(shù)超過(guò)閾值，則擴(kuò)容     if (++size > threshold)         resize();     //同樣的空實(shí)現(xiàn)     afterNodeInsertion(evict);     return null; }

hash()計(jì)算原理

前面 put 方法中說(shuō)到，需要先把當(dāng)前key進(jìn)行哈希處理，我們看下這個(gè)方法是怎么實(shí)現(xiàn)的。

static final int hash(Object key) {     int h;     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

這里，會(huì)先判斷key是否為空，若為空則返回0。這也說(shuō)明了hashMap是支持key傳 null  的。若非空，則先計(jì)算key的hashCode值，賦值給h，然后把h右移16位，并與原來(lái)的h進(jìn)行異或處理。為什么要這樣做，這樣做有什么好處呢?

我們知道，hashCode()方法繼承自父類(lèi)Object，它返回的是一個(gè) int  類(lèi)型的數(shù)值，可以保證同一個(gè)應(yīng)用單次執(zhí)行的每次調(diào)用，返回結(jié)果都是相同的(這個(gè)說(shuō)明可以在hashCode源碼上找到)，這就保證了hash的確定性。在此基礎(chǔ)上，再進(jìn)行某些固定的運(yùn)算，肯定結(jié)果也是可以確定的。

我隨便運(yùn)行一段程序，把它的 hashCode的二進(jìn)制打印出來(lái)，如下。

public static void main(String[] args) {     Object o = new Object();     int hash = o.hashCode();     System.out.println(hash);     System.out.println(Integer.toBinaryString(hash));  } //1836019240 //1101101011011110110111000101000

然后，進(jìn)行 (h = key.hashCode()) ^ (h >>> 16) 這一段運(yùn)算。

//h原來(lái)的值 0110 1101 0110 1111 0110 1110 0010 1000 //無(wú)符號(hào)右移16位，其實(shí)相當(dāng)于把低位16位舍去，只保留高16位 0000 0000 0000 0000 0110 1101 0110 1111 //然后高16位和原 h進(jìn)行異或運(yùn)算 0110 1101 0110 1111 0110 1110 0010 1000 ^ 0000 0000 0000 0000 0110 1101 0110 1111 = 0110 1101 0110 1111 0000 0011 0100 0111

可以看到，其實(shí)相當(dāng)于，我們把高16位值和當(dāng)前h的低16位進(jìn)行了混合，這樣可以盡量保留高16位的特征，從而降低哈希碰撞的概率。

思考一下，為什么這樣做，就可以降低哈希碰撞的概率呢?先別著急，我們需要結(jié)合 i = (n - 1) & hash 這一段運(yùn)算來(lái)理解。

** (n-1) & hash 作用**

//② //這是 put 方法中用來(lái)根據(jù)hash()值尋找在數(shù)組中的下標(biāo)的邏輯， //n為數(shù)組長(zhǎng)度， hash為調(diào)用 hash()方法混合處理之后的hash值。 i = (n - 1) & hash

我們知道，如果給定某個(gè)數(shù)值，去找它在某個(gè)數(shù)組中的下標(biāo)位置時(shí)，直接用模運(yùn)算就可以了(假設(shè)數(shù)組值從0開(kāi)始遞增)。如，我找 14  在數(shù)組長(zhǎng)度為16的數(shù)組中的下標(biāo)，即為 14 % 16，等于14 。18的位置即為 18%16，等于2。

而②中，就是取模運(yùn)算的位運(yùn)算形式。以18%16為例

//18的二進(jìn)制 0001 0010 //16 -1 即 15的二進(jìn)制 0000 1111 //與運(yùn)算之后的結(jié)果為 0000 0010 // 可以看到，上邊的結(jié)果轉(zhuǎn)化為十進(jìn)制就是 2 。 //其實(shí)我們會(huì)發(fā)現(xiàn)一個(gè)規(guī)律，因?yàn)閚是2的n次冪，因此它的二進(jìn)制表現(xiàn)形式肯定是類(lèi)似于 0001 0000 //這樣的形式，只有一個(gè)位是1，其他位都是0。而它減 1 之后的形式就是類(lèi)似于 0000 1111 //這樣的形式，高位都是0，低位都是1，因此它和任意值進(jìn)行與運(yùn)算，結(jié)果值肯定在這個(gè)區(qū)間內(nèi) 0000 0000  ~  0000 1111 //也就是0到15之間，（以n為16為例） //因此，這個(gè)運(yùn)算就可以實(shí)現(xiàn)取模運(yùn)算，而且位運(yùn)算還有個(gè)好處，就是速度比較快。

為什么高低位異或運(yùn)算可以減少哈希碰撞

我們想象一下，假如用 key 原來(lái)的hashCode值，直接和 (n-1) 進(jìn)行與運(yùn)算來(lái)求數(shù)組下標(biāo)，而不進(jìn)行高低位混合運(yùn)算，會(huì)產(chǎn)生什么樣的結(jié)果。

//例如我有另外一個(gè)h3，和原來(lái)的 h相比較，高16位有很大的不同，但是低16位相似度很高，甚至相同的話。 //原h(huán)值 0110 1101 0110 1111 0110 1110 0010 1000 //另外一個(gè)h3值 0100 0101 1110 1011 0110 0110 0010 1000 // n -1 ,即 15 的二進(jìn)制 0000 0000 0000 0000 0000 0000 0000 1111 //可以發(fā)現(xiàn) h3 和 h 的高位不相同，但是低位相似度非常高。 //他們分別和 n -1 進(jìn)行與運(yùn)算時(shí)，得到的結(jié)果卻是相同的。（此處n假設(shè)為16） //因?yàn)?nbsp;n-1 的高16位都是0，不管 h 的高 16 位是什么，與運(yùn)算之后，都不影響最終結(jié)果，高位一定全是 0 //因此，哈希碰撞的概率就大大增加了，并且 h 的高16 位特征全都丟失了。

愛(ài)思考的同學(xué)可能就會(huì)有疑問(wèn)了，我進(jìn)行高低16位混合運(yùn)算，是可以的，這樣可以保證盡量減少高區(qū)位的特征丟失。那么，為什么選擇用異或運(yùn)算呢，我用與、或、非運(yùn)算不行嗎?

這是有一定的道理的。我們看一個(gè)表格，就能明白了。

可以看到兩個(gè)值進(jìn)行與運(yùn)算，結(jié)果會(huì)趨向于0;或運(yùn)算，結(jié)果會(huì)趨向于1;而只有異或運(yùn)算，0和1的比例可以達(dá)到1:1的平衡狀態(tài)。(非呢?別扯犢子了，兩個(gè)值怎么做非運(yùn)算。。。)

所以，異或運(yùn)算之后，可以讓結(jié)果的隨機(jī)性更大，而隨機(jī)性大了之后，哈希碰撞的概率當(dāng)然就更小了。

以上，就是為什么要對(duì)一個(gè)hash值進(jìn)行高低位混合，并且選擇異或運(yùn)算來(lái)混合的原因。

resize() 擴(kuò)容機(jī)制

在上邊 put 方法中，我們會(huì)發(fā)現(xiàn)，當(dāng)數(shù)組為空的時(shí)候，會(huì)調(diào)用 resize 方法，當(dāng)數(shù)組的 size 大于閾值的時(shí)候，也會(huì)調(diào)用 resize方法。那么看下  resize 方法都做了哪些事情吧。

final Node[] resize() {     //舊數(shù)組     Node[] oldTab = table;     //舊數(shù)組的容量     int oldCap = (oldTab == null) ? 0 : oldTab.length;     //舊數(shù)組的擴(kuò)容閾值，注意看，這里取的是當(dāng)前對(duì)象的 threshold 值，下邊的第2種情況會(huì)用到。     int oldThr = threshold;     //初始化新數(shù)組的容量和閾值，分三種情況討論。     int newCap, newThr = 0;     //1.當(dāng)舊數(shù)組的容量大于0時(shí)，說(shuō)明在這之前肯定調(diào)用過(guò) resize擴(kuò)容過(guò)一次，才會(huì)導(dǎo)致舊容量不為0。     //為什么這樣說(shuō)呢，之前我在 tableSizeFor 賣(mài)了個(gè)關(guān)子，需要注意的是，它返回的值是賦給了 threshold 而不是 capacity。     //我們?cè)谶@之前，壓根就沒(méi)有在任何地方看到過(guò)，它給 capacity 賦初始值。     if (oldCap > 0) {         //容量達(dá)到了最大值         if (oldCap >= MAXIMUM_CAPACITY) {             threshold = Integer.MAX_VALUE;             return oldTab;         }         //新數(shù)組的容量和閾值都擴(kuò)大原來(lái)的2倍         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                  oldCap >= DEFAULT_INITIAL_CAPACITY)             newThr = oldThr << 1; // double threshold     }     //2.到這里，說(shuō)明 oldCap <= 0，并且 oldThr(threshold) > 0，這就是 map 初始化的時(shí)候，第一次調(diào)用 resize的情況     //而 oldThr的值等于 threshold，此時(shí)的 threshold 是通過(guò) tableSizeFor 方法得到的一個(gè)2的n次冪的值(我們以16為例)。     //因此，需要把 oldThr 的值，也就是 threshold ，賦值給新數(shù)組的容量 newCap，以保證數(shù)組的容量是2的n次冪。     //所以我們可以得出結(jié)論，當(dāng)map第一次 put 元素的時(shí)候，就會(huì)走到這個(gè)分支，把數(shù)組的容量設(shè)置為正確的值（2的n次冪)     //但是，此時(shí) threshold 的值也是2的n次冪，這不對(duì)啊，它應(yīng)該是數(shù)組的容量乘以加載因子才對(duì)。別著急，這個(gè)會(huì)在③處理。     else if (oldThr > 0) // initial capacity was placed in threshold         newCap = oldThr;     //3.到這里，說(shuō)明 oldCap 和 oldThr 都是小于等于0的。也說(shuō)明我們的map是通過(guò)默認(rèn)無(wú)參構(gòu)造來(lái)創(chuàng)建的，     //于是，數(shù)組的容量和閾值都取默認(rèn)值就可以了，即 16 和 12。     else {               // zero initial threshold signifies using defaults         newCap = DEFAULT_INITIAL_CAPACITY;         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);     }     //③ 這里就是處理第2種情況，因?yàn)橹挥羞@種情況 newThr 才為0，     //因此計(jì)算 newThr（用 newCap即16 乘以加載因子 0.75，得到 12） ，并把它賦值給 threshold     if (newThr == 0) {         float ft = (float)newCap * loadFactor;         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                   (int)ft : Integer.MAX_VALUE);     }     //賦予 threshold 正確的值，表示數(shù)組下次需要擴(kuò)容的閾值（此時(shí)就把原來(lái)的 16 修正為了 12）。     threshold = newThr;     @SuppressWarnings({"rawtypes","unchecked"})         Node[] newTab = (Node[])new Node[newCap];     table = newTab;     //如果原來(lái)的數(shù)組不為空，那么我們就需要把原來(lái)數(shù)組中的元素重新分配到新的數(shù)組中     //如果是第2種情況，由于是第一次調(diào)用resize，此時(shí)數(shù)組肯定是空的，因此也就不需要重新分配元素。     if (oldTab != null) {         //遍歷舊數(shù)組         for (int j = 0; j < oldCap; ++j) {             Node e;             //取到當(dāng)前下標(biāo)的第一個(gè)元素，如果存在，則分三種情況重新分配位置             if ((e = oldTab[j]) != null) {                 oldTab[j] = null;                 //1.如果當(dāng)前元素的下一個(gè)元素為空，則說(shuō)明此處只有一個(gè)元素                 //則直接用它的hash()值和新數(shù)組的容量取模就可以了，得到新的下標(biāo)位置。                 if (e.next == null)                     newTab[e.hash & (newCap - 1)] = e;                 //2.如果是紅黑樹(shù)結(jié)構(gòu)，則拆分紅黑樹(shù)，必要時(shí)有可能退化為鏈表                 else if (e instanceof TreeNode)                     ((TreeNode)e).split(this, newTab, j, oldCap);                 //3.到這里說(shuō)明，這是一個(gè)長(zhǎng)度大于 1 的普通鏈表，則需要計(jì)算并                 //判斷當(dāng)前位置的鏈表是否需要移動(dòng)到新的位置                 else { // preserve order                     // loHead 和 loTail 分別代表鏈表舊位置的頭尾節(jié)點(diǎn)                     Node loHead = null, loTail = null;                     // hiHead 和 hiTail 分別代表鏈表移動(dòng)到新位置的頭尾節(jié)點(diǎn)                     Node hiHead = null, hiTail = null;                     Node next;                     do {                         next = e.next;                         //如果當(dāng)前元素的hash值和oldCap做與運(yùn)算為0，則原位置不變                         if ((e.hash & oldCap) == 0) {                             if (loTail == null)                                 loHead = e;                             else                                 loTail.next = e;                             loTail = e;                         }                         //否則，需要移動(dòng)到新的位置                         else {                             if (hiTail == null)                                 hiHead = e;                             else                                 hiTail.next = e;                             hiTail = e;                         }                     } while ((e = next) != null);                     //原位置不變的一條鏈表，數(shù)組下標(biāo)不變                     if (loTail != null) {                         loTail.next = null;                         newTab[j] = loHead;                     }                     //移動(dòng)到新位置的一條鏈表，數(shù)組下標(biāo)為原下標(biāo)加上舊數(shù)組的容量                     if (hiTail != null) {                         hiTail.next = null;                         newTab[j + oldCap] = hiHead;                     }                 }             }         }     }     return newTab; }

上邊還有一個(gè)非常重要的運(yùn)算，我們沒(méi)有講解。就是下邊這個(gè)判斷，它用于把原來(lái)的普通鏈表拆分為兩條鏈表，位置不變或者放在新的位置。

if ((e.hash & oldCap) == 0) {} else {}

我們以原數(shù)組容量16為例，擴(kuò)容之后容量為32。說(shuō)明下為什么這樣計(jì)算。

還是用之前的hash值舉例。

//e.hash值 0110 1101 0110 1111 0110 1110 0010 1000 //oldCap值，即16 0000 0000 0000 0000 0000 0000 0001 0000 //做與運(yùn)算，我們會(huì)發(fā)現(xiàn)結(jié)果不是0就是非0， //而且它取決于 e.hash 二進(jìn)制位的倒數(shù)第五位是 0 還是 1， //若倒數(shù)第五位為0，則結(jié)果為0，若倒數(shù)第五位為1，則結(jié)果為非0。 //那這個(gè)和新數(shù)組有什么關(guān)系呢？ //別著急，我們看下新數(shù)組的容量是32，如果求當(dāng)前hash值在新數(shù)組中的下標(biāo)，則為 // e.hash &( 32 - 1) 這樣的運(yùn)算 ，即 hash 與 31 進(jìn)行與運(yùn)算， 0110 1101 0110 1111 0110 1110 0010 1000 & 0000 0000 0000 0000 0000 0000 0001 1111 = 0000 0000 0000 0000 0000 0000 0000 1000 //接下來(lái)，我們對(duì)比原來(lái)的下標(biāo)計(jì)算結(jié)果和新的下標(biāo)結(jié)果，看圖

看下面的圖，我們觀察，hash值和舊數(shù)組進(jìn)行與運(yùn)算的結(jié)果 ，跟新數(shù)組的與運(yùn)算結(jié)果有什么不同。

會(huì)發(fā)現(xiàn)一個(gè)規(guī)律：

若hash值的倒數(shù)第五位是0，則新下標(biāo)與舊下標(biāo)結(jié)果相同，都為 0000 1000

若hash值的倒數(shù)第五位是1，則新下標(biāo)(0001 1000)與舊下標(biāo)(0000 1000)結(jié)果值相差了 16 。

因此，我們就可以根據(jù) (e.hash & oldCap == 0) 這個(gè)判斷的真假來(lái)決定，當(dāng)前元素應(yīng)該在原來(lái)的位置不變，還是在新的位置(原位置 +  16)。

如果，上邊的推理還是不明白的話，我再舉個(gè)簡(jiǎn)單的例子。

18%16=2     18%32=18 34%16=2     34%32=2 50%16=2     50%32=18

怎么樣，發(fā)現(xiàn)規(guī)律沒(méi)，有沒(méi)有那個(gè)感覺(jué)了?

計(jì)算中的18，34 ，50 其實(shí)就相當(dāng)于 e.hash  值，和新舊數(shù)組做取模運(yùn)算，得到的結(jié)果，要么就是原來(lái)的位置不變，要么就是原來(lái)的位置加上舊數(shù)組的長(zhǎng)度。

get()方法

有了前面的基礎(chǔ)，get方法就比較簡(jiǎn)單了。

public V get(Object key) {     Node e;     //如果節(jié)點(diǎn)為空，則返回null，否則返回節(jié)點(diǎn)的value。這也說(shuō)明，hashMap是支持value為null的。     //因此，我們就明白了，為什么hashMap支持Key和value都為null     return (e = getNode(hash(key), key)) == null ? null : e.value; }  final Node getNode(int hash, Object key) {     Node[] tab; Node first, e; int n; K k;     //首先要確保數(shù)組不能為空，然后取到當(dāng)前hash值計(jì)算出來(lái)的下標(biāo)位置的第一個(gè)元素     if ((tab = table) != null && (n = tab.length) > 0 &&         (first = tab[(n - 1) & hash]) != null) {         //若hash值和key都相等，則說(shuō)明我們要找的就是第一個(gè)元素，直接返回         if (first.hash == hash && // always check first node             ((k = first.key) == key || (key != null && key.equals(k))))             return first;         //如果不是的話，就遍歷當(dāng)前鏈表（或紅黑樹(shù)）         if ((e = first.next) != null) {             //如果是紅黑樹(shù)結(jié)構(gòu)，則找到當(dāng)前key所在的節(jié)點(diǎn)位置             if (first instanceof TreeNode)                 return ((TreeNode)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);         }     }     //否則，說(shuō)明沒(méi)有找到，返回null     return null; }

為什么HashMap鏈表會(huì)形成死循環(huán)

準(zhǔn)確的講應(yīng)該是 JDK1.7 的 HashMap  鏈表會(huì)有死循環(huán)的可能，因?yàn)镴DK1.7是采用的頭插法，在多線程環(huán)境下有可能會(huì)使鏈表形成環(huán)狀，從而導(dǎo)致死循環(huán)。JDK1.8做了改進(jìn)，用的是尾插法，不會(huì)產(chǎn)生死循環(huán)。

那么，鏈表是怎么形成環(huán)狀的呢?

關(guān)于這一點(diǎn)的解釋?zhuān)野l(fā)現(xiàn)網(wǎng)上文章抄來(lái)抄去的，而且都來(lái)自左耳朵耗子，更驚奇的是，連配圖都是一模一樣的。(別問(wèn)我為什么知道，因?yàn)槲乙部催^(guò)耗子叔的文章，哈哈。然而，菜雞的我，那篇文章，并沒(méi)有看懂。。。)

我實(shí)在看不下去了，于是一怒之下，就有了這篇文章。我會(huì)照著源碼一步一步的分析變量之間的關(guān)系怎么變化的，并有配圖哦。

我們從 put()方法開(kāi)始，最終找到線程不安全的那個(gè)方法。這里省略中間不重要的過(guò)程，我只把方法的跳轉(zhuǎn)流程貼出來(lái)：

//添加元素方法 -> 添加新節(jié)點(diǎn)方法 -> 擴(kuò)容方法 -> 把原數(shù)組元素重新分配到新數(shù)組中 put()  --> addEntry()  --> resize() -->  transfer()

問(wèn)題就發(fā)生在 transfer 這個(gè)方法中。

圖1

我們假設(shè)，原數(shù)組容量只有2，其中一條鏈表上有兩個(gè)元素 A,B，如下圖

現(xiàn)在，有兩個(gè)線程都執(zhí)行 transfer 方法。每個(gè)線程都會(huì)在它們自己的工作內(nèi)存生成一個(gè)newTable  的數(shù)組，用于存儲(chǔ)變化后的鏈表，它們互不影響(這里互不影響，指的是兩個(gè)新數(shù)組本身互不影響)。但是，需要注意的是，它們操作的數(shù)據(jù)卻是同一份。

因?yàn)?，真正的?shù)組中的內(nèi)容在堆中存儲(chǔ)，它們指向的是同一份數(shù)據(jù)內(nèi)容。就相當(dāng)于，有兩個(gè)不同的引用 X，Y，但是它們都指向同一個(gè)對(duì)象 Z。這里  X、Y就是兩個(gè)線程不同的新數(shù)組，Z就是堆中的A，B 等元素對(duì)象。

假設(shè)線程一執(zhí)行到了上圖1中所指的代碼①處，恰好 CPU 時(shí)間片到了，線程被掛起，不能繼續(xù)執(zhí)行了。記住此時(shí)，線程一中記錄的 e = A ， e.next =  B。

然后線程二正常執(zhí)行，擴(kuò)容后的數(shù)組長(zhǎng)度為 4， 假設(shè) A，B兩個(gè)元素又碰撞到了同一個(gè)桶中。然后，通過(guò)幾次 while  循環(huán)后，采用頭插法，最終呈現(xiàn)的結(jié)構(gòu)如下：

此時(shí)，線程一解掛，繼續(xù)往下執(zhí)行。注意，此時(shí)線程一，記錄的還是 e = A，e.next = B，因?yàn)樗€未感知到最新的變化。

我們主要關(guān)注圖1中標(biāo)注的①②③④處的變量變化：

/** * next = e.next * e.next = newTable[i] * newTable[i] = e; * e = next; */  //第一次循環(huán),(偽代碼) e=A;next=B; e.next=null //此時(shí)線程一的新數(shù)組剛初始化完成，還沒(méi)有元素 newTab[i] = A->null //把A節(jié)點(diǎn)頭插到新數(shù)組中 e=B; //下次循環(huán)的e值

第一次循環(huán)結(jié)束后，線程一新數(shù)組的結(jié)構(gòu)如下圖：

然后，由于 e=B，不為空，進(jìn)入第二次循環(huán)。

//第二次循環(huán) e=B;next=A;  //此時(shí)A，B的內(nèi)容已經(jīng)被線程二修改為 B->A->null，然后被線程一讀到，所以B的下一個(gè)節(jié)點(diǎn)指向A e.next=A->null  // A->null 為第一次循環(huán)后線程一新數(shù)組的結(jié)構(gòu) newTab[i] = B->A->null //新節(jié)點(diǎn)B插入之后，線程一新數(shù)組的結(jié)構(gòu) e=A;  //下次循環(huán)的 e 值

第二次循環(huán)結(jié)束后，線程一新數(shù)組的結(jié)構(gòu)如下圖：

此時(shí)，由于 e=A，不為空，繼續(xù)循環(huán)。

//第三次循環(huán) e=A;next=null;  // A節(jié)點(diǎn)后邊已經(jīng)沒(méi)有節(jié)點(diǎn)了 e.next= B->A->null  // B->A->null 為第二次循環(huán)后線程一新數(shù)組的結(jié)構(gòu) //我們把A插入后，抽象的表達(dá)為 A->B->A->null，但是，A只能是一個(gè)，不能分身啊 //因此實(shí)際上是 e(A).next指向發(fā)生了變化，A的 next 由指向 null 改為指向了 B， //而 B 本身又指向A，因此A和B互相指向，成環(huán) newTab[i] = A->B 且 B->A e=next=null; //e此時(shí)為空，結(jié)束循環(huán)

第三次循環(huán)結(jié)束后，看下圖，A的指向由 null ，改為指向?yàn)?B，因此 A 和 B 之間成環(huán)。

這時(shí)，有的同學(xué)可能就會(huì)問(wèn)了，就算他們成環(huán)了，又怎樣，跟死循環(huán)有什么關(guān)系?

我們看下 get() 方法(最終調(diào)用 getEntry 方法)，

可以看到查找元素時(shí)，只要 e 不為空，就會(huì)一直循環(huán)查找下去。若有某個(gè)元素 C 的 hash 值也落在了和 A，B元素同一個(gè)桶中，則會(huì)由于，  A，B互相指向，e.next 永遠(yuǎn)不為空，就會(huì)形成死循環(huán)。

“HashMap底層原理是什么”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！