什么是Map

? ? ? ?不同于List單列的線性結(jié)構(gòu)痰哨，Map提供的是一種雙列映射的存儲(chǔ)集合虽另，它能夠提供一對(duì)一的數(shù)據(jù)處理能力，雙列中的第一列我們稱為key锨侯，第二列就是value兄一，一個(gè)key只能夠在一個(gè)Map中出現(xiàn)最多一次，通過一個(gè)key能夠獲取Map中唯一一個(gè)與之對(duì)應(yīng)的value值识腿，正是它的這種一對(duì)一映射的數(shù)據(jù)處理關(guān)系出革，在實(shí)際應(yīng)用中可以通過一個(gè)key快速定位到對(duì)應(yīng)的value。綜合上面的概念渡讼，可以概括出以下幾個(gè)核心點(diǎn)：

• Map存儲(chǔ)是以k-v鍵值對(duì)的方式進(jìn)行存儲(chǔ)的骂束，是雙列的
• Map中的key具有唯一性，不可重復(fù)
• 每個(gè)key對(duì)應(yīng)的value值是唯一的
  ? ? ? ?Java中Map是一個(gè)接口成箫，它不繼承任何其他的接口展箱，可以說它是java中所有Map的頂級(jí)父接口。它的設(shè)計(jì)理念完全遵循上面的規(guī)則蹬昌，只是具體的實(shí)現(xiàn)類種類很多混驰，對(duì)應(yīng)不同應(yīng)用場(chǎng)景的使用，所以可能具體細(xì)節(jié)以及設(shè)計(jì)上存在差異皂贩。

Java的Map中提供了三種Map視圖以便于展示Map中的內(nèi)容：

• 只包含key的Set集合
• 只包含value的Collection
• 同時(shí)包含key-value映射的EntrySet

另外需要額外注意：不能使用可變的對(duì)象作為Map的key栖榨，因?yàn)橐坏┰搶?duì)象出現(xiàn)變化它會(huì)導(dǎo)致Map的行為無法預(yù)期(這里的變化指的是影響equals方法比較結(jié)果的變化)；同時(shí)不能將Map本身作為一個(gè)Map的key明刷，但是允許將Map本身作為value存入Map結(jié)構(gòu)中婴栽。

使用Map的時(shí)機(jī)

存儲(chǔ)雙列結(jié)果

? ? ? ?有很多情況下我們都需要將數(shù)據(jù)梳理成雙列的結(jié)果集存儲(chǔ)起來，最常見的就是當(dāng)查詢數(shù)據(jù)庫(kù)時(shí)辈末，它返回的結(jié)果集中愚争，對(duì)應(yīng)字段名key和記錄值value就是一個(gè)map映皆，當(dāng)然如果是列表查詢，還會(huì)在Map的基礎(chǔ)上包裝一層List轰枝，但是它的每一條記錄結(jié)果的表示形式就是借助Map來存儲(chǔ)的捅彻，再比如在數(shù)據(jù)接收時(shí)，如果沒有合適的對(duì)象接收時(shí)鞍陨，可以考慮使用Map進(jìn)行接收沟饥，最常見的就是前端傳入json字符串，后端使用Map來接收數(shù)據(jù)湾戳，但是現(xiàn)在基本都采用JSONObject的方式來接收了，但是Map也是可以作為一個(gè)備用選項(xiàng)广料，在沒有其他第三方插件可用的情況下砾脑，可以考慮使用Map，或者String接收艾杏，然后轉(zhuǎn)成Map韧衣。

快速定位數(shù)據(jù)

? ? ? ?因?yàn)镸ap的一對(duì)一映射的數(shù)據(jù)關(guān)系，利用這一特性购桑，可以快速定位具體數(shù)據(jù)畅铭，現(xiàn)在的一些緩存操作就是利用的這一特點(diǎn)，我們將數(shù)據(jù)以Map的形式存儲(chǔ)在內(nèi)存中勃蜘，在緩存的眾多數(shù)據(jù)當(dāng)中硕噩，未來如果需要獲取數(shù)據(jù)時(shí)只需要給一個(gè)指定的key，可以快速定位到緩存的內(nèi)容缭贡，而不必像List結(jié)構(gòu)那樣炉擅，需要記住具體的位置才能快速定位，當(dāng)然如果能夠確切記得元素位置阳惹，也可以使用List谍失，而且效率更高，但是更多時(shí)候是不現(xiàn)實(shí)的莹汤，我們需要記住每一個(gè)元素在List中的位值快鱼，數(shù)據(jù)過多時(shí)就比較麻煩了，而且寫出來的程序可讀性也很差纲岭，因?yàn)橹皇峭ㄟ^整型的Index獲取抹竹，而Map的key可以是任何類型，完全可以定義一個(gè)具有明確意義的內(nèi)容止潮。

需要唯一性存儲(chǔ)的時(shí)候

? ? ? ?因?yàn)镸ap的key具有唯一性的特點(diǎn)柒莉，我們完全可以利用這一特點(diǎn)作為一個(gè)“變異版”的Set來使用，我們知道Set的特點(diǎn)就是不可重復(fù)沽翔，實(shí)際上在Java中兢孝，HashSet確實(shí)就是這么干的窿凤，它將存入的元素放入一個(gè)HashMap(Map的一種實(shí)現(xiàn))的key中，而Map中所有的value都是一個(gè)固定的Object類型的PRESENT常量跨蟹，因?yàn)樗膋ey不可冗余的特性正好符合了Set的特點(diǎn)雳殊，所以在HashSet的底層實(shí)現(xiàn)就依托于HashMap，而且Map本身也是無需的窗轩，注意：這里的“無序”是“不保證有序”夯秃，而不是“保證無序”，這兩個(gè)概念是有區(qū)別的痢艺，前者說明結(jié)果可能會(huì)有序仓洼，也可能無序，不能保證堤舒；而后者說明結(jié)果一定是無序的色建。所以有時(shí)可以發(fā)現(xiàn)在遍歷HashSet時(shí)竟然是有序的，這其實(shí)并不沖突舌缤。

Map的實(shí)現(xiàn)原理

? ? ? ?因?yàn)镴ava中Map只是一個(gè)接口箕戳，它只是定義了一些方法以及規(guī)范，所以提到實(shí)現(xiàn)原理国撵，還得結(jié)合具體的實(shí)現(xiàn)類來說明陵吸，而且Map的不同實(shí)現(xiàn)類，實(shí)現(xiàn)的原理也有所不同介牙；Map的實(shí)現(xiàn)類很多壮虫，就以我當(dāng)前使用的Java 10.0.2為例，Map接口的實(shí)現(xiàn)類就達(dá)到了31個(gè)之多(包括抽象類)环础，這還只是JDK內(nèi)部的實(shí)現(xiàn)類旨指，不包括第三方庫(kù)的實(shí)現(xiàn)。所以這里僅僅以幾個(gè)常見的Map來詳細(xì)說明喳整，也是面試中經(jīng)常被提及的幾個(gè)Map類型：HashMap谆构、HashTable、ConcurrentHashMap框都、LinkedHashMap等搬素。

HashMap

概念

? ? ? ?它是基于Hash表對(duì)Map接口的實(shí)現(xiàn)，所謂Hash其實(shí)就是散列魏保，這里只需要記装境摺：散列就是將一段變長(zhǎng)的數(shù)據(jù)轉(zhuǎn)換成一個(gè)固定長(zhǎng)度的數(shù)據(jù)，這個(gè)過程稱之為散列谓罗。在這個(gè)過程中會(huì)有一系列的算法計(jì)算粱哼，這里暫不深究；而Java獲取對(duì)象的hash值比較方便檩咱，因?yàn)镺bject類中定義了一個(gè)hashCode方法揭措，所以Java中的任何類都有直接或間接繼承了hashCode方法胯舷，而HashMap就是根據(jù)key的hash散列結(jié)果來具體定位Map中的元素的；另外在HashMap中是可以使用null鍵和null值的绊含；而且HashMap不是線程安全的桑嘶；如果拋去這兩點(diǎn)來看，HashMap其實(shí)與HashTable大致是相同的躬充。它不能保證映射的順序恒久不變逃顶，即：無法保證有序性；它的容量和加載因子緊密關(guān)系著它的迭代性能充甚。

實(shí)現(xiàn)原理

? ? ? ?整體設(shè)計(jì)概念上來說以政，HashMap采用的是數(shù)組加鏈表的方式來存儲(chǔ)元素，因?yàn)閔ash可能存在沖突的問題伴找，所以增加鏈表來存儲(chǔ)hash值相同的元素盈蛮，這種解決hash沖突的方法也叫鏈地址法。

首先疆瑰，如果要深入了解HashMap，就必須明白以下四個(gè)概念：

• capacity：它是指HashMap的容量昙啄，表示的是當(dāng)前HashMap中最大可以存儲(chǔ)的數(shù)據(jù)個(gè)數(shù)穆役。
• size：它反映的是當(dāng)前HashMap中已經(jīng)存放的元素個(gè)數(shù)
• loadFactor：加載因子，它表示當(dāng)前HashMap中的裝滿程度梳凛，默認(rèn)為0.75,耿币，它跟threshold計(jì)算有關(guān)
• threshold：表示臨界值，因?yàn)镠ashMap的容量不是一層不變的韧拒，當(dāng)達(dá)到一定程度淹接，就需要對(duì)HashMap進(jìn)行擴(kuò)容，而這個(gè)擴(kuò)容的臨界值就是用threshold表示叛溢，它的計(jì)算方式是capacity*loadFactor塑悼；因?yàn)榧虞d因子默認(rèn)是0.75，也就是說達(dá)到最大容量的四分之三時(shí)楷掉，再往里面加元素厢蒜，就會(huì)擴(kuò)容。

上面只是一個(gè)大致的介紹烹植，下面就來逐步深入介紹相關(guān)的設(shè)計(jì)原理斑鸦。

hash沖突

? ? ? ?hash本身的意思就是散列，它的作用前面也介紹過草雕，就是將一個(gè)變長(zhǎng)的數(shù)據(jù)散列成一個(gè)固定長(zhǎng)度的數(shù)據(jù)巷屿，在Java中，散列的結(jié)果是一個(gè)int整形數(shù)墩虹，也就是說hash的結(jié)果最大也不會(huì)超過Java中整型的最大值嘱巾，任何對(duì)象都具有hashCode方法憨琳，我們可以重寫hashCode方法，但是對(duì)象的數(shù)量是海量的浓冒，但是hash值就那么多栽渴，所以必然存在一種情況：hash值相同但是對(duì)象不同，這種現(xiàn)象就是hash沖突稳懒。在Java中如果是比較兩個(gè)對(duì)象是否相同也是有策略的闲擦，首先會(huì)比較兩個(gè)對(duì)象的hashCode方法，hashCode不同场梆，對(duì)象肯定不同墅冷，這種判斷可以隔絕大多數(shù)的比較了，而當(dāng)hashCode相同時(shí)或油，會(huì)再去調(diào)用equals方法比較寞忿，如果equals也為true，這才能說明兩個(gè)對(duì)象是相等的顶岸。所以equals為true的對(duì)象腔彰，hashCode一定是相等的，反之則不然辖佣。

HashMap的內(nèi)部存儲(chǔ)容器

? ? ? ?map中最基礎(chǔ)的存儲(chǔ)結(jié)構(gòu)就是數(shù)組霹抛，具體在HashMap中就是一個(gè)Node<K, V>類型的數(shù)組table(即hash表)，這是一個(gè)可以存儲(chǔ)鍵值對(duì)的數(shù)據(jù)類型組成的數(shù)組卷谈，我們放入map中的元素全部都被存入到這個(gè)數(shù)組中杯拐，而map容量的擴(kuò)充實(shí)際上也就是對(duì)這個(gè)數(shù)組的不斷變更。

HashMap的初始容量設(shè)計(jì)

? ? ? ?使用HashMap的時(shí)候世蔗，最常用的就是無參的構(gòu)造方法端逼，然后調(diào)用put方法放入鍵值對(duì)，這種方式采用的是默認(rèn)的初始化策略污淋，此時(shí)當(dāng)我們剛剛new出一個(gè)HashMap對(duì)象時(shí)顶滩，它的內(nèi)部table數(shù)組實(shí)際上是一個(gè)null(我這里是以java 10.0.2為版本介紹的，其他版本可能略有不同)寸爆。只有當(dāng)我們第一次調(diào)用put時(shí)才會(huì)進(jìn)行table的初始化诲祸。此時(shí)它的capacity會(huì)被設(shè)置為DEFAULT_INITIAL_CAPACITY = 1 << 4，也就是16而昨。加載因子loadFactor是默認(rèn)的0.75救氯，所以這時(shí)候它的threshold是12。

但是我們?cè)趧?chuàng)建HashMap時(shí)也可以指定capacity甚至是loadFactor歌憨，這里一般不推薦修改loadFactor：

//DEFAULT_LOAD_FACTOR = 0.75f
public HashMap(int initialCapacity) {
 this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

? ? ? ?需要注意的是：它傳入的initialCapacity并不是最終我們構(gòu)建的HashMap對(duì)象的容器大小着憨，它會(huì)經(jīng)過一次運(yùn)算，得到一個(gè)比initialCapacity值稍大的數(shù)值务嫡，并且一定是離initialCapacity最近的那個(gè)2的N次冪的值甲抖，比如：我們傳入5漆改，它就會(huì)找到8，傳入9准谚，就會(huì)找到16挫剑。也就是說最終得到的capacity的值一定是2的某個(gè)次冪。這個(gè)過程是需要計(jì)算的柱衔，JDK中采用是一種比較高效的位移運(yùn)算樊破，具體如下：

首先來看幾個(gè)簡(jiǎn)單示例：

5   0000 0000 0000 0101      |      19  0000 0000 0001 0011
7   0000 0000 0000 0111      |      31  0000 0000 0001 1111
8   0000 0000 0000 1000      |      32  0000 0000 0010 0000
---------------------------------------------------------------------------------------------------
9   0000 0000 0000 1001      |      37  0000 0000 0010 0101
15  0000 0000 0000 1111      |      63  0000 0000 0011 1111
16  0000 0000 0001 0000      |      64  0000 0000 0100 0000

? ? ? ?根據(jù)上面的數(shù)據(jù)展示，可以看到如果我們想要將5最終變成離它最近的那個(gè)8唆铐，需經(jīng)歷：5 -- 7 -- 8這么一個(gè)過程哲戚，也就是將它的原本二進(jìn)制數(shù)據(jù)有效部分全部轉(zhuǎn)換成1，然后在此基礎(chǔ)上加1就可以得到目標(biāo)值艾岂，同理9到16,19到32等也是如此顺少，而JDK中HashMap源碼采用就是這種不斷右移然后按位或運(yùn)算，最終得到一個(gè)有效數(shù)據(jù)部分全為1的數(shù)值王浴，然后加1得到結(jié)果脆炎，這樣再來看HashMap的這部分計(jì)算源碼就不會(huì)迷惑了：

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;
}

? ? ? ?可以看到，最終計(jì)算出來的n與MAXIMUM_CAPACITY比較氓辣，只要比它小秒裕，就會(huì)加1，而在此之前的邏輯主要就是為了將對(duì)應(yīng)的二進(jìn)制位全部轉(zhuǎn)換成1筛婉。這里有一點(diǎn)需要注意：按照上面介紹的邏輯會(huì)有有個(gè)情況簇爆，就是如果我們傳入的數(shù)值本身就是2的次冪值癞松，那就會(huì)有問題爽撒，因?yàn)榇藭r(shí)傳入的capacity本身就已經(jīng)可以作為初始容量了，解決方式很簡(jiǎn)單响蓉，就是上面方法中的第一步操作硕勿，先將傳入的capacity減1，再進(jìn)行計(jì)算枫甲，此時(shí)如果傳入的是8源武，那么減1之后，n其實(shí)是7想幻，經(jīng)過計(jì)算后正好是8粱栖，符合邏輯；那如果此時(shí)傳入的是9脏毯，雖然減1后得到了8闹究，但是此時(shí)需要的是更大數(shù)值的16，經(jīng)過位移計(jì)算食店，正好得到15渣淤，加1后得到16赏寇，所以邏輯上也沒有問題。

HashMap的存儲(chǔ)

? ? ? ?HashMap的存儲(chǔ)方式就是利用了map中的key的hash值作為定位基礎(chǔ)的价认，具體做法就是：我們?cè)诖嫒胍粋€(gè)k-v鍵值對(duì)的時(shí)候嗅定，它會(huì)計(jì)算key的hash值，也就是調(diào)用key對(duì)象的hashCode方法用踩，因?yàn)閔ashCode的取值范圍是整個(gè)整型范圍渠退，所以可能會(huì)非常大，為了讓它能夠和table數(shù)組的下標(biāo)index掛鉤捶箱，這里就會(huì)將得到的hashCode值與table的長(zhǎng)度取模智什，這樣得到的數(shù)據(jù)肯定是在table.length之內(nèi)的整數(shù)，然后用它作為數(shù)組對(duì)應(yīng)的下標(biāo)丁屎。注意：這里JDK采用了一定的優(yōu)化荠锭，它的取模并不是常規(guī)的hash % table.length，它使用的是hash & (table.length - 1)這種按位與的操作晨川，這么做有兩個(gè)好處：

• 首先就是效率很高证九，比正常的取模運(yùn)算符要快
• 避免了負(fù)數(shù)問題，結(jié)合前面的初始容量設(shè)計(jì)可以知道共虑，table.length - 1得到的一定是一個(gè)正數(shù)值愧怜，所以它的最高位一定是0，而0與任何數(shù)按位與運(yùn)算妈拌，得到的一定是0申尼，此時(shí)無論hashCode值是整數(shù)還是負(fù)數(shù)，計(jì)算出來的結(jié)果一定是正數(shù)峭跳。

而為何會(huì)出現(xiàn)hash & (table.length - 1) == hash % table.length呢唱矛？其實(shí)想想也能明白：

經(jīng)過前面分析可以得到table的長(zhǎng)度必然是：table.length == 2^N，則hash % table.length實(shí)際上就是hash / table.length然后取余數(shù)培愁，也就是hash >> N 位移運(yùn)算過程中著摔，移出的那部分?jǐn)?shù)據(jù)即為需要的模運(yùn)算結(jié)果。而table.length - 1的結(jié)果必定是一個(gè)二進(jìn)制有效位全為1的數(shù)據(jù)(參考前面容量初始化設(shè)計(jì))定续，此時(shí)hash與減1后的值進(jìn)行按位與谍咆，可以保證低位的結(jié)果保留，而超過table.length - 1數(shù)值的高位部分得0私股，這個(gè)結(jié)果正好就是前面位移運(yùn)算過程中需要得到的那個(gè)移出的部分摹察。

? ? ? ?按照上面的介紹，最終可以根據(jù)key的hash得到一個(gè)對(duì)應(yīng)的數(shù)組位置index倡鲸，但是我們也知道hash是會(huì)沖突的供嚎，這里如果出現(xiàn)了沖突，經(jīng)過計(jì)算后得到的index位置上已經(jīng)有元素了怎么辦，這時(shí)候鏈表結(jié)構(gòu)就發(fā)生作用了查坪，它會(huì)將最新添加的元素放在數(shù)組中寸宏，將該位置上之前的元素以鏈表的形式放在新加入的元素的后面，Node的設(shè)計(jì)本身就是一種鏈表存儲(chǔ)格式：

static class Node<K,V> implements Map.Entry<K,V> {
 final int hash;
 final K key;
 V value;
 Node<K,V> next;
 ...
}

所以：數(shù)組中的元素肯定是最新放入的元素偿曙，之前的老元素會(huì)按照鏈表的方式掛在最新元素的后面氮凝。這種存儲(chǔ)就是數(shù)組加鏈表的存儲(chǔ)方式。

需要注意的是：HashMap中使用到的hash值并非是對(duì)應(yīng)key對(duì)象上調(diào)用hashCode方法望忆，它又經(jīng)歷了一步計(jì)算：

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

? ? ? ?這么做的目的也就是為了降低hash沖突罩阵，盡可能的讓key的每一位數(shù)據(jù)都會(huì)影響到散列的結(jié)果，所以它會(huì)對(duì)hash進(jìn)行擾動(dòng)計(jì)算启摄，防止hashCode的高位不同但低位相同導(dǎo)致的hash沖突稿壁，將hash的高位和低位的特征結(jié)合起來，共同影響hash結(jié)果歉备，盡可能將每一位數(shù)據(jù)都與hash結(jié)果相關(guān)聯(lián)傅是，從而降低沖突。具體的計(jì)算蕾羊，強(qiáng)烈推薦H大的博文：透徹分析hash()

? ? ? ?隨著數(shù)據(jù)的不斷增多喧笔，沖突的可能性就會(huì)越來越大，極端情況就是鏈表部分會(huì)變得很長(zhǎng)龟再，而鏈表結(jié)構(gòu)的增刪的效率很高书闸，但查詢的效率很低，這樣如果鏈表過長(zhǎng)利凑，會(huì)影響Map的查詢性能浆劲，所以JDK1.8之后，對(duì)鏈表部分做了改動(dòng)哀澈，一旦鏈表的長(zhǎng)度超過了8個(gè)Node牌借，就會(huì)直接轉(zhuǎn)換成紅黑樹結(jié)構(gòu)，檢索的時(shí)間復(fù)雜度大大降低日丹。

? ? ? ?另外對(duì)于擴(kuò)容方面走哺，如果元素個(gè)數(shù)超過了capacity*threshold的值蚯嫌，容器就會(huì)調(diào)用resize方法擴(kuò)容哲虾，擴(kuò)容很簡(jiǎn)單：就是將原來的oldCapacity << 1，也就是直接擴(kuò)大一倍择示，這樣也保證了capacity的值始終都是2的指數(shù)值束凑。

使用HashMap時(shí)機(jī)

? ? ? ?總體上來說，HashMap的查找效率比較高栅盲，常見的應(yīng)用場(chǎng)景中汪诉，需要使用Map的地方，HashMap足以解決大多數(shù)問題，而且它的效率也是很高的扒寄，如果數(shù)據(jù)量較大鱼鼓，這個(gè)效率提升還是很可觀的，如果沒有線程安全的要求该编，并且可以允許Key出現(xiàn)null值的情況下迄本，可以考慮使用HashMap。

HashMap的問題

線程安全

? ? ? ?觀察HashMap的源碼课竣，可以看到嘉赎，沒有任何線程安全的概念，對(duì)于put于樟，remove等操作方法公条，沒有任何加鎖、同步化的操作迂曲，所以它是線程不安全的靶橱，在多線程環(huán)境下，可以考慮如下方案：

• 使用HashTable路捧，但是效率極低抓韩，它是方法加鎖，加鎖粒度很粗糙鬓长，性能較低
• 使用Collections工具類可以創(chuàng)建一個(gè)線程安全的HashMap谒拴，實(shí)際的結(jié)果跟前面一種類似，也是一種方法加鎖涉波，不推薦
• 可以考慮在自己的業(yè)務(wù)邏輯中自行實(shí)現(xiàn)同步邏輯英上，靈活性較高，但是會(huì)影響代碼的整體閱讀邏輯
• 可以使用ConcurrentHashMap啤覆，它是也是線程安全的map苍日，引入了段加鎖機(jī)制，效率比HashTable要高很多

另外窗声，據(jù)網(wǎng)上有些博客提出：在并發(fā)狀況下相恃，多個(gè)線程同時(shí)對(duì)一個(gè)map進(jìn)行put，可能會(huì)導(dǎo)致get死循環(huán)笨觅，具體可能表現(xiàn)為：

• 多線程put操作后拦耐，get操作導(dǎo)致死循環(huán)。
• 多線程put非NULL元素后见剩，get操作得到NULL值杀糯。
• 多線程put操作，導(dǎo)致元素丟失苍苞。

? ? ? ?但是這種情況我寫了一些demo固翰，暫時(shí)沒有出現(xiàn)上面這種情況，可能是因?yàn)镴DK版本的緣故，新版本的HashMap做了一定的優(yōu)化骂际，故暫時(shí)無法重現(xiàn)這個(gè)問題疗琉。

性能開銷

? ? ? ?hash函數(shù)的計(jì)算會(huì)影響這個(gè)性能，對(duì)于一些極端情況歉铝，例如對(duì)象比較復(fù)雜没炒，hash的計(jì)算可能比較耗時(shí)，這部分性能的損耗也應(yīng)該考慮在后續(xù)實(shí)際生產(chǎn)中犯戏，如果Map中存儲(chǔ)的key比較復(fù)雜送火，就要考慮是否需要換一種存儲(chǔ)方式了。

初始容量設(shè)置問題

? ? ? ?我們?cè)趧?chuàng)建一個(gè)HashMap的時(shí)候先匪，一般都是用默認(rèn)的無參構(gòu)造方法种吸，這種方法雖然方便，但是性能上面可能并不是最符合我們當(dāng)前正在運(yùn)行的程序環(huán)境呀非，所以一般都建議指定一個(gè)初始容量坚俗，這樣可以盡可能保證減少map擴(kuò)容帶來的性能耗損問題，同時(shí)也減少了rehash(擴(kuò)容后重新進(jìn)行hash計(jì)算)的次數(shù)岸裙，對(duì)性能的提升也有一定好處猖败。

? ? ? ?但是初始容量的設(shè)計(jì)也是有講究的，不能越大越好降允，要最符合當(dāng)前的應(yīng)用環(huán)境恩闻，當(dāng)然前提是能夠預(yù)知到map中到底會(huì)存儲(chǔ)多少元素，否則默認(rèn)的構(gòu)造方法是最好的選擇剧董。在阿里巴巴的Java開發(fā)者手冊(cè)中給出了一個(gè)計(jì)算初始容量的公式：

capacity = (要存儲(chǔ)元素個(gè)數(shù) / 加載因子loadFactor) + 1
//加載因子loadFactor默認(rèn)0.75

? ? ? ?其實(shí)這種計(jì)算方案在Google的Java開源工具庫(kù)guava也有幢尚，最終的靈感來源還是JDK源碼中HashMap的putAll方法得來的，它里面采用的就是這種計(jì)算方式翅楼，它這么設(shè)計(jì)是有一定的好處的：

例如現(xiàn)在需要加入7個(gè)元素尉剩，如果只是直接傳入7，那么最終的HashMap容量會(huì)被設(shè)置為8毅臊，但是由于此時(shí)threshold = 8 * 0.75 = 6理茎，所以在加入第七個(gè)元素的時(shí)候會(huì)有一個(gè)hash表擴(kuò)容，這個(gè)是比較耗費(fèi)資源的操作管嬉。而如果使用上面推薦的公式皂林，可以計(jì)算最終傳入的值為：7 / 0.75 + 1 = 10；那么最終計(jì)算后的capacity為16宠蚂，在進(jìn)行元素裝入的時(shí)候就可以有效避免過于頻繁的hash表擴(kuò)容操作式撼，從而提升性能童社。

其他

? ? ? ?說到HashMap求厕，這里順便說一下HashSet，它在前面也稍微提到了一下，它是一種Set呀癣，Set的特性就是：無序美浦，唯一。而HashSet的底層實(shí)現(xiàn)就是利用的HashMap的key唯一性特點(diǎn)项栏，而且HashMap本身也是不保證有序的浦辨，所以正好與Set的特性不謀而合，所以HashSet在存儲(chǔ)元素的時(shí)候沼沈，都是將元素存入HashMap的key中流酬，value部分始終都是一個(gè)固定的常量Object對(duì)象，沒有實(shí)際意義列另。

HashTable

? ? ? ?首先在概念上芽腾，它基本上與HashMap沒有太大區(qū)別，甚至于使用的方式都差不多页衙，不同的只是它的底層設(shè)計(jì)上與HashMap存在一定的差異摊滔，而正是這些差異，使它的使用場(chǎng)景更加單一店乐。另外：HashTable是不存能出null值的艰躺，無論是key還是value，這點(diǎn)與HashMap完全不同眨八，而且它是線程安全的腺兴。

實(shí)現(xiàn)原理

? ? ? ?它的整體設(shè)計(jì)思路基本和HashMap差不多，都是基于Node數(shù)組進(jìn)行存儲(chǔ)廉侧，這個(gè)Node實(shí)際上就是一個(gè)鏈表的節(jié)點(diǎn)類型含长，內(nèi)部維護(hù)一個(gè)Node類型的數(shù)組，Node的結(jié)構(gòu)設(shè)計(jì)基本都差不多伏穆，下面主要從幾個(gè)與HashMap不同的地方說明以下具體的細(xì)節(jié)差異拘泞。

線程安全

? ? ? ?首先明確一點(diǎn)，HashTable是線程安全的枕扫，看它的源碼就知道了陪腌，它里面的所有涉及到更新HashTable的操作都被加了synchronized鎖。

繼承關(guān)系

? ? ? ?與HashMap不同的是HashTable繼承自Dictionary(HashMap繼承自AbstractMap)烟瞧，這是一個(gè)非常古老的抽象類诗鸭，它從java1.0的時(shí)候就已經(jīng)存在了，現(xiàn)在連這個(gè)類的頭部注釋中都說這個(gè)類已經(jīng)是obsolete（過時(shí)的）類了参滴，對(duì)于現(xiàn)在的JDK而言强岸，Dictionary所能達(dá)到的效果，Map接口都能達(dá)到砾赔，甚至還比它的靈活性更高(因?yàn)榻涌诳梢远鄬?shí)現(xiàn)蝌箍，類只能單繼承)青灼，所以官方推薦后續(xù)的實(shí)現(xiàn)都基于Map接口了。

迭代

? ? ? ?HashTable的遍歷使用的是枚舉Enumeration妓盲，而不是我們常見的Iterator迭代器杂拨，例如我們?nèi)绻{(diào)用它的keys方法，它會(huì)返回一個(gè)Enumeration類型的對(duì)象悯衬，這個(gè)查看一下源碼就可以很清楚的看到弹沽。當(dāng)然，它本身也是有Iterator的筋粗，Enumeration是因?yàn)闅v史遺留問題才一直存在的策橘。它的Iterator迭代與HashMap都是支持fast-fail的，fail-fast這里就不再贅述娜亿，參考Java集合--List役纹。

初始容量設(shè)計(jì)

? ? ? ?它默認(rèn)的初始容量為11，并非HashMap的16暇唾，但是它的默認(rèn)加載因子loadFactor卻仍然是0.75促脉，官方采用0.75做加載因子其實(shí)也是經(jīng)過時(shí)間空間的消耗權(quán)衡得到的結(jié)果，按照官方的注釋解釋：如果過高策州，雖然會(huì)減少空間上的開銷瘸味，但是會(huì)增加查詢上的時(shí)間成本，所以才說不建議修改loadFactor够挂。

擴(kuò)容設(shè)計(jì)

它的擴(kuò)容不同于HashMap的直接翻倍旁仿，每次當(dāng)容量達(dá)到threshold后，新的capacity = 2 * oldCapacity + 1孽糖。所以它的到的capacity值始終都是一個(gè)奇數(shù)枯冈，默認(rèn)是從11開始的。另外它也沒有對(duì)傳入的capacity再計(jì)算的過程办悟，它的源碼中只有如下設(shè)計(jì)：

if (initialCapacity==0)
 initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);

? ? ? ?可以看到尘奏，只是對(duì)initialCapacity進(jìn)行了是否為0的判斷，如果為0病蛉，默認(rèn)賦值為1炫加，否則capacity的值就是傳入的值。所以我們?cè)跇?gòu)建HashTable對(duì)象時(shí)铺然，如果需要傳入capacity俗孝，最好也按照它的設(shè)計(jì)初衷，傳入一個(gè)奇素?cái)?shù)魄健。

hash計(jì)算

? ? ? ?HashTable的hash計(jì)算就是直接調(diào)用key對(duì)象的hashCode方法赋铝，沒有進(jìn)行進(jìn)一步擴(kuò)散計(jì)算，而且它的取模運(yùn)算也沒有HashMap那種采用效率更高的&操作沽瘦，據(jù)說這是跟HashTable的長(zhǎng)度數(shù)值有關(guān)革骨，當(dāng)哈希表的大小為素?cái)?shù)時(shí)农尖，簡(jiǎn)單的取模，哈希的結(jié)果會(huì)更加均勻苛蒲。沒有具體深入研究過卤橄，有待探討绿满。

HashTable的問題

性能

? ? ? ?它的性能問題是廣為詬病的臂外，因?yàn)樗膕ynchronized鎖都是加在方法上的，synchronized本身就是重量級(jí)鎖喇颁，并且加鎖粒度又很粗糙(方法級(jí)鎖)漏健，我們?cè)诂F(xiàn)實(shí)場(chǎng)景中，其實(shí)99%的情況可能都不會(huì)出現(xiàn)線程安全問題橘霎，所以僅僅為了那1%的并發(fā)安全去使用它多少有點(diǎn)浪費(fèi)性能蔫浆，完全可以自己控制同步，而且如果有選擇姐叁，選擇ConcurrentHashMap也是一種不錯(cuò)的方案瓦盛。只有在一些特殊的應(yīng)用場(chǎng)景中可能會(huì)采用HashTable存儲(chǔ)數(shù)據(jù)。

并發(fā)迭代修改

? ? ? ?雖然HashTable被描述為線程安全的外潜，似乎在多線程環(huán)境下就不存在任何問題了原环，但是仍需注意，如果我們使用迭代器對(duì)HashTable進(jìn)行遍歷的時(shí)候处窥，它采用的是fail-fast機(jī)制嘱吗，所以仍然有可能拋出ConcurrentModificationException異常。另外HashTable的另一種迭代方式：Enumeration滔驾，它是不支持fail-fast的谒麦，所以如果有需要檢測(cè)這種并發(fā)修改迭代的情況，Iterator是唯一的選擇哆致。

ConcurrentHashMap

原理

? ? ? ?因?yàn)镠ashTable的加鎖粒度過大绕德，所以JDK1.5以后出現(xiàn)了這個(gè)同樣支持并發(fā)操作的Map結(jié)構(gòu)，ConcurrentHashMap引入了Segment（段）的機(jī)制摊阀，所謂段迁匠，就是將Map的容器進(jìn)行分段(也就是常說的“桶”)，每段單獨(dú)加鎖驹溃，所以當(dāng)并發(fā)修改時(shí)城丧，如果不是同時(shí)操作同一個(gè)段內(nèi)的數(shù)據(jù)，段與段之間是互不影響的豌鹤，這就是所謂的鎖分段技術(shù)亡哄，正是因?yàn)槎闻c段之間是獨(dú)立的加鎖，所以大大提升了并發(fā)性能布疙。

? ? ? ?對(duì)于java6和java7的版本中蚊惯，主要就是segment機(jī)制的引入愿卸，內(nèi)部擁有一個(gè)Entry數(shù)組，數(shù)組中每個(gè)元素又是一個(gè)鏈表結(jié)構(gòu)截型，但是同時(shí)也是一個(gè)ReentrantLock(Segment繼承了ReentrantLock)趴荸。

? ? ? ?而Java8以后，ConcurrentHashMap做了很大的改動(dòng)宦焦，有些甚至是顛覆性的发钝，它摒棄了之前一直使用的Segment機(jī)制，雖然源碼中仍然存在該類波闹，但是源碼的注釋中已經(jīng)說明了它是一個(gè)unused(無用的)類酝豪，它只是用來兼容之前版本的ConcurrentHashMap。新版本的ConcurrentHashMap采用了CAS算法精堕，無鎖化的操作大大提高了性能孵淘，底層仍然采用HashMap的那套實(shí)現(xiàn)，即：“數(shù)組+鏈表+紅黑樹”的方式歹篓。同時(shí)為了做到并發(fā)瘫证，也增加了一些輔助類，如：TreeBin庄撮、Traverser等內(nèi)部類背捌。

繼承關(guān)系

? ? ? ?ConcurrentHashMap除了和HashMap一樣繼承了AbstractMap，同時(shí)它也實(shí)現(xiàn)了一個(gè)叫ConcurrentMap的接口重窟，這個(gè)接口的作用主要是為Map提供線程安全以及原子性的保證载萌。另外不同于HashMap，它沒有實(shí)現(xiàn)Cloneable接口巡扇，所以如果涉及對(duì)象復(fù)制扭仁，需要額外考慮其他方式。其他的基本都與HashMap一致了厅翔。

初始化容量和擴(kuò)容機(jī)制

? ? ? ?對(duì)于初始容量的設(shè)置乖坠，默認(rèn)加載因子以及擴(kuò)容的方式，ConcurrentHashMap采用的方案與HashMap的機(jī)制是一模一樣刀闷，所以對(duì)于HashMap的那一套在這里是通用的熊泵，它的內(nèi)部結(jié)構(gòu)也是一個(gè)Node數(shù)組，并且它的Node類的內(nèi)部定義幾乎與HashMap的一致甸昏，不同的是此時(shí)的Node中代表Value的val和指向下一個(gè)Node節(jié)點(diǎn)的引用next是volatile修飾的顽分，這個(gè)也是為了在高并發(fā)情況下，為不同線程間數(shù)據(jù)可見性而考慮的施蜜。而且不僅僅是這兩個(gè)字段卒蘸，在整個(gè)類中，除去靜態(tài)常量，其余的變量幾乎全部都用volatile修飾缸沃。

? ? ? ?如果在創(chuàng)建ConcurrentHashMap對(duì)象時(shí)恰起，我們手動(dòng)傳入了capacity值，這里它不是像HashMap那樣直接對(duì)傳入的capacity值進(jìn)行計(jì)算求取最近的2的指數(shù)值趾牧，而是會(huì)將傳入的initialCapacity進(jìn)行如下運(yùn)算：

tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)

? ? ? ?而這里的tableSizeFor方法就是根據(jù)傳入的值检盼，對(duì)capacity進(jìn)行不斷位移以及按位或的操作，最終求出一個(gè)合適的2的指數(shù)值翘单。即：如果創(chuàng)建ConcurrentHashMap對(duì)象時(shí)吨枉，如果指定了capacity，在實(shí)際創(chuàng)建最大容量時(shí)县恕，會(huì)先對(duì)傳入的capacity擴(kuò)大3倍并加1东羹，再根據(jù)此時(shí)的值再此進(jìn)行求取最近的不小于該值的2的指數(shù)冪值剂桥。

幾個(gè)重要的屬性

? ? ? ?前面HashMap中介紹過的幾個(gè)重要屬性這里就不再重復(fù)了忠烛，這里就重點(diǎn)提一下sizeCtl屬性，它的作用很大权逗，用途比較多美尸，根據(jù)不同的值，可以分為以下幾種情況：

• 負(fù)數(shù)代表正在進(jìn)行初始化或擴(kuò)容操作

• -1代表正在初始化

• -N表示當(dāng)前有N - 1個(gè)線程正在進(jìn)行擴(kuò)容

• 整數(shù)或0代表hash還沒有被初始化斟薇，此時(shí)它的值表示的是初始化大小或者是下一次擴(kuò)容的大小师坎，有點(diǎn)類似于前面介紹過的threshold(閾值)的概念，它的值始終是當(dāng)前ConcurrentHashMap容量的0.75倍堪滨，與loadFactor正好相對(duì)應(yīng)胯陋。

//下面兩個(gè)值主要是用于與hash值進(jìn)行比較時(shí)使用，判斷當(dāng)前節(jié)點(diǎn)類型
static final int MOVED     = -1; // hash值是-1袱箱，表示這是一個(gè)forwardNode節(jié)點(diǎn)
static final int TREEBIN   = -2; // hash值是-2  表示這時(shí)一個(gè)TreeBin節(jié)點(diǎn)</pre>

MOVED和TREEBIN在容器擴(kuò)容遏乔，遍歷以及存放元素的時(shí)候，有很重要的作用发笔。

核心類

Node

? ? ? ?跟HashMap一樣盟萨，它是包裝了K-V鍵值對(duì)的類，前面說過了讨，它的整體設(shè)計(jì)思路跟HashMap幾乎一樣捻激，只是它的value和next屬性使用了volatile修飾，保證了在并發(fā)環(huán)境下線程間的可見性前计，同時(shí)比較有意思的是它的setValue方法：

public final V setValue(V value) {
 throw new UnsupportedOperationException();
}

? ? ? ?可以看到胞谭，它不允許直接使用setValue方法對(duì)Node中的value屬性進(jìn)行修改纵潦，如果這么做指郁，會(huì)直接拋出異常。這個(gè)方法在HashMap中是可以正常使用的柏腻。同時(shí)势就，相較于HashMap泉瞻，它又新增了一個(gè)find方法脉漏，注釋上解釋它的功能主要是為了輔助map.get方法，在子類中會(huì)進(jìn)行重寫袖牙。

TreeNode

? ? ? ?當(dāng)Node的鏈表結(jié)構(gòu)過長(zhǎng)時(shí)（一般是為8個(gè)元素）侧巨，HashMap就是將其轉(zhuǎn)換成紅黑樹形式，而轉(zhuǎn)換的基礎(chǔ)就是直接借助TreeNode鞭达，但是ConcurrentHashMap中卻不是直接使用TreeNode司忱，它是將這些TreeNode節(jié)點(diǎn)放在TreeBin對(duì)象中，然后由TreeBin完成紅黑樹的包裝畴蹭，而且這里的TreeNode是繼承自ConcurrentHashMap中的Node類坦仍。

TreeBin

? ? ? ?TreeBin的作用很明確，它的構(gòu)造函數(shù)就一個(gè)叨襟，接收的參數(shù)就是TreeNode繁扎，它對(duì)TreeNode進(jìn)行包裝，甚至于當(dāng)鏈表轉(zhuǎn)換成樹結(jié)構(gòu)的時(shí)候糊闽，哪怕它的根節(jié)點(diǎn)也是TreeBin梳玫，并非HashMap中的TreeNode，所以可以說：ConcurrentHashMap中右犹，如果數(shù)組中某個(gè)數(shù)組位置上的結(jié)構(gòu)轉(zhuǎn)變成了樹結(jié)構(gòu)提澎，那么存儲(chǔ)在數(shù)組中的實(shí)際元素就是TreeBin對(duì)象。而對(duì)于其他沒有轉(zhuǎn)換成樹結(jié)構(gòu)的位置(鏈表長(zhǎng)度仍然在8個(gè)以內(nèi))念链，仍然是原本的Node類型盼忌。

ForwardingNode

? ? ? ?一個(gè)用于連接兩個(gè)table的節(jié)點(diǎn)類，這個(gè)類在進(jìn)行擴(kuò)容的時(shí)候有很大的作用掂墓，它內(nèi)部包含了一個(gè)nextTable引用谦纱，類型是Node類型，而且它的key梆暮、value以及next都是null服协，hash值為-1，后面在介紹擴(kuò)容的時(shí)候會(huì)說道它的作用啦粹。

CAS無鎖化

UnSafe靜態(tài)代碼塊

? ? ? ?在我當(dāng)前使用的java10.0.2版本中偿荷，源碼的6373行到6403行這段代碼是無鎖化的靜態(tài)語句塊部分，它里面利用了jdk.internal.misc.Unsafe類對(duì)一些重要屬性的修改采用CAS操作唠椭，大大提高了程序的性能跳纳，因?yàn)闆]有鎖的開銷問題，許多鎖帶來的問題也就不存在了贪嫂。

三個(gè)無鎖化的核心方法

//獲取tab數(shù)組中i位置上的Node
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
 return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);
}
//利用CAS設(shè)置tab數(shù)組中i位置上的Node節(jié)點(diǎn)寺庄，這里就是典型的CAS操作，設(shè)置值的時(shí)候，傳入待修改的值v和比較值c
//在修改時(shí)斗塘，將c的值與內(nèi)存中的值比較赢织，只有相等時(shí)，才將該位置上的Node設(shè)置為傳入的v馍盟，否則修改失敗
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
 Node<K,V> c, Node<K,V> v) {
 return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
//顧名思義于置，這個(gè)方法就是利用CAS操作，將tab數(shù)組中的i位置設(shè)置為傳入的v
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
 U.putObjectRelease(tab, ((long)i << ASHIFT) + ABASE, v);
}

正是有了上面這三個(gè)核心操作贞岭，才保證了ConcurrentHashMap的線程安全的特性八毯。

初始化initTable

? ? ? ?在構(gòu)建ConcurrentHashMap對(duì)象的時(shí)候，它的構(gòu)造方法采用的策略和HashMap中的大致是一樣瞄桨，在構(gòu)造方法中其實(shí)并沒有對(duì)具體的存儲(chǔ)數(shù)組進(jìn)行指定话速，只是簡(jiǎn)單初始化了一些必要的參數(shù)指標(biāo)，具體的table的初始化都是放在插入元素時(shí)進(jìn)行的芯侥，在插入前會(huì)對(duì)table進(jìn)行null值判斷泊交。

private final Node<K,V>[] initTable() {
  Node<K,V>[] tab; int sc;
  while ((tab = table) == null || tab.length == 0) {
    //根據(jù)前面的介紹，此時(shí)sizeCtl若小于0筹麸，表示有其他線程正在進(jìn)行初始化操作
    //此時(shí)當(dāng)前線程放棄初始化活合，自旋直至其他線程初始化結(jié)束
    if ((sc = sizeCtl) < 0)
      Thread.yield(); 
    else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
      //此時(shí)表示當(dāng)前線程得到了初始化權(quán)限雏婶，此時(shí)將sizeCtl設(shè)置為-1物赶，阻止其他線程進(jìn)入
      try {
        if ((tab = table) == null || tab.length == 0) {
          //DEFAULT_CAPACITY = 16
          int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
          @SuppressWarnings("unchecked")
          Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
          table = tab = nt;
          //此時(shí)n是當(dāng)前table容器的大小，n>>>2實(shí)際上就等于0.25n
          //所以sc = 0.75n
          sc = n - (n >>> 2);
        }
      } finally {
//修改sizeCtl的值為當(dāng)前容器大小的0.75倍值
        sizeCtl = sc;
      }
      break;
    }
}
return tab;
}

擴(kuò)容transfer方法

? ? ? ?由于這個(gè)方法過長(zhǎng)留晚，這里就不再貼它的源碼了酵紫，強(qiáng)烈建議琢磨一下源代碼，它里面的涉及到的設(shè)計(jì)思路還是比較精妙的错维，它的大致擴(kuò)容思路是這樣的：

• 開始的時(shí)候它會(huì)進(jìn)行一次CPU的可用線程的計(jì)算奖地，根據(jù)可用線程數(shù)目和 Map 數(shù)組的長(zhǎng)度，平均分配處理當(dāng)前待擴(kuò)容的“桶”赋焕。默認(rèn)的是每個(gè)線程需要處理16個(gè)“桶”参歹，所以換句話說，如果當(dāng)前map的容量為16的時(shí)候隆判，那么擴(kuò)容階段就只有一個(gè)線程在擴(kuò)容犬庇。

• 它在擴(kuò)容時(shí)需要用到一個(gè)額外的數(shù)組空間nextTable，它的大小是原table的兩倍侨嘀，一旦擴(kuò)容完成臭挽，原來的table就會(huì)被新的nextTable所取代。

• 擴(kuò)容后咬腕，就是將原來數(shù)組中的內(nèi)容復(fù)制到新的nextTable數(shù)組中去欢峰，這里的復(fù)制轉(zhuǎn)移并不是簡(jiǎn)單的copy，它是有策略的

• 通過前面的分析我們知道，數(shù)組中的元素存在不同的情況纽帖，既有Node(此時(shí)說明是鏈表結(jié)構(gòu))宠漩，也會(huì)有TreeBin(鏈表過長(zhǎng)轉(zhuǎn)換成了紅黑樹)以及null(這部分是還未存放元素的“桶”)。

• 首先在進(jìn)行遍歷復(fù)制的時(shí)候懊直，原數(shù)組中null的位置在新的數(shù)組中同樣位置上會(huì)插入一個(gè)占位符forwarNode節(jié)點(diǎn)哄孤，當(dāng)其他線程在遍歷到當(dāng)前節(jié)點(diǎn)是forwardNode類型，就直接跳過該節(jié)點(diǎn)吹截，繼續(xù)向后遍歷瘦陈。

• 剩下的鏈表和紅黑樹結(jié)構(gòu)中，在復(fù)制到新的數(shù)組中時(shí)會(huì)對(duì)其進(jìn)行拆分波俄，拆分的規(guī)則是將當(dāng)前節(jié)點(diǎn)的hash值與length進(jìn)行取余操作晨逝，假如在原數(shù)組中的位置是index，那么根據(jù)取余的結(jié)果懦铺，如果為0捉貌，就在新數(shù)組的index位置防止，否則不為0的話冬念，就將其放在index+n的位置趁窃，這里的n一般就是16。

? ? ? ?這樣原來數(shù)組中的鏈表和紅黑樹部分就都各自被拆分成了兩份存儲(chǔ)在新的數(shù)組中急前，原來的null位置依然為null醒陆，沒有任何變化，這樣就完成了數(shù)組的擴(kuò)容操作裆针。下面一份關(guān)于擴(kuò)容的示意圖：

首先我們現(xiàn)在假設(shè)當(dāng)前map的容量為16：

concurrentHashMap01.png

其余數(shù)組中的內(nèi)容暫時(shí)不用考慮刨摩，單獨(dú)看這里的index為1和4的位置上的內(nèi)容，假設(shè)其他位置上的內(nèi)容都是null世吨，那么擴(kuò)容后澡刹，數(shù)組的容量就會(huì)變成32，然后1位置上的藍(lán)色節(jié)點(diǎn)會(huì)組成一個(gè)新的鏈表耘婚，放在新數(shù)組中的1位置上罢浇，而1位置上的黃色節(jié)點(diǎn)會(huì)組成新的鏈表放在新數(shù)組的17位置上。同樣的4位置上此時(shí)鏈表長(zhǎng)高度達(dá)到8沐祷，應(yīng)為樹結(jié)構(gòu)嚷闭，但是為了方便表示，這里也將其畫成了鏈表結(jié)構(gòu)戈轿，在拆分后凌受，藍(lán)色黃色節(jié)點(diǎn)各自組成新的鏈表，且長(zhǎng)度減到了4思杯，重新變成了鏈表結(jié)構(gòu)胜蛉，如果拆分后鏈表長(zhǎng)度仍然過長(zhǎng)挠进，擴(kuò)容后仍然會(huì)保持紅黑樹結(jié)構(gòu)。

concurrentHashMap02.png

put方法存放元素

? ? ? ?首先需要明確的是誊册，ConcurrentHashMap中put是不能存放key或者value為null的元素的领突，否則會(huì)直接拋出空指針異常，這一點(diǎn)有別于HashMap案怯。另外因?yàn)镃oncurrentHashMap可以運(yùn)行于多線程環(huán)境中君旦，所以它的put方法邏輯比較復(fù)雜，簡(jiǎn)單來說嘲碱，它的put方法的主要邏輯就是：

• 首先根據(jù)傳入的key計(jì)算對(duì)應(yīng)的table中的位置index

• 判斷table[index]當(dāng)前位置中是否存在元素金砍，如果沒有元素，直接放入麦锯，沒有加鎖操作

• 如果當(dāng)前位置上已經(jīng)存在元素了恕稠，節(jié)點(diǎn)上鎖，然后依次遍歷鏈表節(jié)點(diǎn)扶欣，如果遇到了key和hash都是一致的元素鹅巍，就更新這個(gè)位置上的value，注意這里的上鎖的節(jié)點(diǎn)可以理解為hash值相同組成的鏈表的頭結(jié)點(diǎn)料祠。

• 如果一致遍歷到節(jié)點(diǎn)鏈的末尾骆捧，都沒有找到key和hash都相同的元素，那么就可以認(rèn)為它是一個(gè)插入操作髓绽，此時(shí)就把這個(gè)節(jié)點(diǎn)插入到鏈表末尾敛苇。

• 如果table[index]位置上的內(nèi)容為樹節(jié)點(diǎn)，就按照樹的方式是插入節(jié)點(diǎn)

• 在插入結(jié)束后梧宫，如果是鏈表結(jié)構(gòu)接谨，需要判斷當(dāng)前鏈表長(zhǎng)度是否達(dá)到了8，如果是塘匣，還需要將其轉(zhuǎn)換成紅黑樹。

• 最后同步更新一下當(dāng)前map中的元素?cái)?shù)量

? ? ? ?可以看到巷帝，新版本的ConcurrentHashMap中忌卤，put時(shí)鎖住的是Node節(jié)點(diǎn)，而不是像之前JDK1.6和1.7那樣鎖住整個(gè)segment楞泼。而且在鎖住Node之前的操作也是線程安全的驰徊，它的線程安全就依托于前面介紹過的三個(gè)核心的CAS方法。

size屬性

? ? ? ?因?yàn)榭赡艽嬖诟卟l(fā)的情況堕阔，所以不像HashMap那樣直接調(diào)用size方法就可以準(zhǔn)確獲取當(dāng)前map中的元素個(gè)數(shù)棍厂，在高并發(fā)下，可能存在當(dāng)我們需要獲取size值的時(shí)候超陆，其他線程正在往map中寫數(shù)據(jù)牺弹，我們不能像虛擬機(jī)的垃圾回收一樣浦马，在統(tǒng)計(jì)時(shí)“Stop The World”，所以得到的size值其實(shí)并不是一個(gè)精確的值张漂。對(duì)于這個(gè)大概的size值的獲取晶默，ConcurrentHashMap也是利用了一些策略才得到的，并非直接返回size屬性值航攒。

輔助的內(nèi)部類和變量

@jdk.internal.vm.annotation.Contended static final class CounterCell {
 volatile long value;
 CounterCell(long x) { value = x; }
}
//它是一個(gè)基于計(jì)數(shù)器的值磺陡，其實(shí)也就是存放的是map中的元素個(gè)數(shù)，使用CAS更新
//但是它并不是強(qiáng)制的等于當(dāng)前map中元素的個(gè)數(shù)
private transient volatile long baseCount;
//當(dāng)調(diào)整大小漠畜、創(chuàng)建CounterCells時(shí)用于CAS自旋鎖操作
private transient volatile int cellsBusy;
//計(jì)數(shù)表币他，當(dāng)非空的時(shí)候，它的容量是2的冪
private transient volatile CounterCell[] counterCells;

size方法

public int size() {
 long n = sumCount();
 return ((n < 0L) ? 0 :
 (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
 (int)n);
}
//JDK1.8開始新增的一個(gè)方法憔狞，它與size方法很類似圆丹，而且從它的注釋上來看，很推薦使用它來代替size方法
public long mappingCount() {
 long n = sumCount();
 return (n < 0L) ? 0L : n; // ignore transient negative values
}
//無論是size還是mappingCount躯喇，都沒有直接返回baseCount的值
//而是在baseCount的基礎(chǔ)上繼續(xù)進(jìn)行了計(jì)算辫封，即便如此，它得到的仍然是一個(gè)估計(jì)值
final long sumCount() {
   CounterCell[] as = counterCells; CounterCell a;
   long sum = baseCount;
   if (as != null) {
     for (int i = 0; i < as.length; ++i) {
       if ((a = as[i]) != null)
         sum += a.value;
       }
     }
   return sum;
}

addCount方法

? ? ? ?前面在介紹put方法的時(shí)候廉丽，在最后一步說到“同步更新一下當(dāng)前map中的元素?cái)?shù)量”倦微，這句話在put方法的代碼中其實(shí)就是調(diào)用addCount方法，而這個(gè)方法會(huì)做兩件事情：利用CAS對(duì)baseCount的值進(jìn)行更新正压，然后判斷此時(shí)是否需要擴(kuò)容欣福。

ConcurrentHashMap的問題

size的準(zhǔn)確性

? ? ? ?上面說過，它的size方法得到的值并不是一個(gè)準(zhǔn)確的值焦履，但是在大多數(shù)情況下拓劝，這個(gè)值是可以保證的，只有在極端并發(fā)環(huán)境下才有可能出現(xiàn)不一致的情況嘉裤，所以我們?cè)谑褂脮r(shí)郑临，不能依賴于size方法來確定map中精確的元素個(gè)數(shù)，應(yīng)當(dāng)有適當(dāng)誤差屑宠。并且現(xiàn)在也更加推薦了mappingCount方法來代替size方法使用厢洞。

數(shù)據(jù)覆蓋問題

? ? ? ?當(dāng)我們?cè)诟卟l(fā)環(huán)境下，純粹put或者get操作典奉，其實(shí)是沒有問題的躺翻，但是當(dāng)我們調(diào)用get之后，在下次調(diào)用put方法之前卫玖，如果有其他線程也對(duì)該map調(diào)用了put方法公你，那么后續(xù)在調(diào)用put方法的時(shí)候，就有可能把剛才其他線程填入的值覆蓋掉假瞬，即使ConcurrentHashMap中使用CAS操作陕靠，仍然不可能完全避免這種情況迂尝。但是這中屬于具體編碼問題，控制合理的話懦傍，編碼人員可以避免這樣做雹舀，只要稍加注意，可以采用一些額外的手段保證它的一致性粗俱。

空值問題

? ? ? ?一定不能使用ConcurrentHashMap的put方法放入一個(gè)key或value為null的元素说榆，否者直接NullPointerException。

LinkedHashMap

原理

可以看以下它的定義：

public class LinkedHashMap<K,V>
 extends HashMap<K,V>
 implements Map<K,V>

? ? ? ?從它的定義中可以明顯的看出寸认，它就是HashMap的子類签财，所以它的一切都是基于HashMap的，查看它的源代碼可以看到偏塞，它的初始化唱蒸，擴(kuò)容，元素的存放與獲取底部都是基于HashMap的那一套原理灸叼，所以這里就不再繼續(xù)介紹了神汹，但是它有一個(gè)HashMap沒有的特點(diǎn)，就是雙向鏈表古今，簡(jiǎn)單來說就是：它的本身的存儲(chǔ)結(jié)構(gòu)依然采用HashMap的那套數(shù)組加鏈表的方式屁魏，但是它的節(jié)點(diǎn)內(nèi)部又多維護(hù)了兩個(gè)引用before和after，before指向當(dāng)前元素之前放入的元素捉腥，next指向緊接著放入的元素引用氓拼，所以它們的引用關(guān)系與放入Map中的元素順序有關(guān)，也就是說它除了之前介紹的每個(gè)“桶”內(nèi)部的鏈表結(jié)構(gòu)抵碟，桶與桶之間的不同節(jié)點(diǎn)也有一個(gè)引用在維護(hù)桃漾，并且是雙向的鏈表結(jié)構(gòu)，這樣整體的感覺就是：

LinkedHashMap01.png

概括起來就是：它的主體存儲(chǔ)結(jié)構(gòu)仍然是HashMap的那套邏輯拟逮，只是在HashMap的基礎(chǔ)上撬统，每個(gè)節(jié)點(diǎn)又多維護(hù)了一份之前存入的元素引用以及之后存入的元素引用，這樣每個(gè)節(jié)點(diǎn)內(nèi)部算起來實(shí)際上有三個(gè)引用（HashMap本身就有一個(gè)鏈表引用唱歧，主要是hash值相同的元素之間的引用宪摧，然后又有了這個(gè)新增的兩個(gè)引用）。

LinkedHashMap02.png

特點(diǎn)

? ? ? ?從它的結(jié)構(gòu)可以看出颅崩，HashMap所擁有的特性它都是存在的，同時(shí)因?yàn)榧尤肓穗p向鏈表的維護(hù)蕊苗，所以它是一個(gè)有序的Map沿后，前面說過，HashMap是不保證有序的朽砰，也就是它遍歷的結(jié)果可能與它放入的順序不是一致的（不保證結(jié)果有序性尖滚，并不是一定是無序的）喉刘，而LinkedHashMap的結(jié)果必定是有序的，所以如果需要使用有序的Map場(chǎng)景漆弄，可以考慮使用LinkedHashMap睦裳。

使用場(chǎng)景

? ? ? ?前面介紹過的Map的使用時(shí)機(jī)這里都完全可以適用于LinkedHashMap，此外它還可以保證結(jié)果的有序性撼唾，所以如果對(duì)遍歷的有序性有要求廉邑，可以使用它。

? ? ? ?另外：它還可以用來實(shí)現(xiàn)LRU(Least recently used, 最近最少使用)算法倒谷，這是因?yàn)樗鼉?nèi)部有一個(gè)removeEldestEntry方法蛛蒙，這個(gè)方法的返回值為boolean類型，如果我們需要實(shí)現(xiàn)LRU渤愁，可以繼承自LinkedHashMap牵祟，重寫它的方法，此時(shí)抖格，如果需要使用實(shí)現(xiàn)LRU诺苹，它有一個(gè)屬性必須設(shè)置為true，那就是：accessOrder雹拄，只有它為true的時(shí)候收奔，雙向鏈表中的元素就會(huì)按照訪問先后順序排列。這里有一個(gè)簡(jiǎn)單使用的例子：

public class LRU<K, V> extends LinkedHashMap<K, V> implements Map<K, V> {
   public LRU(int initialCapacity, float loadFactor, boolean accessOrder) {
   super(initialCapacity, loadFactor, accessOrder);
 }
 @Override
 protected boolean removeEldestEntry(Entry<K, V> eldest) {
   //保證map中元素個(gè)數(shù)
   return size() > 6;
 }
 public static void main(String[] args) {
   LRU<Character, Integer> lru = new LRU<Character, Integer>(
     16, 0.75f, true);
   String s = "abcdefghijk";
   for (int i = 0, len = s.length(); i < len; i++) {
     lru.put(s.charAt(i), i);
   }
   System.out.println(lru); //{f=5, g=6, h=7, i=8, j=9, k=10}
 }
}

? ? ? ?最終得到的結(jié)果可以看到办桨，map中始終都是只包含6個(gè)元素筹淫，如果過多，之前插入的節(jié)點(diǎn)都會(huì)被拋棄呢撞，拋棄的都是最近最少使用的節(jié)點(diǎn)损姜。

存在的問題

? ? ? ?總體來說，前面說道到的HashMap的存在的問題在這里仍然是存在的殊霞，它不是線程安全的摧阅，而且它的存儲(chǔ)開銷比HashMap更大，這個(gè)也好理解绷蹲，畢竟它又多了一個(gè)雙向鏈表的維護(hù)棒卷，所以無論是復(fù)雜度還是維護(hù)成本都會(huì)高一些。

ConcurrentSkipListMap

介紹

? ? ? ?最后再來看一個(gè)基于跳表的數(shù)據(jù)結(jié)構(gòu)祝钢，它是一個(gè)支持排序和并發(fā)的Map比规，是線程安全的，這種跳表的結(jié)構(gòu)我們正常開發(fā)中很少用到拦英，所以對(duì)于我而言蜒什，它是一個(gè)知識(shí)盲點(diǎn)，下面就簡(jiǎn)單介紹一下這個(gè)跳表疤估。

原理

? ? ? ?在介紹跳表之前灾常，首先需要知道傳統(tǒng)的鏈表結(jié)構(gòu)是什么樣子霎冯，傳統(tǒng)的鏈表是一個(gè)線性結(jié)構(gòu)，如果我們需要查詢某個(gè)元素钞瀑，需要從鏈表的頭部挨個(gè)遍歷訪問沈撞，然后找出目標(biāo)元素。所以雕什，鏈表結(jié)構(gòu)的查詢需要O(n)的時(shí)間缠俺，它與鏈表長(zhǎng)度緊密相關(guān)。而跳表就是基于傳統(tǒng)鏈表上做的一次改進(jìn)监徘，它是采用空間換時(shí)間的方式來提高查詢效率晋修，這里以一個(gè)最簡(jiǎn)單的方式來描述一下它的數(shù)據(jù)結(jié)構(gòu)，實(shí)際情況中它的結(jié)構(gòu)會(huì)比下面的圖示復(fù)雜一點(diǎn)凰盔，后面會(huì)介紹：

SkipListMap1.png

上面的結(jié)構(gòu)就是最簡(jiǎn)單的一種跳表的結(jié)構(gòu)墓卦，首先需要明確的是：跳表天然是有序的，所以上面的鏈表結(jié)構(gòu)是有序的户敬。它除了正常的鏈表結(jié)構(gòu)(有一個(gè)引用指向下一個(gè)節(jié)點(diǎn))外落剪，每個(gè)節(jié)點(diǎn)多了一個(gè)引用，用于指向下下個(gè)節(jié)點(diǎn)尿庐，這里忠怖，如果我們查詢一個(gè)值為12的元素，具體查詢步驟就是：

SkipListMap2.png

1. 首先12與1比較抄瑟，比1大凡泣，向后找到6節(jié)點(diǎn)

2. 12與6比較，比6節(jié)點(diǎn)大皮假，向后找到9節(jié)點(diǎn)

3. 12與9比較鞋拟，比9節(jié)點(diǎn)大，向后找到17節(jié)點(diǎn)惹资，說明12在9節(jié)點(diǎn)與17節(jié)點(diǎn)之間

4. 12與9比較贺纲，比9節(jié)點(diǎn)大，向后找到12節(jié)點(diǎn)褪测，即為目標(biāo)節(jié)點(diǎn)

? ? ? ?可以看到猴誊，它的查詢是跳躍式進(jìn)行的，跳過了中間的3和7節(jié)點(diǎn)侮措，所以它查詢的時(shí)間復(fù)雜度為O(n/2)懈叹。但是前面也說過了，這只是最簡(jiǎn)單的一種方式分扎，實(shí)際情況中项阴，一個(gè)鏈表節(jié)點(diǎn)的內(nèi)部可能包含的不僅僅只有兩個(gè)引用(下一個(gè)節(jié)點(diǎn)+下下個(gè)節(jié)點(diǎn))，每個(gè)節(jié)點(diǎn)內(nèi)部到底會(huì)帶有多少個(gè)后續(xù)節(jié)點(diǎn)的引用是隨機(jī)生成的笆包，所以實(shí)際情況可能是這樣：

SkipListMap3.png

每個(gè)節(jié)點(diǎn)中擁有的后續(xù)節(jié)點(diǎn)的引用個(gè)數(shù)不定环揽，這是一種概率均衡技術(shù)，而不是強(qiáng)制性均衡約束庵佣，所以對(duì)于節(jié)點(diǎn)的插入和刪除比傳統(tǒng)的平衡樹算法更為簡(jiǎn)潔高效歉胶。

查找

SkipListMap4.png

例如查找值為12的元素，就會(huì)按照紅色箭頭上的數(shù)字步驟查詢即可巴粪，這里就不再贅述了通今。

插入

1. 找到需要插入的位置

2. 申請(qǐng)新的節(jié)點(diǎn)

3. 調(diào)整指針

SkipListMap5.png

上圖的解釋如下：

? ? ? ?假設(shè)我們這里需要插入一個(gè)值為15的節(jié)點(diǎn)，最后找到的位置就是上圖中紅色圓圈的位置肛根，然后申請(qǐng)新的節(jié)點(diǎn)辫塌，將節(jié)點(diǎn)調(diào)整指針，放入12的后面即可派哲，這里有一個(gè)技巧：使用一個(gè)update數(shù)組保存將要插入位置之前的節(jié)點(diǎn)直接引用臼氨，這里就是上圖中紅色線框框住的三個(gè)引用，因?yàn)樵诓迦牍?jié)點(diǎn)時(shí)芭届，只有這三個(gè)引用可能涉及到指針的調(diào)整储矩。調(diào)整后的情況即為：

SkipListMap6.png

刪除

? ? ? ?刪除操作其實(shí)和插入很類似，找到節(jié)點(diǎn)褂乍，將其刪除持隧，然后調(diào)整指針即完成整個(gè)刪除操作，插入邏輯中用到的update數(shù)組技巧在這里仍然適用逃片。

Java中的ConcurrentSkipListMap實(shí)現(xiàn)

在java中屡拨，跳躍表是具有層級(jí)結(jié)構(gòu)的，即所謂的level褥实，整體結(jié)構(gòu)大致如下：

SkipListMap7.png

跳表的結(jié)構(gòu)具備以下特征：

• 最底層包含所有節(jié)點(diǎn)的一個(gè)有序的鏈表

• 每一層都是一個(gè)有序的鏈表

• 每個(gè)節(jié)點(diǎn)都有兩個(gè)指針呀狼，一個(gè)指向右側(cè)節(jié)點(diǎn)（沒有則為空），一個(gè)指向下層節(jié)點(diǎn)（沒有則為空）

• 必備一個(gè)頭節(jié)點(diǎn)指向最高層的第一個(gè)節(jié)點(diǎn)性锭，通過它可以遍歷整張表赠潦，如上圖中的左上角的藍(lán)色節(jié)點(diǎn)BASE_HEADER

在新增節(jié)點(diǎn)時(shí)，假設(shè)此時(shí)我們加入一個(gè)值為80的節(jié)點(diǎn)草冈，它是通過如下步驟來添加的：

1. 首先她奥，它會(huì)將80節(jié)點(diǎn)加入level1中的鏈表中

SkipListMap8.png

2. 根據(jù)概率算法，計(jì)算處一個(gè)level值怎棱，這里假設(shè)為4哩俭，然后根據(jù)跳表算法描述，構(gòu)建新的索引

SkipListMap9.png

3. 將各個(gè)索引層次上的節(jié)點(diǎn)連接

SkipListMap10.png

其他

目前常用的key-value數(shù)據(jù)結(jié)構(gòu)有三種：Hash表拳恋、紅黑樹以及SkipList凡资，它們各自有著不同的優(yōu)缺點(diǎn)（不考慮刪除操作）：

• Hash表：插入、查找最快，為O(1)隙赁，數(shù)據(jù)的有序化需要顯式的排序操作

• 紅黑樹：插入垦藏、查找為O(logN)，但是常數(shù)項(xiàng)較小伞访，如果采用無鎖化實(shí)現(xiàn)掂骏，復(fù)雜度很高，一般需要加鎖厚掷，數(shù)據(jù)天然有序

• SkipList：插入弟灼、查找為O(n)，常數(shù)項(xiàng)比紅黑樹要大冒黑，底層結(jié)構(gòu)為鏈表田绑，可無鎖實(shí)現(xiàn)，數(shù)據(jù)天然有序