2、容器——Java 面試題答案

容器

18. java 容器都有哪些？

常用容器的圖錄：

18. java 容器都有哪些？

常用容器的圖錄：

19. Collection 和 Collections 有什麼差別？

• java.util.Collection 是一個集合接口（集合類的一個頂級接口）。它提供了對集合對象進行基本操作的通用接口方法。Collection接口在Java 類庫中有很多具體的實作。Collection接口的意義是為各種具體的集合提供了最大化的統一操作方式，其直接繼承接口有List與Set。
• Collections則是集合類的一個工具類/幫助類，其中提供了一系列靜态方法，用于對集合中元素進行排序、搜尋以及線程安全等各種操作。稍微舉個例子：

public static void main(String args[]) {   
       //注意List是實作Collection接口的   
       List list = new ArrayList();   
       double array[] = { 112, 111, 23, 456, 231 };   
       for (int i = 0; i < array.length; i++) {   
           list.add(new Double(array[i]));   
       }   
       Collections.sort(list);   //把list按從小到大排序
       for (int i = 0; i < array.length; i++) {   
           System.out.println(list.get(i));   
       }   
       // 結果：23.0 111.0 112.0 231.0 456.0   
 }   
           

然後Collections還有混排（Shuffling）、反轉（Reverse）、替換所有的元素（fill）、拷貝（copy）、傳回Collections中最小元素（min）、傳回Collections中最大元素（max）、傳回指定源清單中最後一次出現指定目标清單的起始位置（lastIndexOfSubList）、傳回指定源清單中第一次出現指定目标清單的起始位置（IndexOfSubList）、根據指定的距離循環移動指定清單中的元素（Rotate）等方法。

20. List、Set、Map 之間的差別是什麼？

比較	List	Set	Map
繼承接口	Collection	Collection
常見實作類	AbstractList（其常見子類有ArrayList、LinkedList、Vector）	AbstractSet（其常見子類有HashSet、LinkedHashSet、TreeSet）	HashMap、HashTable
常見方法	add()、remove()、clear()、get()、contains()、size()	add()、remove()、clear()、get()、contains()、size()	put()、get()、remove()、clear()、containsKey()、containsValue()、keySet()、values()、size()
元素	可重複	不可重複（用equals()判斷）	不可重複
順序	有序	無序（實際上由HashCode決定）
線程安全	Vector安全	HashTable安全

21. HashMap 和 Hashtable 有什麼差別？

• HashMap去掉了HashTable 的contains方法，但是加上了containsValue（）和containsKey（）方法。
• HashTable是同步的，而HashMap是非同步的，效率上比HashTable要高。
• HashMap允許空鍵值，而HashTable不允許。

Hashtable	HashMap
方法是同步的	方法是非同步的
基于Dictionary類	基于AbstractMap，而AbstractMap基于Map接口的實作
key和value都不允許為null，遇到null，直接傳回 NullPointerException	key和value都允許為null，遇到key為null的時候，調用putForNullKey方法進行處理，而對value沒有處理
hash數組預設大小是11，擴充方式是old*2+1	hash數組的預設大小是16，而且一定是2的指數

更詳細的介紹可以參考部落格HashTable和HashMap的差別詳解

HashMap和TreeMap差別詳解以及底層實作

22. 如何決定使用 HashMap 還是 TreeMap？

TreeMap<K,V>的Key值是要求實作java.lang.Comparable，是以疊代的時候TreeMap預設是按照Key值升序排序的；TreeMap的實作也是基于紅黑樹結構。

而HashMap<K,V>的Key值實作散列hashCode(),分布是散列的均勻的，不支援排序；資料結構主要是桶(數組),連結清單或紅黑樹。

大多情況下HashMap有更好的性能，是以大多不需要排序的時候我們會使用HashMap。

23. 說一下 HashMap 的實作原理？

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

HashMap的資料結構： 在java程式設計語言中，最基本的結構就是兩種，一個是數組，另外一個是模拟指針（連結清單），所有的資料結構都可以用這兩個基本結構來構造的，HashMap也不例外。HashMap實際上是一個“連結清單散列”的資料結構，即數組和連結清單的結合體。

當我們往Hashmap中put元素時,首先根據key的hashcode重新計算hash值,根絕hash值得到這個元素在數組中的位置(下标),如果該數組在該位置上已經存放了其他元素,那麼在這個位置上的元素将以連結清單的形式存放,新加入的放在鍊頭,最先加入的放傳入連結尾.如果數組中該位置沒有元素,就直接将該元素放到數組的該位置上。

需要注意Jdk 1.8中對HashMap的實作做了優化,當連結清單中的節點資料超過八個之後,該連結清單會轉為紅黑樹來提高查詢效率,從原來的O(n)到O(logn)

24. 說一下 HashSet 的實作原理？

HashSet底層由HashMap實作

HashSet的值存放于HashMap的key上

HashMap的value統一為PRESENT

25. ArrayList 和 LinkedList 的差別是什麼？

最明顯的差別是 ArrrayList底層的資料結構是數組，支援随機通路，而 LinkedList 的底層資料結構是雙向循環連結清單，不支援随機通路。使用下标通路一個元素，ArrayList 的時間複雜度是 O(1)，而 LinkedList 是 O(n)。

26. 如何實作數組和 List 之間的轉換？

List轉換成為數組：調用ArrayList的toArray()方法。

數組轉換成為List：調用Arrays.asList()方法。

27. ArrayList 和 Vector 的差別是什麼？

參考這篇部落格arrayList和vector的差別

首先看這兩類都實作List接口，而List接口一共有三個實作類，分别是ArrayList、Vector和LinkedList。List用于存放多個元素，能夠維護元素的次序，并且允許元素的重複。3個具體實作類的相關差別如下：

• ArrayList是最常用的List實作類，内部是通過數組實作的，它允許對元素進行快速随機通路。數組的缺點是每個元素之間不能有間隔，當數組大小不滿足時需要增加存儲能力，就要講已經有數組的資料複制到新的存儲空間中。當從ArrayList的中間位置插入或者删除元素時，需要對數組進行複制、移動、代價比較高。是以，它适合随機查找和周遊，不适合插入和删除。
• Vector與ArrayList一樣，也是通過數組實作的，不同的是它支援線程的同步，即某一時刻隻有一個線程能夠寫Vector，避免多線程同時寫而引起的不一緻性，但實作同步需要很高的花費，是以，通路它比通路ArrayList慢。
• LinkedList是用連結清單結構存儲資料的，很适合資料的動态插入和删除，随機通路和周遊速度比較慢。另外，他還提供了List接口中沒有定義的方法，專門用于操作表頭和表尾元素，可以當作堆棧、隊列和雙向隊列使用。
• vector是線程（Thread）同步（Synchronized）的，是以它也是線程安全的，而Arraylist是線程異步（ASynchronized）的，是不安全的。如果不考慮到線程的安全因素，一般用Arraylist效率比較高。
• 如果集合中的元素的數目大于目前集合數組的長度時，vector增長率為目前數組長度的100%,而arraylist增長率為目前數組長度的50%.如過在集合中使用資料量比較大的資料，用vector有一定的優勢。
• 如果查找一個指定位置的資料，vector和arraylist使用的時間是相同的，都是O(1),這個時候使用vector和arraylist都可以。而如果移動一個指定位置的資料花費的時間為O(n-i)n為總長度，這個時候就應該考慮到使用Linkedlist,因為它移動一個指定位置的資料所花費的時間為O(1),而查詢一個指定位置的資料時花費的時間為0(i)。

• ArrayList 和Vector是采用數組方式存儲資料，此數組元素數大于實際存儲的資料以便增加和插入元素，都允許直接序号索引元素，但是插入資料要設計到數組元素移動 等記憶體操作，是以索引資料快插入資料慢，Vector由于使用了synchronized方法（線程安全）是以性能上比ArrayList要差，LinkedList使用雙向連結清單實作存儲，按序号索引資料需要進行向前或向後周遊，但是插入資料時隻需要記錄本項的前後項即可，是以插入數度較快！

  籠統來說：LinkedList：增删改快； ArrayList：查詢快（有索引的存在）

28. Array 和 ArrayList 有何差別？

• Array可以容納基本類型和對象，而ArrayList隻能容納對象。
• Array是指定大小的，而ArrayList大小是固定的。 （在Java集合架構中的大部分類的大小是可以随着元素個數的增加而相應的增加的，我們一般不用關心它的初始大小,除非考慮性能問題時）
• Array沒有提供ArrayList那麼多功能，比如addAll()、removeAll()和iterator()等。

29. 在 Queue 中 poll()和 remove()有什麼差別？

poll()和 remove() 都是從隊列中取出一個元素，但是 poll() 在擷取元素失敗的時候會傳回空，但是 remove() 失敗的時候會抛出異常。

peek()隻取但不删除隊首元素。

30. 哪些集合類是線程安全的？

Vector：就比ArrayList多了個同步化機制（線程安全），因為效率較低，現在已經不太建議使用。在web應用中，特别是前台頁面，往往效率（頁面響應速度）是優先考慮的。

HashTable：就比HashTable多了個線程安全。

Statck：堆棧類，先進後出。

Enumeration：枚舉，相當于疊代器。

31. 疊代器 Iterator 是什麼？

疊代器是一種設計模式，它是一個對象，它可以周遊并選擇序列中的對象，而開發人員不需要了解該序列的底層結構。疊代器通常被稱為“輕量級”對象，因為建立它的代價小。

32. Iterator 怎麼使用？有什麼特點？

Java中的Iterator功能比較簡單，并且隻能單向移動：

(1) 使用方法iterator()要求容器傳回一個Iterator。第一次調用Iterator的next()方法時，它傳回序列的第一個元素。注意：iterator()方法是java.lang.Iterable接口,被Collection繼承。

(2) 使用next()獲得序列中的下一個元素。

(3) 使用hasNext()檢查序列中是否還有元素。

(4) 使用remove()将疊代器新傳回的元素删除。

Iterator是Java疊代器最簡單的實作，為List設計的ListIterator具有更多的功能，它可以從兩個方向周遊List，也可以從List中插入和删除元素。

33. Iterator 和 ListIterator 有什麼差別？

Iterator可用來周遊Set和List集合，但是ListIterator隻能用來周遊List。

Iterator對集合隻能是前向周遊，ListIterator既可以前向也可以後向。

ListIterator實作了Iterator接口，并包含其他的功能，比如：增加元素add()，替換元素set()，擷取前一個和後一個元素或索引next()/nextIndex()、previous()/previousIndex()，等等。

34.怎麼確定一個集合不能被修改

怎麼確定一個集合不能被修改

我們很容易想到用final關鍵字進行修飾，我們都知道：

final關鍵字可以修飾類，方法，成員變量，final修飾的類不能被繼承，final修飾的方法不能被重寫，final修飾的成員變量必須初始化值，如果這個成員變量是基本資料類型，表示這個變量的值是不可改變的，如果說這個成員變量是引用類型，則表示這個引用的位址值是不能改變的，但是這個引用所指向的對象裡面的内容還是可以改變的。

那麼，我們怎麼確定一個集合不能被修改？首先我們要清楚，集合（map,set,list…）都是引用類型，是以我們如果用final修飾的話，集合裡面的内容還是可以修改的。

我們可以做一個實驗：

可以看到：我們用final關鍵字定義了一個map集合，這時候我們往集合裡面傳值，第一個鍵值對1,1；我們再修改後，可以把鍵為1的值改為100，說明我們是可以修改map集合的值的。

那我們應該怎麼做才能確定集合不被修改呢？

我們可以采用Collections包下的unmodifiableMap方法，通過這個方法傳回的map,是不可以修改的。他會報java.lang.UnsupportedOperationException錯。

同理：Collections包也提供了對list和set集合的方法：

Collections.unmodifiableList(List)

Collections.unmodifiableSet(Set)

35.如何擷取Map中的所有元素

原理：Map沒有疊代器，Collection具備疊代器，隻要将Map轉成Set集合，就可使用疊代器。之是以轉成Set，是因為Map集合具備鍵的唯一性，其實Set集合就來自于Map，Set集合底層其實用的就是Map的方法。

把Map集合轉成Set的方法：(決定了兩種周遊方式)

• Set keySet();

• Set entrySet();//取的是鍵和值的映射關系。 Entry就是Map接口中的内部接口；

  為什麼要定義在Map内部呢？Entry是通路鍵值關系的入口，是Map的入口，通路的是Map中的鍵值對。

  取出map集合中所有元素的方式一：keySet()方法。

可以将map集合中的鍵都取出存放到set集合中。對set集合進行疊代。疊代完成，再通過get方法對擷取到的鍵進行值的擷取。

Set keySet = map.keySet();
Iterator it = keySet.iterator();
while(it.hasNext()) {
	Object key = it.next();
	Objectvalue = map.get(key);
	System.out.println(key+":"+value);  
}   
           

取出map集合中所有元素的方式二：entrySet()方法。

Set entrySet = map.entrySet();
Iterator it =entrySet.iterator();
while(it.hasNext()) {
    Map.Entry  me =(Map.Entry)it.next();
    System.out.println(me.getKey()+"::::"+me.getValue());
}
           

使用集合的技巧：

• 看到Array就是數組結構，有角标，查詢速度很快。
• 看到Link就是連結清單結構：增删速度快，而且有特有方法。addFirst()； addLast()；removeFirst()； removeLast()；getFirst()；getLast()；
• 看到Hash就是哈希表，就要想要哈希值，就要想到唯一性，就要想到存入到該結構中的元素必須覆寫hashCode和equals方法。
• 看到Tree就是二叉樹，就要想到排序，就想要用到比較。

*比較的兩種方式：

- 一個是Comparable：覆寫compareTo方法；

- 一個是Comparator：覆寫compare方法。

集合部分更多題目：

Java集合面試總結