集合架構和泛型程式設計

Java集合架構

• 一組存儲對象的容器（動态）

常見的集合算法

• 周遊集合
• 添加集合元素
• 删除集合元素
• 查找集合元素
• 集合元素排序

Java SE提供了：

• Collection接口：存儲另一個元素的集合
• Map接口（圖）：存儲鍵/值對
• Collection：操作集合的工具類

注意：

1. 所有集合類都位于java.util包下，Java的集合類主要由兩個接口派生而出；Collection和Map是Java集合架構的根接口，這兩個接口又包含了一些子接口或實作類
2. 集合架構中所有的具體類都實作了Cloneable和Serializable接口，即他們執行個體都是可複制且可序列化的
3. 集合接口：6個接口，表示不同集合類型，是集合架構的基礎
4. 抽象類：5個抽象類，對集合接口的部分實作，可擴充為自定義集合類
5. 實作類：8個實作類，對接口的具體實作
6. Collection接口是一組允許重複的對象
7. Set接口繼承Collection，集合元素不重複
8. List接口繼承Collection，允許重複，維護元素插入順序
9. Map接口是鍵-值對象，與Collection接口沒有什麼關系
10. Set，List，和Map可以看做集合的三大分類：

List集合是有序集合，集合中的元素可以重複，通路集合中的元素可以根據元素索引來通路

Set集合是無序集合，集合中的元素不可以重複，通路集合中的元素隻能根據元素本身來通路（也是集合裡元素不允許重複的原因）

集合架構包含内容

• Set（規則集）
• List（線性表）
• Queue（隊列）
• Map（圖）

Collection接口

方法	描述
boolean add(E e); / int size();	向集合中添加元素e / 傳回集合中的元素個數
boolean addAll(Collection<? extends E> c);	将集合c 中的所有元素添加到目前這個集合
boolean contains(Object o);	如果該集合中包含對象o，傳回true
boolean containsAll(Collection<?> c);	如果該集合中包含集合c的所有元素，傳回true
boolean isEmpty(); / void clear();	如果集合不包含任何元素，傳回true / 删除集合中所有元素
Iterator iterator();	傳回集合中元素所用的疊代器
boolean remove(Object o);	從集合中删除元素o
boolean removeAll(Collection<?> c);	從集合中删除集合c擁有的所有元素
boolean retainAll(Collection<?> c);	保留c和目前集合都有的元素（交集）
Object[] toArray();	傳回該集合元素構成的Object數組

疊代器Iterator和ListIterator

• 相同點：都是疊代器，當需要對集合中的元素進行周遊不需要幹涉其周遊過程時，這兩種疊代器都可以使用
• 不同點：
  • 1. 使用範圍不同，Iterator可以應用于所有集合，Set、List和Map和這些集合的子類型。而ListIterator隻能用于List及其子類型
    2. ListIterator有add方法，可以向list中增加對象。Iterator不可以
    3. Iterator和ListIterator都有hasNext（）和next（）方法，可以向後順序周遊；ListIterator有hasPrevious（）和previous（）方法，可以逆向（順序向前）周遊，Iterator不可以
    4. ListIterator可以定位目前索引位置，nextIndex()和previousIndex()可以實作，Iterator沒有此功能
    5. 都可以實作删除操作，但ListIterator可以利用set()方法實作對象修改，Iterator不可以

Iterator 疊代器包含方法有：

• hasNext()：如果疊代器指向位置後面還有元素，則傳回true，否則傳回false
• next()：傳回集合中Iterator指向位置後面的元素
• remove()：删除集合中Iterator指向位置後面的元素

ListIterator 疊代器包含的方法：

• add(E e)：将指定元素插入清單，插入位置為疊代器目前位置之前
• hasNext()：以正向周遊清單時，如果清單疊代器後面還有元素，則傳回true，否則傳回false
• hasPrevious()：以逆向周遊清單時，如果清單疊代器前面還有元素，則傳回true，否則傳回false
• next()：傳回清單中ListIterator指向位置後面的元素
• nextIndex()：傳回清單中ListIterator目前位置後面的元素索引
• previous()：傳回清單中ListIterator指向位置前面的元素
• previousIndex()：傳回清單中ListIterator指向位置前面的元素索引
• remove()：删除清單中next()或previous()傳回的最後一個元素
• set(E e)：從清單中将next()或previous()傳回的最後一個元素傳回的最後一個元素更改為指定元素e

List接口的實作類

ArrayList（數組線性表）

• 是一個大小可變的數組，在記憶體中配置設定連續空間
• 周遊元素和随機通路元素的效率比較高
• 在一列資料後面添加資料而不是在中間或前面，并且需要随機通路其中的元素時，使用ArrayList性能更好

LinkedList（連結清單）

• 采用連結清單存儲方式
• 提供從線性兩端提取，插入和删除元素的方法
• 插入，删除元素效率比較高
• 在一列資料前面或中間添加資料而且需要按照順序通路其中的元素時，使用LinkedList性能更好

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public abstract class ListDemo {
	public static void main(String[] args) {
		List<Integer> arrayList = new ArrayList<Integer>();
		arrayList.add(1);	arrayList.add(3);	arrayList.add(4);
		arrayList.add(1);	arrayList.add(2);
		arrayList.add(0,10);
		arrayList.add(3,30);
		System.out.println(arrayList);
		
		LinkedList<Object> linkedList = new LinkedList<Object>(arrayList);
		linkedList.add(1,"red");
		linkedList.removeFirst();
		linkedList.addFirst("green");
		ListIterator<Object> listIt = linkedList.listIterator();
		while(listIt.hasNext()) {
			System.out.print(listIt.next() + ";");
		}
		System.out.println();
		
		listIt = linkedList.listIterator(linkedList.size());
		System.out.println("倒序通路：");
		while(listIt.hasPrevious()) {
			System.out.print(listIt.previous() + ";");
		}
		
		LinkedList<String> list = new LinkedList<String>();
		System.out.println();
		list.add("哈哈");
		list.add("嘻嘻");
		list.add("呵呵");
		System.out.println(list);
	}
}

           

列印結果：

[10, 1, 3, 30, 4, 1, 2]
green;red;1;3;30;4;1;2;
倒序通路：
2;1;4;30;3;1;red;green;
[哈哈, 嘻嘻, 呵呵]

           

ArrayList與Vector

相同點

實作原理相同，功能相同，很多情況可以互用

不同點

• Vector線性安全，ArrayList重速度輕安全，線性非安全
• 長度需增長時，Vector預設增長一倍；ArrayList增長50%，有利于節約空間
• 不需要同步最好使用ArrayList，因為速度快

使用集合建議

1. 若需要周遊List集合元素，對于ArrayList、Vetor，應該使用随機通路方法（get）來周遊集合，性能更好；對于LinkedList，應該采用疊代器來周遊元素
2. 若需要經常執行插入，删除操作來改變包含大量資料List集合大小，可以考慮LinkedList
3. 若有多個線程需要同時通路List集合中的元素，可以考慮用Collections将集合包裝成線程安全的集合

Set接口和實作類

Set接口：用來操作存儲一組唯一、無序的對象

• HashSet：用來存儲互不相同的任何元素

  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.Set;
  
  /**
   * HashSet集合的使用
   * @author
   * @version
   * @data
   */
  public class SetDemo {
  
  	public static void main(String[] args) {
  		Set<String> set1 = new HashSet<String>();
  		set1.add("London");
  		set1.add("Paris");
  		set1.add("New York");
  		set1.add("San Francisco");
  		set1.add("Beijing");
  		set1.add("New York");//set是無序集合，不可以有重複的元素
  		
  		System.out.println(set1);
  		
  		Iterator<String> it = set1.iterator();//疊代器周遊
  		while(it.hasNext()) {
  			System.out.print(it.next() + "; ");
  		}
  		
  		System.out.println();
  		Set<String> set2 = new HashSet<String>();
  		set2.add("Paris");
  		set2.add("廣東");
  		set2.add("廣西");
  		set2.add("上海");
  		set2.add("New York");
  		set1.removeAll(set2);//在set1中移除set2的所有元素
  		set1.retainAll(set2);//在set1中保留set2的所有元素
  		System.out.println(set1);
  	}
  
  }
             

• LinkedHashSet：使用連結清單擴充實作HashSet類，支援對元素的排序
  • 注意：若不需要維護元素插入的順序，建議使用HashSet更加高效
• TreeSet：可以確定所有元素都是有序的

  import java.util.HashSet;
  import java.util.Set;
  import java.util.TreeSet;
  
  /**
   * TreeSet集合使用
   * @author
   * @version
   * @data
   */
  public class TreeSetDemo {
  
  	public static void main(String[] args) {
  		/**
  		 * 當更新一個規則集時，如果不需要保持元素的排序關系，就應該使用散列集
  		 * 因為在散列集中插入，删除元素所花的時間比較少
  		 * 當需要一個排好序的集合時，可以從這個散列集建立一個樹形集
  		 */
  		Set<String> set1 = new HashSet<String>();
  		set1.add("London");
  		set1.add("Paris");
  		set1.add("San Francisco");
  		set1.add("Beijing");
  		set1.add("New York");
  		
  		TreeSet<String> treeSet = new TreeSet<String>(set1);//會自動按照字母順序排序
  		System.out.println("排序：" + treeSet);
  		/**
  		 * 方法first和last：傳回第一個和最後一個元素
  		 * headSet(toElement)和tailSet(fromElement):傳回Set中小于element的元素；傳回Set中大于等于element的元素
  		 */
  		System.out.println("首元素：" + treeSet.first());
  		System.out.println("尾元素：" + treeSet.last());
  		System.out.println("New York之前的元素：" + treeSet.headSet("New York"));
  		System.out.println("New York之後的元素：" + treeSet.tailSet("New York",false));
  		
  		/**
  		 * lower(e),floor(e),ceiling(e)和higher(e)：分别傳回小于、小于等于、大于等于、大于一個給定的元素，若沒有這個元素，傳回null
  		 */
  		System.out.println(treeSet.lower("P"));//傳回集合中小于P的最大元素
  		System.out.println(treeSet.higher("P"));//傳回集合中大于P的最小元素
  		System.out.println(treeSet.floor("P"));//傳回集合中小于等于P的最大元素
  		System.out.println(treeSet.ceiling("P"));//傳回集合中大于等于P的最小元素
  		
  		/**
  		 * pollFirst():删除并傳回集合中的第一個元素
  		 * pollLast():删除并傳回集合中最後一個元素
  		 */
  		System.out.println("删除前：" + treeSet);
  		System.out.println("删除第一個元素：" + treeSet.pollFirst());//删除并傳回集合中第一個元素
  		System.out.println("删除最後一個元素：" + treeSet.pollLast());//删除并傳回集合中最後一個元素
  		System.out.println("删除後：" + treeSet);
  
  		
  	}
  
  }
  
             

  Set和List的運作性能對比

  • 規則集比線性表更加高效，若應用程式使用規則集足夠，那麼就用規則集
  • 若程式不需要特别的順序，就用散列集
  • 若線性表中除了結尾之外的任意位置上進行插入或删除操作，鍊式線性表會比數組線性表更加有效

Comparable 接口

• 需要排序的元素必須實作該接口
• 集合中的元素本身能夠實作比較

Comparator 接口

• 自定義比較器實作該接口
• 集合中的元素本身不能實作排序

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;
import java.util.Comparator;

public class CompareDemo {
	static final int N = 50000;
	public static void main(String[] args) {
		
		Set<Student> hashSet = new HashSet<Student>();
		
		hashSet.add(new Student(5,"曹沖"));
		hashSet.add(new Student(1,"曹操"));
		hashSet.add(new Student(3,"曹丕"));
		hashSet.add(new Student(2,"曹仁"));
		hashSet.add(new Student(4,"曹植"));
		
		System.out.println("排序前：" + hashSet);
		
		Set<Student> treeSet = new TreeSet<Student>(new StudentComparator());
		treeSet.addAll(hashSet);
		treeSet.add(new Student(6,"關羽"));
		System.out.println("排序後：" + treeSet);
		
	}

}

public class Student {
	private int id;
	private String name;
	
	public Student(int id, String name) {
		setId(id);
		setName(name);
	}

	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}
	
	@Override
	public String toString() {
		return id + "-" + name;
	}
}

/**
 * 定義一個比較類，實作Comparator接口
 * @author
 * @version
 * @data
 */
public class StudentComparator implements Comparator<Student>{
	@Override
	public int compare(Student o1, Student o2) {
		if(o1.getId() == o2.getId()) {
			return 0;
		}
		if(o1.getId() < o2.getId()) {
			return -1;
		}
		return 1;
	}
}
           

java.util.Collection 工具類

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class CollectionDemo {

	public static void main(String[] args) {
		
		List<String> list = Arrays.asList("are","you","ok");
		Collections.sort(list);//對指定清單進行排序
		System.out.println(list);
		
		Collections.sort(list, Collections.reverseOrder());//使用指定比較器進行排序，reverseOrder()：傳回逆序的比較器
		System.out.println(list);
		
		int index = Collections.binarySearch(list, "ok");//使用二分查找法搜尋有序清單的鍵值
		System.out.println(index);
		
		Collections.shuffle(list);//随機打亂順序
		Collections.shuffle(list,new Random(20));//使用随機對象打亂指定清單
		System.out.println(list);
		
		List<String> list2 = Arrays.asList("my","name","is","cai");
		Collections.copy(list2, list);//複制list給list2
		System.out.println(list);
		System.out.println(list2);
		
		Collections.fill(list, "abc");//使用對象填充清單
		System.out.println("list:" + list);
		System.out.println("list2" + list2);
		
		System.out.println("沒有相同的元素：" + Collections.disjoint(list, list2));//若沒有公共元素傳回true
		
		System.out.println("abc出現次數" + Collections.frequency(list, "abc"));//傳回集合中指定元素出現的次數
		
		
	}

}

           

[are, ok, you]
[you, ok, are]
1
[ok, you, are]
[ok, you, are]
[ok, you, are, cai]
list:[abc, abc, abc]
list2[ok, you, are, cai]
沒有相同的元素：true
abc出現次數3
           

支援隊列操作的Queue

• Queue通常用于操作存儲一組隊列方式的對象資訊
  • 一般存儲方式為先進先出（FIFO）

    boolean offer(element)	向隊列中插入一個元素（類似于add方法）
    E poll()	擷取并删除隊列頭元素，如果隊列為空傳回null
    E remove（）	擷取并删除隊列頭元素，若為空抛出異常
    E peek（）	擷取但不删除隊列頭元素，如果隊列為空傳回null
    E element（）

圖（Map）

• 以鍵 - 值存儲元素的容器
  • 根據關鍵字（key）找到對應資料
  • 主要存儲鍵值對，根據鍵得到值，不允許重複（重複就覆寫），但允許值重複
  • HashMap是最常用的Map，HashMap最多隻允許一條記錄的鍵為null；允許多條記錄值為null
  • HashMap不支援線程同步，是以任一時刻可以有多個線程同時寫HashMap，但可能導緻資料不一緻

  V put(key, value)	将一個鍵/值映射放入圖中
  V get(key)	根據鍵擷取對應的value值
  Set keySet()	傳回包含鍵的規則集
  Collection values	傳回包含值的集合
  boolean containsKey(key)	傳回圖中是否包含鍵值key
  Set<Map.Entry<K.V>> entrySet()	傳回一個圖中包含條目的規則集
  int size()	傳回圖中的鍵值對個數
  V remove(key)	删除指定鍵對應的條目

  • HashMap的查詢，插入和删除都比較高效
  • LinkedHashMap支援元素的插入順序
  • TreeMap在周遊有序的鍵值時非常高效
• 使用建議
  • 如果更新圖時不需要保持圖中元素的順序，就使用HashMap
  • 如果需要保持圖中元素的插入順序和通路順序，就使用LinkedHashMap
  • 如果需要使圖按照鍵值排序，就使用TreeMap

Properties

• 鍵值對集合
  • 通常用于儲存字元串類型鍵值對
  • 更多用于讀取屬性檔案

  String getProperty(key)	通過指定的鍵（key）擷取配置檔案中對應的值（value）
  Object setProperty(key, value)	通過調用父類的put方法來設定鍵-值對
  void load(instream)	從輸入流讀取屬性清單
  void store(outStream, comments)	将屬性清單（鍵值對）寫入到對應的配置檔案中
  void clear()	清除所有的鍵值對

泛型程式設計

泛型類就是具有一個或多個類型變量的類

• 泛型
  • 指參數化類型的能力
  • 可以定義帶泛型類型的類或方法，随後編譯器會用具體的類型來替換它
  注意
  1. 指定類型後，添加其他類型的元素就會編譯錯誤
  2. 泛型類型必須是引用類型，不能是基本類型
  3. 添加基本類型時，Java會自動打包

  public class Main {
  
  	public static void main(String[] args) {
  		Holder<AutoMobile> holder = new Holder<AutoMobile>(new Trunk());
  		AutoMobile auto = holder.getA();//無需轉類型
  		auto.run();
  	}
  
  }
  
  /**
   * 泛型類
   */
  public class Holder<T> {
  	private T a;
  	public Holder(T a) {
  		this.a = a;
  	}
  	
  	public T getA() {
  		return a;
  	}
  	public void setA(T a) {
  		this.a = a;
  	}	
  }
  
  abstract class AutoMobile {
  	public abstract void run();
  }
  public class Car extends AutoMobile{
  	@Override
  	public void run() {
  		System.out.println("小車在跑");
  	}
  }
  public class Trunk extends AutoMobile{
  	@Override
  	public void run() {
  		System.out.println("卡車在跑");
  	}
  }
  
             

  列印結果：卡車在跑
             

使用泛型時的注意點

1. 不能使用泛型類型參數建立執行個體：錯誤語句： E object = new E(); 原因：運作時執行的是new E()，但運作時泛型類型是不可用的
2. 不能使用泛型類型建立數組：

   E[] elements =  new E[capacity];//錯誤
   ArrayList<String>[] list = new ArrayList<String>[10];//錯誤
   
   E[] elements = (E[])new Object[capacity];//正确
   ArrayList<String>[] list = (ArrayList<String>)new ArrayList[10];//正确
              

3. 靜态環境下不允許類的參數是泛型類型。由于泛型類的所有執行個體都有相同的運作時類，是以泛型類的精通變量和方法是被他所有執行個體共享的。是以，在靜态方法中，資料域或初始化語句中，為了類而引用泛型類型參數是非法的

   public class Test<E>{
       public static test1(E o1){}//非法
       public static E o1;//非法
       static{
           E o2;//非法
       }
   }
              

4. 異常類不能是泛型的，泛型類不能擴充java.lang.Throwable

   public class MyException<T> extends Exception{}
              

   捕獲異常時：

   try{}catch(MyException<T> e){}//JVM必須檢查這個從try中抛出的異常，以确定它是否與catch子句指定的類型比對，但在運作時類型的資訊是不出現的
              

泛型使用場合

• 如果需要對多種類型進行相同的操作，建議使用泛型
• 如果需要處理的資料是值類型，可以使用泛型避免裝箱和拆箱帶來的性能損耗
• 使用泛型可以在應用程式編譯時發現類型錯誤，增強程式的健壯性
• 可以減少重複代碼，使代碼結構更加清晰