大廠必問的Java集合面試題

本文目錄：

常見的集合有哪些？

List 、Set和Map 的區(qū)別

ArrayList 了解嗎？

ArrayList 的擴(kuò)容機(jī)制？

怎么在遍歷 ArrayList 時(shí)移除一個(gè)元素？

Arraylist 和 Vector 的區(qū)別

Arraylist 與 LinkedList 區(qū)別

HashMap

解決hash沖突的辦法有哪些？HashMap用的哪種？

使用的hash算法？

擴(kuò)容過程？

put方法流程？

紅黑樹的特點(diǎn)？

為什么使用紅黑樹而不使用AVL樹？

在解決 hash 沖突的時(shí)候，為什么選擇先用鏈表，再轉(zhuǎn)紅黑樹?

HashMap 的長(zhǎng)度為什么是 2 的冪次方？

HashMap默認(rèn)加載因子是多少？為什么是 0.75？

一般用什么作為HashMap的key?

HashMap為什么線程不安全？

HashMap和HashTable的區(qū)別？

LinkedHashMap底層原理？

講一下TreeMap？

HashSet底層原理？

HashSet、LinkedHashSet 和 TreeSet 的區(qū)別？

什么是fail fast？

什么是fail safe？

講一下ArrayDeque？

哪些集合類是線程安全的？哪些不安全？

迭代器 Iterator 是什么？

Iterator 和 ListIterator 有什么區(qū)別？

并發(fā)容器

ConcurrentHashMap

put執(zhí)行流程？

怎么擴(kuò)容？

ConcurrentHashMap 和 Hashtable 的區(qū)別？

CopyOnWrite

ConcurrentLinkedQueue

阻塞隊(duì)列

JDK提供的阻塞隊(duì)列

原理

本文已經(jīng)收錄到github倉庫，此倉庫用于分享互聯(lián)網(wǎng)大廠高頻面試題、Java核心知識(shí)總結(jié)，包括Java基礎(chǔ)、并發(fā)、MySQL、Springboot、MyBatis、Redis、RabbitMQ等等，面試必備！歡迎大家star！

github地址：https://github.com/Tyson0314/Java-learning

常見的集合有哪些？

Java集合類主要由兩個(gè)接口Collection和Map派生出來的，Collection有三個(gè)子接口：List、Set、Queue。

Java集合框架圖如下：

List代表了有序可重復(fù)集合，可直接根據(jù)元素的索引來訪問；Set代表無序不可重復(fù)集合，只能根據(jù)元素本身來訪問；Queue是隊(duì)列集合。Map代表的是存儲(chǔ)key-value對(duì)的集合，可根據(jù)元素的key來訪問value。

集合體系中常用的實(shí)現(xiàn)類有ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap等實(shí)現(xiàn)類。

List 、Set和Map 的區(qū)別

List 以索引來存取元素，有序的，元素是允許重復(fù)的，可以插入多個(gè)null；

Set 不能存放重復(fù)元素，無序的，只允許一個(gè)null；

Map 保存鍵值對(duì)映射；

List 底層實(shí)現(xiàn)有數(shù)組、鏈表兩種方式；Set、Map 容器有基于哈希存儲(chǔ)和紅黑樹兩種方式實(shí)現(xiàn)；

Set 基于 Map 實(shí)現(xiàn)，Set 里的元素值就是 Map的鍵值。

ArrayList 了解嗎？

ArrayList 的底層是動(dòng)態(tài)數(shù)組，它的容量能動(dòng)態(tài)增長(zhǎng)。在添加大量元素前，應(yīng)用可以使用ensureCapacity操作增加 ArrayList 實(shí)例的容量。ArrayList 繼承了 AbstractList ，并實(shí)現(xiàn)了 List 接口。

ArrayList 的擴(kuò)容機(jī)制？

ArrayList擴(kuò)容的本質(zhì)就是計(jì)算出新的擴(kuò)容數(shù)組的size后實(shí)例化，并將原有數(shù)組內(nèi)容復(fù)制到新數(shù)組中去。默認(rèn)情況下，新的容量會(huì)是原容量的1.5倍。以JDK1.8為例說明:

public boolean add(E e) { //判斷是否可以容納e，若能，則直接添加在末尾；若不能，則進(jìn)行擴(kuò)容，然后再把e添加在末尾 ensureCapacityInternal(size + 1); // Increments modCount!! //將e添加到數(shù)組末尾 elementData[size++] = e; return true; } // 每次在add()一個(gè)元素時(shí)，arraylist都需要對(duì)這個(gè)list的容量進(jìn)行一個(gè)判斷。通過ensureCapacityInternal()方法確保當(dāng)前ArrayList維護(hù)的數(shù)組具有存儲(chǔ)新元素的能力，經(jīng)過處理之后將元素存儲(chǔ)在數(shù)組elementData的尾部 private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { //如果傳入的是個(gè)空數(shù)組則最小容量取默認(rèn)容量與minCapacity之間的最大值 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; // 若ArrayList已有的存儲(chǔ)能力滿足最低存儲(chǔ)要求，則返回add直接添加元素；如果最低要求的存儲(chǔ)能力>ArrayList已有的存儲(chǔ)能力，這就表示ArrayList的存儲(chǔ)能力不足，因此需要調(diào)用 grow();方法進(jìn)行擴(kuò)容 if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // 獲取elementData數(shù)組的內(nèi)存空間長(zhǎng)度 int oldCapacity = elementData.length; // 擴(kuò)容至原來的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); //校驗(yàn)容量是否夠 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //若預(yù)設(shè)值大于默認(rèn)的最大值，檢查是否溢出 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 調(diào)用Arrays.copyOf方法將elementData數(shù)組指向新的內(nèi)存空間 //并將elementData的數(shù)據(jù)復(fù)制到新的內(nèi)存空間 elementData = Arrays.copyOf(elementData, newCapacity); }

怎么在遍歷 ArrayList 時(shí)移除一個(gè)元素？

foreach刪除會(huì)導(dǎo)致快速失敗問題，可以使用迭代器的 remove() 方法。

Iterator itr = list.iterator(); while(itr.hasNext()) { if(itr.next().equals("jay") { itr.remove(); } }

Arraylist 和 Vector 的區(qū)別

ArrayList在內(nèi)存不夠時(shí)默認(rèn)是擴(kuò)展50% + 1個(gè)，Vector是默認(rèn)擴(kuò)展1倍。

Vector屬于線程安全級(jí)別的，但是大多數(shù)情況下不使用Vector，因?yàn)椴僮鱒ector效率比較低。

Arraylist 與 LinkedList 區(qū)別

ArrayList基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)；LinkedList基于鏈表實(shí)現(xiàn)。

對(duì)于隨機(jī)index訪問的get和set方法，ArrayList的速度要優(yōu)于LinkedList。因?yàn)锳rrayList直接通過數(shù)組下標(biāo)直接找到元素；LinkedList要移動(dòng)指針遍歷每個(gè)元素直到找到為止。

新增和刪除元素，LinkedList的速度要優(yōu)于ArrayList。因?yàn)锳rrayList在新增和刪除元素時(shí)，可能擴(kuò)容和復(fù)制數(shù)組；LinkedList實(shí)例化對(duì)象需要時(shí)間外，只需要修改指針即可。

HashMap

HashMap 使用數(shù)組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）實(shí)現(xiàn)的， 鏈表長(zhǎng)度大于8（TREEIFY_THRESHOLD）時(shí)，會(huì)把鏈表轉(zhuǎn)換為紅黑樹，紅黑樹節(jié)點(diǎn)個(gè)數(shù)小于6（UNTREEIFY_THRESHOLD）時(shí)才轉(zhuǎn)化為鏈表，防止頻繁的轉(zhuǎn)化。

解決hash沖突的辦法有哪些？HashMap用的哪種？

解決Hash沖突方法有:開放定址法、再哈希法、鏈地址法。HashMap中采用的是 鏈地址法 。

開放定址法基本思想就是，如果p=H(key)出現(xiàn)沖突時(shí)，則以p為基礎(chǔ)，再次hash，p1=H(p),如果p1再次出現(xiàn)沖突，則以p1為基礎(chǔ)，以此類推，直到找到一個(gè)不沖突的哈希地址pi。 因此開放定址法所需要的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)行插入和刪除的情況。

使用的hash算法？

Hash算法：取key的hashCode值、高位運(yùn)算、取模運(yùn)算。

h=key.hashCode() //第一步 取hashCode值 h^(h>>>16) //第二步 高位參與運(yùn)算，減少?zèng)_突 return h&(length-1); //第三步 取模運(yùn)算

在JDK1.8的實(shí)現(xiàn)中，優(yōu)化了高位運(yùn)算的算法，通過hashCode()的高16位異或低16位實(shí)現(xiàn)的：這么做可以在數(shù)組比較小的時(shí)候，也能保證考慮到高低位都參與到Hash的計(jì)算中，可以減少?zèng)_突，同時(shí)不會(huì)有太大的開銷。

擴(kuò)容過程？

1.8擴(kuò)容機(jī)制：當(dāng)元素個(gè)數(shù)大于threshold時(shí)，會(huì)進(jìn)行擴(kuò)容，使用2倍容量的數(shù)組代替原有數(shù)組。采用尾插入的方式將原數(shù)組元素拷貝到新數(shù)組。1.8擴(kuò)容之后鏈表元素相對(duì)位置沒有變化，而1.7擴(kuò)容之后鏈表元素會(huì)倒置。

1.7鏈表新節(jié)點(diǎn)采用的是頭插法，這樣在線程一擴(kuò)容遷移元素時(shí)，會(huì)將元素順序改變，導(dǎo)致兩個(gè)線程中出現(xiàn)元素的相互指向而形成循環(huán)鏈表，1.8采用了尾插法，避免了這種情況的發(fā)生。

原數(shù)組的元素在重新計(jì)算hash之后，因?yàn)閿?shù)組容量n變?yōu)?倍，那么n-1的mask范圍在高位多1bit。在元素拷貝過程不需要重新計(jì)算元素在數(shù)組中的位置，只需要看看原來的hash值新增的那個(gè)bit是1還是0，是0的話索引沒變，是1的話索引變成“原索引+oldCap”（根據(jù)e.hash & (oldCap - 1) == 0判斷） 。這樣可以省去重新計(jì)算hash值的時(shí)間，而且由于新增的1bit是0還是1可以認(rèn)為是隨機(jī)的，因此resize的過程會(huì)均勻的把之前的沖突的節(jié)點(diǎn)分散到新的bucket。

put方法流程？

如果table沒有初始化就先進(jìn)行初始化過程

使用hash算法計(jì)算key的索引

判斷索引處有沒有存在元素，沒有就直接插入

如果索引處存在元素，則遍歷插入，有兩種情況，一種是鏈表形式就直接遍歷到尾端插入，一種是紅黑樹就按照紅黑樹結(jié)構(gòu)插入

鏈表的數(shù)量大于閾值8，就要轉(zhuǎn)換成紅黑樹的結(jié)構(gòu)

添加成功后會(huì)檢查是否需要擴(kuò)容

紅黑樹的特點(diǎn)？

每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。

根節(jié)點(diǎn)是黑色。

每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色。

如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。

從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。

為什么使用紅黑樹而不使用AVL樹？

ConcurrentHashMap 在put的時(shí)候會(huì)加鎖，使用紅黑樹插入速度更快，可以減少等待鎖釋放的時(shí)間。紅黑樹是對(duì)AVL樹的優(yōu)化，只要求部分平衡，用非嚴(yán)格的平衡來換取增刪節(jié)點(diǎn)時(shí)候旋轉(zhuǎn)次數(shù)的降低，提高了插入和刪除的性能。

在解決 hash 沖突的時(shí)候，為什么選擇先用鏈表，再轉(zhuǎn)紅黑樹?

因?yàn)榧t黑樹需要進(jìn)行左旋，右旋，變色這些操作來保持平衡，而單鏈表不需要。當(dāng)元素小于 8 個(gè)的時(shí)候，鏈表結(jié)構(gòu)可以保證查詢性能。當(dāng)元素大于 8 個(gè)的時(shí)候， 紅黑樹搜索時(shí)間復(fù)雜度是 O(logn)，而鏈表是 O(n)，此時(shí)需要紅黑樹來加快查詢速度，但是插入和刪除節(jié)點(diǎn)的效率變慢了。如果一開始就用紅黑樹結(jié)構(gòu)，元素太少，插入和刪除節(jié)點(diǎn)的效率又比較慢，浪費(fèi)性能。

HashMap 的長(zhǎng)度為什么是 2 的冪次方？

Hash 值的范圍值比較大，使用之前需要先對(duì)數(shù)組的長(zhǎng)度取模運(yùn)算，得到的余數(shù)才是元素存放的位置也就是對(duì)應(yīng)的數(shù)組下標(biāo)。這個(gè)數(shù)組下標(biāo)的計(jì)算方法是(n - 1) & hash。將HashMap的長(zhǎng)度定為2 的冪次方，這樣就可以使用(n - 1)&hash位運(yùn)算代替%取余的操作，提高性能。

HashMap默認(rèn)加載因子是多少？為什么是 0.75？

先看下HashMap的默認(rèn)構(gòu)造函數(shù)：

int threshold; // 容納鍵值對(duì)的最大值 final float loadFactor; // 負(fù)載因子 int modCount; int size;

Node[] table的初始化長(zhǎng)度length為16，默認(rèn)的loadFactor是0.75，0.75是對(duì)空間和時(shí)間效率的一個(gè)平衡選擇，根據(jù)泊松分布，loadFactor 取0.75碰撞最小。一般不會(huì)修改，除非在時(shí)間和空間比較特殊的情況下 ：

如果內(nèi)存空間很多而又對(duì)時(shí)間效率要求很高，可以降低負(fù)載因子Load factor的值 。

如果內(nèi)存空間緊張而對(duì)時(shí)間效率要求不高，可以增加負(fù)載因子loadFactor的值，這個(gè)值可以大于1。

一般用什么作為HashMap的key?

一般用Integer、String 這種不可變類當(dāng) HashMap 當(dāng) key。String類比較常用。

因?yàn)?String 是不可變的，所以在它創(chuàng)建的時(shí)候 hashcode 就被緩存了，不需要重新計(jì)算。這就是 HashMap 中的key經(jīng)常使用字符串的原因。

獲取對(duì)象的時(shí)候要用到 equals() 和 hashCode() 方法，而Integer、String這些類都已經(jīng)重寫了 hashCode() 以及 equals() 方法，不需要自己去重寫這兩個(gè)方法。

HashMap為什么線程不安全？

多線程下擴(kuò)容死循環(huán)。JDK1.7中的 HashMap 使用頭插法插入元素，在多線程的環(huán)境下，擴(kuò)容的時(shí)候有可能導(dǎo)致環(huán)形鏈表的出現(xiàn)，形成死循環(huán)。

在JDK1.8中，在多線程環(huán)境下，會(huì)發(fā)生數(shù)據(jù)覆蓋的情況。

HashMap和HashTable的區(qū)別？

HashMap和Hashtable都實(shí)現(xiàn)了Map接口。

HashMap可以接受為null的key和value，key為null的鍵值對(duì)放在下標(biāo)為0的頭結(jié)點(diǎn)的鏈表中，而Hashtable則不行。

HashMap是非線程安全的，HashTable是線程安全的。Jdk1.5提供了ConcurrentHashMap，它是HashTable的替代。

Hashtable很多方法是同步方法，在單線程環(huán)境下它比HashMap要慢。

哈希值的使用不同，HashTable直接使用對(duì)象的hashCode。而HashMap重新計(jì)算hash值。

LinkedHashMap底層原理？

HashMap是無序的，迭代HashMap所得到元素的順序并不是它們最初放到HashMap的順序，即不能保持它們的插入順序。

LinkedHashMap繼承于HashMap，是HashMap和LinkedList的融合體，具備兩者的特性。每次put操作都會(huì)將entry插入到雙向鏈表的尾部。

講一下TreeMap？

TreeMap是一個(gè)能比較元素大小的Map集合，會(huì)對(duì)傳入的key進(jìn)行了大小排序。可以使用元素的自然順序，也可以使用集合中自定義的比較器來進(jìn)行排序。

public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, java.io.Serializable { }

TreeMap 的繼承結(jié)構(gòu)：

TreeMap的特點(diǎn)：

TreeMap是有序的key-value集合，通過紅黑樹實(shí)現(xiàn)。根據(jù)鍵的自然順序進(jìn)行排序或根據(jù)提供的Comparator進(jìn)行排序。

TreeMap繼承了AbstractMap，實(shí)現(xiàn)了NavigableMap接口，支持一系列的導(dǎo)航方法，給定具體搜索目標(biāo)，可以返回最接近的匹配項(xiàng)。如floorEntry()、ceilingEntry()分別返回小于等于、大于等于給定鍵關(guān)聯(lián)的Map.Entry()對(duì)象，不存在則返回null。lowerKey()、floorKey、ceilingKey、higherKey()只返回關(guān)聯(lián)的key。

HashSet底層原理？

HashSet 基于 HashMap 實(shí)現(xiàn)。放入HashSet中的元素實(shí)際上由HashMap的key來保存，而HashMap的value則存儲(chǔ)了一個(gè)靜態(tài)的Object對(duì)象。

public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable { static final long serialVersionUID = -5024744406713321676L; private transient HashMap map; //基于HashMap實(shí)現(xiàn) //... }

HashSet、LinkedHashSet 和 TreeSet 的區(qū)別？

HashSet 是 Set 接口的主要實(shí)現(xiàn)類 ，HashSet 的底層是 HashMap，線程不安全的，可以存儲(chǔ) null 值；

LinkedHashSet 是 HashSet 的子類，能夠按照添加的順序遍歷；

TreeSet 底層使用紅黑樹，能夠按照添加元素的順序進(jìn)行遍歷，排序的方式可以自定義。

什么是fail fast？

fast-fail是Java集合的一種錯(cuò)誤機(jī)制。當(dāng)多個(gè)線程對(duì)同一個(gè)集合進(jìn)行操作時(shí)，就有可能會(huì)產(chǎn)生fast-fail事件。例如：當(dāng)線程a正通過iterator遍歷集合時(shí)，另一個(gè)線程b修改了集合的內(nèi)容，此時(shí)modCount（記錄集合操作過程的修改次數(shù)）會(huì)加1，不等于expectedModCount，那么線程a訪問集合的時(shí)候，就會(huì)拋出ConcurrentModificationException，產(chǎn)生fast-fail事件。邊遍歷邊修改集合也會(huì)產(chǎn)生fast-fail事件。

解決方法：

使用Colletions.synchronizedList方法或在修改集合內(nèi)容的地方加上synchronized。這樣的話，增刪集合內(nèi)容的同步鎖會(huì)阻塞遍歷操作，影響性能。

使用CopyOnWriteArrayList來替換ArrayList。在對(duì)CopyOnWriteArrayList進(jìn)行修改操作的時(shí)候，會(huì)拷貝一個(gè)新的數(shù)組，對(duì)新的數(shù)組進(jìn)行操作，操作完成后再把引用移到新的數(shù)組。

什么是fail safe？

采用安全失敗機(jī)制的集合容器，在遍歷時(shí)不是直接在集合內(nèi)容上訪問的，而是先復(fù)制原有集合內(nèi)容，在拷貝的集合上進(jìn)行遍歷。java.util.concurrent包下的容器都是安全失敗，可以在多線程下并發(fā)使用，并發(fā)修改。

原理：由于迭代時(shí)是對(duì)原集合的拷貝進(jìn)行遍歷，所以在遍歷過程中對(duì)原集合所作的修改并不能被迭代器檢測(cè)到，所以不會(huì)觸發(fā)Concurrent Modification Exception。

缺點(diǎn)：基于拷貝內(nèi)容的優(yōu)點(diǎn)是避免了Concurrent Modification Exception，但同樣地，迭代器并不能訪問到修改后的內(nèi)容，即：迭代器遍歷的是開始遍歷那一刻拿到的集合拷貝，在遍歷期間原集合發(fā)生的修改迭代器是不知道的。

講一下ArrayDeque？

ArrayDeque實(shí)現(xiàn)了雙端隊(duì)列，內(nèi)部使用循環(huán)數(shù)組實(shí)現(xiàn)，默認(rèn)大小為16。它的特點(diǎn)有：

在兩端添加、刪除元素的效率較高

根據(jù)元素內(nèi)容查找和刪除的效率比較低。

沒有索引位置的概念，不能根據(jù)索引位置進(jìn)行操作。

ArrayDeque和LinkedList都實(shí)現(xiàn)了Deque接口，如果只需要從兩端進(jìn)行操作，ArrayDeque效率更高一些。如果同時(shí)需要根據(jù)索引位置進(jìn)行操作，或者經(jīng)常需要在中間進(jìn)行插入和刪除（LinkedList有相應(yīng)的 api，如add(int index, E e)），則應(yīng)該選LinkedList。

ArrayDeque和LinkedList都是線程不安全的，可以使用Collections工具類中synchronizedXxx()轉(zhuǎn)換成線程同步。

哪些集合類是線程安全的？哪些不安全？

線性安全的集合類：

Vector：比ArrayList多了同步機(jī)制。

Hashtable。

ConcurrentHashMap：是一種高效并且線程安全的集合。

Stack：棧，也是線程安全的，繼承于Vector。

線性不安全的集合類：

Hashmap

Arraylist

LinkedList

HashSet

TreeSet

TreeMap

迭代器 Iterator 是什么？

Iterator模式用同一種邏輯來遍歷集合。它可以把訪問邏輯從不同類型的集合類中抽象出來，不需要了解集合內(nèi)部實(shí)現(xiàn)便可以遍歷集合元素，統(tǒng)一使用 Iterator 提供的接口去遍歷。它的特點(diǎn)是更加安全，因?yàn)樗梢员ＷC，在當(dāng)前遍歷的集合元素被更改的時(shí)候，就會(huì)拋出 ConcurrentModificationException 異常。

public interface Collection extends Iterable { Iterator iterator(); }

主要有三個(gè)方法：hasNext()、next()和remove()。

Iterator 和 ListIterator 有什么區(qū)別？

ListIterator 是 Iterator的增強(qiáng)版。

ListIterator遍歷可以是逆向的，因?yàn)橛衟revious()和hasPrevious()方法，而Iterator不可以。

ListIterator有add()方法，可以向List添加對(duì)象，而Iterator卻不能。

ListIterator可以定位當(dāng)前的索引位置，因?yàn)橛衝extIndex()和previousIndex()方法，而Iterator不可以。

ListIterator可以實(shí)現(xiàn)對(duì)象的修改，set()方法可以實(shí)現(xiàn)。Iierator僅能遍歷，不能修改。

ListIterator只能用于遍歷List及其子類，Iterator可用來遍歷所有集合。

并發(fā)容器

JDK 提供的這些容器大部分在 java.util.concurrent 包中。

ConcurrentHashMap: 線程安全的 HashMap

CopyOnWriteArrayList: 線程安全的 List，在讀多寫少的場(chǎng)合性能非常好，遠(yuǎn)遠(yuǎn)好于 Vector.

ConcurrentLinkedQueue: 高效的并發(fā)隊(duì)列，使用鏈表實(shí)現(xiàn)。可以看做一個(gè)線程安全的 LinkedList，這是一個(gè)非阻塞隊(duì)列。

BlockingQueue: 阻塞隊(duì)列接口，JDK 內(nèi)部通過鏈表、數(shù)組等方式實(shí)現(xiàn)了這個(gè)接口。非常適合用于作為數(shù)據(jù)共享的通道。

ConcurrentSkipListMap: 跳表的實(shí)現(xiàn)。使用跳表的數(shù)據(jù)結(jié)構(gòu)進(jìn)行快速查找。

ConcurrentHashMap

多線程環(huán)境下，使用Hashmap進(jìn)行put操作會(huì)引起死循環(huán)，應(yīng)該使用支持多線程的 ConcurrentHashMap。

JDK1.8 ConcurrentHashMap取消了segment分段鎖，而采用CAS和synchronized來保證并發(fā)安全。數(shù)據(jù)結(jié)構(gòu)采用數(shù)組+鏈表/紅黑二叉樹。synchronized只鎖定當(dāng)前鏈表或紅黑二叉樹的首節(jié)點(diǎn)，相比1.7鎖定HashEntry數(shù)組，鎖粒度更小，支持更高的并發(fā)量。當(dāng)鏈表長(zhǎng)度過長(zhǎng)時(shí)，Node會(huì)轉(zhuǎn)換成TreeNode，提高查找速度。

在put的時(shí)候需要鎖住Segment，保證并發(fā)安全。調(diào)用get的時(shí)候不加鎖，因?yàn)閚ode數(shù)組成員val和指針next是用volatile修飾的，更改后的值會(huì)立刻刷新到主存中，保證了可見性，node數(shù)組table也用volatile修飾，保證在運(yùn)行過程對(duì)其他線程具有可見性。

transient volatile Node[] table; static class Node implements Map.Entry { volatile V val; volatile Node next; }

put 操作流程：

如果table沒有初始化就先進(jìn)行初始化過程

使用hash算法計(jì)算key的位置

如果這個(gè)位置為空則直接CAS插入，如果不為空的話，則取出這個(gè)節(jié)點(diǎn)來

如果取出來的節(jié)點(diǎn)的hash值是MOVED(-1)的話，則表示當(dāng)前正在對(duì)這個(gè)數(shù)組進(jìn)行擴(kuò)容，復(fù)制到新的數(shù)組，則當(dāng)前線程也去幫助復(fù)制

如果這個(gè)節(jié)點(diǎn)，不為空，也不在擴(kuò)容，則通過synchronized來加鎖，進(jìn)行添加操作，這里有兩種情況，一種是鏈表形式就直接遍歷到尾端插入或者覆蓋掉相同的key，一種是紅黑樹就按照紅黑樹結(jié)構(gòu)插入

鏈表的數(shù)量大于閾值8，就會(huì)轉(zhuǎn)換成紅黑樹的結(jié)構(gòu)或者進(jìn)行擴(kuò)容（table長(zhǎng)度小于64）

添加成功后會(huì)檢查是否需要擴(kuò)容

數(shù)組擴(kuò)容transfer方法中會(huì)設(shè)置一個(gè)步長(zhǎng)，表示一個(gè)線程處理的數(shù)組長(zhǎng)度，最小值是16。在一個(gè)步長(zhǎng)范圍內(nèi)只有一個(gè)線程會(huì)對(duì)其進(jìn)行復(fù)制移動(dòng)操作。

Hashtable通過使用synchronized修飾方法的方式來實(shí)現(xiàn)多線程同步，因此，Hashtable的同步會(huì)鎖住整個(gè)數(shù)組。在高并發(fā)的情況下，性能會(huì)非常差。ConcurrentHashMap采用了更細(xì)粒度的鎖來提高在并發(fā)情況下的效率。注：Synchronized容器（同步容器）也是通過synchronized關(guān)鍵字來實(shí)現(xiàn)線程安全，在使用的時(shí)候會(huì)對(duì)所有的數(shù)據(jù)加鎖。

Hashtable默認(rèn)的大小為11，當(dāng)達(dá)到閾值后，每次按照下面的公式對(duì)容量進(jìn)行擴(kuò)充：newCapacity = oldCapacity * 2 + 1。ConcurrentHashMap默認(rèn)大小是16，擴(kuò)容時(shí)容量擴(kuò)大為原來的2倍。

CopyOnWrite

寫時(shí)復(fù)制。當(dāng)我們往容器添加元素時(shí)，不直接往容器添加，而是先將當(dāng)前容器進(jìn)行復(fù)制，復(fù)制出一個(gè)新的容器，然后往新的容器添加元素，添加完元素之后，再將原容器的引用指向新容器。這樣做的好處就是可以對(duì)CopyOnWrite容器進(jìn)行并發(fā)的讀而不需要加鎖，因?yàn)楫?dāng)前容器不會(huì)被修改。

public boolean add(E e) { final ReentrantLock lock = this.lock; lock.lock(); //add方法需要加鎖 try { Object[] elements = getArray(); int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len + 1); //復(fù)制新數(shù)組 newElements[len] = e; setArray(newElements); //原容器的引用指向新容器 return true; } finally { lock.unlock(); } }

從JDK1.5開始Java并發(fā)包里提供了兩個(gè)使用CopyOnWrite機(jī)制實(shí)現(xiàn)的并發(fā)容器，它們是CopyOnWriteArrayList和CopyOnWriteArraySet。

CopyOnWriteArrayList中add方法添加的時(shí)候是需要加鎖的，保證同步，避免了多線程寫的時(shí)候復(fù)制出多個(gè)副本。讀的時(shí)候不需要加鎖，如果讀的時(shí)候有其他線程正在向CopyOnWriteArrayList添加數(shù)據(jù)，還是可以讀到舊的數(shù)據(jù)。

缺點(diǎn)：

內(nèi)存占用問題。由于CopyOnWrite的寫時(shí)復(fù)制機(jī)制，在進(jìn)行寫操作的時(shí)候，內(nèi)存里會(huì)同時(shí)駐扎兩個(gè)對(duì)象的內(nèi)存。

CopyOnWrite容器不能保證數(shù)據(jù)的實(shí)時(shí)一致性，可能讀取到舊數(shù)據(jù)。

ConcurrentLinkedQueue

非阻塞隊(duì)列。高效的并發(fā)隊(duì)列，使用鏈表實(shí)現(xiàn)。可以看做一個(gè)線程安全的 LinkedList，通過 CAS 操作實(shí)現(xiàn)。

如果對(duì)隊(duì)列加鎖的成本較高則適合使用無鎖的 ConcurrentLinkedQueue 來替代。適合在對(duì)性能要求相對(duì)較高，同時(shí)有多個(gè)線程對(duì)隊(duì)列進(jìn)行讀寫的場(chǎng)景。

非阻塞隊(duì)列中的幾種主要方法：

add(E e) : 將元素e插入到隊(duì)列末尾，如果插入成功，則返回true；如果插入失敗（即隊(duì)列已滿），則會(huì)拋出異常；

remove() ：移除隊(duì)首元素，若移除成功，則返回true；如果移除失敗（隊(duì)列為空），則會(huì)拋出異常；

offer(E e) ：將元素e插入到隊(duì)列末尾，如果插入成功，則返回true；如果插入失敗（即隊(duì)列已滿），則返回false；

poll() ：移除并獲取隊(duì)首元素，若成功，則返回隊(duì)首元素；否則返回null；

peek() ：獲取隊(duì)首元素，若成功，則返回隊(duì)首元素；否則返回null

對(duì)于非阻塞隊(duì)列，一般情況下建議使用offer、poll和peek三個(gè)方法，不建議使用add和remove方法。因?yàn)槭褂胦ffer、poll和peek三個(gè)方法可以通過返回值判斷操作成功與否，而使用add和remove方法卻不能達(dá)到這樣的效果。

阻塞隊(duì)列

阻塞隊(duì)列是java.util.concurrent包下重要的數(shù)據(jù)結(jié)構(gòu)，BlockingQueue提供了線程安全的隊(duì)列訪問方式：當(dāng)阻塞隊(duì)列進(jìn)行插入數(shù)據(jù)時(shí)，如果隊(duì)列已滿，線程將會(huì)阻塞等待直到隊(duì)列非滿；從阻塞隊(duì)列取數(shù)據(jù)時(shí)，如果隊(duì)列已空，線程將會(huì)阻塞等待直到隊(duì)列非空。并發(fā)包下很多高級(jí)同步類的實(shí)現(xiàn)都是基于BlockingQueue實(shí)現(xiàn)的。BlockingQueue 適合用于作為數(shù)據(jù)共享的通道。

使用阻塞算法的隊(duì)列可以用一個(gè)鎖（入隊(duì)和出隊(duì)用同一把鎖）或兩個(gè)鎖（入隊(duì)和出隊(duì)用不同的鎖）等方式來實(shí)現(xiàn)。

阻塞隊(duì)列和一般的隊(duì)列的區(qū)別就在于：

多線程支持，多個(gè)線程可以安全的訪問隊(duì)列

阻塞操作，當(dāng)隊(duì)列為空的時(shí)候，消費(fèi)線程會(huì)阻塞等待隊(duì)列不為空；當(dāng)隊(duì)列滿了的時(shí)候，生產(chǎn)線程就會(huì)阻塞直到隊(duì)列不滿。

方法

JDK 7 提供了7個(gè)阻塞隊(duì)列，如下

1、ArrayBlockingQueue

有界阻塞隊(duì)列，底層采用數(shù)組實(shí)現(xiàn)。ArrayBlockingQueue 一旦創(chuàng)建，容量不能改變。其并發(fā)控制采用可重入鎖來控制，不管是插入操作還是讀取操作，都需要獲取到鎖才能進(jìn)行操作。此隊(duì)列按照先進(jìn)先出（FIFO）的原則對(duì)元素進(jìn)行排序。默認(rèn)情況下不能保證線程訪問隊(duì)列的公平性，參數(shù)fair可用于設(shè)置線程是否公平訪問隊(duì)列。為了保證公平性，通常會(huì)降低吞吐量。

private static ArrayBlockingQueue blockingQueue = new ArrayBlockingQueue(10,true);//fair

2、LinkedBlockingQueue

LinkedBlockingQueue是一個(gè)用單向鏈表實(shí)現(xiàn)的有界阻塞隊(duì)列，可以當(dāng)做無界隊(duì)列也可以當(dāng)做有界隊(duì)列來使用。通常在創(chuàng)建 LinkedBlockingQueue 對(duì)象時(shí)，會(huì)指定隊(duì)列最大的容量。此隊(duì)列的默認(rèn)和最大長(zhǎng)度為Integer.MAX_VALUE。此隊(duì)列按照先進(jìn)先出的原則對(duì)元素進(jìn)行排序。與 ArrayBlockingQueue 相比起來具有更高的吞吐量。

3、PriorityBlockingQueue

支持優(yōu)先級(jí)的無界阻塞隊(duì)列。默認(rèn)情況下元素采取自然順序升序排列。也可以自定義類實(shí)現(xiàn)compareTo()方法來指定元素排序規(guī)則，或者初始化PriorityBlockingQueue時(shí)，指定構(gòu)造參數(shù)Comparator來進(jìn)行排序。

PriorityBlockingQueue 只能指定初始的隊(duì)列大小，后面插入元素的時(shí)候，如果空間不夠的話會(huì)自動(dòng)擴(kuò)容。

PriorityQueue 的線程安全版本。不可以插入 null 值，同時(shí)，插入隊(duì)列的對(duì)象必須是可比較大小的（comparable），否則報(bào) ClassCastException 異常。它的插入操作 put 方法不會(huì) block，因?yàn)樗菬o界隊(duì)列（take 方法在隊(duì)列為空的時(shí)候會(huì)阻塞）。

4、DelayQueue

支持延時(shí)獲取元素的無界阻塞隊(duì)列。隊(duì)列使用PriorityBlockingQueue來實(shí)現(xiàn)。隊(duì)列中的元素必須實(shí)現(xiàn)Delayed接口，在創(chuàng)建元素時(shí)可以指定多久才能從隊(duì)列中獲取當(dāng)前元素。只有在延遲期滿時(shí)才能從隊(duì)列中提取元素。

5、SynchronousQueue

不存儲(chǔ)元素的阻塞隊(duì)列，每一個(gè)put必須等待一個(gè)take操作，否則不能繼續(xù)添加元素。支持公平訪問隊(duì)列。

SynchronousQueue可以看成是一個(gè)傳球手，負(fù)責(zé)把生產(chǎn)者線程處理的數(shù)據(jù)直接傳遞給消費(fèi)者線程。隊(duì)列本身不存儲(chǔ)任何元素，非常適合傳遞性場(chǎng)景。SynchronousQueue的吞吐量高于LinkedBlockingQueue和ArrayBlockingQueue。

6、LinkedTransferQueue

由鏈表結(jié)構(gòu)組成的無界阻塞TransferQueue隊(duì)列。相對(duì)于其他阻塞隊(duì)列，多了tryTransfer和transfer方法。

transfer方法：如果當(dāng)前有消費(fèi)者正在等待接收元素（take或者待時(shí)間限制的poll方法），transfer可以把生產(chǎn)者傳入的元素立刻傳給消費(fèi)者。如果沒有消費(fèi)者等待接收元素，則將元素放在隊(duì)列的tail節(jié)點(diǎn)，并等到該元素被消費(fèi)者消費(fèi)了才返回。

tryTransfer方法：用來試探生產(chǎn)者傳入的元素能否直接傳給消費(fèi)者。如果沒有消費(fèi)者在等待，則返回false。和上述方法的區(qū)別是該方法無論消費(fèi)者是否接收，方法立即返回。而transfer方法是必須等到消費(fèi)者消費(fèi)了才返回。

JDK使用通知模式實(shí)現(xiàn)阻塞隊(duì)列。所謂通知模式，就是當(dāng)生產(chǎn)者往滿的隊(duì)列里添加元素時(shí)會(huì)阻塞生產(chǎn)者，當(dāng)消費(fèi)者消費(fèi)了一個(gè)隊(duì)列中的元素后，會(huì)通知生產(chǎn)者當(dāng)前隊(duì)列可用。

ArrayBlockingQueue使用Condition來實(shí)現(xiàn)：

private final Condition notEmpty; private final Condition notFull; public ArrayBlockingQueue(int capacity, boolean fair) { if (capacity <= 0) throw new IllegalArgumentException(); this.items = new Object[capacity]; lock = new ReentrantLock(fair); notEmpty = lock.newCondition(); notFull = lock.newCondition(); } public E take() throws InterruptedException { final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { while (count == 0) // 隊(duì)列為空時(shí)，阻塞當(dāng)前消費(fèi)者 notEmpty.await(); return dequeue(); } finally { lock.unlock(); } } public void put(E e) throws InterruptedException { checkNotNull(e); final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { while (count == items.length) notFull.await(); enqueue(e); } finally { lock.unlock(); } } private void enqueue(E x) { final Object[] items = this.items; items[putIndex] = x; if (++putIndex == items.length) putIndex = 0; count++; notEmpty.signal(); // 隊(duì)列不為空時(shí)，通知消費(fèi)者獲取元素 }

文章對(duì)你有用的話，點(diǎn)個(gè)贊，支持一下~

我是大彬，非科班轉(zhuǎn)碼，校招拿了多家互聯(lián)網(wǎng)中大廠offer，專注分享Java技術(shù)干貨，歡迎關(guān)注~

Java

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。