集合（上）_ZenDei技術網路在線

傳統的容器(數組)在進行增、刪等破壞性操作時，需要移動元素，可能導致性能問題；同時添加、刪除等演算法和具體業務耦合在一起，增加了程式開發的複雜度。Java集合框架提供了一套性能優良、使用方便的介面和類，它們位於java.util包中。 1 Collection 介面 Collection是java集合 ...

傳統的容器(數組)在進行增、刪等破壞性操作時，需要移動元素，可能導致性能問題；同時添加、刪除等演算法和具體業務耦合在一起，增加了程式開發的複雜度。Java集合框架提供了一套性能優良、使用方便的介面和類，它們位於java.util包中。

1 Collection 介面

Collection是java集合框架(collection-frame)中的頂層介面。Collection介面是一個容器，容器中只能存儲引用數據類型，建議存同一類型的引用類型，方便後續遍歷等操作。容器中的元素可以是有序的、可重覆的，稱為List介面；也可能是無序的、唯一的，稱為Set介面。

1.1 集合常用方法

 1 public static void main(String[] args) {
 2         
 3         /**
 4          * 增:add/addAll
 5          * 刪:clear/remove/removeAll/retainAll
 6          * 改:
 7          * 查:contains/containsAll/isEmpty/size
 8          */
 9         
10         Collection c1 = new ArrayList();
11         
12         // 追加
13         c1.add("apple"); // Object object = new String("apple");
14         // c1.add(1);         // Object object = new Integer(1); 
15         c1.add("banana");
16         System.out.println(c1);
17         
18         // 追加一個集合 
19         Collection c2 = new ArrayList();
20         c2.add("java");
21         c2.add("c++");
22         c1.addAll(c2);
23         System.out.println(c1);
24         
25         System.out.println(c1.contains("apple"));
26         c2.add("js");
27         System.out.println(c1.containsAll(c2));
28         // c1.clear();
29         System.out.println(c1.isEmpty());
30         // 返回集合元素的個數
31         System.out.println(c1.size());
32         
33         System.out.println(c1.equals(c2));        
34 }

1.3 集合的遍歷

Iterable 是一個可遍歷的介面，集合介面繼承於它，集合支持快速遍歷。

for (Object item : c1) {
    System.out.println(item.toString());
}

快速遍歷的本質：

Collection 繼承 Iterable 介面，表示集合支持快速遍歷。Iterable 介面定義了一個方法iterator()用於獲取集合的迭代器，是一個 Iterator 介面類型，iterator()內部返回一個實現類實現類 Iterator 介面。這個實現類一定具有 hasNext 和 next 方法用於判斷是否有下一個元素和獲取下一個元素。快速遍歷就是基於迭代器工作的。

 1 public static void main(String[] args) {
 2         
 3         Collection c1 = new ArrayList();
 4         c1.add("apple");
 5         c1.add("banana");
 6         c1.add("coco");
 7         
 8         // 快速遍歷
 9         // for-each
10         // Object 表示元素類型 
11         // item表示迭代變數
12         // c1表示集合
13         for (Object item : c1) {
14             System.out.println(item.toString());
15         }
16         
17         // 方法1
18         Iterator it = c1.iterator();
19         while(it.hasNext()) {
20             Object item = it.next();
21             System.out.println(item.toString());
22         }
23         
24         // 方法2（推薦）
25         for(Iterator it2=c1.iterator();it2.hasNext();) {
26             Object item = it2.next();
27             System.out.println(item.toString());
28         }    
29 }

查看源碼可以看到 next 方法的實現

 1 @SuppressWarnings("unchecked")
 2         public E next() {
 3             checkForComodification();
 4             int i = cursor;
 5             if (i >= size)
 6                 throw new NoSuchElementException();
 7             Object[] elementData = ArrayList.this.elementData;
 8             if (i >= elementData.length)
 9                 throw new ConcurrentModificationException();
10             cursor = i + 1;
11             return (E) elementData[lastRet = i];
12         }

iterator 方法會返回一個私有類 Itr 的實例，該類中定義了一個 cursor 變數，初始值為 0，表示當前”游標“指向的元素索引；定義了一個 lastRet 變數初始值為 -1，表示上一個遍歷過的元素的索引。每次使用 next 後，將 cursor 賦給 i ，游標 cursor 後移一位，同時返回當前 i 指向的元素，並將 i 賦給 lastRet。

iterator 是線程不安全的，不支持在遍歷的同時修改集合元素。每次使用 next 的時候，會首先使用 checkForComodification 方法，查看源碼可知，該方法會判斷兩個變數 modcount、expectedModCount 是否相等，如果不相等就拋出“同時修改異常”。modcount 是 ArrayList 的父類 AbstractList 中定義的一個變數，Arraylist 的 add 方法每次執行時，會先調用 ensureCapacityInternal 方法判斷容量並自動擴容，該方法又調用了 ensureExplicitCapacity 方法，該方法每次調用時 modcount 會自加一次。而expectedMoCount 是在創建 Itr 實例時生成的，將ArrayList 的 modcount 賦給它，所以當在遍歷過程中修改集合元素，next 方法調用時就會拋出“同時修改異常”。

 1 private void ensureCapacityInternal(int minCapacity) {
 2         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
 3     }
 4 
 5     private void ensureExplicitCapacity(int minCapacity) {
 6         modCount++;
 7 
 8         // overflow-conscious code
 9         if (minCapacity - elementData.length > 0)
10             grow(minCapacity);
11     }

2 List 介面

List 繼承 Collection。List 介面中的元素時有序的、可重覆的。List介面中的元素通過索引(index)來確定元素的順序。可以對列表中每個元素的插入位置進行精確地控制。用戶可以根據元素的整數索引（在列表中的位置）訪問元素，並搜索列表中的元素。

2.1 List 常用方法

 1 public static void main(String[] args) {
 2         
 3         /**
 4          * 增:add/addAll/add(index,el)/addAll(index,collection)
 5          * 刪:clear/remove/removeAll/remove(index)
 6          * 改:set(index,el)
 7          * 查:get(index)/indexOf/lastIndexOf()
 8          * 其他:contains/containsAll/isEmpty/size
 9          */
10         List list1 = new ArrayList();
11         // 添加元素
12         list1.add("apple");
13         list1.add("banana");
14         // 在指定位置添加元素
15         list1.add(0, "coco");
16         
17         System.out.println(list1);
18         
19         List list2 = new ArrayList();
20         list2.add("java");
21         list2.add("c++");
22         
23         list1.addAll(1, list2);
24         System.out.println(list1);
25         
26         // 刪除
27         list1.remove(0);
28         System.out.println(list1);
29         
30         // 修改
31         list1.set(0, "javax");
32         System.out.println(list1);
33         
34         // 查
35         System.out.println(list1.get(0));
36         list1.add("apple");
37         list1.add("apple");
38         System.out.println(list1);
39         System.out.println(list1.indexOf("apple"));
40         System.out.println(list1.lastIndexOf("apple"));
41 }

2.2 List 介面的遍歷

ListIterator 繼承於Iterator，在Iterator的基礎上提供了以正向遍歷集合，也可以以逆序遍歷集合。hasNext/next 以正向遍歷；hasPrevious/previous 以逆序遍歷。

 1 public static void main(String[] args) {
 2     
 3         List list1 = new ArrayList();
 4         list1.add("apple");
 5         list1.add("banana");
 6         list1.add("coco");
 7         
 8         // 【1】快速遍歷
 9         System.out.println("--for each--");
10         for (Object item : list1) {
11             System.out.println(item.toString());
12         }
13         
14         // 【2】普通for
15         System.out.println("--for--");
16         for(int i=0;i<list1.size();i++) {
17             System.out.println(list1.get(i));
18         }
19         
20         // 【3】集合迭代器
21         System.out.println("--iterator--");
22         Iterator it = list1.iterator();
23         while(it.hasNext()) {
24             System.out.println(it.next());
25         }
26         
27         System.out.println("--list iterator--");
28         // 正向遍歷
29         ListIterator it2 = list1.listIterator();
30         while(it2.hasNext()) {
31             System.out.println(it2.next());
32         }
33         
34         // 逆序遍歷
35         while(it2.hasPrevious()) {
36             System.out.println(it2.previous());
37         }
38         
39         System.out.println("--list iterator with index--");
40         ListIterator it3 = list1.listIterator(1);
41         while(it3.hasNext()) {
42             System.out.println(it3.next());
43         }
44 }

3 ArrayList/Vector

ArrayList 是List介面的實現類，底層數據結構是數組，實現大小可變的數組。ArrayList 線程不安全，從 jdk1.2 開始使用。ArrayList 底層數據結構是數組，預設數組大小是10,如果添加的元素個數超過預設容量，ArrayList會自動拓容，拓容原則:newCapacity = oldCapacity + oldCapacity / 2；如果未來確定序列的元素不在增加，通過調用trimToSize()調製容量至合適的空間。ArrayList作為List介面的實現類，常用方法和遍歷方法參考List介面。

Vector 是List介面的實現類，底層數據結構也是數組，也是大小可變的數組。Vector是線程安全的，從 jdk1.0 開始使用。Vector底層數據結構是數組，預設數組大小是10,如果添加的元素個數超過預設容量，Vector會自動拓容，拓容原則:newCapacity = oldCapacity +capacityIncrement(增長因數);如果未來確定序列的元素不在增加，通過調用trimToSize()調製容量至合適的空間。

註意:Vector 在實現List介面的同時，同添加了自身特有的方法xxxElement,未來使用時為了程式的可拓展性，一定要按照介面來操作Vector。

4 LinkedList

LinkedList是List介面的實現類，底層數據結構是鏈表。LinekList常用方法和遍歷方法參照List介面。LinkedList 線程不安全。

除了實現List介面，還實現了棧介面（後進先出 LIFO），通過 push 和 pop 方法實現棧的操作。

 1 public static void main(String[] args) {
 2         LinkedList list = new LinkedList();
 3         list.push("apple");
 4         list.push("banana");
 5         list.push("coco");
 6         
 7         
 8         System.out.println(list.pop()); //coco
 9         System.out.println(list.pop()); //banana
10         System.out.println(list.pop());
11         
12         // java.util.NoSuchElementException
13         System.out.println(list.pop());
14 }

也實現了隊列介面（先進先出 FIFO），提供兩套方法實現。

add/remove/element() 可能會出現NoSuchElementException異常

 1 public static void main(String[] args) {
 2         
 3         LinkedList queue = new LinkedList();
 4         // 入隊
 5         /**
 6          * 隊列頭                          隊列尾
 7          *<-----          <-----
 8          * [apple, banana, coco]
 9          */
10         queue.add("apple");
11         queue.add("banana");
12         queue.add("coco");
13         System.out.println(queue);
14         
15         // 出隊
16         System.out.println(queue.remove()); //返回隊列頭元素，並從隊列中移除
17         System.out.println(queue.remove());
18         System.out.println(queue.remove());        
19         System.out.println(queue);
20         
21         // java.util.NoSuchElementException
22         System.out.println(queue.remove());
23         
24         
25         // 獲取表頭元素
26         System.out.println(queue.element());
27 }

offer/poll/peek 可能會返回特殊值(null)

 1 public static void main(String[] args) {
 2         
 3         LinkedList queue = new LinkedList();
 4         // 入隊
 5         /**
 6          * 隊列頭                          隊列尾
 7          *<-----          <-----
 8          * [apple, banana, coco]
 9          */
10         queue.offer("apple");
11         queue.offer("banana");
12         queue.offer("coco");
13         
14         // 出隊列
15         //System.out.println(queue.poll());
16         //System.out.println(queue.poll());
17         //System.out.println(queue.poll());
18         System.out.println(queue);
19 
20         //System.out.println(queue.poll());//輸出 null
21         
22         // 獲取表頭元素
23         System.out.println(queue.peek());
24     
25 }

同時也繼承了雙向隊列介面，兩頭可進可出，一樣提供兩套方法，一個會拋異常，一個會返回 null。

用法如上面代碼類似。

5 ListIterator

正如上文講遍歷時所說的，Iterator 不支持遍歷的過程中修改集合元素，而 ListIterator 正好彌補了這個缺陷，ArrayList 對象可以使用 listIterator 方法獲得一個 ListIterator 的實例。ListIterator允許程式員按任一方向遍歷列表、迭代期間修改列表，並獲得迭代器在列表中的當前位置。

 1 public static void main(String[] args) {
 2         ArrayList list = new ArrayList();
 3         list.add("apple");
 4         list.add("banana");
 5         list.add("coco");
 6         
 7         ListIterator it = list.listIterator();
 8         while(it.hasNext()) {
 9             String item = (String) it.next();
10             if(item.equals("banana")) {
11                 it.add("test");  
12                         //在當前游標（cursor）位置插入一個元素，這個 add 方法是屬於ListIterator 的
13                         // next 方法調用後，游標 cursor 會後移
14             }
15         }
16         
17         System.out.println(list); //[apple, banana, test, coco]
18 }

6 泛型（generic）

6.1 概念

泛型允許開發者在強類型程式設計語言（java）編寫代碼時定義一些可變部分，這些部分在使用前必須作出指明。泛型就是將類型參數化。

ArrayList<E> list表示聲明瞭一個列表list，列表的元素是E類型
ArrayList<String> list = new ArrayList<String>()；聲明瞭一個列表list，列表的元素只能是String類型。

6.2 泛型的擦除

泛型在編譯器起作用，運行時jvm察覺不到泛型的存在。泛型在運行時已經被擦除了。

1 public static void main(String[] args) {
2         ArrayList<String> list = new ArrayList<String>();
3         list.add("apple");
4         System.out.println(list instanceof ArrayList); //true
5         System.out.println(list instanceof ArrayList<String>);
6                //Cannot perform instanceof check against parameterized type ArrayList<String>.
7                // Use the form ArrayList<?> instead since further generic type information will 
8                //be erased at runtime
9 }

6.3 泛型的應用

泛型類

當一個類中屬性的數據類型不確定時，具體是什麼類型由使用者來確定時，使用泛型。泛型類的形式：

1 public class 類名<T> {
2     
3 }

定義一個泛型類：

 1 class FanClass<T> {
 2     private T t;
 3 
 4     public T getT() {
 5         return t;
 6     }
 7 
 8     public void setT(T t) {
 9         this.t = t;
10     }
11 
12     public FanClass(T t) {
13         super();
14         this.t = t;
15     }
16 
17     public FanClass() {
18         super();
19     }
20 }
21 public class Test01 {
22     public static void main(String[] args) {
23         FanClass<String> fan = new FanClass<String>();
24         fan.setT("apple");
25         
26         FanClass<Integer> fan2 = new FanClass<Integer>();
27         fan2.setT(1);
28     }
29 }

泛型方法

當一個方法的參數類型不確定時，具體是什麼類型由使用者來確定，可以考慮使用泛型方法，泛型方法在調用時確定(指明)類型。形式：

1 public <T> void xxx(T a) {
2     System.out.println(a);
3 }

舉例：

 1 class Student {
 2     public <T> void showInfo(T a) {
 3         System.out.println(a);
 4     }
 5 }
 6 public class test {
 7         public static void main(String[] args) {
 8         Student stu = new Student();
 9         stu.showInfo(1);
10         stu.showInfo("apple");
11         stu.showInfo(1.0f);  //傳入的參數是什麼類型，T 就是什麼類型
12     }
13 }

泛型介面

如果介面中的方法的參數(形參、返回值)不確定時，可以考慮使用泛型介面。形式：

1 public interface FanInterface<T> {
2     public void showInfo(T t);
3 }

實現類能確定泛型介面的類型

1 public class ImplClass implements FanInterface<String>{
2 
3     @Override
4     public void showInfo(String t) {
5         // TODO Auto-generated method stub
6         
7     }
8 }

實現類不能確定泛型介面的類型->繼續泛。

1 public class ImplClass2<T> implements FanInterface<T>{
2 
3     @Override
4     public void showInfo(T t) {
5         
6     }
7 }

6.4 泛型的上、下限

1 public static void print(ArrayList<? extends Pet> list) {
2         for (Pet pet : list) {
3             pet.showInfo();
4         }
5 }

泛型的上限ArrayList(? extends Pet) list 聲明瞭一個容器，容器中的元素類型一定要繼承於Pet，我們稱這種形式叫做泛型的上限。
泛型的下限ArrayList(? super Pet) list 聲明瞭一個容器，容器中的元素類型一定要是Pet的父類，我們稱這個形式為泛型的下限。