# 基本概述 Java中的集合框架與數組類似，都是用于存儲多個同一類型數據的容器。 但是對于數組的使用，會因為數組本身的特性會導致一些使用限制，例如： 數組要求在構造時，就必須確定數組的長度。所以如果想要存放的數據個數不確定，數組就無法使用。 于是促使了集合框架的誕生，與數組相比，集合框架最大特點在于： - 集合框架下的容器類只能存放對象類型數據；而數組支持對基本類型數據的存放。 - 任何集合框架下的容器類，其長度都是可變的。所以不必擔心其長度的指定問題。 - 集合框架下的不同容器了底層采用了不同的數據結構實現，而因不同的數據結構也有自身各自的特性與優劣。 # 常用容器類關系圖 網上找的一張圖，基本描述了Java集合框架中最常用部分的構成關系：  # 集合框架的分類 1、Collection體系：以單值的形式存儲對象數據的容器體系。 1.1、List容器：允許重復元素的存儲。(最常用的為ArrayList以及LinkedList；另外在JDK1.2集合框架出現之前，該類型使用的容器為Vector) - ArrayList? ：線程不同步、底層的數據結構是數組結構、元素存儲順序有序、訪問元素速度相對較快，存取或刪除元素等操作速度較慢 - LinkedList ：線程不同步、底層的數據結構是鏈表結構、元素存儲順序有序、訪問元素速度相對較慢，存取或刪除元素等操作速度快 - Vector???? ：線程同步、? 底層的數據結構是數組結構、元素存儲順序有序、訪問，存取，刪除元素的操作都很慢。 1.2、Set容器：不允許重復元素的存儲，該容器中存儲的對象都是唯一的。(最常用的為HashSet與TreeSet) - HashSet? ：線程不同步、底層的數據結構為哈希表結構、無序 - TreeSet? ：線程不同步、底層的數據結構為二叉樹結構、會按自然排序方式或指定排序方式對元素進行排序 2、Map體系：以“鍵值對”的形式存儲數據的容器體系。即是將鍵映射到值的對象；一個映射不能包含重復的鍵；每個鍵最多只能映射到一個值。 - HashMap?? ：線程不同步、底層數據結構是哈希表結構、無序、允許NUll作為鍵或值 - Hashtable ：線程同步? 、底層數據結構是哈希表結構、無序、不允許NUll作為鍵或值 - TreeMap?? ：線程不同步、底層數據結構是二叉樹結構、可以按照自然或指定排序方式對映射中的鍵進行排序 面試中常常會問到HashMap和HashTable的不同，由此就可以做出回答： 1、HashTable與Vector一樣，在JDK1.2之前就存在，是基于陳舊的Dictionary類實現的。 HashMap是JDK1.2之后，經集合框架出現之后，基于Map接口實現的。 2、HashTable是線程同步的，而HashMap默認并沒有實現線程同步。 也就是說，如果存在多線程并發操作同一個HashMap容器對象時，需要自己加上同步。 3、HashTable中存放的數據允許將null作為鍵或值，而HashMap則不支持。 # List接口的常用操作 List接口是Collection的子接口，這就意味著：除開Collection接口提供的方法列表之外，它又根據自身特性新增了一些額外的方法。 所謂數據存放的容器，所涉及的操作自然離不開“增刪改查”。那就不妨來看一下關于List體系下，常用的操作方法。 ### List接口的常用方法列表 1.添加操作 - void add(index,element);??? //在列表的指定位置插入元素 - void add(index,collection); //將指定collection中的所有元素都插入到列表中的指定位置 2.刪除操作 - Object remove(index): ? ? ? //移除列表中指定位置的元素 3.修改操作 - Object set(index,element);? //修改(替換)列表指定位置的元素的值 4.獲取操作 - Object get(index);????????? //獲取列表指定位置的元素的值 - int indexOf(object);??????? //獲取對象在列表中的位置,如果不包含該對象，則返回-1 - int lastIndexOf(object);??? //獲取對象在列表中最后一次出現的位置，如果不包含該對象，則返回-1 - List subList(from,to);????? //從指定起始位置from(包括)到指定結束位置to(不包括)截取列表 可以看到與其父接口Collection提供的方法列表相比，List接口新增的方法有一個顯著的特性：**可以操作角標**。 ### **ArrayList的基本應用** ~~~ package com.tsr.j2seoverstudy.collection; import java.util.ArrayList; import java.util.List; public class ArrayListTest { public static void main(String[] args) { //ArrayList容器對象的創建 ArrayList<Integer> arrayList = new ArrayList<Integer>(); List<Integer> listTemp = new ArrayList<Integer>(); //添加數據的操作 //添加單個元素 arrayList.add(1); arrayList.add(2); listTemp.add(3); listTemp.add(4); //一次性添加另一個容器內的所有元素 arrayList.addAll(listTemp); //在指定位置添加元素 arrayList.add(0, 5); //打印一次數據 printList(arrayList); System.out.println(); //刪除數據 System.out.println("刪除的元素為:"+arrayList.remove(2)); System.out.println("刪除元素值為5的元素是否成功:"+arrayList.remove(new Integer(5))); printList(arrayList); System.out.println(); //修改數據 System.out.println("修改下標為1的元素值為6，修改前的值是："+arrayList.set(1, 6)); printList(arrayList); System.out.println(); //獲取元素總個數 System.out.println("size:"+arrayList.size()); //元素截取 listTemp = arrayList.subList(0, 2); System.out.print("listTemp:"); printList(listTemp); } static void printList(List<Integer> list){ for (Integer integer : list) { System.out.print(integer + "\t"); } } } /* 輸出結果為： 5 1 2 3 4 刪除的元素為:2 刪除元素值為5的元素是否成功:true 1 3 4 修改下標為1的元素值為6，修改前的值是：3 1 6 4 size:3 listTemp:1 6 */ ~~~ ### LinkedList的基本使用 與ArrayList不同，LinkedList內部采用鏈表結構所實現，它每一個節點（Node）都包含兩方面的內容：? 節點本身的數據（data）以及下一個節點的信息（nextNode）。 之所以LinkedList對于數據的增加，刪除動作的速度更快，正是源于其內部的鏈表結構。 由于ArrayList內部采用數組結構，所以一旦你在某個位置添加或刪除一個數據，之后的所有元素都不得不跟著進行一次位移。 而對于LinkedList則只需要更改nextNode的相關信息就可以實現了，這是LinkedList的優勢。 而也正是基于鏈表結構的特性，LinkedList還新增了一些自身特有的方法。 其中最常用的是:addFirst(E e),addLast(E e),getFirst(),getLast(),removeFirst(),removeLast()等方法。 對于LinkedList中元素的基本操作方法，與ArrayList并無多大區別。 所以這里主要看一下對于LinkedList的鏈表特性和新增方法的使用方式。 根據這些特性，我們可以通過封裝LinkedList來實現我們自己的容器類。 并且，可以完成隊列，或是棧的不同存儲方式的實現。 而在面試中，也可能遇到類似問題：請分別自定義實現一個采用隊列和棧存儲方式的容器類。 那么，隊列意味著數據先進先出，而棧則意味著數據先進后出的特性，正好可以通過LinkedList來實現： ~~~ package com.tsr.j2seoverstudy.collection; import java.util.LinkedList; /* * 輸出結果為： * 隊列: s1 s2 s3 s4 * 棧： s4 s3 s2 s1 */ public class QueueAndStack { public static void main(String[] args) { MyQueue q = new MyQueue(); q.add("s1"); q.add("s2"); q.add("s3"); q.add("s4"); System.out.print("隊列:"+"\t"); while (!q.isEmpty()) { System.out.print(q.get()+"\t"); } System.out.println(); System.out.print("棧："+"\t"); MyStack s = new MyStack(); s.push("s1"); s.push("s2"); s.push("s3"); s.push("s4"); while (!s.isEmpty()) { System.out.print(s.pop()+"\t"); } } } //我的隊列 class MyQueue { private LinkedList linklist; MyQueue() { this.linklist = new LinkedList(); } public void add(Object obj) { linklist.addFirst(obj); } public Object get() { return linklist.removeLast(); } public boolean isEmpty() { return linklist.isEmpty(); } } //我的棧 class MyStack { private LinkedList linklist; MyStack() { this.linklist = new LinkedList(); } public void push(Object obj) { linklist.addFirst(obj); } public Object pop() { return linklist.removeFirst(); } public boolean isEmpty() { return linklist.isEmpty(); } } ~~~ 簡而言之，如果不涉及到底層實現的“數據結構”的具體研究，而只是針對于容器自身的使用。 那么了解了不同容器之間的特點就應放在首位。因為了解了不同容器之間的差別，基本上也就對集合框架有一個不錯的掌握了。 正如ArrayList和LinkedList，它們對于操作數據提供的方法使用都是沒有太大區別的。因為它們都是基于List接口而實現的。 而針對于它們的使用，則是根據實際需求，來選擇更適合的容器類。例如說：可以考慮你的數據是否需要頻繁的增刪操作？ 如果需要，則選擇LinkedList。否則就可以選擇ArrayList，因為其訪問元素的速度更快。 # Set接口的常用操作 與同樣隸屬于Colleciton體系下的List接口不同的是，實現Set接口的容器類有著保證存放元素唯一性的特性。 Set接口的實現子類當中，最為常用的容器類分別是HashSet和TreeSet。 ### HashSet的基本使用 顧名思義，HashSet內部采用的是哈希表結構。而該容器也正是基于此特性來保證元素唯一的。 HashSet容器會通過存放的元素的類型中的hashCode方法和equals方法判斷元素是否相同。 首先經hashCode方法判斷，如果通過hashCode()方法返回的哈希值不同，則證明不是重復元素，直接存儲到哈希表中。 而如果判斷得到的元素的hashCode值相同，則接著調用對象的equal方法判斷元素是否重復。 來看一個例子： ~~~ package com.tsr.j2seoverstudy.collection; import java.util.HashSet; import java.util.Set; /* * 輸出結果為： * name:張三..age:19 * name:張三..age:19 * name:李四..age:20 */ public class HashSetDemo { public static void main(String[] args) { HashSet<Student> set = new HashSet<Student>(); set.add(new Student("張三", 19)); set.add(new Student("李四", 20)); set.add(new Student("張三", 19)); printSet(set); } static void printSet(Set<Student> set) { for (Student student : set) { System.out.println(student); } } } class Student { private String name; private int age; Student(String name, int age) { this.name = name; this.age = age; } @Override public String toString() { return new StringBuilder().append("name:").append(name) .append("..age:").append(age).toString(); } } ~~~ 從程序的輸出結果中注意到Set中存放了兩個姓名同為“張三”，年齡同為19歲的學生。 這可能與我們最初的設想偏離甚遠，不是說Set容器類保證元素唯一性嗎？為何出現重復。 這正是因為自定義的Student中并沒有對hashCode于equals方法進行覆寫。 所以HashSet容器在通過equals方法判斷元素是否重復的時候，采用的原本Object當中“obj1==obj2”的方式。 ==用于比較對象的時候，是比較內存中的地址，所以自然得到的結果是兩個對象不是相同的。 所以說，在使用HashSet容器存儲自定義對象的時候。請一定記得按照自己的需求，重新覆寫hashCode與equals方法。 修改后的Student類如下： ~~~ class Student { private String name; private int age; Student(String name, int age) { this.name = name; this.age = age; } @Override public String toString() { return new StringBuilder().append("name:").append(name) .append("..age:").append(age).toString(); } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + age; result = prime * result + ((name == null) ? 0 : name.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Student other = (Student) obj; if (age != other.age) return false; if (name == null) { if (other.name != null) return false; } else if (!name.equals(other.name)) return false; return true; } } ~~~ ### **TreeSet的基本使用** 與HashSet一樣，從命名我們就可以猜到：TreeSet內部的結構采用的是二叉樹結構。 所謂的二叉樹數據結構是指：每個結點最多有兩個子樹的有序樹，子樹有左右之分，次序不能顛倒。 TreeSet容器通過底層的二叉樹保證數據唯一性的原理基本可以分析為： 當向TreeSet容器內添加進第一個元素，二叉樹就在最頂端有了一個結點。 當插入第二個元素時，TreeSet就會用這第二個元素與該結點的元素進行比較。 假定該次插入的元素比上一個元素的結點小，就會被放在頂端節點的左子樹上。而如果較大，則放在右子樹上。 以此類推，當所有的元素完成存儲，所有左邊子樹上的元素值都較小，右邊則較大。 而比較結果為相同的元素則無法進入到該數據結構中。從而保證了數據的唯一性。 那么，同樣以上面的需求為例，我們這次利用TreeSet寫一個測試類： ~~~ package com.tsr.j2seoverstudy.collection; import java.util.Set; import java.util.TreeSet; public class TreeSetDemo { public static void main(String[] args) { TreeSet<Student> set = new TreeSet<Student>(); set.add(new Student("張三", 19)); set.add(new Student("李四", 20)); set.add(new Student("張三", 19)); printSet(set); } static void printSet(Set<Student> set) { for (Student student : set) { System.out.println(student); } } } ~~~ 當我們再次運行程序，得到的信息是這樣的：  沒錯，通過該異常打印信息我們能夠讀到的是：自定義的Student類不能轉換為Comparable。 也就是說我們定義的該類不具備比較性。我們已經說過了，二叉樹結果會針對元素進行比較。 根據結果決定其是否進入該結構，或者應當排在左邊子樹還是右邊子樹。那么，自然就應該有一個比較的方式。 而TreeSet容器對元素進行比較的方式有兩種： - 讓存儲的元素所屬類實現Comparable接口，并覆寫compareTo()方法。 - 新建比較器類，實現Comparatorj接口，并覆寫compare()方法。將比較器對象作為TreeSet的構造器的參數傳遞給TreeSet對象 假設我們選用第一種方式對Student類進行修改： ~~~ package com.tsr.j2seoverstudy.collection; import java.util.TreeSet; import java.util.Set; /* * 輸出結果為： * name:張三..age:19 * name:張三..age:19 * name:李四..age:20 */ public class HashSetDemo { public static void main(String[] args) { TreeSet<Student> set = new TreeSet<Student>(); set.add(new Student("張三", 19)); set.add(new Student("李四", 20)); set.add(new Student("張三", 19)); printSet(set); } static void printSet(Set<Student> set) { for (Student student : set) { System.out.println(student); } } } class Student implements Comparable<Student>{ private String name; private int age; Student(String name, int age) { this.name = name; this.age = age; } @Override public String toString() { return new StringBuilder().append("name:").append(name) .append("..age:").append(age).toString(); } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + age; result = prime * result + ((name == null) ? 0 : name.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Student other = (Student) obj; if (age != other.age) return false; if (name == null) { if (other.name != null) return false; } else if (!name.equals(other.name)) return false; return true; } @Override public int compareTo(Student s) { int temp = this.age - s.age; return temp == 0 ? this.name.compareTo(s.name) : temp; } } ~~~ 我們實現的compareTo方法的含義在于：先通過年齡進行比較，如果兩個對象的年齡相同，則再通過姓名進行比較。 注：compareTo方法返回的是一個int型的值，該值代表的含義是：負數代表小于，0代表對象相等，正數代表大于。 而此時運行main方法得到的輸出結果為： name:張三..age:19 name:李四..age:20 可以發現相對于HashSet來說，TreeSet除了保持了元素的唯一性之外。 還可以按照我們定義的比較方法，來保證元素的順序。 例如上面例子中實現的compareTo方法正是：讓元素按照年齡從小到大的順序排序； 如果年齡相同，則按照姓名字母從小到大的順序排序。 # Map接口的常用操作 我們已經說過，Map體系與Collection體系最大的不同之處就在于：不再采用單值，而是采用鍵值對的方式存儲元素。 也就是說，除開存儲對象本身之外，還給每個對象關聯了一張“身份證”，這張“身份證”就是所謂的“鍵”。 那么，對應的其對于元素的操作方法，自然也就有了不同。Map接口常用的方法為： **添加：** - V put(K key,V value); //將指定的值與此映射中的指定鍵關聯，如果此映射以前包含一個該鍵的映射關系，則用該指定值覆蓋舊值。返回前一個和key關聯的值，如果沒有返則回null. - void putAll(Map<? extends K,? extend V> m)//從指定映射中將所有映射關系復制到此映射中. **刪除：** - V remove(Object key); //如果存在一個鍵的映射關系，則將其從此映射中移除 - void clear(); //從此映射中移除所有映射關系 **判斷：** - boolean containsKey(Object key);? //判斷是否存在對應的鍵的映射關系。如果包含，則返回 true - boolean containsValue(Object value); //判斷是否該map內是否有一個或多個鍵映射到該指定值，如果有，則返回true. - boolean isEmpty(); //如果此映射未包含任何鍵-值映射關系，則返回 true **獲取：** - V get(Obejct key);//獲取該指定鍵所映射的值，如果此映射不包含該鍵的映射關系，則返回`null` - Set<K> keySet();? //獲取該map內包含的所有鍵的set視圖 - Set<Map.Entry<K,V>> entrySet(); //獲取該map內包含的所有映射關系的set視圖 - Collection<V> values(); //獲取該map內包含的所有值的collection視圖。 - int size();???????????? //獲取該map內所包含的映射關系的總數，如果該映射包含的元素大于 Integer.MAX_VALUE，則返回 Integer.MAX_VALUE 可以通過一個例子，來簡單的看一下對于Map容器的常用操作： ~~~ public class MapDemo { public static void main(String[] args) { Map<String, Integer> map = new HashMap<String, Integer>(); //存儲 map.put("張三", 19); map.put("李四", 18); System.out.println(map); //獲取 System.out.println("size:"+map.size()); Set<String> nameSet = map.keySet(); for (Iterator<String> it = nameSet.iterator(); it.hasNext(); ) { System<span style="font-size:12px;">.</span>out.println(map.get(it.next())); } Set<Map.Entry<String, Integer>> set = map.entrySet(); for (Iterator<Map.Entry<String, Integer>> it = set.iterator(); it.hasNext(); ) { Entry<String, Integer> entry = it.next(); String name = entry.getKey(); Integer age = entry.getValue(); System.out.println("name:"+name+"..age:"+age); } Collection<Integer> values = map.values(); for (Iterator<Integer> it = values.iterator(); it.hasNext(); ) { System.out.println(it.next()); } //刪除 System.out.println("..."+map.remove("張三")); } } ~~~ 關于Map容器的使用，可能值得注意的就是： 1.取出數據時，是根據鍵獲取該鍵映射的值。 2.Map容器本身無法進行迭代，但可以： 通過keySet()方法獲取該容器內所有鍵的Set視圖進行迭代； 通過entrySet()方法獲取該容器內所有映射關系的Set視圖進行迭代； 通過values()方法獲取該容器內所有值的Collection視圖進行迭代； 3.通過命名，就可以猜想到。與HashSet與TreeSet的使用相同。 在通過該HashMap與TreeMap的時候，請不要忘記覆寫hashcode、equals方法和添加實現比較器接口. # 總結 所謂的集合框架，究其根本其實都是對于對象數據的一個存儲容器。 之所分離出如此之多的不同容器，原因也是因為根據實際需求提供不同特性的容器。 而之所各個容器類之間具備不同的特性，也正是因為它們底層采用了不同的數據結構實現。 正如前面談到過的一樣，如果你暫時不想或者沒有經理去更深一步的了解不同數據結構的具體實現。 那么針對于集合框架中不同容器類的使用，應該掌握的重點就是，它們各自不同的特性。 因為只有掌握了其各自的優劣點，就可以根據實際的需求選擇最合適的容器來使用。 前面對于最常用的各種容器的特點都做了一個說明，而對于容器類的選擇技巧，其實簡單歸納就是： 1、思考你是只需要保存單個的值，還是希望以鍵值對(字典)的形式保存數據。 如果存儲單值，則選用Collection；如果存儲字典，則選用Map。 2、選用Collection體系時，思考你存儲的數據是否需要保證唯一性？ 如果需要，則選用Set。如果不需要，則選用List。 2.1、如果選用的是List，則考慮元素是否涉及到頻繁的增刪操作。 ??? 如果是，則選用LinkedList；如果不是，則選用ArrayList。 2.2、如果選用的是Set，則考慮是否需要指定存儲順序。 ??? 如果是，則選用TreeSet；如果不是，則選用HashSet。 ??? 另外一種情況，如果不需要自定義順序，而希望讓元素按存儲的先后順序排序，則可以直接選用LinkedHashSet。 3、當選用Map體系時，與Set的選擇一樣。 如果需要按指定存儲順序，則選用TreeMap。如果不需要則選用HashMap。 如果想讓元素按照存儲的先后順序進行排列，則選用LinkedHashMap。