Java集合框架，數(shù)據(jù)結(jié)構(gòu)

image.png

image.png

所有的集合類位于 jdk下的 rt.jar 包下java.util下；

1、所有集合類都位于java.util包下。Java的集合類主要由兩個接口派生而出：Collection和Map罢艾，Collection和Map是Java集合框架的根接口楣颠，這兩個接口又包含了一些子接口或?qū)崿F(xiàn)類。
2咐蚯、集合接口：6個接口（短虛線表示）童漩，表示不同集合類型，是集合框架的基礎(chǔ)春锋。
3矫膨、抽象類：5個抽象類（長虛線表示），對集合接口的部分實現(xiàn)期奔〔嘞冢可擴展為自定義集合類。
4呐萌、實現(xiàn)類：8個實現(xiàn)類（實線表示）馁痴，對接口的具體實現(xiàn)。
5肺孤、Collection 接口是一組允許重復的對象罗晕。
6、Set 接口繼承 Collection赠堵，集合元素不重復小渊。
7、List 接口繼承 Collection顾腊，允許重復粤铭，維護元素插入順序挖胃。
8杂靶、Map接口是鍵－值對象，與Collection接口沒有什么關(guān)系酱鸭。
9吗垮、Set、List和Map可以看做集合的三大類：

• List集合是有序集合凹髓，集合中的元素可以重復烁登，訪問集合中的元素可以根據(jù)元素的索引來訪問。
• Set集合是無序集合蔚舀，集合中的元素不可以重復饵沧，訪問集合中的元素只能根據(jù)元素本身來訪問（也是集合里元素不允許重復的原因）。
• Map集合中保存Key-value對形式的元素赌躺，訪問時只能根據(jù)每項元素的key來訪問其value狼牺。

Collection和Map

1、Collection是一個接口礼患，是高度抽象出來的集合是钥，它包含了集合的基本操作和屬性掠归。Collection包含了List和Set兩大分支。

• List是一個有序的隊列悄泥，每一個元素都有它的索引虏冻。第一個元素的索引值是0。List的實現(xiàn)類有LinkedList, ArrayList, Vector, Stack弹囚。
• Set是一個不允許有重復元素的集合厨相。Set的實現(xiàn)類有HastSet和TreeSet。HashSet依賴于HashMap余寥，它實際上是通過HashMap實現(xiàn)的悔雹；TreeSet依賴于TreeMap凡资，它實際上是通過TreeMap實現(xiàn)的。

2、Map是一個映射接口牧抽，即key-value鍵值對。Map中的每一個元素包含“一個key”和“key對應的value”芙委。AbstractMap是個抽象類绣张，它實現(xiàn)了Map接口中的大部分API。而HashMap绎狭，TreeMap细溅，WeakHashMap都是繼承于AbstractMap。Hashtable雖然繼承于Dictionary儡嘶，但它實現(xiàn)了Map接口喇聊。

3、接下來蹦狂，再看Iterator誓篱。它是遍歷集合的工具，即我們通常通過Iterator迭代器來遍歷集合凯楔。我們說Collection依賴于Iterator窜骄，是因為Collection的實現(xiàn)類都要實現(xiàn)iterator()函數(shù)，返回一個Iterator對象摆屯。ListIterator是專門為遍歷List而存在的邻遏。

4、再看Enumeration虐骑，它是JDK 1.0引入的抽象類准验。作用和Iterator一樣，也是遍歷集合廷没；但是Enumeration的功能要比Iterator少糊饱。在上面的框圖中，Enumeration只能在Hashtable, Vector, Stack中使用腕柜。

5济似、最后矫废，看Arrays和Collections。它們是操作數(shù)組砰蠢、集合的兩個工具類蓖扑。

Collection接口

Collection接口是處理對象集合的根接口，其中定義了很多對元素進行操作的方法台舱。Collection接口有兩個主要的子接口List和Set律杠，

Collection接口中的方法如下:

image.png

另外，Collection中有一個 iterator() 函數(shù)浑厚，它的作用是返回一個Iterator接口股耽。通常，我們通過Iterator迭代器來遍歷集合钳幅。ListIterator是List接口所特有的物蝙，在List接口中，通過 ListIterator() 返回一個ListIterator對象敢艰。

Collection接口有兩個常用的子接口：

1.List接口

List集合代表一個有序集合诬乞，集合中每個元素都有其對應的順序索引。List集合允許使用重復元素钠导，可以通過索引來訪問指定位置的集合元素震嫉。

List接口繼承于Collection接口，它可以定義一個允許重復的有序集合辈双。因為List中的元素是有序的责掏，所以我們可以通過使用索引（元素在List中的位置柜砾，類似于數(shù)組下標）來訪問List中的元素湃望，這類似于Java的數(shù)組。

List接口為Collection直接接口痰驱。List所代表的是有序的Collection证芭，即它用某種特定的插入順序來維護元素順序。用戶可以對列表中每個元素的插入位置進行精確地控制担映，同時可以根據(jù)元素的整數(shù)索引（在列表中的位置）訪問元素废士，并搜索列表中的元素。

image.png

實現(xiàn)List接口的集合主要有：ArrayList蝇完、LinkedList官硝、Vector矗蕊、Stack。

（1）ArrayList

ArrayList是一個動態(tài)數(shù)組氢架，也是我們最常用的集合傻咖。它允許任何符合規(guī)則的元素插入甚至包括null。每一個ArrayList都有一個初始容量（10）岖研，該容量代表了數(shù)組的大小卿操。隨著容器中的元素不斷增加，容器的大小也會隨著增加孙援。在每次向容器中增加元素的同時都會進行容量檢查害淤，當快溢出時，就會進行擴容操作拓售。所以如果我們明確所插入元素的多少窥摄，最好指定一個初始容量值，避免過多的進行擴容操作而浪費時間础淤、效率溪王。

size、isEmpty值骇、get莹菱、set、iterator和 listIterator 操作都以固定時間運行吱瘩。add 操作以分攤的固定時間運行道伟，也就是說，添加 n 個元素需要 O(n) 時間（由于要考慮到擴容使碾，所以這不只是添加元素會帶來分攤固定時間開銷那樣簡單）蜜徽。

ArrayList擅長于隨機訪問。同時ArrayList是非同步的票摇。

image.png

image.png

（2）LinkedList鏈表

同樣實現(xiàn)List接口的LinkedList與ArrayList不同拘鞋，ArrayList是一個動態(tài)數(shù)組，而LinkedList是一個雙向鏈表矢门。所以它除了有ArrayList的基本操作方法外還額外提供了get盆色，remove，insert方法在LinkedList的首部或尾部祟剔。

由于實現(xiàn)的方式不同隔躲，LinkedList不能隨機訪問，它所有的操作都是要按照雙重鏈表的需要執(zhí)行物延。在列表中索引的操作將從開頭或結(jié)尾遍歷列表（從靠近指定索引的一端）宣旱。這樣做的好處就是可以通過較低的代價在List中進行插入和刪除操作。

與ArrayList一樣叛薯，LinkedList也是非同步的浑吟。如果多個線程同時訪問一個List笙纤，則必須自己實現(xiàn)訪問同步。一種解決方法是在創(chuàng)建List時構(gòu)造一個同步的List：

List list = Collections.synchronizedList(new LinkedList(...));

image.png

image.png

image.png

（3）Vector

與ArrayList相似组力，但是Vector是同步的粪糙。所以說Vector是線程安全的動態(tài)數(shù)組。它的操作與ArrayList幾乎一樣忿项。

image.png

image.png

image.png

（4）Stack棧

Stack繼承自Vector蓉冈，實現(xiàn)一個后進先出的堆棧。Stack提供5個額外的方法使得Vector得以被當作堆棧使用轩触∧穑基本的push和pop 方法，還有peek方法得到棧頂?shù)脑赝阎琫mpty方法測試堆棧是否為空伐弹，search方法檢測一個元素在堆棧中的位置。Stack剛創(chuàng)建后是空棧榨为。

image.png

List 實現(xiàn)類
ArrayList的特點：數(shù)組結(jié)構(gòu)惨好，線程不安全，查找速度快随闺。
缺點：增加日川，刪除速度較慢。
LinkedList的特點：鏈表結(jié)構(gòu)矩乐，線程安全龄句，查找速度慢，增加刪除速度較快

CopyOnWriteArrayList

CopyOnWriteArrayList是線程安全的List散罕，內(nèi)部使用數(shù)組存儲數(shù)據(jù)分歇，集合中多線程并行操作一般存在4種情況：讀讀、讀寫欧漱、寫寫职抡、寫讀，這個只有在寫寫操作過程中會導致其他線程阻塞误甚，其他3種情況均不會阻塞缚甩，所以讀取的效率非常高。

當這個List需要修改時靶草，并不修改原有內(nèi)容（這對于保證當前在讀線程的數(shù)據(jù)一致性非常重要）蹄胰，而是在原有存放數(shù)據(jù)的數(shù)組上產(chǎn)生一個副本岳遥，在副本上修改數(shù)據(jù)奕翔，修改完畢之后，用副本替換原來的數(shù)組浩蓉，這樣也保證了寫操作不會影響讀派继。

特性：

1. 迭代結(jié)果和存入順序一致
2. 元素不重復
3. 元素可以為空
4. 線程安全的
5. 讀讀宾袜、讀寫、寫讀3種情況不會阻塞驾窟；寫寫會阻塞
6. 無界的

2.Set接口

Set是一種不包括重復元素的Collection庆猫。它維持它自己的內(nèi)部排序，所以隨機訪問沒有任何意義绅络。與List一樣月培，它同樣允許null的存在但是僅有一個。由于Set接口的特殊性恩急，所有傳入Set集合中的元素都必須不同杉畜，同時要注意任何可變對象，如果在對集合中元素進行操作時衷恭，導致e1.equals(e2)==true此叠，則必定會產(chǎn)生某些問題。Set接口有三個具體實現(xiàn)類随珠，分別是 散列集HashSet灭袁、鏈式散列集LinkedHashSet和 樹形集TreeSet。

Set是一種不包含重復的元素的Collection窗看，無序茸歧，即任意的兩個元素e1和e2都有e1.equals(e2)=false，Set最多有一個null元素显沈。

需要注意的是：雖然Set中元素沒有順序举娩，但是元素在set中的位置是由該元素的HashCode決定的，其具體位置其實是固定的构罗。

在set接口中的不重復是有特殊要求的：
對象A和對象B铜涉，本來是不同的兩個對象，正常情況下它們是能夠放入到Set里面的遂唧，但是如果對象A和B的都重寫了hashcode和equals方法芙代，并且重寫后的hashcode和equals方法是相同的話。那么A和B是不能同時放入到Set集合中去的盖彭，也就是Set集合中的去重和hashcode與equals方法直接相關(guān)纹烹。

image.png

（1）HashSet

HashSet 是一個沒有重復元素的集合。它是由HashMap實現(xiàn)的召边，不保證元素的順序(這里所說的沒有順序是指：元素插入的順序與輸出的順序不一致)铺呵，而且HashSet允許使用null 元素。HashSet是非同步的隧熙，如果多個線程同時訪問一個哈希set片挂，而其中至少一個線程修改了該set，那么它必須保持外部同步。 HashSet按Hash算法來存儲集合的元素音念，因此具有很好的存取和查找性能沪饺。

HashSet的實現(xiàn)方式大致如下，通過一個HashMap存儲元素闷愤，元素是存放在HashMap的Key中整葡，而Value統(tǒng)一使用一個Object對象。

HashSet使用和理解中容易出現(xiàn)的誤區(qū):

a.HashSet中存放null值讥脐。HashSet中是允許存入null值的遭居，但是在HashSet中僅僅能夠存入一個null值。

b.HashSet中存儲元素的位置是固定的旬渠。HashSet中存儲的元素的是無序的魏滚，這個沒什么好說的，但是由于HashSet底層是基于Hash算法實現(xiàn)的坟漱，使用了hashcode鼠次，所以HashSet中相應的元素的位置是固定的。

c.必須小心操作可變對象（Mutable Object）芋齿。如果一個Set中的可變元素改變了自身狀態(tài)導致Object.equals(Object)=true將導致一些問題腥寇。

image.png

（2）LinkedHashSet

LinkedHashSet繼承自HashSet，其底層是基于LinkedHashMap來實現(xiàn)的觅捆，有序赦役，非同步。LinkedHashSet集合同樣是根據(jù)元素的hashCode值來決定元素的存儲位置栅炒，但是它同時使用鏈表維護元素的次序掂摔。這樣使得元素看起來像是以插入順序保存的，也就是說赢赊，當遍歷該集合時候乙漓，LinkedHashSet將會以元素的添加順序訪問集合的元素。

image.png

（3）TreeSet

TreeSet是一個有序集合释移，其底層是基于TreeMap實現(xiàn)的叭披，非線程安全。TreeSet可以確保集合元素處于排序狀態(tài)玩讳。TreeSet支持兩種排序方式涩蜘，自然排序和定制排序，其中自然排序為默認的排序方式熏纯。當我們構(gòu)造TreeSet時同诫，若使用不帶參數(shù)的構(gòu)造函數(shù)，則TreeSet的使用自然比較器樟澜；若用戶需要使用自定義的比較器误窖，則需要使用帶比較器的參數(shù)叮盘。

注意：TreeSet集合不是通過hashcode和equals函數(shù)來比較元素的.它是通過compare或者comparaeTo函數(shù)來判斷元素是否相等.compare函數(shù)通過判斷兩個對象的id，相同的id判斷為重復元素贩猎，不會被加入到集合中熊户。

image.png

ConcurrentSkipListSet

有序的Set萍膛，內(nèi)部基于ConcurrentSkipListMap實現(xiàn)的吭服，放入的元素會進行排序，排序算法支持2種方式來指定：

1. 通過構(gòu)造方法傳入一個Comparator
2. 放入的元素實現(xiàn)Comparable接口

上面2種方式需要實現(xiàn)一個蝗罗，如果2種都有艇棕，走規(guī)則1
特性：

1. 迭代結(jié)果和存入順序不一致
2. 放入的元素會排序
3. 元素不重復
4. 元素不能為空
5. 線程安全的
6. 無界的

CopyOnWriteArraySet

內(nèi)部使用CopyOnWriteArrayList實現(xiàn)的，將所有的操作都會轉(zhuǎn)發(fā)給CopyOnWriteArrayList串塑。
特性：

1. 迭代結(jié)果和存入順序不一致
2. 元素不重復
3. 元素可以為空
4. 線程安全的
5. 讀讀沼琉、讀寫、寫讀 不會阻塞桩匪；寫寫會阻塞
6. 無界的

Map接口

Map與List打瘪、Set接口不同，它是由一系列鍵值對組成的集合傻昙，提供了key到Value的映射闺骚。同時它也沒有繼承Collection。在Map中它保證了key與value之間的一一對應關(guān)系妆档。也就是說一個key對應一個value僻爽，所以它不能存在相同的key值，當然value值可以相同贾惦。

1.HashMap

以哈希表數(shù)據(jù)結(jié)構(gòu)實現(xiàn)胸梆，查找對象時通過哈希函數(shù)計算其位置，它是為快速查詢而設計的须板，其內(nèi)部定義了一個hash表數(shù)組（Entry[] table）碰镜，元素會通過哈希轉(zhuǎn)換函數(shù)將元素的哈希地址轉(zhuǎn)換成數(shù)組中存放的索引，如果有沖突习瑰，則使用散列鏈表的形式將所有相同哈希地址的元素串起來洋措，可能通過查看HashMap.Entry的源碼它是一個單鏈表結(jié)構(gòu)。

image.png

image.png

2.LinkedHashMap

LinkedHashMap是HashMap的一個子類杰刽，它保留插入的順序菠发，如果需要輸出的順序和輸入時的相同，那么就選用LinkedHashMap贺嫂。

LinkedHashMap是Map接口的哈希表和鏈接列表實現(xiàn)滓鸠，具有可預知的迭代順序。此實現(xiàn)提供所有可選的映射操作第喳，并允許使用null值和null鍵糜俗。此類不保證映射的順序，特別是它不保證該順序恒久不變。

LinkedHashMap實現(xiàn)與HashMap的不同之處在于悠抹，后者維護著一個運行于所有條目的雙重鏈接列表珠月。此鏈接列表定義了迭代順序，該迭代順序可以是插入順序或者是訪問順序楔敌。

根據(jù)鏈表中元素的順序可以分為：按插入順序的鏈表啤挎，和按訪問順序(調(diào)用get方法)的鏈表。默認是按插入順序排序卵凑，如果指定按訪問順序排序庆聘，那么調(diào)用get方法后，會將這次訪問的元素移至鏈表尾部勺卢，不斷訪問可以形成按訪問順序排序的鏈表伙判。

注意，此實現(xiàn)不是同步的黑忱。如果多個線程同時訪問鏈接的哈希映射宴抚，而其中至少一個線程從結(jié)構(gòu)上修改了該映射，則它必須保持外部同步甫煞。由于LinkedHashMap需要維護元素的插入順序菇曲，因此性能略低于HashMap的性能，但在迭代訪問Map里的全部元素時將有很好的性能危虱，因為它以鏈表來維護內(nèi)部順序羊娃。

image.png

3.TreeMap

TreeMap 是一個有序的key-value集合，非同步埃跷，基于紅黑樹（Red-Black tree）實現(xiàn)蕊玷，每一個key-value節(jié)點作為紅黑樹的一個節(jié)點。TreeMap存儲時會進行排序的弥雹，會根據(jù)key來對key-value鍵值對進行排序垃帅，其中排序方式也是分為兩種，一種是自然排序剪勿，一種是定制排序贸诚，具體取決于使用的構(gòu)造方法。
自然排序：TreeMap中所有的key必須實現(xiàn)Comparable接口厕吉，并且所有的key都應該是同一個類的對象酱固，否則會報ClassCastException異常。
定制排序：定義TreeMap時头朱，創(chuàng)建一個comparator對象运悲，該對象對所有的treeMap中所有的key值進行排序，采用定制排序的時候不需要TreeMap中所有的key必須實現(xiàn)Comparable接口项钮。
TreeMap判斷兩個元素相等的標準：兩個key通過compareTo()方法返回0班眯，則認為這兩個key相等希停。
如果使用自定義的類來作為TreeMap中的key值，且想讓TreeMap能夠良好的工作署隘，則必須重寫自定義類中的equals()方法宠能，TreeMap中判斷相等的標準是：兩個key通過equals()方法返回為true，并且通過compareTo()方法比較應該返回為0磁餐。

image.png

image.png

image.png

ConcurrentHashMap

功能和HashMap基本一致违崇，內(nèi)部使用紅黑樹實現(xiàn)的。
特性：

1. 迭代結(jié)果和存入順序不一致
2. key和value都不能為空
3. 線程安全的

ConcurrentSkipListMap

內(nèi)部使用跳表實現(xiàn)的崖媚，放入的元素會進行排序亦歉，排序算法支持2種方式來指定：

1. 通過構(gòu)造方法傳入一個Comparator
2. 放入的元素實現(xiàn)Comparable接口

上面2種方式必選一個恤浪，如果2種都有畅哑，走規(guī)則1。
特性：

1. 迭代結(jié)果和存入順序不一致
2. 放入的元素會排序
3. key和value都不能為空
4. 線程安全的

Iterator 與 ListIterator詳解

1.Iterator迭代器

Iterator的定義如下：

public interface Iterator<E> {}

Iterator是一個接口水由，它是集合的迭代器荠呐。集合可以通過Iterator去遍歷集合中的元素。

Iterator提供的API接口如下：

• boolean hasNext()：判斷集合里是否存在下一個元素砂客。如果有泥张，hasNext()方法返回 true。
• Object next()：返回集合里下一個元素鞠值。
• void remove()：刪除集合里上一次next方法返回的元素媚创。

注意：

• Iterator只能單向移動。
• Iterator.remove()是唯一安全的方式來在迭代過程中修改集合彤恶；如果在迭代過程中以任何其它的方式修改了基本集合將會產(chǎn)生未知的行為钞钙。而且每調(diào)用一次next()方法，remove()方法只能被調(diào)用一次声离，如果違反這個規(guī)則將拋出一個異常芒炼。
  
  image.png

2.ListIterator

ListIterator是一個功能更加強大的迭代器, 它繼承于Iterator接口，****只能用于各種List類型的訪問术徊”竟簦可以通過調(diào)用listIterator()方法產(chǎn)生一個指向 ** List開始處的ListIterator, 還可以調(diào)用listIterator(n)方法創(chuàng)建一個一開始就指向列表索引為n的元素處的ListIterator。

ListIterator接口定義如下:

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
}

由以上定義我們可以推出ListIterator可以:

• 雙向移動（向前/向后遍歷）.
• 產(chǎn)生相對于迭代器在列表中指向的當前位置的前一個和后一個元素的索引.
• 可以使用set()方法替換它訪問過的最后一個元素.
• 可以使用add()方法在next()方法返回的元素之前或previous()方法返回的元素之后插入一個元素.
  
  image.png

異同點

1.ArrayList和LinkedList

• ArrayList是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)赠涮，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)子寓。
• 對于隨機訪問get和set，ArrayList絕對優(yōu)于LinkedList笋除，因為LinkedList要移動指針斜友。
• 對于新增和刪除操作add和remove，LinedList比較占優(yōu)勢株憾，因為ArrayList要移動數(shù)據(jù)蝙寨。

這一點要看實際情況的晒衩。若只對單條數(shù)據(jù)插入或刪除，ArrayList的速度反而優(yōu)于LinkedList墙歪。但若是批量隨機的插入刪除數(shù)據(jù)听系，LinkedList的速度大大優(yōu)于ArrayList. 因為ArrayList每插入一條數(shù)據(jù)，要移動插入點及之后的所有數(shù)據(jù)虹菲。

2.HashTable與HashMap

相同點：

• 都實現(xiàn)了Map靠胜、Cloneable、java.io.Serializable接口毕源。
• 都是存儲"鍵值對(key-value)"的散列表浪漠，而且都是采用拉鏈法實現(xiàn)的。

不同點：

（1）歷史原因：HashTable是基于陳舊的Dictionary類的霎褐，HashMap是Java 1.2引進的Map接口的一個實現(xiàn) 址愿。
（2）同步性：HashTable是線程安全的，也就是說是同步的，而HashMap是線程序不安全的，不是同步的 陕赃。
（3）對null值的處理：HashMap的key、value都可為null娘纷，HashTable的key、value都不可為null 跋炕。
（4）基類不同：HashMap繼承于AbstractMap赖晶，而Hashtable繼承于Dictionary。

• Dictionary是一個抽象類辐烂，它直接繼承于Object類遏插，沒有實現(xiàn)任何接口。Dictionary類是JDK 1.0的引入的棉圈。雖然Dictionary也支持“添加key-value鍵值對”涩堤、“獲取value”、“獲取大小”等基本操作分瘾，但它的API函數(shù)比Map少胎围；而且Dictionary一般是通過Enumeration(枚舉類)去遍歷，Map則是通過Iterator(迭代M器)去遍歷德召。然而由于Hashtable也實現(xiàn)了Map接口白魂，所以，它即支持Enumeration遍歷上岗，也支持Iterator遍歷福荸。
• AbstractMap是一個抽象類，它實現(xiàn)了Map接口的絕大部分API函數(shù)肴掷；為Map的具體實現(xiàn)類提供了極大的便利敬锐。它是JDK 1.2新增的類背传。
  （5）支持的遍歷種類不同：HashMap只支持Iterator(迭代器)遍歷。而Hashtable支持Iterator(迭代器)和Enumeration(枚舉器)兩種方式遍歷台夺。

3.HashMap径玖、Hashtable、LinkedHashMap和TreeMap比較

Hashmap 是一個最常用的Map颤介，它根據(jù)鍵的HashCode 值存儲數(shù)據(jù)梳星，根據(jù)鍵可以直接獲取它的值，具有很快的訪問速度滚朵。遍歷時冤灾，取得數(shù)據(jù)的順序是完全隨機的。HashMap最多只允許一條記錄的鍵為Null辕近；允許多條記錄的值為Null韵吨；HashMap不支持線程的同步，即任一時刻可以有多個線程同時寫HashMap亏推；可能會導致數(shù)據(jù)的不一致学赛。如果需要同步年堆，可以用Collections的synchronizedMap方法使HashMap具有同步的能力吞杭。

Hashtable 與 HashMap類似，不同的是：它不允許記錄的鍵或者值為空变丧；它支持線程的同步芽狗，即任一時刻只有一個線程能寫Hashtable，因此也導致了Hashtale在寫入時會比較慢痒蓬。
LinkedHashMap保存了記錄的插入順序童擎，在用Iterator遍歷LinkedHashMap時，先得到的記錄肯定是先插入的攻晒，也可以在構(gòu)造時用帶參數(shù)顾复，按照應用次數(shù)排序。在遍歷的時候會比HashMap慢鲁捏，不過有種情況例外芯砸，當HashMap容量很大，實際數(shù)據(jù)較少時给梅，遍歷起來可能會比LinkedHashMap慢假丧，因為LinkedHashMap的遍歷速度只和實際數(shù)據(jù)有關(guān)，和容量無關(guān)动羽，而HashMap的遍歷速度和他的容量有關(guān)包帚。

如果需要輸出的順序和輸入的相同，那么用LinkedHashMap可以實現(xiàn)运吓，它還可以按讀取順序來排列渴邦，像連接池中可以應用疯趟。LinkedHashMap實現(xiàn)與HashMap的不同之處在于，后者維護著一個運行于所有條目的雙重鏈表谋梭。此鏈接列表定義了迭代順序迅办，該迭代順序可以是插入順序或者是訪問順序。
對于LinkedHashMap而言章蚣，它繼承與HashMap站欺、底層使用哈希表與雙向鏈表來保存所有元素。其基本操作與父類HashMap相似纤垂，它通過重寫父類相關(guān)的方法矾策，來實現(xiàn)自己的鏈接列表特性。

TreeMap實現(xiàn)SortMap接口峭沦，內(nèi)部實現(xiàn)是紅黑樹贾虽。能夠把它保存的記錄根據(jù)鍵排序，默認是按鍵值的升序排序吼鱼，也可以指定排序的比較器蓬豁，當用Iterator 遍歷TreeMap時，得到的記錄是排過序的菇肃。TreeMap不允許key的值為null地粪。非同步的。

一般情況下琐谤，我們用的最多的是HashMap蟆技，HashMap里面存入的鍵值對在取出的時候是隨機的，它根據(jù)鍵的HashCode值存儲數(shù)據(jù)斗忌，根據(jù)鍵可以直接獲取它的值质礼，具有很快的訪問速度。在Map 中插入织阳、刪除和定位元素眶蕉，HashMap 是最好的選擇。

TreeMap取出來的是排序后的鍵值對唧躲。但如果您要按自然順序或自定義順序遍歷鍵造挽，那么TreeMap會更好。

LinkedHashMap 是HashMap的一個子類惊窖，如果需要輸出的順序和輸入的相同刽宪，那么用LinkedHashMap可以實現(xiàn)，它還可以按讀取順序來排列界酒，像連接池中可以應用圣拄。

4.HashSet、LinkedHashSet毁欣、TreeSet比較

Set接口

Set不允許包含相同的元素庇谆，如果試圖把兩個相同元素加入同一個集合中岳掐，add方法返回false。
Set判斷兩個對象相同不是使用==運算符饭耳，而是根據(jù)equals方法串述。也就是說，只要兩個對象用equals方法比較返回true寞肖，Set就不會接受這兩個對象纲酗。

HashSet

HashSet有以下特點：

• 不能保證元素的排列順序，順序有可能發(fā)生變化新蟆。
• 不是同步的觅赊。
• 集合元素可以是null，但只能放入一個null琼稻。

當向HashSet結(jié)合中存入一個元素時吮螺，HashSet會調(diào)用該對象的hashCode()方法來得到該對象的hashCode值，然后根據(jù) hashCode值來決定該對象在HashSet中存儲位置帕翻。簡單的說鸠补，HashSet集合判斷兩個元素相等的標準是兩個對象通過equals方法比較相等，并且兩個對象的hashCode()方法返回值也相等嘀掸。

注意紫岩，如果要把一個對象放入HashSet中，重寫該對象對應類的equals方法横殴，也應該重寫其hashCode()方法被因。其規(guī)則是如果兩個對象通過equals方法比較返回true時，其hashCode也應該相同衫仑。另外，對象中用作equals比較標準的屬性堕花，都應該用來計算 hashCode的值文狱。

LinkedHashSet

LinkedHashSet集合同樣是根據(jù)元素的hashCode值來決定元素的存儲位置，但是它同時使用鏈表維護元素的次序缘挽。這樣使得元素看起來像是以插入順序保存的瞄崇，也就是說，當遍歷該集合時候壕曼，LinkedHashSet將會以元素的添加順序訪問集合的元素苏研。

LinkedHashSet在迭代訪問Set中的全部元素時，性能比HashSet好腮郊，但是插入時性能稍微遜色于HashSet摹蘑。

TreeSet

TreeSet是SortedSet接口的唯一實現(xiàn)類，TreeSet可以確保集合元素處于排序狀態(tài)轧飞。TreeSet支持兩種排序方式衅鹿，自然排序和定制排序撒踪，其中自然排序為默認的排序方式。向TreeSet中加入的應該是同一個類的對象大渤。

TreeSet判斷兩個對象不相等的方式是兩個對象通過equals方法返回false制妄，或者通過CompareTo方法比較沒有返回0。

自然排序
自然排序使用要排序元素的CompareTo（Object obj）方法來比較元素之間大小關(guān)系泵三，然后將元素按照升序排列耕捞。

Java提供了一個Comparable接口，該接口里定義了一個compareTo(Object obj)方法烫幕，該方法返回一個整數(shù)值砸脊，實現(xiàn)了該接口的對象就可以比較大小。obj1.compareTo(obj2)方法如果返回0纬霞，則說明被比較的兩個對象相等凌埂，如果返回一個正數(shù)，則表明obj1大于obj2诗芜，如果是負數(shù)瞳抓，則表明obj1小于obj2。如果我們將兩個對象的equals方法總是返回true伏恐，則這兩個對象的compareTo方法返回應該返回0孩哑。

定制排序
自然排序是根據(jù)集合元素的大小，以升序排列翠桦，如果要定制排序横蜒，應該使用Comparator接口，實現(xiàn) int compare(T o1,T o2)方法销凑。

5丛晌、Iterator和ListIterator區(qū)別

List和Set都有iterator()來取得其迭代器。對List來說斗幼，你也可以通過listIterator()取得其迭代器澎蛛，兩種迭代器在有些時候是不能通用的，Iterator和ListIterator主要區(qū)別在以下方面：

• ListIterator有add()方法蜕窿，可以向List中添加對象谋逻，而Iterator不能
• ListIterator和Iterator都有hasNext()和next()方法，可以實現(xiàn)順序向后遍歷桐经，但是ListIterator有hasPrevious()和previous()方法毁兆，可以實現(xiàn)逆向（順序向前）遍歷。Iterator就不可以阴挣。
• ListIterator可以定位當前的索引位置气堕，nextIndex()和previousIndex()可以實現(xiàn)。Iterator沒有此功能。
• 都可實現(xiàn)刪除對象送巡，但是ListIterator可以實現(xiàn)對象的修改摹菠，set()方法可以實現(xiàn)。Iierator僅能遍歷骗爆，不能修改次氨。

因為ListIterator的這些功能，可以實現(xiàn)對LinkedList等List數(shù)據(jù)結(jié)構(gòu)的操作摘投。其實煮寡，數(shù)組對象也可以用迭代器來實現(xiàn)。

6犀呼、Collection 和 Collections區(qū)別

（1）java.util.Collection 是一個集合接口（集合類的一個頂級接口）幸撕。它提供了對集合對象進行基本操作的通用接口方法。Collection接口在Java 類庫中有很多具體的實現(xiàn)外臂。Collection接口的意義是為各種具體的集合提供了最大化的統(tǒng)一操作方式坐儿，其直接繼承接口有List與Set。

 Collection   
├List   
│├LinkedList   
│├ArrayList   
│└Vector   
│　└Stack   
└Set 

（2）java.util.Collections 是一個包裝類（工具類/幫助類）宋光。它包含有各種有關(guān)集合操作的靜態(tài)多態(tài)方法貌矿。此類不能實例化，就像一個工具類罪佳，用于對集合中元素進行排序逛漫、搜索以及線程安全等各種操作，服務于Java的Collection框架赘艳。

image.png

image.png

Queue隊列

image.png

3種操作酌毡，每種操作有2個方法，不同點是隊列為空或者滿載時蕾管，調(diào)用方法是拋出異常還是返回特殊值.

ConcurrentLinkedQueue

高效并發(fā)隊列枷踏，內(nèi)部使用鏈表實現(xiàn)的。
特性：

1. 線程安全的
2. 迭代結(jié)果和存入順序一致
3. 元素可以重復
4. 元素不能為空
5. 線程安全的
6. 無界隊列