集合

1. Arraylist與 LinkedList 異同點(diǎn)旋炒？

2. HashMap的底層數(shù)據(jù)結(jié)構(gòu)是什么掌测？

3. 解決hash沖突的辦法有哪些乖阵？HashMap用的哪種旅择？

4. HashMap默認(rèn)加載因子是多少惭笑？為什么是 0.75，不是 0.6 或者 0.8 生真？

5. HashMap的哈希算法

6. HashMap 的put方法流程沉噩？

7. ConcurrentHashMap 的實(shí)現(xiàn)原理是什么？

8. ConcurrentHashMap 的 put 方法執(zhí)行邏輯是什么柱蟀？

9. 講一講快速失敗(fail-fast)和安全失敗(fail-safe)

10. 介紹下copyOnWriteArrayList

1. 是否保證線程安全川蒙；底層數(shù)據(jù)結(jié)構(gòu)；插入和刪除长已；空間占用

2. 在JDK1.7 和JDK1.8 中有所差別：
   在JDK1.7 中畜眨，由“數(shù)組+鏈表”組成，數(shù)組是 HashMap 的主體术瓮，鏈表則是主要為了解決哈希沖突而存在的康聂。
   在JDK1.8 中，由“數(shù)組+鏈表+紅黑樹(shù)”組成胞四。當(dāng)鏈表過(guò)長(zhǎng)恬汁，則會(huì)嚴(yán)重影響 HashMap 的性能，紅黑樹(shù)搜索時(shí)間復(fù)雜度是 O(logn)辜伟，而鏈表是糟糕的 O(n)氓侧。因此，JDK1.8 對(duì)數(shù)據(jù)結(jié)構(gòu)做了進(jìn)一步的優(yōu)化导狡，引入了紅黑樹(shù)约巷，鏈表和紅黑樹(shù)在達(dá)到一定條件會(huì)進(jìn)行轉(zhuǎn)換：
   當(dāng)鏈表超過(guò) 8 且數(shù)據(jù)總量超過(guò) 64 才會(huì)轉(zhuǎn)紅黑樹(shù)。
   將鏈表轉(zhuǎn)換成紅黑樹(shù)前會(huì)判斷旱捧，如果當(dāng)前數(shù)組的長(zhǎng)度小于 64（大于64進(jìn)行擴(kuò)容）独郎，那么會(huì)選擇先進(jìn)行數(shù)組擴(kuò)容，而不是轉(zhuǎn)換為紅黑樹(shù)廊佩，以減少搜索時(shí)間囚聚。

3. 解決Hash沖突方法有:開(kāi)放定址法、再哈希法标锄、鏈地址法（拉鏈法）顽铸、建立公共溢出區(qū)。HashMap中采用的是 鏈地址法 料皇。
   開(kāi)放定址法也稱為再散列法谓松，基本思想就是星压，如果p=H(key)出現(xiàn)沖突時(shí)，則以p為基礎(chǔ)鬼譬，再次hash娜膘，p1=H(p),如果p1再次出現(xiàn)沖突，則以p1為基礎(chǔ)优质，以此類推竣贪，直到找到一個(gè)不沖突的哈希地址pi。 因此開(kāi)放定址法所需要的hash表的長(zhǎng)度要大于等于所需要存放的元素巩螃，而且因?yàn)榇嬖谠俅蝖ash演怎，所以只能在刪除的節(jié)點(diǎn)上做標(biāo)記，而不能真正刪除節(jié)點(diǎn)避乏。
   再哈希法(雙重散列爷耀，多重散列)，提供多個(gè)不同的hash函數(shù)拍皮，當(dāng)R1=H1(key1)發(fā)生沖突時(shí)歹叮，再計(jì)算R2=H2(key1)，直到?jīng)]有沖突為止铆帽。 這樣做雖然不易產(chǎn)生堆集咆耿，但增加了計(jì)算的時(shí)間。
   鏈地址法(拉鏈法)锄贼，將哈希值相同的元素構(gòu)成一個(gè)同義詞的單鏈表,并將單鏈表的頭指針存放在哈希表的第i個(gè)單元中票灰，查找、插入和刪除主要在同義詞鏈表中進(jìn)行宅荤。鏈表法適用于經(jīng)常進(jìn)行插入和刪除的情況屑迂。
   建立公共溢出區(qū)，將哈希表分為公共表和溢出表冯键，當(dāng)溢出發(fā)生時(shí)惹盼，將所有溢出數(shù)據(jù)統(tǒng)一放到溢出區(qū)。

4. 默認(rèn)的loadFactor是0.75惫确，0.75是對(duì)空間和時(shí)間效率的一個(gè)平衡選擇手报，一般不要修改，除非在時(shí)間和空間比較特殊的情況下 ：
   如果內(nèi)存空間很多而又對(duì)時(shí)間效率要求很高改化，可以降低負(fù)載因子Load factor的值 掩蛤。
   相反，如果內(nèi)存空間緊張而對(duì)時(shí)間效率要求不高陈肛，可以增加負(fù)載因子loadFactor的值揍鸟，這個(gè)值可以大于1。

5. key值的hashCode無(wú)符號(hào)右移16位與hashCode本身進(jìn)行異或運(yùn)算

// jdk1.8
static final int hash(Object key) {   
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    /* 
     h = key.hashCode() 為第一步：取hashCode值
     h ^ (h >>> 16)  為第二步：hashCode無(wú)符號(hào)右移16位與hashCode本身進(jìn)行異或運(yùn)算
     https://cloud.tencent.com/developer/article/1338265
    */
}

6. 以JDK1.8為例句旱，簡(jiǎn)要流程如下：
   首先根據(jù) key 的值計(jì)算 hash 值阳藻，找到該元素在數(shù)組中存儲(chǔ)的下標(biāo)晰奖；
   如果數(shù)組是空的，則調(diào)用 resize 進(jìn)行初始化腥泥；
   如果沒(méi)有哈希沖突直接放在對(duì)應(yīng)的數(shù)組下標(biāo)里匾南；
   如果沖突了，且 key 已經(jīng)存在蛔外，就覆蓋掉 value蛆楞；
   如果沖突后，發(fā)現(xiàn)該節(jié)點(diǎn)是紅黑樹(shù)冒萄，就將這個(gè)節(jié)點(diǎn)掛在樹(shù)上臊岸；
   如果沖突后是鏈表橙数，判斷該鏈表是否大于 8 尊流，如果大于 8 并且數(shù)組容量小于 64，就進(jìn)行擴(kuò)容灯帮；如果鏈表節(jié)點(diǎn)大于 8 并且數(shù)組的容量大于 64崖技，則將這個(gè)結(jié)構(gòu)轉(zhuǎn)換為紅黑樹(shù)；否則钟哥，鏈表插入鍵值對(duì)迎献，若 key 存在，就覆蓋掉 value腻贰。

7. ConcurrentHashMap 在 JDK1.7 和 JDK1.8 的實(shí)現(xiàn)方式是不同的吁恍。

先來(lái)看下JDK1.7

JDK1.7中的ConcurrentHashMap 是由 Segment 數(shù)組結(jié)構(gòu)和 HashEntry 數(shù)組結(jié)構(gòu)組成，即ConcurrentHashMap 把哈希桶切分成小數(shù)組（Segment ）播演，每個(gè)小數(shù)組有 n 個(gè) HashEntry 組成冀瓦。

其中，Segment 繼承了 ReentrantLock写烤，所以 Segment 是一種可重入鎖翼闽，扮演鎖的角色；HashEntry 用于存儲(chǔ)鍵值對(duì)數(shù)據(jù)洲炊。

image.png

首先將數(shù)據(jù)分為一段一段的存儲(chǔ)感局，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個(gè)線程占用鎖訪問(wèn)其中一個(gè)段數(shù)據(jù)時(shí)暂衡，其他段的數(shù)據(jù)也能被其他線程訪問(wèn)询微，能夠?qū)崿F(xiàn)真正的并發(fā)訪問(wèn)。

再來(lái)看下JDK1.8

在數(shù)據(jù)結(jié)構(gòu)上狂巢， JDK1.8 中的ConcurrentHashMap 選擇了與 HashMap 相同的數(shù)組+鏈表+紅黑樹(shù)結(jié)構(gòu)撑毛；在鎖的實(shí)現(xiàn)上，拋棄了原有的 Segment 分段鎖隧膘，采用 CAS + synchronized 實(shí)現(xiàn)更加低粒度的鎖代态。

將鎖的級(jí)別控制在了更細(xì)粒度的哈希桶元素級(jí)別寺惫，也就是說(shuō)只需要鎖住這個(gè)鏈表頭結(jié)點(diǎn)（紅黑樹(shù)的根節(jié)點(diǎn)），就不會(huì)影響其他的哈希桶元素的讀寫(xiě)蹦疑，大大提高了并發(fā)度西雀。

image.png

先來(lái)看JDK1.7

首先，會(huì)嘗試獲取鎖歉摧，如果獲取失敗艇肴，利用自旋獲取鎖；如果自旋重試的次數(shù)超過(guò) 64 次叁温，則改為阻塞獲取鎖再悼。

獲取到鎖后：

1. 將當(dāng)前 Segment 中的 table 通過(guò) key 的 hashcode 定位到 HashEntry。
2. 遍歷該 HashEntry膝但，如果不為空則判斷傳入的 key 和當(dāng)前遍歷的 key 是否相等冲九，相等則覆蓋舊的 value。
3. 不為空則需要新建一個(gè) HashEntry 并加入到 Segment 中跟束，同時(shí)會(huì)先判斷是否需要擴(kuò)容莺奸。
4. 釋放 Segment 的鎖。

再來(lái)看JDK1.8
大致可以分為以下步驟：

1. 判斷key和valve是否為null冀宴，是則拋出異常
2. 根據(jù) key 計(jì)算出 hash值灭贷。
3. 判斷是否需要進(jìn)行初始化。
4. 定位到 Node略贮，拿到首節(jié)點(diǎn) f甚疟，判斷首節(jié)點(diǎn) f：

• 如果為 null ，則通過(guò)cas的方式嘗試添加逃延。
• 如果為 f.hash = MOVED = -1 览妖，說(shuō)明其他線程在擴(kuò)容，參與一起擴(kuò)容真友。>>
• 如果都不滿足 黄痪，synchronized 鎖住 f 節(jié)點(diǎn)，判斷是鏈表還是紅黑樹(shù)盔然，遍歷插入桅打。

4. 當(dāng)在鏈表長(zhǎng)度達(dá)到8的時(shí)候，數(shù)組擴(kuò)容或者將鏈表轉(zhuǎn)換為紅黑樹(shù)愈案。

9. 快速失斖ξ病（fail—fast）

在用迭代器遍歷一個(gè)集合對(duì)象時(shí)，如果遍歷過(guò)程中對(duì)集合對(duì)象的內(nèi)容進(jìn)行了修改（增加站绪、刪除遭铺、修改），則會(huì)拋出Concurrent Modification Exception。

• 原理：迭代器在遍歷時(shí)直接訪問(wèn)集合中的內(nèi)容魂挂，并且在遍歷過(guò)程中使用一個(gè) modCount 變量甫题。集合在被遍歷期間如果內(nèi)容發(fā)生變化，就會(huì)改變modCount的值涂召。每當(dāng)?shù)魇褂胔ashNext()/next()遍歷下一個(gè)元素之前坠非，都會(huì)檢測(cè)modCount變量是否為expectedmodCount值，是的話就返回遍歷果正；否則拋出異常炎码，終止遍歷。
• 注意：這里異常的拋出條件是檢測(cè)到 modCount秋泳！=expectedmodCount 這個(gè)條件潦闲。如果集合發(fā)生變化時(shí)修改modCount值剛好又設(shè)置為了expectedmodCount值，則異常不會(huì)拋出迫皱。因此歉闰，不能依賴于這個(gè)異常是否拋出而進(jìn)行并發(fā)操作的編程，這個(gè)異常只建議用于檢測(cè)并發(fā)修改的bug舍杜。
• 場(chǎng)景：java.util包下的集合類都是快速失敗的新娜，不能在多線程下發(fā)生并發(fā)修改（迭代過(guò)程中被修改），比如HashMap既绩、ArrayList 這些集合類。

安全失敾够荨（fail—safe）

采用安全失敗機(jī)制的集合容器饲握，在遍歷時(shí)不是直接在集合內(nèi)容上訪問(wèn)的，而是先復(fù)制原有集合內(nèi)容蚕键，在拷貝的集合上進(jìn)行遍歷救欧。

• 原理：由于迭代時(shí)是對(duì)原集合的拷貝進(jìn)行遍歷，所以在遍歷過(guò)程中對(duì)原集合所作的修改并不能被迭代器檢測(cè)到锣光，所以不會(huì)觸發(fā)Concurrent Modification Exception笆怠。
• 缺點(diǎn)：基于拷貝內(nèi)容的優(yōu)點(diǎn)是避免了Concurrent Modification Exception，但同樣地誊爹，每次復(fù)制數(shù)組都需要占用了內(nèi)存蹬刷。而且為了 內(nèi)容最終一致性要在修改方法上加鎖
• 場(chǎng)景：java.util.concurrent包下的容器都是安全失敗，可以在多線程下并發(fā)使用频丘，并發(fā)修改办成，比如：ConcurrentHashMap。

/**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        final ReentrantLock lock = this.lock;//重入鎖
        lock.lock();//加鎖啦
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);//拷貝新數(shù)組
            newElements[len] = e;
            setArray(newElements);//將引用指向新數(shù)組  1
            return true;
        } finally {
            lock.unlock();//解鎖啦
        }
    }

copyOnWriteArrayList,顧名思義寫(xiě)時(shí)復(fù)制搂漠，讀取數(shù)據(jù)時(shí)候不加鎖迂卢，但是讀取的數(shù)據(jù)不一定是實(shí)時(shí)的。修改數(shù)據(jù)的時(shí)候復(fù)制并加鎖。場(chǎng)景適合讀多寫(xiě)少而克，數(shù)據(jù)較小靶壮，不要求實(shí)時(shí)性的的場(chǎng)景