本文介紹一些和List、Set、Map面試常問(wèn)問(wèn)題驻民。
在 Java 中除了以 Map 結(jié)尾的類之外绽左， 其他類都實(shí)現(xiàn)了 Collection 接口悼嫉。并且以 Map 結(jié)尾的類都實(shí)現(xiàn)了 Map 接口。
注意：文中提到的線程安全拼窥，并發(fā)承粤，Sychronized等知識(shí)點(diǎn)，如果不太清楚闯团，作者會(huì)在后面的Java并發(fā)面試題中會(huì)有所整理和解釋辛臊。
問(wèn)題1：List和Set和Map的區(qū)別？
- List可以有重復(fù)的對(duì)象房交，Set不可以有重復(fù)的對(duì)象彻舰；
- List元素是有序的，Set沒(méi)法保證有序候味；
- List可以插入多個(gè)null值刃唤，Set只能插入一個(gè)；
- Map,key-value的鍵值對(duì)白群，entry對(duì)象形式尚胞，key是無(wú)序，不可重復(fù)的帜慢；value是無(wú)序笼裳，可重復(fù)的唯卖；
問(wèn)題2：List和Set和Map的實(shí)現(xiàn)方式分別由哪些？
-
List的實(shí)現(xiàn)方式：數(shù)據(jù)結(jié)構(gòu)
1）ArrayList ： Object[]數(shù)組
2）Vector： Object[]數(shù)組
3）LinkedList： 雙向鏈表 -
Set的實(shí)現(xiàn)方式：數(shù)據(jù)結(jié)構(gòu)
1）HashSet（無(wú)序躬柬，唯一）: 基于 HashMap 實(shí)現(xiàn)的拜轨，底層采用 HashMap 來(lái)保存元素
2）LinkedHashSet：LinkedHashSet 是 HashSet 的子類，并且其內(nèi)部是通過(guò) LinkedHashMap 來(lái)實(shí)現(xiàn)的允青。
3）TreeSet（有序橄碾，唯一）： 紅黑樹(shù)(自平衡的排序二叉樹(shù)) -
Map的實(shí)現(xiàn)方式：數(shù)據(jù)結(jié)構(gòu)
1）HashMap： JDK1.8 之前 HashMap 由數(shù)組+鏈表組成的。JDK1.8 以后颠锉，將鏈表轉(zhuǎn)化為紅黑樹(shù)
2）LinkedHashMap： LinkedHashMap 繼承自 HashMap法牲，所以它的底層仍然是基于拉鏈?zhǔn)缴⒘薪Y(jié)構(gòu)即由數(shù)組和鏈表或紅黑樹(shù)組成
3）Hashtable： 數(shù)組+鏈表組成的
4）TreeMap： 紅黑樹(shù)
問(wèn)題3：ArrayList 和 Vector 和 LinkedList 的區(qū)別？
- 線程安全： ArrayList 和 LinkedList 都是不同步的琼掠，也就是不保證線程安全拒垃；Vector是線程安全的；
- 底層數(shù)據(jù)結(jié)構(gòu)： Arraylist 和Vector 底層使用的是 Object 數(shù)組眉枕；LinkedList 底層使用的是 雙向鏈表恶复；
- 插入和刪除： ArrayList 采用數(shù)組存儲(chǔ)，所以插入和刪除元素的時(shí)間復(fù)雜度受元素位置的影響速挑；LinkedList 采用鏈表存儲(chǔ)谤牡，所以對(duì)于add(E e)方法的插入，刪除元素時(shí)間復(fù)雜度不受元素位置的影響姥宝；
- 支持快速隨機(jī)訪問(wèn)： LinkedList 不支持高效的隨機(jī)元素訪問(wèn)翅萤，而 ArrayList 支持。
- 內(nèi)存空間： LinkedList 比ArrayList的空間花費(fèi)更多的空間（因?yàn)橐娣胖苯雍罄^和直接前驅(qū)以及數(shù)據(jù)）腊满。
問(wèn)題4：HashSet 和 LinkedHashSet 和 TreeSet 的區(qū)別套么？
- HashSet 是 Set 接口的主要實(shí)現(xiàn)類 ，HashSet 的底層是 HashMap碳蛋，線程不安全的胚泌，可以存儲(chǔ) null 值；
- LinkedHashSet 是 HashSet 的子類肃弟，能夠按照添加的順序遍歷玷室；
- TreeSet 底層使用紅黑樹(shù)，能夠按照添加元素的順序進(jìn)行遍歷笤受，排序的方式有自然排序和定制排序穷缤。
問(wèn)題5：HashMap 和 HashTable 的區(qū)別？
- 線程安全： HashMap 是非線程安全的箩兽，HashTable 是線程安全的津肛。因?yàn)?HashTable 內(nèi)部的方法基本都經(jīng)過(guò)synchronized 修飾。
- 效率： 因?yàn)榫€程安全的問(wèn)題汗贫，HashMap 要比 HashTable 效率高身坐。另外秸脱，HashTable 基本被淘汰，不要在代碼中使用它掀亥；
- key / value 為 null ： HashMap 可以存儲(chǔ) null 的 key 和 value撞反，但 null 作為鍵只能有一個(gè)妥色，null 作為值可以有多個(gè)搪花；HashTable 不允許有 null 鍵和 null 值，否則會(huì)拋出 NullPointerException嘹害。
- 初始容量和擴(kuò)容：1）創(chuàng)建時(shí)如果不指定容量初始值撮竿，Hashtable 默認(rèn)的初始大小為 11，之后每次擴(kuò)充笔呀，容量變?yōu)樵瓉?lái)的 2n+1幢踏。HashMap 默認(rèn)的初始化大小為 16。之后每次擴(kuò)充许师，容量變?yōu)樵瓉?lái)的 2 倍房蝉。2）創(chuàng)建時(shí)如果給定了容量初始值，那么 Hashtable 會(huì)直接使用你給定的大小微渠，而 HashMap 會(huì)將其擴(kuò)充為 2 的冪次方大小搭幻。
- 底層數(shù)據(jù)結(jié)構(gòu)： JDK1.8 以后的 HashMap 在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為 8）時(shí)逞盆，將鏈表轉(zhuǎn)化為紅黑樹(shù)檀蹋，以減少搜索時(shí)間。
從以上幾個(gè)問(wèn)題可以總結(jié)出云芦，當(dāng)問(wèn)到這些集合之間的區(qū)別的時(shí)候俯逾，一般要答這幾點(diǎn)：線程安全、底層數(shù)據(jù)結(jié)構(gòu)舅逸、有序無(wú)序桌肴、可否存null值、效率等琉历。
問(wèn)題6：如何選擇該使用哪些集合坠七？
- 當(dāng)要保存一組同類型數(shù)據(jù)時(shí)，首先想到的容器可能就時(shí)數(shù)組善已，但用數(shù)組存儲(chǔ)對(duì)象存在弊端灼捂， 因?yàn)槲覀冊(cè)趯?shí)際開(kāi)發(fā)中，存儲(chǔ)的數(shù)據(jù)的類型是多種多樣的换团，“集合”的出現(xiàn)就使得數(shù)據(jù)存儲(chǔ)更加靈活悉稠，集合同樣也是用來(lái)存儲(chǔ)多個(gè)數(shù)據(jù)的。
- 數(shù)組的缺點(diǎn)是聲明時(shí)要初始化大兴野的猛；聲明數(shù)組時(shí)的數(shù)據(jù)類型也決定了該數(shù)組存儲(chǔ)的數(shù)據(jù)的類型耀盗；而且，數(shù)組存儲(chǔ)的數(shù)據(jù)是有序的卦尊、可重復(fù)的叛拷，特點(diǎn)單一。 集合靈活性更高岂却，Java 中集合可用來(lái)存儲(chǔ)不同類型不同數(shù)量的對(duì)象忿薇，也可保存具有映射關(guān)系的數(shù)據(jù)。
1）根據(jù)集合的特點(diǎn)來(lái)選躏哩，如我們需要根據(jù)鍵值獲取到元素值時(shí)就選用 Map 接口下的集合署浩，需要排序時(shí)選擇 TreeMap,不需要排序時(shí)就選擇HashMap,需要保證線程安全就選用 ConcurrentHashMap。
2）只需要存放元素值時(shí)扫尺，就選擇實(shí)現(xiàn)Collection 接口的集合筋栋，需要保證元素唯一時(shí)選擇實(shí)現(xiàn) Set 接口的集合比如 TreeSet 或 HashSet，不需要就選擇實(shí)現(xiàn) List 接口的比如 ArrayList 或 LinkedList正驻，然后再根據(jù)實(shí)現(xiàn)這些接口的集合的特點(diǎn)來(lái)選用弊攘。
