集合框架

JCF（Java collections framework），也就是java集合框架

包括：

• 集合（Collection）
  • 列表（List）
    • ArrayList
    • LinkedList
    • Vector
    • Stack
    • CopyOnWriteArrayList
  • 隊(duì)列（Queue）
    • ArrayBlockingQueue
    • LinkedBlockingQueue
    • PriorityBlockingQueue
    • DelayQueue
    • PriorityQueue
    • ConcurrentLinkedQueue
  • Set集合
    • HashSet
    • LinkedHashSet
    • TreeSet
• 映射（Map）
  • HashMap
  • LinkedHashMap
  • HashTable
  • ConcurrentHashMap
  • TreeMap
  • WeakHashMap

集合圖

集合類圖

集合匯總圖

各種數(shù)據(jù)結(jié)構(gòu)的區(qū)別

• 數(shù)組：采用一段連續(xù)的存儲(chǔ)單元來(lái)存儲(chǔ)數(shù)據(jù)。對(duì)于指定下標(biāo)的查找缴川，時(shí)間復(fù)雜度為O(1)臣嚣；通過(guò)給定值進(jìn)行查找腐碱，需要遍歷數(shù)組年缎，逐一比對(duì)給定關(guān)鍵字和數(shù)組元素忍弛，時(shí)間復(fù)雜度為O(n)歼争，當(dāng)然拜马，對(duì)于有序數(shù)組，則可采用二分查找沐绒，插值查找俩莽，斐波那契查找等方式，可將查找復(fù)雜度提高為O(logn)乔遮；對(duì)于一般的插入刪除操作扮超，涉及到數(shù)組元素的移動(dòng)，其平均復(fù)雜度也為O(n)

• 線性鏈表：對(duì)于鏈表的新增，刪除等操作（在找到指定操作位置后）出刷，僅需處理結(jié)點(diǎn)間的引用即可璧疗，時(shí)間復(fù)雜度為O(1)，而查找操作需要遍歷鏈表逐一進(jìn)行比對(duì)馁龟，復(fù)雜度為O(n)

• 二叉樹(shù)：對(duì)一棵相對(duì)平衡的有序二叉樹(shù)崩侠，對(duì)其進(jìn)行插入，查找坷檩，刪除等操作却音，平均復(fù)雜度均為O(logn)。

• 哈希表：相比上述幾種數(shù)據(jù)結(jié)構(gòu)矢炼，在哈希表中進(jìn)行添加系瓢，刪除，查找等操作句灌，性能十分之高夷陋，不考慮哈希沖突的情況下，僅需一次定位即可完成涯塔，時(shí)間復(fù)雜度為O(1)肌稻，接下來(lái)我們就來(lái)看看哈希表是如何實(shí)現(xiàn)達(dá)到驚艷的常數(shù)階O(1)的。

列表1——ArrayList

ArrayList的內(nèi)部實(shí)現(xiàn)是一個(gè)數(shù)組（會(huì)自動(dòng)擴(kuò)容的動(dòng)態(tài)數(shù)組）匕荸。
ArrayList是非線程安全的。

幾個(gè)關(guān)鍵屬性：

• DEFAULT_CAPACITY：默認(rèn)容量枷邪，值為10榛搔，也就是沒(méi)有指定容量時(shí)，ArrayList內(nèi)部數(shù)組elementData的默認(rèn)大小;
• elementData：元素?cái)?shù)據(jù)东揣，Object[]類型践惑，也就是ArrayList內(nèi)部真正存儲(chǔ)元素的數(shù)組。
• size：大小嘶卧，也就是ArrayList的真實(shí)大小

擴(kuò)容：
ArrayList的容量也是elementData數(shù)組的大小尔觉，默認(rèn)大小是10，初始化時(shí)可以指定大小芥吟，如果add()元素時(shí)數(shù)組大小不夠侦铜，則數(shù)組會(huì)自動(dòng)擴(kuò)大，新數(shù)組大小 = 舊數(shù)組大小 * 1.5钟鸵，數(shù)組最大不能超過(guò)Integer的最大值钉稍。

遍歷方式：

1. 隨機(jī)訪問(wèn)for (int i=0; list.size();<size; i++) {list.get(i);}：3 ms
2. foreach循環(huán)for (Integer integ:list)：5 ms
3. 迭代器Iterator iter = list.iterator();while (iter.hasNext()) {}：8 ms

因?yàn)锳rrayList是基于數(shù)組的集合，適合隨機(jī)訪問(wèn)（通過(guò)元素下標(biāo)訪問(wèn)）棺耍，所以3種遍歷方式按速度排序如下：
隨機(jī)訪問(wèn) > foreach遍歷 > 迭代器遍歷

列表2——LinkedList

雖然把LinkedList放在列表目錄贡未，當(dāng)時(shí)它也實(shí)現(xiàn)了Deque隊(duì)列接口，所以可以認(rèn)為它是具有列表功能的隊(duì)列。
LinkedList內(nèi)部是一個(gè)雙向俊卤、雙端鏈表嫩挤。
LinkedList實(shí)現(xiàn)了List<E>和Deque<E>接口，可以作為列表（隨機(jī)訪問(wèn)）消恍、隊(duì)列（FIFO先入先出）俐镐、棧（LIFO后入先出）來(lái)使用。

關(guān)鍵變量：

• size：大小哺哼，即LinkedList包含多少元素
• first：第一個(gè)元素佩抹，是一個(gè)Node<E>實(shí)例
• last：最后一個(gè)元素，是一個(gè)Node<E>實(shí)例

Node<E>類：

• item：一個(gè)泛型的變量取董，是真正加入LinkedList的元素
• next：是一個(gè)Node<E>實(shí)例棍苹，指下一個(gè)元素
• prev：是一個(gè)Node<E>實(shí)例，指上一個(gè)元素

作為列表（隨機(jī)訪問(wèn)）：

public E get(int index) {}

LinkedList本身是一個(gè)鏈表茵汰，而不是數(shù)組枢里，那它是怎么實(shí)現(xiàn)隨機(jī)訪問(wèn)（通過(guò)元素下標(biāo)訪問(wèn)）呢？
實(shí)際原理非常簡(jiǎn)單蹂午，它就是通過(guò)一個(gè)計(jì)數(shù)索引值來(lái)實(shí)現(xiàn)的栏豺。當(dāng)我們調(diào)用get(int index)時(shí)，首先會(huì)比較“index”和“雙向鏈表長(zhǎng)度的1/2”豆胸；若前者大奥洼，則從鏈表頭first開(kāi)始往后查找，直到index位置晚胡；否則灵奖，從鏈表末尾last開(kāi)始先前查找，直到index位置估盘。
所以LinkedList隨機(jī)訪問(wèn)的速度比較慢瓷患，不建議使用。

作為棧（LIFO后入先出）：

• 入棧方法push(e)或者addFirst(e)
• 出棧方法pop()或者removeFirst()
• 查看棧頂元素方法peek()或者peekFirst()

作為隊(duì)列（FIFO先入先出）：

• 入隊(duì)方法add(e)或者addLast(e)
• 出隊(duì)方法poll()或者pollFirst()
• 查看隊(duì)頭元素peek()或者peekFirst()

遍歷方式：
十萬(wàn)條數(shù)據(jù)遣妥，耗時(shí)時(shí)間從低到高：

1. pollFirst()擅编、pollLast()、removeFirst()箫踩、removeLast() 邊讀邊刪爱态，4 ms
2. 迭代器遍歷， 6 ms
3. Foreach遍歷 班套，6 ms
4. get()方法隨機(jī)遍歷 肢藐，3414 ms

所以，LinkedList不要使用get()隨機(jī)遍歷吱韭。

列表3——矢量列表（Vector）

Vector的結(jié)構(gòu)與ArrayList差不多吆豹，內(nèi)部實(shí)現(xiàn)也是一個(gè)動(dòng)態(tài)數(shù)組鱼的。
差別在于：

1. Vector是線程安全的
2. Vector擴(kuò)容與ArrayList不太一樣，可以自定義擴(kuò)容增量大小

幾個(gè)關(guān)鍵屬性：

• elementData：動(dòng)態(tài)數(shù)組痘煤，存儲(chǔ)Vector的元素凑阶。
• elementCount：存儲(chǔ)的元素個(gè)數(shù)，也就是Vector的真實(shí)大小
• capacityIncrement：擴(kuò)容增量衷快，是elementData動(dòng)態(tài)數(shù)組每次擴(kuò)容時(shí)增加的容量大小;

擴(kuò)容：
Vector初始默認(rèn)容量大小是10宙橱，當(dāng)Vector容量不足以容納全部元素時(shí)，Vector的容量會(huì)增加蘸拔。若capacityIncrement>0师郑，則將容量的值增加capacityIncrement；否則调窍，將容量大小增加為舊容量*2宝冕。

遍歷方式：
隨機(jī)訪問(wèn) > Enumeration > foreach > 迭代器遍歷

列表4——棧（Stack）

Stack是棧，特性是先進(jìn)后出(FILO, First In Last Out)邓萨。
Stack繼承了Vector地梨，跟Vector幾乎一樣，內(nèi)部實(shí)現(xiàn)也是一個(gè)動(dòng)態(tài)數(shù)組缔恳。
Stack使用數(shù)組來(lái)實(shí)現(xiàn)棧宝剖，而非鏈表。

為什么使用數(shù)組而不是鏈表來(lái)實(shí)現(xiàn)呢歉甚？
其實(shí)很簡(jiǎn)單万细，因?yàn)闂Ｊ荈ILO，對(duì)于數(shù)組而言铃芦，每次入棧和出棧都只要操作最后一個(gè)數(shù)組元素就可以雅镊，不會(huì)造成數(shù)組重組，所以效率跟鏈表一樣快刃滓。

與LinkedList實(shí)現(xiàn)的棧對(duì)比：

1. Stack是線程安全的，LinkedList是非線程安全
2. Stack基于數(shù)組實(shí)現(xiàn)耸弄，LinkedList基于鏈表實(shí)現(xiàn)咧虎。
3. Stack類比較突兀，因?yàn)樗鎯?chǔ)順序和棧是相反的计呈，LinkedList方式的棧存儲(chǔ)順序和棧是一致的砰诵。

列表5——讀寫(xiě)分離列表（CopyOnWriteArrayList）

CopyOnWriteArrayList是java.util.concurrent下面的一個(gè)類。
CopyOnWriteArrayList的實(shí)現(xiàn)原理是讀寫(xiě)分離+寫(xiě)時(shí)復(fù)制捌显，數(shù)據(jù)結(jié)構(gòu)也是數(shù)組茁彭。
CopyOnWriteArrayList是線程安全的，適合高并發(fā)的場(chǎng)景扶歪。

實(shí)現(xiàn)原理：
CopyOnWriteArrayList使用了CopyOnWrite容器——即寫(xiě)時(shí)復(fù)制的容器理肺。
通俗的理解是當(dāng)我們往一個(gè)容器添加元素的時(shí)候，不直接往當(dāng)前容器添加，而是先將當(dāng)前容器進(jìn)行Copy妹萨，復(fù)制出一個(gè)新的容器年枕，然后新的容器里添加元素，添加完元素之后乎完，再將原容器的引用指向新的容器熏兄。這樣做的好處是我們可以對(duì)CopyOnWrite容器進(jìn)行并發(fā)的讀，而不需要加鎖树姨，因?yàn)楫?dāng)前容器不會(huì)添加任何元素摩桶。

優(yōu)點(diǎn)：

• CopyOnWriteArrayList只對(duì)寫(xiě)操作加鎖，在兼顧了線程安全的同時(shí)帽揪，又提高了并發(fā)性硝清，特別適合讀多寫(xiě)少的場(chǎng)景。
• CopyOnWriteArrayList性能比Vector提高不少台丛，因?yàn)閂ector既對(duì)寫(xiě)加鎖也對(duì)讀加鎖

缺點(diǎn)：

• 內(nèi)存占用問(wèn)題：因?yàn)樵趯?xiě)的時(shí)候耍缴，需要復(fù)制一份列表，會(huì)占用兩倍的內(nèi)存挽霉，可能會(huì)引起頻繁的Yong GC和Full GC
• 數(shù)據(jù)一致性問(wèn)題：CopyOnWrite容器只能保證數(shù)據(jù)的最終一致性防嗡，不能保證數(shù)據(jù)的實(shí)時(shí)一致性。所以如果你希望寫(xiě)入的的數(shù)據(jù)侠坎，馬上能讀到蚁趁，請(qǐng)不要使用CopyOnWrite容器。

映射1——HashMap

下面的介紹是java7的實(shí)現(xiàn)实胸，java8已經(jīng)做了改動(dòng)他嫡。
參考：https://www.cnblogs.com/chengxiao/p/6059914.html
我們知道，數(shù)據(jù)結(jié)構(gòu)的物理存儲(chǔ)結(jié)構(gòu)只有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（像棧庐完，隊(duì)列钢属，樹(shù)，圖等是從邏輯結(jié)構(gòu)去抽象的门躯，映射到內(nèi)存中淆党，也這兩種物理組織形式），而在上面我們提到過(guò)讶凉，在數(shù)組中根據(jù)下標(biāo)查找某個(gè)元素染乌，一次定位就可以達(dá)到，哈希表利用了這種特性懂讯，哈希表的主干就是數(shù)組荷憋。

哈希表（HashMap）采用了鏈地址法，也就是數(shù)組+鏈表的方式存儲(chǔ)數(shù)據(jù)

HashMap的主干是一個(gè)Entry數(shù)組褐望。Entry是HashMap的基本組成單元勒庄，每一個(gè)Entry包含一個(gè)key-value鍵值對(duì)串前。

Entry數(shù)組

在存儲(chǔ)一個(gè)Entry（key-value鍵值對(duì)）時(shí)，首先使用hashcode計(jì)算出key的哈希值锅铅，進(jìn)行hash擾亂計(jì)算后酪呻，再通過(guò)和 length-1進(jìn)行位運(yùn)算得到數(shù)組下標(biāo)，最后將這個(gè)Entry插入該數(shù)組下標(biāo)位置盐须。

key轉(zhuǎn)換為數(shù)組下標(biāo)的過(guò)程

拉鏈法解決"哈希沖突"

有可能兩個(gè)不同key計(jì)算出來(lái)的hashcode是一樣的玩荠，或者不同hashcode轉(zhuǎn)換后的數(shù)組下標(biāo)一樣，這時(shí)候就存在存儲(chǔ)位置沖突贼邓，為了解決沖突阶冈，HashMap在每個(gè)數(shù)組存儲(chǔ)位置，加入一個(gè)鏈表塑径，用來(lái)存儲(chǔ)相同下標(biāo)的Entry女坑。
所以，哈希表的實(shí)際存儲(chǔ)結(jié)構(gòu)如下：

哈希表數(shù)據(jù)結(jié)構(gòu)

哈希表擴(kuò)容

HashMap類有兩個(gè)屬性用于控制哈希表的容量（capacity）：閾值（threshold）和負(fù)載因子（loadFactor）统舀。

• 容量（capacity）匆骗，即Entry數(shù)組的大小，默認(rèn)是16誉简，會(huì)隨著哈希表變大而動(dòng)態(tài)擴(kuò)容碉就，容量大小是2的n次冪。
• threshold是HashMap的閾值闷串，用于判斷是否需要調(diào)整HashMap的容量瓮钥。threshold的值="容量 * 加載因子"，當(dāng)HashMap中存儲(chǔ)數(shù)據(jù)的數(shù)量達(dá)到threshold時(shí)烹吵，就需要將HashMap擴(kuò)容碉熄，新容量=舊容量*2。
• loadFactor就是加載因子肋拔，默認(rèn)值為0.75

擴(kuò)容需要重建哈希表：
因?yàn)镋ntry的存儲(chǔ)位置index = h&(length-1)是通過(guò)數(shù)組長(zhǎng)度（容量）計(jì)算出來(lái)的锈津，擴(kuò)容后數(shù)組長(zhǎng)度大，所以凉蜂，需要對(duì)哈希表進(jìn)行 rehash 操作（即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)）一姿，將老數(shù)組中的數(shù)據(jù)逐個(gè)鏈表地遍歷，計(jì)算新的數(shù)組下標(biāo)跃惫，扔到新的擴(kuò)容后的數(shù)組中。

因?yàn)橹亟ㄟ^(guò)程很耗資源艾栋，因此爆存，構(gòu)造HashMap時(shí)應(yīng)該設(shè)置一個(gè)合理的初始容量（initialCapacity），避免哈希表因?yàn)閿U(kuò)容而重建

空間換時(shí)間

如果希望加快Key查找的時(shí)間蝗砾，還可以進(jìn)一步降低加載因子先较，加大初始大小携冤，以降低哈希沖突的概率。也就是讓每個(gè)數(shù)組存儲(chǔ)位置上的鏈表大小變小闲勺，最優(yōu)情況下一個(gè)位置只有一個(gè)元素曾棕，這樣的查找速度是最快的。

解決HashMap的并發(fā)問(wèn)題

HashMap本身是線程非安全的菜循，在并發(fā)情況下翘地，會(huì)導(dǎo)致數(shù)據(jù)不一致，有可能會(huì)造成環(huán)狀鏈表（擴(kuò)容時(shí)可能會(huì)發(fā)生）癌幕，導(dǎo)致get操作時(shí)衙耕，cpu空轉(zhuǎn)。

在并發(fā)場(chǎng)景勺远，有幾種解決方法

1. 使用SynchronizedMap
   Map<String,String> m = Collections.synchronizedMap(new HashMap<String,String>());
2. 使用Hashtable代替HashMap
3. 使用ConcurrentHashMap代替HashMap

java8 HashMap

Java8 對(duì) HashMap 進(jìn)行了一些修改橙喘，最大的不同就是利用了紅黑樹(shù)，所以其由 數(shù)組+鏈表+紅黑樹(shù) 組成胶逢。
因?yàn)?Java7 HashMap使用鏈表解決哈希沖突厅瞎，當(dāng)鏈表變大時(shí)，查找時(shí)間復(fù)雜度取決于鏈表的長(zhǎng)度初坠，為 O(n)和簸，在 Java8 中，當(dāng)鏈表中的元素超過(guò)了 8 個(gè)以后某筐，會(huì)將鏈表轉(zhuǎn)換為紅黑樹(shù)比搭，在這些位置進(jìn)行查找的時(shí)候可以降低時(shí)間復(fù)雜度為 O(logN)。

圖片.png

映射2——LinkedHashMap

參考：https://www.cnblogs.com/xiaoxi/p/6170590.html

LinkedHashMap與HashMap

• LinkedHashMap是HashMap的子類南誊。
• LinkedHashMap與HashMap的區(qū)別在于身诺，HashMap是無(wú)序的，LinkedHashMap是有序的
• LinkedHashMap比HashMap抄囚，增加了時(shí)間和空間上的開(kāi)銷霉赡，它為了保證元素迭代的有序性，內(nèi)部維護(hù)了一個(gè)雙向鏈表幔托，可以控制迭代順序按照插入順序或者是訪問(wèn)順序穴亏。
• LinkedHashMap繼承HashMap，并通過(guò)多態(tài)來(lái)實(shí)現(xiàn)維護(hù)元素次序的功能重挑。

LinkedHashMap定義了兩個(gè)屬性：

1. Entry<K,V> header：雙向鏈表的頭結(jié)點(diǎn)嗓化，這個(gè)雙向鏈表就是用來(lái)維護(hù)元素的次序。
2. boolean accessOrder：迭代順序控制屬性谬哀，true表示最近最少使用次序刺覆，false表示插入順序三妈。

HashMap的數(shù)組+鏈表的結(jié)構(gòu)苫纤，再增加一個(gè)雙向鏈表阐枣，形成了LinkedHashMap的結(jié)構(gòu)涛漂，如下圖：

LinkedHashMap結(jié)構(gòu)圖

LinkedHashMap遍歷圖

LinkedHashMap遍歷圖

LinkedHashMap有兩種遍歷順序

1. 當(dāng)accessOrder=false，元素按插入的順序排序氢橙，最先插入的元素排在第一位酝枢。
2. 當(dāng)accessOrder=true，元素按最近最少使用的順序排序悍手，最近使用的元素排在第一位帘睦，利用LinkedHashMap的這個(gè)功能可以實(shí)現(xiàn)LRU算法緩存，LRUCache實(shí)現(xiàn)緩存LRU功能都是源自LinkedHashMap的谓苟，當(dāng)緩存滿了官脓，會(huì)優(yōu)先淘汰那些最近最不常訪問(wèn)的數(shù)據(jù)。

映射3——HashTable

HashTable已經(jīng)不建議使用涝焙，被ConcurrentHashMap替代卑笨。
HashTable和HashMap的區(qū)別

• HashTable與HashMap的實(shí)現(xiàn)原理幾乎一樣
• HashTable不允許key和value為null，而HashMap允許
• HashTable是線程安全的
• HashTable為了線程安全仑撞，性能非常差

HashTable的全表鎖

圖片.png

HashTable雖然是線程安全赤兴，但是線程安全的策略實(shí)現(xiàn)代價(jià)卻太大了，簡(jiǎn)單粗暴隧哮，get/put所有相關(guān)操作都是synchronized的桶良，這相當(dāng)于給整個(gè)哈希表加了一把大鎖，多線程訪問(wèn)時(shí)候沮翔，只要有一個(gè)線程訪問(wèn)或操作該對(duì)象陨帆，那其他線程只能阻塞，相當(dāng)于將所有的操作串行化采蚀，在競(jìng)爭(zhēng)激烈的并發(fā)場(chǎng)景中性能就會(huì)非常差疲牵。

映射4——ConcurrentHashMap

下面介紹的是java7的ConcurrentHashMap，java8做了改動(dòng)榆鼠。
參考：http://www.importnew.com/28263.html
ConcurrentHashMap是HashTable的替代者纲爸。
ConcurrentHashMap是線程安全的，支持并發(fā)場(chǎng)景妆够。
ConcurrentHashMap使用的是分段鎖识啦，性能比HashTable好。

數(shù)據(jù)結(jié)構(gòu)

ConcurrentHashMap的結(jié)構(gòu)與HashMap不一樣神妹，使用了Segment + HashEntry的數(shù)據(jù)結(jié)構(gòu)颓哮，整個(gè) ConcurrentHashMap由一個(gè)個(gè) Segment（段）組成，每個(gè)Segment相當(dāng)一個(gè)HashMap（數(shù)組+鏈表）鸵荠。

圖片.png

ConcurrentHashMap 幾個(gè)初始化參數(shù)

• concurrencyLevel：并發(fā)級(jí)別题翻，也是Segment 的數(shù)量，默認(rèn)16個(gè)，這個(gè)值一旦初始化不會(huì)改變嵌赠，這時(shí)，ConcurrentHashMap最多可以同時(shí)支持 16 個(gè)線程并發(fā)寫(xiě)熄赡。
• initialCapacity：初始容量姜挺，這個(gè)值指的是整個(gè)ConcurrentHashMap 的初始容量，實(shí)際操作的時(shí)候需要平均分給每個(gè) Segment彼硫。
• loadFactor：負(fù)載因子炊豪，這個(gè)負(fù)載因子是給每個(gè) Segment 內(nèi)部的數(shù)組使用的。

分段鎖

Segment 通過(guò)繼承 ReentrantLock 來(lái)進(jìn)行加鎖拧篮，所以每次需要加鎖的操作鎖住的是一個(gè) segment词渤，而不是整個(gè)哈希表，這叫分段鎖串绩，這樣只要保證每個(gè) Segment 是線程安全的缺虐，也就實(shí)現(xiàn)了全局的線程安全。這個(gè)設(shè)計(jì)讓ConcurrentHashMap 比HashTable性能提升很多倍礁凡。

圖片.png

java8的ConcurrentHashMap

java8對(duì)ConcurrentHashMap的改動(dòng)非常大高氮，完全不用java7那套Segment的主干結(jié)構(gòu)，變得更像java8的HashMap顷牌，也使用了數(shù)組+鏈表+紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)剪芍，鏈表轉(zhuǎn)紅黑樹(shù)的臨界點(diǎn)也是8（注意：當(dāng)數(shù)組長(zhǎng)度小于64時(shí)會(huì)先通過(guò)擴(kuò)容解決鏈表過(guò)長(zhǎng)問(wèn)題），并且采用final + volatile + CAS + synchronized來(lái)保證并發(fā)安全進(jìn)行實(shí)現(xiàn)窟蓝。

圖片.png

java 8的ConcurrentHashMap實(shí)現(xiàn)極其細(xì)致：

1. 它的大部分變量都是volatile和final類型罪裹，保證可見(jiàn)性。
2. 使用了大量的本地CAS方法+循環(huán)运挫，樂(lè)觀鎖的經(jīng)典使用状共。
3. 使用synchronized來(lái)保證線程同步，java8的內(nèi)置鎖已經(jīng)經(jīng)過(guò)優(yōu)化滑臊，性能可以與ReentrantLock媲美口芍。

具體實(shí)現(xiàn)：

1. initTable初始化方法使用CAS樂(lè)觀鎖
2. transfer擴(kuò)容方法支持多線程同時(shí)擴(kuò)容，每個(gè)線程負(fù)責(zé)stride個(gè)節(jié)點(diǎn)的擴(kuò)容雇卷。使用volatile類型的transferIndex變量鬓椭，通過(guò)cas計(jì)算transferIndex=transferIndex-stride來(lái)安全分配每個(gè)線程所負(fù)責(zé)的hash桶。
3. put方法使用synchronized加鎖关划，但是鎖定的只是數(shù)組的一個(gè)節(jié)點(diǎn)小染，粒度比Segment更小。
4. get方法不需要加鎖贮折。因?yàn)镹ode的val是volatile修飾的裤翩，所以其他線程的修改對(duì)當(dāng)前線程是可見(jiàn)的。

映射5——TreeMap

要了解TreeMap，需要先了解紅黑樹(shù)
參考：https://www.cnblogs.com/CarpenterLee/p/5503882.html

圖片.png

TreeMap是有序的踊赠，它實(shí)現(xiàn)了SortedMap接口呵扛，也就是說(shuō)會(huì)按照key的大小順序?qū)ap中的元素進(jìn)行排序，key大小的評(píng)判可以通過(guò)其本身的自然順序（natural ordering）筐带，也可以通過(guò)構(gòu)造時(shí)傳入的比較器（Comparator）今穿。

TreeMap底層通過(guò)紅黑樹(shù)（Red-Black tree）實(shí)現(xiàn)，也就意味著containsKey(), get(), put(), remove()都有著log(n)的時(shí)間復(fù)雜度伦籍，查找key的速度跟二分查找一樣快蓝晒。

TreeMap是線程不安全的，如果需要在并發(fā)場(chǎng)景使用帖鸦，可以使用synchronizedSortedMap：

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

映射6——WeakHashMap

參考：http://www.cnblogs.com/skywang12345/p/3311092.html
WeakHashMap是弱鍵的哈希表芝薇。
WeakHashMap和HashMap都是通過(guò)"拉鏈法"實(shí)現(xiàn)的散列表，數(shù)據(jù)結(jié)構(gòu)和java7的HashMap一樣使用哈希數(shù)組+單向鏈表作儿。
弱鍵意思是：key是弱引用洛二，當(dāng)key不被其它對(duì)象引用時(shí)，會(huì)被GC回收立倍，然后灭红，它對(duì)應(yīng)的鍵值對(duì)也就從WeakHashMap中移除。

關(guān)鍵屬性：

1. queue口注，是一個(gè)引用隊(duì)列（ReferenceQueue）变擒，用來(lái)保存的是“已被GC清除”的“弱引用的鍵”。

private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

2. table寝志，是一個(gè)Entry數(shù)組娇斑，和HashMap一樣，保存哈希表所有鍵值對(duì)材部，不同的是Entry繼承了WeakReference類毫缆，使得Entry里面的key是弱引用。

Entry<K,V>[] table;
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
}

實(shí)現(xiàn)原理：
WeakHashMap使用WeakReference和ReferenceQueue來(lái)實(shí)現(xiàn)弱鍵功能乐导。

1. 整個(gè)哈希表的主干是table（Entry數(shù)組）苦丁，每個(gè)Entry中存儲(chǔ)了key和value，而key是一個(gè)WeakReference弱引用
2. 當(dāng)key引用的對(duì)象不再被使用到時(shí)（不存在強(qiáng)引用）物臂，垃圾回收器會(huì)回收它旺拉，Java虛擬機(jī)就會(huì)把這個(gè)弱引用（key）加入到與之關(guān)聯(lián)的引用隊(duì)列（queue）中。
3. 接著棵磷，下次操作WeakHashMap時(shí)蛾狗，WeakHashMap會(huì)根據(jù)引用隊(duì)列（queue）中的key，來(lái)刪除已被GC回收的弱鍵對(duì)應(yīng)的鍵值對(duì)仪媒。

Set集合

set集合的特點(diǎn)是有：

• 元素不重復(fù)沉桌，add()重復(fù)的元素會(huì)返回false
• 存取無(wú)序，集合里面的對(duì)象沒(méi)有什么特定順序
• set集合的相等使用equals()方法

主要實(shí)現(xiàn)類：

• HashSet
• LinkedHashSet
• TreeSet

HashSet

HashSet內(nèi)部實(shí)際是一個(gè)HashMap，元素的值就是key留凭，value值是一個(gè)空的對(duì)象佃扼。
所以，HashSet是使用哈希算法來(lái)定位元素的存儲(chǔ)位置冰抢，而判斷兩個(gè)元素相等的標(biāo)準(zhǔn)是兩個(gè)對(duì)象的equals()方法相等且hashCode()方法值相等松嘶。

LinkedHashSet

LinkedHashSet內(nèi)部實(shí)際是一個(gè)LinkedHashMap。

• LinkedHashSet也是根據(jù)元素的hashCode值來(lái)決定元素的存儲(chǔ)位置挎扰，但和HashSet不同的是，它同時(shí)使用鏈表維護(hù)元素的次序巢音，這樣使得元素看起來(lái)是以插入的順序保存的遵倦。
• 當(dāng)遍歷LinkedHashSet集合里的元素時(shí)，LinkedHashSet將會(huì)按元素的添加順序來(lái)訪問(wèn)集合里的元素官撼。
• LinkedHashSet需要維護(hù)元素的插入順序梧躺，因此性能略低于HashSet的性能，但在迭代訪問(wèn)Set里的全部元素時(shí)(遍歷)將有很好的性能(鏈表很適合進(jìn)行遍歷)

TreeSet

TreeSet是SortedSet接口的實(shí)現(xiàn)類傲绣。
TreeSet內(nèi)部實(shí)際是一個(gè)TreeMap掠哥。
TreeSet可以確保集合元素處于排序狀態(tài)。

隊(duì)列（Queue接口）

圖片.png

隊(duì)列是一個(gè)先入先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)秃诵。
Queue接口的實(shí)現(xiàn)：

• 簡(jiǎn)單實(shí)現(xiàn)续搀，LinkedList實(shí)現(xiàn)了Queue接口，可以使用LinkedList創(chuàng)建一個(gè)隊(duì)列對(duì)象菠净。

• 阻塞隊(duì)列禁舷，當(dāng)隊(duì)列滿時(shí)put()元素或者隊(duì)列為空時(shí)take()元素，線程將會(huì)阻塞毅往，使用加鎖的方式來(lái)實(shí)現(xiàn)線程安全牵咙。

  • ArrayBlockingQueue，基于數(shù)組的阻塞隊(duì)列攀唯，有界
  • LinkedBlockingQueue洁桌，基于鏈表的阻塞隊(duì)列，有界
  • PriorityBlockingQueue侯嘀，使用優(yōu)先級(jí)取代先入先出的阻塞隊(duì)列另凌，無(wú)界，元素按優(yōu)先級(jí)順序被移除残拐。
  • DelayQueue途茫，帶延遲期的阻塞隊(duì)列，無(wú)界溪食，只有在延遲期滿時(shí)才能從中提取元素囊卜。

• 非阻塞隊(duì)列，使用CAS循環(huán)的方式來(lái)實(shí)現(xiàn)線程安全

  • PriorityQueue ，使用優(yōu)先級(jí)取代先入先出的隊(duì)列栅组，無(wú)界雀瓢，元素按優(yōu)先級(jí)順序被移除。
  • ConcurrentLinkedQueue玉掸，基于鏈表刃麸、線程安全的隊(duì)列，適用于并發(fā)訪問(wèn)司浪，獲取隊(duì)列大小需要遍歷泊业。

• 操作方法

image.png

圖片.png

隊(duì)列1——ConcurrentLinkedQueue

ConcurrentLinkedQueue是一個(gè)雙端單向列表結(jié)構(gòu)、無(wú)界啊易、線程安全的吁伺、非阻塞隊(duì)列。

• 雙端單向：每個(gè)元素都是一個(gè)節(jié)點(diǎn)租谈，每個(gè)節(jié)點(diǎn)都包含next指向下一個(gè)節(jié)點(diǎn)篮奄，默認(rèn)有head結(jié)點(diǎn)和tail結(jié)點(diǎn)。初始化時(shí)割去，head結(jié)點(diǎn)和hail結(jié)點(diǎn)都指向同一個(gè)空結(jié)點(diǎn)窟却，其中head節(jié)點(diǎn)存放鏈表第一個(gè)item為null的節(jié)點(diǎn)，tail則并不是總指向最后一個(gè)節(jié)點(diǎn)呻逆。
• 無(wú)界：因?yàn)槭橇斜斫Y(jié)構(gòu)夸赫，加上不設(shè)限，所以它是無(wú)界的页慷。
• 線程安全的：出隊(duì)憔足、入隊(duì)的函數(shù)都是操作volatile變量：head，tail酒繁。所以要保證隊(duì)列線程安全只需要保證對(duì)這兩個(gè)Node操作的可見(jiàn)性和原子性滓彰，由于volatile本身保證可見(jiàn)性，所以只需要看下多線程下如果保證對(duì)著兩個(gè)變量操作的原子性州袒。比如offer操作揭绑，是在tail后面添加元素，也就是調(diào)用tail.casNext方法郎哭，而這個(gè)方法是使用的CAS操作他匪，只有一個(gè)線程會(huì)成功，然后失敗的線程會(huì)循環(huán)一下夸研，重新獲取tail邦蜜，然后執(zhí)行casNext方法。
• 非阻塞：不適用加鎖的方式亥至，而是使用CAS循環(huán)悼沈，所以它是非阻塞的贱迟。

隊(duì)列2——ArrayBlockingQueue

ArrayBlockingQueue是線程安全的、有界的絮供、阻塞隊(duì)列（FIFO先入先出）衣吠。
ArrayBlockingQueue內(nèi)部是一個(gè)定長(zhǎng)數(shù)組。
ArrayBlockingQueue的阻塞隊(duì)列是通過(guò)重入鎖ReenterLock和Condition條件隊(duì)列實(shí)現(xiàn)的壤靶。

    /** 存儲(chǔ)元素的對(duì)象數(shù)組 */
    final Object[] items;
    /** 出隊(duì)指針 */
    int takeIndex;
    /** 入隊(duì)指針 */
    int putIndex;
    /** 隊(duì)列里元素個(gè)數(shù) */
    int count;
    /** 可重入鎖 */
    final ReentrantLock lock;
    /** 阻塞控制-隊(duì)列空 */
    private final Condition notEmpty;
    /** 阻塞控制-隊(duì)列滿 */
    private final Condition notFull;
    /** 構(gòu)造方法 */
    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();
    }

從源碼可以看出缚俏，ArrayBlockingQueue的實(shí)現(xiàn)原理。

數(shù)據(jù)結(jié)構(gòu)

• capacity贮乳，構(gòu)造參數(shù)忧换，必填，創(chuàng)建ArrayBlockingQueue時(shí)必須指定向拆，表示隊(duì)列大小包雀，所以ArrayBlockingQueue是有界的。
• items亲铡，全局變量，Object[]數(shù)組葡兑，用來(lái)存儲(chǔ)隊(duì)列的元素奖蔓，所以ArrayBlockingQueue是基于數(shù)組的。
• count讹堤，全局變量吆鹤，表示隊(duì)列的元素個(gè)數(shù)。

阻塞控制

• lock洲守，全局變量疑务，ReentrantLock可重入鎖，用來(lái)控制線程阻塞
• fair梗醇，構(gòu)造參數(shù)知允，可選，設(shè)置lock的訪問(wèn)策略（公平/不公平）叙谨。
• notEmpty温鸽，全局變量，用來(lái)控制隊(duì)列為空時(shí)阻塞
• notEmpty手负，全局變量涤垫，用來(lái)控制隊(duì)列滿時(shí)阻塞

出隊(duì)入隊(duì)控制

• takeIndex：出隊(duì)指針，指向ArrayBlockingQueue隊(duì)列（數(shù)組）的隊(duì)頭
• putIndex：入隊(duì)指針竟终，指向ArrayBlockingQueue隊(duì)列（數(shù)組）的隊(duì)尾

ArrayBlockingQueue很巧妙地使用了兩個(gè)指針蝠猬，讓數(shù)組實(shí)現(xiàn)先入先出的隊(duì)列結(jié)構(gòu)，每加入一個(gè)元素统捶，putIndex就加1榆芦，每彈出一個(gè)元素柄粹，takeIndex就加1，當(dāng)putIndex或takeIndex遞增到等于數(shù)組長(zhǎng)度時(shí)歧杏，重新置為0镰惦，指針從0開(kāi)始。

圖片.png

隊(duì)列3——LinkedBlockingQueue

LinkedBlockingQueue是線程安全的犬绒、有界的旺入、阻塞隊(duì)列（FIFO先入先出）。
LinkedBlockingQueue內(nèi)部是一個(gè)單向鏈表凯力。
LinkedBlockingQueue的阻塞隊(duì)列也是通過(guò)重入鎖ReenterLock和Condition條件隊(duì)列實(shí)現(xiàn)的茵瘾。

與ArrayBlockingQueue不同的是

1. LinkedBlockingQueue內(nèi)部是一個(gè)鏈表
2. LinkedBlockingQueue默認(rèn)大小是Integer.MAX_VALUE
3. LinkedBlockingQueue的入隊(duì)和出隊(duì)分別使用兩個(gè)可重入鎖ReenterLock，兩個(gè)操作是可以并行的咐鹤，所以吞吐量比ArrayBlockingQueue高拗秘。

集合相關(guān)

clone

Iterator迭代器

參考：http://www.reibang.com/p/a16ca1560551
通過(guò)集合類，可以了解迭代器的實(shí)現(xiàn)原理祈惶。
比如ArrayList雕旨，可以使用迭代器來(lái)遍歷所有元素

        List<String> list = new ArrayList<String>();
        Iterator<String> iterator = list.iterator();
        while(it.hasNext()){
            String str = it.next();
        }

從ArrayList類的實(shí)現(xiàn)結(jié)構(gòu)可以看出迭代器的實(shí)現(xiàn)原理。

1. ArrayList實(shí)現(xiàn)了Iterable<T>接口捧请，重寫(xiě)了iterator()方法凡涩。
2. ArrayList有個(gè)內(nèi)部類實(shí)現(xiàn)了Iterator<E>接口，重寫(xiě)了hasNext()和next()方法疹蛉。

public interface Iterator<E> {
    boolean hasNext();
    E next();
}
public interface Iterable<T> {
    Iterator<T> iterator();
}
public interface Collection<E> extends Iterable<E> {
}
public interface List<E> extends Collection<E> {
}
public class ArrayList<E>  implements List<E> {
    public Iterator<E> iterator() {
        return new Itr();
    }
    private class Itr implements Iterator<E> {   
        public boolean hasNext() { }
        public E next() { }
    }
}

fail-fast機(jī)制

參考：http://www.cnblogs.com/skywang12345/p/3308762.html
fail-fast 機(jī)制是java集合(Collection)中的一種錯(cuò)誤機(jī)制活箕。
當(dāng)多個(gè)線程對(duì)同一個(gè)集合進(jìn)行操作的時(shí)候，某線程訪問(wèn)集合的過(guò)程中可款，該集合的內(nèi)容被其他線程所改變(即其它線程通過(guò)add育韩、remove、clear等方法闺鲸，改變了modCount的值)筋讨；這時(shí)，就會(huì)拋出ConcurrentModificationException異常翠拣，產(chǎn)生fail-fast事件版仔。

我們舉例ArrayList迭代的源碼，來(lái)分析fail-fast的原理：

1. ArrayList集合有個(gè)屬性modCount误墓，每次改變集合元素（add蛮粮、remove、clear）都會(huì)改變這個(gè)值谜慌。
2. 開(kāi)始迭代ArrayList集合時(shí)然想，會(huì)創(chuàng)建Iterator對(duì)象，把modCount值賦給Iterator對(duì)象的expectedModCount
3. 每次迭代調(diào)用 next()或remove()前欣范，都會(huì)檢查expectedModCount是否等于modCount变泄。
4. 假設(shè)線程A在迭代集合令哟，這時(shí)線程B也在修改集合元素，從而導(dǎo)致modCount變化妨蛹，線程A在迭代時(shí)發(fā)現(xiàn)expectedModCount!=modCount屏富，會(huì)拋出ConcurrentModificationException異常，產(chǎn)生fail-fast事件蛙卤。

如何避免fail-fast呢狠半，只需要使用線程安全的集合，就可以颤难。
比如使用java.util.concurrent包下面的CopyOnWriteArrayList神年，代替java.util.ArrayList

Enumeration枚舉類和Iterator迭代器的區(qū)別

Enumeration是另外一個(gè)遍歷集合的接口，在Vector行嗤、Hashtable集合類中使用了Enumeration已日。

public interface Enumeration<E> {
    boolean hasMoreElements();
    E nextElement();
}
public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
}

Enumeration和Iterator的區(qū)別如下：

1. 接口個(gè)數(shù)不同，Iterator除了有遍歷函數(shù)栅屏，還有刪除函數(shù)飘千。
2. Iterator支持fail-fast，而Enumeration不支持

使用Hashtable集合栈雳，測(cè)試兩種遍歷方式的速度

• Iterator: 9ms
• Enumeration: 5ms

因?yàn)镮terator添加了fail-fast占婉，所以Enumeration速度比Iterator快一點(diǎn)

自然排序Comparator和定制排序Comparable

兩個(gè)接口定義如下：

public interface Comparable<T> {
    public int compareTo(T o);
}
public interface Comparator<T> {
    int compare(T o1, T o2);
}

• Comparable是排序接口，若一個(gè)類實(shí)現(xiàn)了Comparable接口甫恩，就意味著該類支持排序。
  實(shí)現(xiàn)了Comparable接口的類的對(duì)象的列表或數(shù)組可以通過(guò)Collections.sort或Arrays.sort進(jìn)行自動(dòng)排序酌予。
  此外磺箕，實(shí)現(xiàn)此接口的對(duì)象可以用作有序映射（TreeMap）中的鍵或有序集合（TreeSet）中的集合，無(wú)需指定比較器抛虫。

• Comparator是比較器接口松靡，若一個(gè)類要進(jìn)行排序，但它本身不支持排序（即沒(méi)有實(shí)現(xiàn)Comparable接口）建椰，那么我們就可以建立一個(gè)實(shí)現(xiàn)Comparator接口的比較器來(lái)進(jìn)行排序雕欺。
  在初始化排序集合類時(shí)，可以指定比較器來(lái)對(duì)集合內(nèi)的元素進(jìn)行排序棉姐，指定比較器后屠列，本身支持排序的元素的排序規(guī)則將會(huì)被忽略。

TreeMap<String, String> treeMap = new TreeMap<String, String>(new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
       return o2.compareTo(o1);
    }
});

注意：如果元素需要使用排序集合類伞矩，那么元素要么本身支持排序（實(shí)現(xiàn)Comparable接口）笛洛，要么排序集合類需要指定比較器（實(shí)現(xiàn)Comparator接口），不然將會(huì)發(fā)生不可預(yù)測(cè)的異常乃坤。

equals()和hashcode()

這兩個(gè)方法都是從object類中繼承過(guò)來(lái)的苛让。
object類的默認(rèn)實(shí)現(xiàn)中沟蔑，equals()是對(duì)兩個(gè)對(duì)象的地址值進(jìn)行的比較（即比較引用是否相同），而hashCode()是一個(gè)本地方法狱杰，它的實(shí)現(xiàn)是根據(jù)本地機(jī)器相關(guān)的瘦材。

比較：

• equals和hashcode都是比較兩個(gè)對(duì)象是否相等。
• hashcode的速度比equals要快仿畸，但是equals更加可靠食棕，因?yàn)閔ashcode相等的兩個(gè)對(duì)象不一定相等（哈希碰撞）。
• 所以颁湖，在比較相等時(shí)宣蠕，合理的做法是先比較hashcode，如果相等甥捺，在比較equals抢蚀，即能滿足效率也可靠。

1. equals和==
   在比較對(duì)象時(shí)镰禾，==比較的是兩個(gè)對(duì)象的引用（存儲(chǔ)地址）是否相等皿曲，如果不重寫(xiě)equals方法，equals和==的作用是一樣的吴侦，這時(shí)候除非兩個(gè)對(duì)象變量是同個(gè)引用屋休，不然永遠(yuǎn)不相等。
2. 什么時(shí)候重寫(xiě)hashCode和equals方法
   一般的地方不需要重寫(xiě)hashCode备韧，只有當(dāng)類需要放在HashTable劫樟、HashMap、HashSet等等hash結(jié)構(gòu)的集合時(shí)才會(huì)重寫(xiě)织堂。
   而且叠艳，如果重寫(xiě)了equals方法，需要同時(shí)重寫(xiě)hashCode易阳，因?yàn)镠ashMap在比較對(duì)象是否相等時(shí)使用了equals+hashCode附较。

隨機(jī)訪問(wèn)、Iterator迭代器遍歷潦俺、foreach遍歷拒课、Enumeration枚舉

1. 隨機(jī)訪問(wèn)：
   通過(guò)元素的序號(hào)（下標(biāo)）來(lái)獲取集合的元素，其實(shí)就是get(int index)方法事示，ArrayList實(shí)現(xiàn)了RandmoAccess接口早像，這個(gè)接口是個(gè)空接口，唯一作用就是標(biāo)識(shí)它的實(shí)現(xiàn)類支持快速隨機(jī)訪問(wèn)肖爵，因?yàn)锳rrayList本身就是一個(gè)數(shù)組扎酷，所以根據(jù)下標(biāo)獲取元素速度非常快遏匆。

Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {
    value = (Integer)list.get(i);        
}

2. Iterator迭代器訪問(wèn)：
   是利用實(shí)現(xiàn)的迭代器循環(huán)遍歷集合的元素法挨，LinkedList是以鏈表形式存儲(chǔ)元素谁榜，它不適合get(int index)的隨機(jī)訪問(wèn)方式，但它適合以next()的方式遍歷元素凡纳。

Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}

3. foreach遍歷：

Integer value = null;
for (Integer integ:list) {
    value = integ;
}

4. Enumeration枚舉方式遍歷HashTable

Enumeration enu = table.elements();
while(enu.hasMoreElements()) {
    enu.nextElement();
}