簡介

1.所有的集合類都位于java.util包下，Java的結合主要由兩個接口類派生出來，分別是Collection和Map
2.Collection接口是一組允許重復的對象集合
3.Set接口繼承自Collection接口，是一組不允許重復的集合
4.List接口也繼承自Collection接口，允許重復，并維護元素的插入順序

5. Map是鍵值對形式存儲數(shù)據(jù)，可以根據(jù)key訪問對應得value
   6.Set，List，Map可以看做集合的三大類
   首先我們需要清楚有序無序不是指集合中的排序，而是指是否按照元素的添加順序來存儲數(shù)據(jù)：
   List：是按照元素添加順序來存儲數(shù)據(jù)的，因此是有序的，他的實現(xiàn)類ArrayList、LinkedList、Vector都是有序的。
   Set：是無序的，并且Set中元素的順序不允許重復，Set的底層實現(xiàn)原理其實是使用Map,他是計算key的哈希值來確定元素在數(shù)組中的存放位置，所以是無序的，因為Map中的key不允許重復，所以Set也不允許重復，Set的實現(xiàn)類有hashSet、TreeSet
   特例：LinkedHashSet是有序的，LinkedHashSet底層數(shù)據(jù)結構由哈希表和鏈表組成。

• 哈希表保證元素的唯一性。
• 鏈表保證元素有素。(存儲和取出是一致)
  Map：是無序的，他的存儲結構式哈希表<key,value>鍵值對形式，map中插入元素是根據(jù)key計算出的哈希值來存儲元素的，因此他不是按照元素的添加順序存儲數(shù)據(jù)的，所以Map是無序的，他的實現(xiàn)類有HashMap、TableMap、TreeMap，只有LinkedHashSet是有序的，即保證元素的插入順序。
  特例：LinkedHashMap是有序的，底層除了哈希表還添加了一個鏈表用來保證元素順序。
• 哈希表保證元素的唯一性。
• 鏈表保證元素有素。(存儲和取出是一致)

HashMap和HashSet的區(qū)別

什么是 HashMap??

HashMap實現(xiàn)了Map接口，Map接口對鍵值對進行映射，Map中不允許重復的鍵，Map接口有兩個基本的實現(xiàn)，HashMap和TreeMap.其中TreeMap保存了對象的排列次序，而HashMap則不能,HashMap允許鍵和值為null,HashMap是非syncronized的，但是collection提供方法能保證HashMap 同步，這樣多個線程訪問HashMap時候可以保證只有一個線程更改Map.
可以用put方法添加元素

什么是HashSet??

HashSet實現(xiàn)了Set接口，不允許集合中有重復的值，當提到HashSet時，第一件事就是將對象存儲在HashSet之前，要先確保對象重寫equals()和HashCode()方法，這樣才能比較對象的值是否相等，用來確保Set中沒有存儲相等的對象，如果沒重寫這兩個方法，將會使用這個方法的默認實現(xiàn)。
可以用add()添加元素

image.png

image.png

1.Collection是一個接口，是高度抽象出來的集合，它包含了集合的基本操作和屬性，Collection包含了List和Set兩大分支。
1).List是一個有序的集合，每一個元素都有他的索引，索引值0開始，List的實現(xiàn)類主要有LinkedList、ArrayList、Vector、Stack
2).Set是一個不允許重復的集合，Set的實現(xiàn)類有HashSet和TreeSet,
HashSet依賴于HashMap,實際上是通過HashMap實現(xiàn)的，TreeSet依賴于TreeMap，實際上是通過TreeMap實現(xiàn)的。
2.Map是一個映射接口，即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也是遍歷集合用的，只是比Iteratorde功能少，在上面的圖解中所示，Enumeration只作用于HashTable、Vector、Stack
5.Arrays和Collections是操作數(shù)組集合的兩個工具類

詳細介紹

Collection接口

image.png

image.png

List接口

image.png

List集合代表一個有序集合，集合中的每個元素都有其對應順序的索引，List集合允許有重復的元素，可以通過索引來訪問指定位置的元素。
List接口繼承自Collection接口，List代表的是有序的Collection，他用特定的插入順序來維護元素順序，用戶可以對列表中的每個元素進行精確控制，同時可以根據(jù)元素的索引訪問元素，實現(xiàn)List的集合主要有ArrayList、LinkedList、Vector、Stack
Vector：線程安全，但速度慢，已被ArrayList替代。
ArrayList：線程不安全，查詢速度快，增刪速度慢。
LinkedList：線程不安全，鏈表結構，增刪速度快，查詢速度慢。

ArrayList

image.png

ArrayList是一個動態(tài)數(shù)組，也是我們最常用的集合，他允許任何符合規(guī)則的元素插入甚至null,每一個ArrayList的初始容量是10，該容量代表了數(shù)組的大小，容器的大小會隨著容器中的元素不斷增加，每次向容器中添加元素都會進行容量檢測，當快要溢出時，就會進行擴容。
ArrayList與Vector對比：
ArrayList，此實現(xiàn)不是同步的。性能比較好，優(yōu)先使用；-------方法中沒有synchronized
Vector的底層也是靜態(tài)數(shù)組，但是Vector中的大量方法，都是synchronized，需要線程等待，性能比較差

一點通

HashSet：實現(xiàn) Set 接口，不允許重復的元素，底層數(shù)據(jù)結構 hash table
LinkedHashSet：實現(xiàn) Set 接口，不允許重復的元素，底層數(shù)據(jù)結構 hash table 與雙鏈表
TreeSet：實現(xiàn) NavigableSet 接口，不允許重復的元素，底層數(shù)據(jù)結構紅黑樹
ArrayList：實現(xiàn) List 接口，允許重復元素，底層數(shù)據(jù)結構可變數(shù)組
LinkedList：實現(xiàn) List 接口，允許重復元素，底層數(shù)據(jù)結構雙鏈表
Vector：實現(xiàn) List 接口，允許重復元素，底層數(shù)據(jù)結構可變數(shù)組
HashMap：實現(xiàn) Map 接口，不允許重復的 key，底層數(shù)據(jù)結構 hash table
LinkedHashMap：實現(xiàn) Map 接口，不允許重復的 key，底層數(shù)據(jù)結構 hash table 與雙鏈表
HashTable：實現(xiàn) Map 接口，不允許重復的 key，底層數(shù)據(jù)結構 hash table
TreeMap：實現(xiàn) SortedMap 接口，不允許重復的 key，底層數(shù)據(jù)結構紅黑樹

LinkedList

image.png

LinkedList是一個雙向鏈表，所以LinkedList不能隨機訪問，他的所有操作都要按照雙重鏈表的操作執(zhí)行，在列表中索引的操作將從頭或者尾遍歷，好處是用比較小的代價插入和刪除元素。LinkedList也是非同步的，多線程下需要自己實現(xiàn)同步訪問，一種解決方法是創(chuàng)建List的同時構造一個同步的List
List list = Collections.stnchronizedList(new LinkedList(.........));

Vector

image.png

Vector是線程同步的，也就是線程安全的，底層也是動態(tài)數(shù)組，但是效率低下，一般來說不考慮線程安全的情況下都用ArrayList.

Stack

image.png

Stack繼承自Vector,實現(xiàn)了一個后進先出的堆棧，Stack提供了5個額外的方法使得Vector可以被當作堆棧使用，基本的push，pop方法，peek()得到棧頂?shù)脑兀琫mpty（）測試是否為空，search（）檢測一個元素在堆棧中的位置，Stack剛創(chuàng)建后是空棧。

Set接口

image.png

HashSet

image.png

HashSet實現(xiàn)了Set接口，是沒有重復元素的集合，由HashMap實現(xiàn)，不保證元素的插入和輸出順序，允許使用null元素，線程非同步的，HashSet按照Hash算法存儲集合的元素，因此具有很好的查找和存取功能。HashSet的實現(xiàn)方式大致如下,通過一個HashMap存儲元素，元素存放在HashMap的key中，而value同意使用一個Object對象。

LinkedHashSet

image.png

LinkedHashSet繼承自HashSet并且實現(xiàn)了Set接口，其底層是基于LinkedHashMap實現(xiàn)的，有序，線程非同步，LinkedHashSet同樣是根據(jù)HashCode值來決定元素的存儲位置，但是他同時使用了一個鏈表維護元素的次序,也就是遍歷的時候會根據(jù)元素的 添加順序訪問元素。

TreeSet

image.png

TreeMap是一個有序集合，底層基于TreeMap實現(xiàn)的，非線程安全，TreeSet支持兩種排序方式，自然排序和定制排序，如果構造TreeSet時候，使用不帶參數(shù)的構造函數(shù)，則使用自然比較器，若用戶想要定制比較器，需要使用帶比較器的參數(shù)。
注意：TreeSet集合不是通過hashCode和equals（）來比較元素的，他是通過compare或者comparaeTo函數(shù)判斷元素是否相等，compare判斷兩個對象的id，相同的id算作重復元素，不會加入到集合中。

Map接口

image.png

Map與List和Set接口不同，它是由鍵值對組成的集合，提供了Key-value的映射，同時他不繼承Collection，保證key-value的一一對應，他不存在相同的key值，但是value值可以相同。

HashMap

image.png

以hash表數(shù)據(jù)結構實現(xiàn)，查找對象時通過哈希函數(shù)計算其位置，他是為了快速查詢而設計的，內(nèi)部定義了一個hash表數(shù)組Entry[] table,元素會通過哈希轉換函數(shù)將元素的哈希地址轉換成數(shù)組中存放的索引，如果有沖突，則使用散列鏈表的形式將所有相同哈希地址的元素串起來，可以通過查看HashMap.Entry的源碼知道他是一個單鏈表結構。

LinkedHashMap

image.png

繼承自HashMap實現(xiàn)了Map接口，它保留元素的插入順序，底層是Hash表和鏈表實現(xiàn)的，允許使用null值和null鍵，不保證映射的順序，特別是不保證映射順序永遠不變。LinkedHashMap因為需要維護插入順序，所以性能略低于HashMap,但是在迭代訪問Map里全部元素的時候會有很好的性能，因為他一鏈表來維護元素的內(nèi)部順序。

TreeMap

image.png

image.png

比較總結

1.ArrayList和LinkedList
①ArrayList是一個動態(tài)數(shù)組結構，LinkedList是鏈表結構
②對于隨機訪問get和set，ArrayList對于優(yōu)于LinkedList，因為linkedList要移動指針
③對于新增和刪除，LinkedList占據(jù)絕對優(yōu)勢,因為ArrayList要移動元素位置
但是要看實際情況，如果是單條數(shù)據(jù)的插入和刪除ArrayList速度更快，但是批量隨機插入和刪除的話LinkedList才是最好的選擇。
2.HashTable和HashMap
①都實現(xiàn)了Map、Cloneable、Serializable接口
②都是存儲鍵值對的散列表，并且都是使用拉鏈法實現(xiàn)的
③歷史原因：HashTable是基于陳舊的Dictionary類的，HashMap是Map接口的一個實現(xiàn)
④同步性：HashTable是線程安全的，HashMap是線程不安全的
⑤對null值得處理： HashTable的key-value都不能為null,HashMap都可以
⑥基類不同：HashMap繼承自AbstractMap，HashTable繼承自Dictionary
⑦Dictionary是一個抽象類，她直接繼承自Object類，沒有實現(xiàn)任何接口，Api比Map少，一般通過Enumeration遍歷，Map則是使用Iterator迭代器遍歷，由于HashTable也實現(xiàn)了Map接口，所以他也支持Iterator遍歷。
⑧AbstractMap是一個抽象類，他實現(xiàn)了Map接口的絕大多數(shù)api，為Map的具體實現(xiàn)類提供了極大的便利。
3.HashMap、HashTable、LikedHashMap、TreeMap的比較
①HashMap是一個最常用的Map，他根據(jù)鍵的HashCode值存儲數(shù)據(jù)，根據(jù)key可以直接獲取到value，具有很快的訪問速度，遍歷時，取得的數(shù)據(jù)順序是完全隨機的，線程不安全，可以通過用Collections的synchronizedMap方法使HashMap具有同步的能力
②HashTable和HashMap類似，不同點是：他不允許key-value的任意一個為null，他是線程安全的，即任一時刻只有一個線程能寫HashTable，因此也導致寫入時會較慢。
③LinkedHashMap保存了元素的插入順序，再用Iterator遍歷時，先得到的記錄肯定是先插入的，也可以在構造時帶參數(shù)，按照應用次數(shù)排序，在遍歷時會比HashMap慢，特例：在HashMap容量較大，實際數(shù)據(jù)較少的時候，遍歷起來會比LinkedHashMap慢，因為LinkedHashMap的遍歷速度只和實際數(shù)據(jù)有關，和容量無關，而HashMap的遍歷速度和容量有關如果需要輸出順序和輸入順序一樣，可以選擇LinkedHashMap,它繼承自HashMap底層使用Hash表和雙重鏈表保存元素，其基本操作和HashMap類似，他通過重寫父類的方法來實現(xiàn)自己鏈接列表的特性。
④TreeMap實現(xiàn)了NavigableMap實現(xiàn)了SortedMap,內(nèi)部實現(xiàn)是紅黑樹，能夠把他保存的記錄根據(jù)鍵排序，默認是按照鍵值的升序排列，也可以指定排序的比較器，當用Iterator遍歷TreeMap時，得到的記錄是排過序的，TreeMap不允許Key值為null，線程不安全。
4.HashSet、LinkedHashSet、TreeSet比較
①HashSet是無序不重復的，線程不安全的，集合元素可以是null但是僅允許一個，當向HashSet中存入一個元素時，HashSet會調(diào)用該對象的hashCode()值，根據(jù)此值確定存儲位置，判斷兩個元素相等的標準是兩個對象equals()==true并且兩個對象的hashCode()方法返回值也相等。
②LinkedHashSet同樣是根據(jù)元素的HashCode值來決定元素的位置，但是他用鏈表維護元素的插入順序，遍歷的時候，會以元素的添加順序訪問元素。
LinkedHashSet在迭代器訪問Set中的全部元素時，性能比HashSet好，但是插入時的性能不如HashSet
③TreeSet是SortedSet的唯一實現(xiàn)類，TreeSet是無序的，即不能保證元素的插入順序，但是支持自動排序，支持兩種排序，自然排序和定制排序。
TreeSet特性：
它存儲唯一的元素
它不保留元素的插入順序
它按升序對元素進行排序
它不是線程安全的