Java面試題：Java中的集合及其繼承關(guān)系

關(guān)于集合的體系是每個(gè)人都應(yīng)該爛熟于心的,尤其是對(duì)我們經(jīng)常使用的List,Map的原理更該如此.這里我們看這張圖即可:

1、List、Set、Map是否繼承自Collection接口？

List、Set 是，Map 不是。Map是鍵值對(duì)映射容器，與List和Set有明顯的區(qū)別，而Set存儲(chǔ)的零散的元素且不允許有重復(fù)元素（數(shù)學(xué)中的集合也是如此），List是線性結(jié)構(gòu)的容器，適用于按數(shù)值索引訪問元素的情形。

2、闡述ArrayList、Vector、LinkedList的存儲(chǔ)性能和特性。

ArrayList 和Vector都是使用數(shù)組方式存儲(chǔ)數(shù)據(jù)，此數(shù)組元素?cái)?shù)大于實(shí)際存儲(chǔ)的數(shù)據(jù)以便增加和插入元素，它們都允許直接按序號(hào)索引元素，但是插入元素要涉及數(shù)組元素移動(dòng)等內(nèi)存操作，所以索引數(shù)據(jù)快而插入數(shù)據(jù)慢。Vector中的方法由于添加了synchronized修飾，因此Vector是線程安全的容器，但性能上較ArrayList差，因此已經(jīng)是Java中的遺留容器。

LinkedList使用雙向鏈表實(shí)現(xiàn)存儲(chǔ)（將內(nèi)存中零散的內(nèi)存單元通過附加的引用關(guān)聯(lián)起來，形成一個(gè)可以按序號(hào)索引的線性結(jié)構(gòu)，這種鏈?zhǔn)酱鎯?chǔ)方式與數(shù)組的連續(xù)存儲(chǔ)方式相比，內(nèi)存的利用率更高），按序號(hào)索引數(shù)據(jù)需要進(jìn)行前向或后向遍歷，但是插入數(shù)據(jù)時(shí)只需要記錄本項(xiàng)的前后項(xiàng)即可，所以插入速度較快。

Vector屬于遺留容器（Java早期的版本中提供的容器，除此之外，Hashtable、Dictionary、BitSet、Stack、Properties都是遺留容器），已經(jīng)不推薦使用，但是由于ArrayList和LinkedListed都是非線程安全的，如果遇到多個(gè)線程操作同一個(gè)容器的場(chǎng)景，則可以通過工具類Collections中的synchronizedList方法將其轉(zhuǎn)換成線程安全的容器后再使用（這是對(duì)裝潢模式的應(yīng)用，將已有對(duì)象傳入另一個(gè)類的構(gòu)造器中創(chuàng)建新的對(duì)象來增強(qiáng)實(shí)現(xiàn)）。

3、Collection和Collections的區(qū)別？

Collection是一個(gè)接口，它是Set、List等容器的父接口；Collections是個(gè)一個(gè)工具類，提供了一系列的靜態(tài)方法來輔助容器操作，這些方法包括對(duì)容器的搜索、排序、線程安全化等等。

4、List、Map、Set三個(gè)接口存取元素時(shí)，各有什么特點(diǎn)？

List以特定索引來存取元素，可以有重復(fù)元素。

Set不能存放重復(fù)元素（用對(duì)象的equals()方法來區(qū)分元素是否重復(fù)）。

Map保存鍵值對(duì)（key-value pair）映射，映射關(guān)系可以是一對(duì)一或多對(duì)一。

Set和Map容器都有基于哈希存儲(chǔ)和排序樹的兩種實(shí)現(xiàn)版本，基于哈希存儲(chǔ)的版本理論存取時(shí)間復(fù)雜度為O(1)，而基于排序樹版本的實(shí)現(xiàn)在插入或刪除元素時(shí)會(huì)按照元素或元素的鍵（key）構(gòu)成排序樹從而達(dá)到排序和去重的效果。

5、List和Set區(qū)別

Set是最簡(jiǎn)單的一種集合。集合中的對(duì)象不按特定的方式排序，并且沒有重復(fù)對(duì)象。

• HashSet： HashSet類按照哈希算法來存取集合中的對(duì)象，存取速度比較快

• TreeSet ：TreeSet類實(shí)現(xiàn)了SortedSet接口，能夠?qū)现械膶?duì)象進(jìn)行排序。

List的特征是其元素以線性方式存儲(chǔ)，集合中可以存放重復(fù)對(duì)象。

• ArrayList() : 代表長(zhǎng)度可以改變得數(shù)組?？梢詫?duì)元素進(jìn)行隨機(jī)的訪問，向ArrayList()中插入與刪除元素的速度慢。

• LinkedList(): 在實(shí)現(xiàn)中采用鏈表數(shù)據(jù)結(jié)構(gòu)。插入和刪除速度快，訪問速度慢。

6、LinkedHashMap和PriorityQueue的區(qū)別

PriorityQueue 是一個(gè)優(yōu)先級(jí)隊(duì)列,保證最高或者最低優(yōu)先級(jí)的的元素總是在隊(duì)列頭部，但是 LinkedHashMap 維持的順序是元素插入的順序。當(dāng)遍歷一個(gè) PriorityQueue 時(shí)，沒有任何順序保證，但是 LinkedHashMap 課保證遍歷順序是元素插入的順序。

7、WeakHashMap與HashMap的區(qū)別是什么？

WeakHashMap 的工作與正常的 HashMap 類似，但是使用弱引用作為 key，意思就是當(dāng) key 對(duì)象沒有任何引用時(shí)，key/value 將會(huì)被回收。

8、ArrayList和LinkedList的區(qū)別？

最明顯的區(qū)別是 ArrrayList底層的數(shù)據(jù)結(jié)構(gòu)是數(shù)組，支持隨機(jī)訪問，而 LinkedList 的底層數(shù)據(jù)結(jié)構(gòu)是雙向循環(huán)鏈表，不支持隨機(jī)訪問。使用下標(biāo)訪問一個(gè)元素，ArrayList 的時(shí)間復(fù)雜度是 O(1)，而 LinkedList 是 O(n)。

相對(duì)于ArrayList，LinkedList的插入，添加，刪除操作速度更快，因?yàn)楫?dāng)元素被添加到集合任意位置的時(shí)候，不需要像數(shù)組那樣重新計(jì)算大小或者是更新索引。

LinkedList比ArrayList更占內(nèi)存，因?yàn)長(zhǎng)inkedList為每一個(gè)節(jié)點(diǎn)存儲(chǔ)了兩個(gè)引用，一個(gè)指向前一個(gè)元素，一個(gè)指向下一個(gè)元素。

9、ArrayList和Array有什么區(qū)別？

Array可以容納基本類型和對(duì)象，而ArrayList只能容納對(duì)象。

Array是指定大小的，而ArrayList大小是固定的

10、ArrayList與Vector區(qū)別

ArrayList和Vector在很多時(shí)候都很類似。

• 兩者都是基于索引的，內(nèi)部由一個(gè)數(shù)組支持。

• 兩者維護(hù)插入的順序，我們可以根據(jù)插入順序來獲取元素。

• ArrayList和Vector的迭代器實(shí)現(xiàn)都是fail-fast的。

• ArrayList和Vector兩者允許null值，也可以使用索引值對(duì)元素進(jìn)行隨機(jī)訪問。

以下是ArrayList和Vector的不同點(diǎn)。

• Vector是同步的，而ArrayList不是。然而，如果你尋求在迭代的時(shí)候?qū)α斜磉M(jìn)行改變，你應(yīng)該使用CopyOnWriteArrayList。

• ArrayList比Vector快，它因?yàn)橛型?，不?huì)過載。

• ArrayList更加通用，因?yàn)槲覀兛梢允褂肅ollections工具類輕易地獲取同步列表和只讀列表。

11、HashMap和Hashtable的區(qū)別

HashMap和Hashtable都實(shí)現(xiàn)了Map接口，因此很多特性非常相似。但是，他們有以下不同點(diǎn)：

• HashMap允許鍵和值是null，而Hashtable不允許鍵或者值是null。

• Hashtable是同步的，而HashMap不是。因此，HashMap更適合于單線程環(huán)境，而Hashtable適合于多線程環(huán)境。

• HashMap提供了可供應(yīng)用迭代的鍵的集合，因此，HashMap是快速失敗的。另一方面，Hashtable提供了對(duì)鍵的列舉(Enumeration)。

• 一般認(rèn)為Hashtable是一個(gè)遺留的類。

12、HashSet和HashMap區(qū)別

• HashSet實(shí)現(xiàn)了Set接口，它不允許集合中有重復(fù)的值。它存儲(chǔ)的是對(duì)象

• HashMap實(shí)現(xiàn)了Map接口，Map接口對(duì)鍵值對(duì)進(jìn)行映射。Map中不允許重復(fù)的鍵。Map接口有兩個(gè)基本的實(shí)現(xiàn)，HashMap和TreeMap。

13、HashMap和ConcurrentHashMap的區(qū)別

• ConcurrentHashMap對(duì)整個(gè)桶數(shù)組進(jìn)行了分段，而HashMap則沒有。

• ConcurrentHashMap在每一個(gè)分段上都用鎖進(jìn)行保護(hù)，從而讓鎖的粒度更精細(xì)一些，并發(fā)性能更好，而HashMap沒有鎖機(jī)制，不是線程安全的。

引入ConcurrentHashMap是為了在同步集合HashTable之間有更好的選擇，HashTable與HashMap、ConcurrentHashMap主要的區(qū)別在于HashMap不是同步的、線程不安全的和不適合應(yīng)用于多線程并發(fā)環(huán)境下，而ConcurrentHashMap是線程安全的集合容器，特別是在多線程和并發(fā)環(huán)境中，通常作為Map的主要實(shí)現(xiàn)。

14、Comparator和Comparable的區(qū)別？

Comparable 接口用于定義對(duì)象的自然順序，而 comparator 通常用于定義用戶定制的順序。Comparable 總是只有一個(gè)，但是可以有多個(gè) comparator 來定義對(duì)象的順序。

15、poll()方法和remove()方法區(qū)別？

poll() 和 remove() 都是從隊(duì)列中取出一個(gè)元素，但是 poll() 在獲取元素失敗的時(shí)候會(huì)返回空，但是 remove() 失敗的時(shí)候會(huì)拋出異常。

16、ArrayList、HashMa和LinkedList的默認(rèn)空間是多少？擴(kuò)容機(jī)制是什么

• ArrayList 的默認(rèn)大小是 10 個(gè)元素。擴(kuò)容點(diǎn)規(guī)則是，新增的時(shí)候發(fā)現(xiàn)容量不夠用了，就去擴(kuò)容；擴(kuò)容大小規(guī)則是：擴(kuò)容后的大小= 原始大小+原始大小/2 + 1。

• HashMap 的默認(rèn)大小是16個(gè)元素（必須是2的冪）。擴(kuò)容因子默認(rèn)0.75，擴(kuò)容機(jī)制.(當(dāng)前大小 和 當(dāng)前容量 的比例超過了 擴(kuò)容因子，就會(huì)擴(kuò)容，擴(kuò)容后大小為 一倍。例如：初始大小為 16 ，擴(kuò)容因子 0.75 ，當(dāng)容量為12的時(shí)候，比例已經(jīng)是0.75 。觸發(fā)擴(kuò)容，擴(kuò)容后的大小為 32.)

• LinkedList 是一個(gè)雙向鏈表，沒有初始化大小，也沒有擴(kuò)容的機(jī)制，就是一直在前面或者后面新增就好。

private?static?final?int?DEFAULT_CAPACITY?=?10;

//from?HashMap.java?JDK?7
static?final?int?DEFAULT_INITIAL_CAPACITY?=?1?<<?4;?//?aka?16

17、如何實(shí)現(xiàn)集合排序？

你可以使用有序集合，如 TreeSet 或 TreeMap，你也可以使用有順序的的集合，如 list，然后通過 Collections.sort() 來排序。

18、如何打印數(shù)組內(nèi)容

你可以使用 Arrays.toString() 和 Arrays.deepToString() 方法來打印數(shù)組。由于數(shù)組沒有實(shí)現(xiàn) toString() 方法，所以如果將數(shù)組傳遞給 System.out.println() 方法，將無法打印出數(shù)組的內(nèi)容，但是 Arrays.toString() 可以打印每個(gè)元素。

19、LinkedList的是單向鏈表還是雙向？

雙向循環(huán)列表,具體實(shí)現(xiàn)自行查閱源碼.

20、TreeMap是實(shí)現(xiàn)原理

采用紅黑樹實(shí)現(xiàn),具體實(shí)現(xiàn)自行查閱源碼.

21、遍歷ArrayList時(shí)如何正確移除一個(gè)元素

該問題的關(guān)鍵在于面試者使用的是 ArrayList 的 remove() 還是 Iterator 的 remove()方法。這有一段示例代碼，是使用正確的方式來實(shí)現(xiàn)在遍歷的過程中移除元素，而不會(huì)出現(xiàn) ConcurrentModificationException 異常的示例代碼。

22、什么是ArrayMap？它和HashMap有什么區(qū)別？

ArrayMap是Android SDK中提供的,非Android開發(fā)者可以略過。

ArrayMap是用兩個(gè)數(shù)組來模擬map,更少的內(nèi)存占用空間,更高的效率。

具體參考這篇文章:ArrayMap VS HashMap：http://lvable.com/?p=217%5D

23、如何決定選用HashMap還是TreeMap？

對(duì)于在Map中插入、刪除和定位元素這類操作，HashMap是最好的選擇。然而，假如你需要對(duì)一個(gè)有序的key集合進(jìn)行遍歷，TreeMap是更好的選擇。基于你的collection的大小，也許向HashMap中添加元素會(huì)更快，將map換為TreeMap進(jìn)行有序key的遍歷。

24、HashMap的實(shí)現(xiàn)原理

1. HashMap概述： HashMap是基于哈希表的Map接口的非同步實(shí)現(xiàn)。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。

2. HashMap的數(shù)據(jù)結(jié)構(gòu)： 在java編程語言中，最基本的結(jié)構(gòu)就是兩種，一個(gè)是數(shù)組，另外一個(gè)是模擬指針（引用），所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個(gè)基本結(jié)構(gòu)來構(gòu)造的，HashMap也不例外。HashMap實(shí)際上是一個(gè)“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體。

當(dāng)我們往Hashmap中put元素時(shí),首先根據(jù)key的hashcode重新計(jì)算hash值,根絕hash值得到這個(gè)元素在數(shù)組中的位置(下標(biāo)),如果該數(shù)組在該位置上已經(jīng)存放了其他元素,那么在這個(gè)位置上的元素將以鏈表的形式存放,新加入的放在鏈頭,最先加入的放入鏈尾.如果數(shù)組中該位置沒有元素,就直接將該元素放到數(shù)組的該位置上.

需要注意Jdk 1.8中對(duì)HashMap的實(shí)現(xiàn)做了優(yōu)化,當(dāng)鏈表中的節(jié)點(diǎn)數(shù)據(jù)超過八個(gè)之后,該鏈表會(huì)轉(zhuǎn)為紅黑樹來提高查詢效率,從原來的O(n)到O(logn)

25、ConcurrentHashMap 的工作原理及代碼實(shí)現(xiàn)

ConcurrentHashMap具體是怎么實(shí)現(xiàn)線程安全的呢，肯定不可能是每個(gè)方法加synchronized，那樣就變成了HashTable。

從ConcurrentHashMap代碼中可以看出，它引入了一個(gè)“分段鎖”的概念，具體可以理解為把一個(gè)大的Map拆分成N個(gè)小的HashTable，根據(jù)key.hashCode()來決定把key放到哪個(gè)HashTable中。

在ConcurrentHashMap中，就是把Map分成了N個(gè)Segment，put和get的時(shí)候，都是現(xiàn)根據(jù)key.hashCode()算出放到哪個(gè)Segment中。

26、Fail-fast和Fail-safe有什么區(qū)別

Iterator的fail-fast屬性與當(dāng)前的集合共同起作用，因此它不會(huì)受到集合中任何改動(dòng)的影響。Java.util包中的所有集合類都被設(shè)計(jì)為fail->fast的，而java.util.concurrent中的集合類都為fail-safe的。當(dāng)檢測(cè)到正在遍歷的集合的結(jié)構(gòu)被改變時(shí)，F(xiàn)ail-fast迭代器拋出ConcurrentModificationException，而fail-safe迭代器從不拋出ConcurrentModificationException。

27、說出幾點(diǎn) Java 中使用 Collections 的最佳實(shí)踐

這是我在使用 Java 中 Collectionc 類的一些最佳實(shí)踐：

• 使用正確的集合類，例如，如果不需要同步列表，使用 ArrayList 而不是 Vector。

• 優(yōu)先使用并發(fā)集合，而不是對(duì)集合進(jìn)行同步。并發(fā)集合提供更好的可擴(kuò)展性。

• 使用接口代表和訪問集合，如使用List存儲(chǔ) ArrayList，使用 Map 存儲(chǔ) HashMap 等等。

• 使用迭代器來循環(huán)集合。

• 使用集合的時(shí)候使用泛型。

28、BlockingQueue是什么？

Java.util.concurrent.BlockingQueue是一個(gè)隊(duì)列，在進(jìn)行檢索或移除一個(gè)元素的時(shí)候，它會(huì)等待隊(duì)列變?yōu)榉强眨划?dāng)在添加一個(gè)元素時(shí)，它會(huì)等待隊(duì)列中的可用空間。BlockingQueue接口是Java集合框架的一部分，主要用于實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者模式。我們不需要擔(dān)心等待生產(chǎn)者有可用的空間，或消費(fèi)者有可用的對(duì)象，因?yàn)樗荚贐lockingQueue的實(shí)現(xiàn)類中被處理了。Java提供了集中BlockingQueue的實(shí)現(xiàn)，比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue

29、隊(duì)列和棧是什么，列出它們的區(qū)別？

棧和隊(duì)列兩者都被用來預(yù)存儲(chǔ)數(shù)據(jù)。java.util.Queue是一個(gè)接口，它的實(shí)現(xiàn)類在Java并發(fā)包中。隊(duì)列允許先進(jìn)先出（FIFO）檢索元素，但并非總是這樣。Deque接口允許從兩端檢索元素。

棧與隊(duì)列很相似，但它允許對(duì)元素進(jìn)行后進(jìn)先出（LIFO）進(jìn)行檢索。

Stack是一個(gè)擴(kuò)展自Vector的類，而Queue是一個(gè)接口。