List，Set吮炕，Map三者的區(qū)別？
Java 容器分為 Collection 和 Map 兩大接口祝谚，Collection集合的子接口有Set围小、List昵骤、Queue三種子接口。我們比較常用的是Set肯适、List变秦。
Collection集合主要有List和Set兩大接口：
- List：基于數(shù)組、鏈表兩種結(jié)構(gòu)實(shí)現(xiàn)框舔，一個(gè)有序（元素存入集合的順序和取出的順序一致）容器蹦玫，元素可以重復(fù)，可以插入多個(gè)null元素刘绣。常用的實(shí)現(xiàn)類有 ArrayList樱溉、LinkedList 和 Vector。
- Set：一個(gè)無序（存入和取出順序有可能不一致）容器纬凤，不可以存儲重復(fù)元素福贞，只允許存入一個(gè)null元素，必須保證元素唯一性停士。Set 接口常用實(shí)現(xiàn)類是 HashSet挖帘、LinkedHashSet 以及 TreeSet（后兩個(gè)可以實(shí)現(xiàn)有序）。
Map是一個(gè)鍵值對集合恋技，存儲鍵拇舀、值之間的映射。
- Map：Key無序猖任，唯一你稚；value 不要求有序，允許重復(fù)。Map沒有繼承于Collection接口刁赖，從Map集合中檢索元素時(shí)搁痛，只要給出鍵對象，就會返回對應(yīng)的值對象宇弛。Map 的常用實(shí)現(xiàn)類：HashMap鸡典、TreeMap、HashTable枪芒、LinkedHashMap彻况、ConcurrentHashMap
- Set和Map有基于哈希存儲和紅黑樹實(shí)現(xiàn)。
List舅踪，Set纽甘，Map和Queue的底層數(shù)據(jù)結(jié)構(gòu)
（1）Set
TreeSet：通過 TreeMap 實(shí)現(xiàn)的，添加元素到集合時(shí)按照比較規(guī)則將其插入合適的位置抽碌，保證插入后的集合仍然有序悍赢。但是查找效率不如 HashSet，HashSet 查找的時(shí)間復(fù)雜度為 O(1)货徙，TreeSet 則為 O(logN)左权。
HashSet：通過 HashMap 實(shí)現(xiàn)，HashMap 的 Key 即 HashSet 存儲的元素痴颊，所有 Key 都使用相同的 Value 赏迟，一個(gè)名為 PRESENT 的 Object 類型常量。使用 Key 保證元素唯一性蠢棱，但不保證有序性锌杀。由于 HashSet 是 HashMap 實(shí)現(xiàn)的，因此線程不安全裳扯。
LinkedHashSet：繼承自 HashSet抛丽，通過 LinkedHashMap 實(shí)現(xiàn)，使用雙向鏈表維護(hù)元素插入順序饰豺。
（2） List
ArrayList：基于動態(tài)數(shù)組實(shí)現(xiàn)亿鲜，支持隨機(jī)訪問。
Vector：和 ArrayList 類似冤吨，但它是線程安全的蒿柳。
LinkedList：基于雙向鏈表實(shí)現(xiàn)，只能順序訪問漩蟆，但是可以快速地在鏈表中間插入和刪除元素垒探。不僅如此，LinkedList 還可以用作棧怠李、隊(duì)列和雙向隊(duì)列（刷題常用）圾叼。
（3） Queue
LinkedList：可以用它來實(shí)現(xiàn)雙向隊(duì)列蛤克。
PriorityQueue：基于堆結(jié)構(gòu)實(shí)現(xiàn)，可以用它來實(shí)現(xiàn)優(yōu)先隊(duì)列夷蚊。
（4）Map
TreeMap：基于紅黑樹實(shí)現(xiàn)构挤。
HashMap：JDK1.8之前HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體惕鼓，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）筋现。JDK1.8以后在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長度大于閾值（默認(rèn)為8）時(shí)箱歧，將鏈表轉(zhuǎn)化為紅黑樹矾飞，以減少搜索時(shí)間
HashTable：和 HashMap 類似，但它是線程安全的呀邢，這意味著同一時(shí)刻多個(gè)線程同時(shí)寫入 HashTable 不會導(dǎo)致數(shù)據(jù)不一致洒沦。它是遺留類，不應(yīng)該去使用它驼鹅，而是使用 ConcurrentHashMap 來支持線程安全微谓，ConcurrentHashMap 的效率會更高，因?yàn)?ConcurrentHashMap 引入了分段鎖输钩。
LinkedHashMap： LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈?zhǔn)缴⒘薪Y(jié)構(gòu)即由數(shù)組和鏈表或紅黑樹組成仲智。LinkedHashMap使用雙向鏈表來維護(hù)元素的順序买乃，順序?yàn)椴迦腠樞蚧蛘咦罱钌偈褂茫↙RU）順序。
comparable和comparator的區(qū)別钓辆？
- comparable接口實(shí)際上是出自java.lang包剪验，它有一個(gè) compareTo(Object obj)方法用來排序；comparable是一種內(nèi)部自然排序前联，只能有一種定義功戚。接口里只定義了這一個(gè)方法,代表了:傳入一個(gè)對象,將對象和元素自身進(jìn)行比較,如果元素自身大,返回1,相等返回0,元素自身小于參數(shù)則返回-1.
private static class Student implements Comparable {
int id;
String name;
int age;
@Override
public int compareTo(Object o) {
return this.id - ((Student) o).id;
}
}
- comparator接口實(shí)際上是出自 java.util 包，它有一個(gè)compare(Object obj1, Object obj2)方法用來排序似嗤；comparator是一種外部比較器啸臀，可以定義多個(gè)不同的比較器，按需取用烁落。功能是對傳入的兩個(gè)元素進(jìn)行大小的比較,并且返回結(jié)果乘粒。
private static class StudentCom1 implements Comparator<Student>{
@Override
public int compare(Student o1, Student o2) {
return o1.id - o2.id;
}
}
那么問題來了,都有Comparable了,還要Comparator干什么?
設(shè)想一個(gè)場景,我們定義了一個(gè)學(xué)生類,如上面代碼所示,那么學(xué)生可以按著id的大小進(jìn)行排序.
然后現(xiàn)在有兩個(gè)使用的地方,第一個(gè)是考試,需要學(xué)生按照id排序.第二個(gè)是學(xué)生統(tǒng)計(jì),需要學(xué)生按照年齡進(jìn)行排序.
怎么實(shí)現(xiàn)兩種完全不同的排序方式呢?或者更極端一點(diǎn),一會需要按照id增序,一會需要按照id降序呢?改源代碼肯定是不科學(xué)的.
這個(gè)時(shí)候就可以采用以下方案:
- 學(xué)生實(shí)現(xiàn)自然排序,即最通用的那種排序方式,比如按照id增序，在需要默認(rèn)排序的情況下,直接調(diào)用學(xué)生的
comparTo即可. - 實(shí)現(xiàn)幾個(gè)不同的比較器,比如
運(yùn)動會比較器,吃飯比較器等等伤塌，在特定情景下,調(diào)用集合類的排序方法,傳入一個(gè)想要的比較器即可.
總結(jié)：一般我們需要對一個(gè)集合使用自定義排序時(shí)灯萍，我們就要重寫compareTo方法或compare方法，當(dāng)我們需要對某一個(gè)集合實(shí)現(xiàn)兩種排序方式每聪，比如一個(gè)song對象中的歌名和歌手名分別采用一種排序方法的話旦棉，我們可以重寫compareTo方法和使用自制的Comparator方法或者以兩個(gè)Comparator來實(shí)現(xiàn)歌名排序和歌星名排序齿风，第二種代表我們只能使用兩個(gè)參數(shù)版的Collections.sort()。
TreeMap和TreeSet在排序時(shí)如何比較元素绑洛？Collections 工具類中的sort()方法如何比較元素救斑？
- TreeSet 要求存放的對象所屬的類必須實(shí)現(xiàn) Comparable 接口（說明該類是可被排序的），該接口提供了比較元素的 compareTo()方法诊笤，當(dāng)插入元素時(shí)會回調(diào)該方法比較元素的大小系谐。
- TreeMap 要求存放的鍵值對映射的鍵必須實(shí)現(xiàn) Comparable 接口從而根據(jù)鍵對元素進(jìn)行排序。
Collections 工具類的 sort 方法有兩種重載的形式：
- 第一種要求傳入的待排序容器中存放的對象要實(shí)現(xiàn) Comparable 接口以實(shí)現(xiàn)元素的比較讨跟；
- 第二種不強(qiáng)制性的要求容器中的元素必須可比較纪他，但是要求傳入第二個(gè)參數(shù)，參數(shù)是Comparator 接口的子類型（需要重寫 compare 方法實(shí)現(xiàn)元素的比較）晾匠，相當(dāng)于一個(gè)臨時(shí)定義的排序規(guī)則茶袒，其實(shí)就是通過接口注入比較元素大小的算法，也是對回調(diào)模式的應(yīng)用（Java 中對函數(shù)式編程的支持）凉馆。
有沒有有順序的Map實(shí)現(xiàn)類薪寓，如果有，他們是怎么實(shí)現(xiàn)有序的澜共？
- Hashmap和Hashtable 都不是有序的向叉。
- TreeMap和LinkedHashmap都是有序的。（TreeMap默認(rèn)是key升序嗦董，LinkedHashmap默認(rèn)是數(shù)據(jù)插入順序）
TreeMap是基于比較器Comparator來實(shí)現(xiàn)有序的母谎。LinkedHashmap是基于鏈表來實(shí)現(xiàn)數(shù)據(jù)插入有序的。
我們應(yīng)該如何選用集合?
- 主要根據(jù)集合的特點(diǎn)來選用京革，比如我們需要根據(jù)鍵值獲取到元素值時(shí)就選?Map接口下的集合奇唤，需要排序時(shí)選擇TreeMap/LinkedHashmap,不需要排序時(shí)就選擇HashMap,需要保證線程安全就選?ConcurrentHashMap.
- 當(dāng)我們只需要存放元素值時(shí)，就選擇實(shí)現(xiàn)Collection接口集合匹摇，需要保證元素唯?時(shí)選擇實(shí)現(xiàn)Set接口的集合咬扇，?如TreeSet或HashSet，不需要就選擇實(shí)現(xiàn)List接口的比如ArrayList或LinkedList廊勃，然后再根據(jù)實(shí)現(xiàn)這些接?的集合的特點(diǎn)來選?懈贺。
綜上所述，選用集合供搀，首先是我們具體的使用場景：只是存值隅居，還是建立一種映射，便于查詢葛虐。其次胎源，考慮集合的元素有序性、元素的唯一性和線程安全性等問題屿脐。
拓展
（1）Collections.sort和Arrays.sort的實(shí)現(xiàn)原理
Collections.sort方法底層就是調(diào)用的Array.sort方法（中間調(diào)用了list.sort涕蚤，然后list.sort調(diào)用了Array.sort方法）
因此宪卿，Arrays的sort方法底層就是：
- legacyMergeSort(a)，歸并排序万栅，
- ComparableTimSort.sort()：即Timsort排序佑钾。Timsort排序是結(jié)合了合并排序（merge.sort）和插入排序（insertion sort）而得出的排序方法；ps：當(dāng)數(shù)組長度小于某個(gè)值烦粒，采用的是二分插入排序算法休溶，插入然后合并。
（2）poll()方法和 remove()方法的區(qū)別扰她？
Queue隊(duì)列中兽掰，poll() 和 remove() 都是從隊(duì)列中取出一個(gè)元素，在隊(duì)列元素為空的情況下：
- remove() 方法會拋出異常徒役，
- poll() 方法只會返回 null 孽尽。
（3）HashMap，HashTable忧勿，ConcurrentHash的共同點(diǎn)和區(qū)別
- 底層都是數(shù)組+鏈表+紅黑樹
- HashMap可以存儲null鍵和null值杉女，另外兩個(gè)不能存儲null鍵值
- 。鸳吸。熏挎。
HashMap,LinkedHashMap,TreeMap的區(qū)別
- Map主要用于存儲健值對，根據(jù)鍵得到值晌砾，因此不允許鍵重復(fù)(重復(fù)了覆蓋了),但允許值重復(fù)婆瓜。Hashmap 是一個(gè)最常用的Map,它根據(jù)鍵的HashCode 值存儲數(shù)據(jù),根據(jù)鍵可以直接獲取它的值，具有很快的訪問速度贡羔，遍歷時(shí)，取得數(shù)據(jù)的順序是完全隨機(jī)的个初。HashMap最多只允許一條記錄的鍵為Null;允許多條記錄的值為 Null;HashMap不支持線程的同步乖寒，即任一時(shí)刻可以有多個(gè)線程同時(shí)寫HashMap;可能會導(dǎo)致數(shù)據(jù)的不一致。如果需要同步院溺，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力楣嘁，或者使用ConcurrentHashMap。
- Hashtable與 HashMap類似,它繼承自Dictionary類珍逸，不同的是:它不允許記錄的鍵或者值為空;它支持線程的同步逐虚，即任一時(shí)刻只有一個(gè)線程能寫Hashtable,因此也導(dǎo)致了 Hashtable在寫入時(shí)會比較慢。
- LinkedHashMap保存了記錄的插入順序谆膳，在用Iterator遍歷LinkedHashMap時(shí)叭爱，先得到的記錄肯定是先插入的.也可以在構(gòu)造時(shí)用帶參數(shù)，按照應(yīng)用次數(shù)排序漱病。在遍歷的時(shí)候會比HashMap慢买雾，不過有種情況例外把曼，當(dāng)HashMap容量很大，實(shí)際數(shù)據(jù)較少時(shí)漓穿，遍歷起來可能會比LinkedHashMap慢嗤军，因?yàn)長inkedHashMap的遍歷速度只和實(shí)際數(shù)據(jù)有關(guān)，和容量無關(guān)晃危，而HashMap的遍歷速度和他的容量有關(guān)叙赚。
- TreeMap實(shí)現(xiàn)SortMap接口，能夠把它保存的記錄根據(jù)鍵排序,默認(rèn)是按鍵值的升序排序僚饭，也可以指定排序的比較器震叮，當(dāng)用Iterator 遍歷TreeMap時(shí)，得到的記錄是排過序的浪慌。
使用場景：
- 一般情況下冤荆，我們用的最多的是HashMap,HashMap里面存入的鍵值對在取出的時(shí)候是隨機(jī)的,它根據(jù)鍵的HashCode值存儲數(shù)據(jù),根據(jù)鍵可以直接獲取它的值，具有很快的訪問速度权纤。在Map 中插入钓简、刪除和定位元素，HashMap 是最好的選擇汹想。
- TreeMap取出來的是排序后的鍵值對外邓。但如果您要按自然順序或自定義順序遍歷鍵，那么TreeMap會更好古掏。
- LinkedHashMap 是HashMap的一個(gè)子類损话，如果需要輸出的順序和輸入的相同,那么用LinkedHashMap可以實(shí)現(xiàn),它還可以按讀取順序來排列，像連接池中可以應(yīng)用槽唾。
總結(jié)：
- HashSet是通過HashMap實(shí)現(xiàn)的,TreeSet是通過TreeMap實(shí)現(xiàn)的,只不過Set用的只是Map的key
- Map的key和Set都有一個(gè)共同的特性就是集合的唯一性.TreeMap更是多了一個(gè)排序的功能.
- hashCode和equals()是HashMap用的, 因?yàn)闊o需排序所以只需要關(guān)注定位和唯一性即可.
a. hashCode是用來計(jì)算hash值的,hash值是用來確定hash表索引的.
b. hash表中的一個(gè)索引處存放的是一張鏈表, 所以還要通過equal方法循環(huán)比較鏈上的每一個(gè)對象才可以真正定位到鍵值對應(yīng)的Entry.
c. put時(shí),如果hash表中沒定位到,就在鏈表前加一個(gè)Entry,如果定位到了,則更換Entry中的value,并返回舊value - 由于TreeMap需要排序,所以需要一個(gè)Comparator為鍵值進(jìn)行大小比較.當(dāng)然也是用Comparator定位的.
a. Comparator可以在創(chuàng)建TreeMap時(shí)指定
b. 如果創(chuàng)建時(shí)沒有確定,那么就會使用key.compareTo()方法,這就要求key必須實(shí)現(xiàn)Comparable接口.
c. TreeMap是使用Tree數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的,所以使用compare接口就可以完成定位了.
巨人的肩膀：
