前述
複習一下Java中的集合類，是面試筆試中常考察的一個點，特地做的整理。
什麼是集合類？
集合類，也叫容器類。Java集合類可以用來存儲數量龐大的對象。
我們和數組進行對比：
數組：存儲基本資料類型，資料類型單一，長度固定，不能動态增大容量。
集合：存儲的即可是基本類型的值，也可以是對象，可以存儲多種資料類型，長度可變，可以動态增大容量。
Java集合類的體系
Java集合類主要有兩個接口派生而出：Collection和Map。即集合類都是實作的這兩個接口。我們在實際程式設計中經常使用的有 List、Set、Queue（這些是實作的 Collection 接口）HashMap、TreeMap、HashTable（這些實作的 Map 接口）
Collection接口結構
Collection 接口位于 Java.util 包下，是一個父接口， List、Set、Queue 都是實作的 Collection 接口。Collection 做為父接口提供一些操作集合類的方法，是以它的子接口也有這些方法。
Collection 接口不能被執行個體化，并且在實際的程式設計過程中幾乎不會使用它進行資料的存儲。
Map接口結構
Map 接口實作的是鍵值對的存儲，類似 python 中的 dict。
Map中比較常見的是 HashMap、TreeMap、Hashtable 類。
Set接口
Set 接口繼承自 Collection 接口，Collection 接口有的方法 Set 接口中也有。
Set 接口自身的特性：
-
- 不允許重複元素
- 不區分先後順序（無序）
- 允許值是 null
Set 接口有兩個比較常用的具體實作，HashSet、TreeSet。下面分别說一下這兩個集合類。
HashSet
主要特點是快速查找元素。HashSet 是基于 Hash 算法來實作的，在每次添加新的對象的時候，會根據散列碼來判斷對象是否重複，散列碼的擷取是通過 Object 的 hashCode() 來實作的。同樣 HashSet 也是無序的。
1 import java.util.*;
2 /**
3 * @author jyroy
4 * HashSet使用
5 */
6 public class HashSetDemo {
7 public static void main(String[] args) {
8 HashSet hashSet = new HashSet();
9 hashSet.add("Tom");
10 hashSet.add("Jack");
11 hashSet.add("Roy");
12 System.out.println(hashSet);
13 }
14 } 當有重複元素添加時，結果如下
1 import java.util.*;
2 /**
3 * @author jyroy
4 * HashSet使用
5 */
6 public class HashSetDemo {
7 public static void main(String[] args) {
8 HashSet hashSet = new HashSet();
9 hashSet.add("Tom");
10 hashSet.add("Tom");
11 hashSet.add("Jack");
12 hashSet.add("Roy");
13 System.out.println(hashSet);
14 }
15 } TreeSet
主要特點是會進行自然排序，同樣不能重複。參考如下的代碼，可以看出 TreeSet 把原本無序的值進行了重新排序，依據的就是自然排序。
1 import java.util.*;
2 public class TreeSetDemo {
3 public static void main(String[] args) {
4 TreeSet treeSet = new TreeSet();
5 treeSet.add("Tom");
6 treeSet.add("Jack");
7 treeSet.add("Roy");
8 System.out.println(treeSet);
9 }
10 } 然而，在實際開發中很多時候我們很多時候遵循的不是自然排序，而是有自己定義的排序規則，我們要做的就是建立一個類并且實作 compareTo() 方法。
下面的代碼實作的是根據年齡由小到大進行排序，比較簡單，一看就懂的代碼。
1 import java.util.TreeSet;
2 class Person implements Comparable{
3 public String name;
4 public int age;
5 @Override
6 public String toString() {
7 return "Person [name=" + name + ", age=" + age + "]";
8 }
9 @Override
10 public int compareTo(Object o) {
11 Person person = (Person) o;
12 if(this.age < person.age) {
13 return -1;
14 }else if(this.age > person.age) {
15 return 1;
16 }else {
17 return 0;
18 }
19 }
20 }
21 public class TreeSetDemoCompareto {
22 public static void main(String[] args) {
23 TreeSet treeSet = new TreeSet();
24 Person person1 = new Person();
25 Person person2 = new Person();
26 Person person3 = new Person();
27 person1.name = "Tom";
28 person1.age = 20;
29 person2.name = "Jack";
30 person2.age = 21;
31 person3.name = "Roy";
32 person3.age = 22;
33 treeSet.add(person1);
34 treeSet.add(person2);
35 treeSet.add(person3);
36 System.out.println(treeSet);
37 }
38 } List接口
List 接口繼承了 Collection 接口，Collection 接口有的方法 List 中也有。
List 接口自身的特性：
-
- 利用數組方式提供了擷取、修改、删除的功能。
- 可以通過方法來擷取元素的位置。
- 允許重複元素的有序集合。
List 接口有兩個比較常用的具體實作，ArrayList、Vector、LinkedList。下面分别說一下這兩個集合類。
ArrayList
ArrayList 本身是通過數組的方式實作的，大小可以随着對象的增加而增加。查詢效率比較高，增加、删除的效率比較低，這也是數組的一種特性。非線程安全的。而且是有序的。
1 import java.util.*;
2 /**
3 * @author jyroy
4 */
5 public class ArrayListDemo {
6 public static void main(String[] args) {
7 List arrayList = new ArrayList();
8 arrayList.add("Tom");
9 arrayList.add("Jack");
10 arrayList.add("Roy");
11 System.out.println(arrayList);
12 }
13 } Vector
Vector 和 ArrayList 是相似的，都是通過數組來實作的。
最大的差別就是線程安全方面。Vector 是線程安全的，同步的，Vector類對集合的元素操作時都加了synchronized，保證線程安全。而 ArrayList 是非線程安全的。也是因為線程安全的問題，ArrayList 的查詢效率比 Vector 要高。
另外一個差別是在擴容方面，Vector預設擴容是增長一倍的容量，Arraylist是增長50%+1的容量。
Vector與ArrayList的remove,add(index,obj)方法都會導緻内部數組進行資料拷貝的操作，這樣在大資料量時，可能會影響效率。
1 import java.util.*;
2 public class VectorDemo {
3 public static void main(String[] args) {
4 List vectorList = new Vector();
5 vectorList.add("Roy");
6 vectorList.add("Tom");
7 vectorList.add("Jack");
8 System.out.println(vectorList);
9 }
10 } LinkedList
LinkedList 和 ArrayList、Vector相比，在方法的使用上都是相似的。
LinkedList 是基于雙向連結清單的，比較利于對象的增加和删除操作，但是對查詢的支援不夠好，這是連結清單的特點。 LinkedList 同樣是線程不安全的。
1 import java.util.*;
2 public class LinkedListDemo {
3 public static void main(String[] args) {
4 List linkedList = new LinkedList();
5 linkedList.add("Roy");
6 linkedList.add("Jack");
7 linkedList.remove(0);
8 linkedList.add("Tom");
9 System.out.println(linkedList);
10 }
11 } Queue接口
Queue 是 Collection 的子接口，中文稱為隊列，特性就是先進先出，先進入隊列的對象，在進行删除的時候最先被删除。所有的删除操作都是在隊首進行的，所有的插入操作都是在隊尾進行的。
1 import java.util.*;
2 public class QueueDemo {
3 public static void main(String[] args) {
4 Queue queue = new LinkedList();
5 queue.add("Tom");
6 queue.add("Roy");
7 System.out.println(queue.poll()); //出隊列操作
8 queue.add("Jack");
9 System.out.println(queue);
10 }
11 } HashMap
HashMap 是基于散清單的 Map 接口的實作類，線程不安全。
散清單是通過關鍵碼值(Key value)而直接進行通路的資料結構。它通過把關鍵碼值映射到表中一個位置來通路記錄，以加快查找的速度。
當HashMap中的元素個數超過數組大小(數組總大小length,不是數組中個數size)*loadFactor時，就會進行數組擴容，loadFactor的預設值為0.75，這是一個折中的取值。也就是說，預設情況下，數組大小為16，那麼當HashMap中元素個數超過16*0.75=12（這個值就是代碼中的threshold值，也叫做臨界值）的時候，就把數組的大小擴充為 2*16=32，即擴大一倍，然後重新計算每個元素在數組中的位置。
下面的代碼實作了擷取key為 2 的元素的 value。
1 import java.util.*;
2 public class HashMapDemo {
3 public static void main(String[] args) {
4 HashMap hashMap = new HashMap();
5 hashMap.put(1, "Tom");
6 hashMap.put(2, "Jack");
7 hashMap.put(3, "Roy");
8 System.out.println(hashMap.get(2));
9 System.out.println(hashMap);
10 }
11 } TreeMap
TreeMap 是根據紅黑樹算法實作的，TreeMap最大的特性就是支援自然排序。從下面的代碼中也可以非常清晰的看出 TreeMap 利用 key 值進行了自然排序。
紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計算機科學中用到的一種資料結構，典型的用途是實作關聯數組。
1 import java.util.*;
2 public class TreeMapDemo {
3 public static void main(String[] args) {
4 TreeMap treeMap = new TreeMap();
5 treeMap.put("2", "Tom");
6 treeMap.put("1", "Roy");
7 treeMap.put("3", "Jack");
8 System.out.println(treeMap);
9 }
10 } HashTable
HashTable 和 HashMap 是基本一緻的。
最大的差別是 HashTable 是線程安全的，HashMap 不是。
1 import java.util.*;
2 public class HashTableDemo {
3 public static void main(String[] args) {
4 Hashtable hashtable = new Hashtable();
5 hashtable.put("2", "Tom");
6 hashtable.put("1", "Roy");
7 hashtable.put("3", "Jack");
8 System.out.println(hashtable);
9 }
10 } 常見問題
這些問題是在其他一些大佬的部落格中看到，做了一個整理，都是 Java 集合類的問題。
1. ArrayList和LinkedList的特點和差別？
ArrayList： 底層用數組實作，由于數組可以通過下标直接通路指定索引的元素，是以，ArrayList通過索引查詢元素非常快。但由于插入和删除元素時都會進行數組的重新排列，是以，ArrayList的插入和删除操作比較慢。
LinkedList：底層用連結清單實作，由于連結清單沒有具體的下标，是以，通路某個索引的節點時需要周遊該節點前面的所有元素，速度比較慢。由于插入和删除元素時隻需要更新相應元素的指針（或引用），不用重新排列元素，是以，LinkedList對插入和删除操作比較快。
LinkedList 比 ArrayList消耗更多的記憶體，因為 LinkedList 中的每個節點存儲了前後節點的引用。
2. ArrayList和Vector的差別？
ArrayList非線程安全，Vector線程安全。在擴容時，ArrayList預設擴容目前容量的50%，但Vector預設擴容目前容量的100%。
3. HashSet和TreeSet的差別？
HashSet基于HashMap，用鍵來存放HashSet的值，由于HashMap的鍵不能重複，是以，HashSet的值也不會重複，這是集合的一個特點。
TreeSet基于TreeMap，也是用鍵來存放TreeSet的值。TreeMap的底層實作是紅黑樹，其根據鍵排序，可以得到排好序的資料。
4. HashMap和HashTable的差別？
HashMap非線程安全，HashTable線程安全。
HashMap可以允許一個null鍵和多個null值，但HashTable不允許，會出現NullPointerException。
5. HashMap和TreeMap的差別？
HashMap中存放的鍵是随機的，具有較快的通路和存取速度，TreeMap中的鍵是按照自然排序排好的。
6. Java集合架構的基礎接口有哪些？
Collection 和 Map ，一個元素集合，一個是鍵值對集合； 其中 List、Set、Queue 接口繼承了 Collection 接口，一個是有序元素集合，一個是無序元素集合，一個是隊列； 而 ArrayList 和 LinkedList 實作了 List 接口，HashSet 實作了 Set 接口，這幾個都比較常用； HashMap、HashTable、TreeMap 實作了 Map 接口，并且 HashTable 是線程安全的，HashMap 是非線程安全的，但是 HashMap 性能更好。
7. 如何決定選用HashMap還是TreeMap？
對于在Map中插入、删除和定位元素這類操作，HashMap是最好的選擇。然而，假如你需要對一個有序的key集合進行周遊，TreeMap是更好的選擇。
8. 哪些集合類提供對元素的随機通路？
ArrayList、HashMap、TreeMap和HashTable類提供對元素的随機通路。
9. Array和ArrayList有何差別？什麼時候更适合用Array？
Array可以容納基本類型和對象，而ArrayList隻能容納對象。
Array是指定大小的，而ArrayList大小是根據内容自動擴張的。
Array沒有提供ArrayList那麼多功能，比如addAll、removeAll和iterator等。盡管ArrayList明顯是更好的選擇，但也有些時候Array比較好用。
（1）如果清單的大小已經指定，大部分情況下是存儲和周遊它們。
（2）對于周遊基本資料類型，盡管Collections使用自動裝箱來減輕編碼任務，在指定大小的基本類型的清單上工作也會變得很慢。
（3）如果你要使用多元數組，使用[][]比List<List<>>更容易。