本篇文章主要是總結了java容器中的相關(guān)知識點(diǎn)，包括容器層次結構、類(lèi)圖結構，Collection接口的詳細信息，以及Collection的一個(gè)重要子接口List接口的相關(guān)知識點(diǎn)總結。其中涉及到一些類(lèi)如ArrayList、LinkedList、Vector、Stack、CopyOnWriteArrayList等的底層數據結構、實(shí)現機制及用法等的學(xué)習總結。
Java容器類(lèi)庫的用途是保存對象，根據數據結構不同將其劃分為兩個(gè)不同的概念
（1） Collection，一個(gè)獨立元素的序列，其中List按照元素的插入順序保存元素，而set不能有重復元素，Queue按照先進(jìn)先出（FIFO）的方式來(lái)管理數據，Stack按照后進(jìn)先出（LIFO）的順序管理數據。
（2） Map，一組鍵值對（key-value）對象的序列，可以使用key來(lái)查找value，其中key是不可以重復的，value可以重復。我們可以稱(chēng)其為字典或者關(guān)聯(lián)數組。其中HashMap是無(wú)序的，TreeMap是有序的，WeakHashMap是弱類(lèi)型的，Hashtable是線(xiàn)程安全的。
下面這張圖來(lái)自于Thinking in Java Fourth Edition第十七章：
除上面圖中畫(huà)到的內容外在java.util.concurrent包中也實(shí)現了大量的線(xiàn)程安全的集合類(lèi)，可以很方便的使用。如ConcurrentHashMap、CopyOnWriteArrayList、CopyOnWriteArraySet等。
二．Collection接口
由集合類(lèi)圖結構可以得知Collection接口是Java語(yǔ)言中最基本的集合接口，在JDK中沒(méi)有直接提供Collection接口的具體實(shí)現類(lèi)，Collection的功能實(shí)現類(lèi)主要是對它的兩個(gè)更具體的子接口List和Set的具體實(shí)現類(lèi)。但是在Collection接口中定義了一套通用操作的實(shí)現方法和命名規則。
在JDK幫助文檔中可以看到Collection接口以及各個(gè)子接口、各種形式實(shí)現類(lèi)的說(shuō)明。
對Collection接口的實(shí)現類(lèi)構造方法一般至少有下面兩種：一個(gè)是void（無(wú)參數）構造方法，用于創(chuàng )建空的Collection對象實(shí)例；另一個(gè)是帶有一個(gè)Collection類(lèi)型參數的構造方法，用于創(chuàng )建一個(gè)具有與其參數相同元素的Collection對象實(shí)例。例如HashSet類(lèi)的構造方法有下面四種：
a) HashSet()：構造一個(gè)初始容量為16、加載因子為0.75的HashSet類(lèi)的實(shí)例對象；
b) HashSet(Collection<? extends E> c)：構造一個(gè)包含指定集合對象的HashSet類(lèi)的對象實(shí)例。
c) HashSet(int initialCapacity)：構造一個(gè)指定初始容量的HashSet類(lèi)的實(shí)例對象。
d) HashSet(int initialCapacity, float loadFactor)：構造一個(gè)指定初始容量以及指定加載因子的HashSet類(lèi)的實(shí)例對象。
Collection接口中共定義了15個(gè)通用的方法：
a) Collection接口方法清單
a) 添加和刪除集合中的某個(gè)元素
· boolean add(E o) ： 將指定的元素追加到集合當中
· boolean remove(Object o) : 將指定的元素從集合中刪除
b) 查詢(xún)與集合有關(guān)的數據
· int size() : 返回此集合中元素的個(gè)數
· boolean isEmpty() : 測試此集合是否為空
· boolean contains(Object element) : 測試此集合中是否有該元素
· Iterator<E> iterator() : 返回此集合中的各個(gè)元素進(jìn)行迭代的迭代器
c) 對若干個(gè)元素以組為單位進(jìn)行操作
· boolean containsAll(Collection<?> c) : 判斷此集合是否包含給定的一組元素，包含返回true，否則false
· boolean addAll(Collection<? extends E> c) : 將指定集合中的所有元素都添加到當前集合中
· void clear() : 移除此集合中的所有元素
· boolean removeAll(Collection<?> c) : 移除此集合中那些也包含在指定集合中的元素（求集合的差集）
· boolean retainAll(Collection<?> c) : 僅保留此集合中那些也包含在指定集合中的元素（求集合的交集）
d) 將集合轉換成Object類(lèi)型的對象數組
· Object[] toArray() : 返回包含此集合中所有元素的數組
· <T> T[] toArray(T[] a) : 返回包含此集合中所有元素的數組；返回數組的運行時(shí)類(lèi)型與指定數組的運行時(shí)類(lèi)型相同
1. List接口及其實(shí)現類(lèi)
List接口中方法清單
List可以將元素維護在特定的序列中，并且允許一個(gè)相同元素在集合中多次出現。List接口在Collection接口的基礎上增加了大量的方法，使得可以在List中間插入和移除元素。除了Abstract類(lèi)之外，在學(xué)習中比較常用的類(lèi)有ArrayList（基于數組實(shí)現），LinkedList（基于循環(huán)鏈表實(shí)現），Vector（基于數組實(shí)現，線(xiàn)程安全），Stack（是Vector的子類(lèi)，基于數組實(shí)現），CopyOnWriteArrayList（基于數組實(shí)現，線(xiàn)程安全）
List接口中提供的面向位置操作的各種方法：（集合中已有的方法略去）
· void add(int index, E element) : 在列表的指定位置插入指定元素。
· boolean addAll(int index, Collection<? extends E> c) : 將指定集合中的所有元素插入到集合中的指定位置。
· E get(int index) : 返回集合中指定位置的元素。
· int indexOf(Object o) : 返回指定對象在集合中第一次出現的索引，從0位置開(kāi)始，返回-1為不存在該元素。
· int lastIndexOf(Object O) : 返回指定對象在集合中最后一次出現的索引位置，返回-1為不存在。
· ListIterator<E> listIterator() : 以正確的順序返回集合中元素的列表迭代器。
· ListIterator<E> listIterator(int index) : 以正確的順序返回集合中元素的列表迭代器，從集合中指定的位置開(kāi)始。
· E remove(int index) : 移除集合中指定位置的元素。
· E set(int index, E element) : 用指定元素替換集合中指定位置的元素。
· List<E> subList(int fromIndex, int toIndex) : 返回集合中指定的fromIndex（包括）和toIndex(不包括)之間的部分視圖。
List接口提供了名稱(chēng)為L(cháng)istIterator的特殊迭代器。
List在數據結構中分別表現為數組、向量、鏈表、堆棧、隊列等形式。
ArrayList的特點(diǎn)、實(shí)現機制及使用方法
a) ArrayList特點(diǎn)：
ArrayList顧名思義，它是用數組實(shí)現的一種線(xiàn)性表。常規數組不具備自動(dòng)遞增的功能，但是ArrayList在使用時(shí)我們不必考慮這個(gè)問(wèn)題?？梢灾苯影次恢眠M(jìn)行索引，查找和修改速度較快，缺點(diǎn)是插入或者刪除速度較慢。在執行插入刪除時(shí)調用的是System.arraycopy方法，是一個(gè)native方法。
b) ArrayList的實(shí)現機制：
在JDK源碼中可以看到ArrayList總共只有兩個(gè)屬性，一個(gè)是Object數組類(lèi)型的elementData，一個(gè)是int型的size。
在構造方法中也可以看到，無(wú)參構造方法調用的是this(10)，調用的帶一個(gè)參數的構造方法，默認無(wú)參構造方法分配一個(gè)size為10的數組。按照Collection接口中定義的構造方法，它必須有一個(gè)通過(guò)其它集合對象構造自身對象的方法。這是一個(gè)相對比較簡(jiǎn)單的線(xiàn)性表。并且JDK中提供了大量的比較好用的方法可以使用。該動(dòng)態(tài)數組在存儲空間不足時(shí)按照下面方法重新分配空間：
newCapacity = (oldCapacity*3)/2 + 1;
if(newCapacity < minCapacity) newCapacity = minCapacity;
c) 使用方法（ArrayList的使用方法其實(shí)是比較簡(jiǎn)單，但是也是比較常用和好用的，個(gè)人感覺(jué)）
下面例子為了盡可能多的用到ArrayList的方法，可能看起來(lái)沒(méi)有多大意義
import java.util.ArrayList;import java.util.Iterator;import java.util.List;public class ExampleForArrayList { public static void main(String[] args) { String[] str = new String[]{"My", "name", "is", "Wang", "Yan", "tao"}; List<String> ls1 = new ArrayList<String>(10); //把數組中的數據添加到ls1中 for(int i=0; i<str.length; i++) { ls1.add(str[i]); } //使用ls1來(lái)構造ls2 List<String> ls2 = new ArrayList<String>(ls1); System.out.println("ls2中元素的個(gè)數：" + ls2.size()); System.out.println("is在ls2中的位置：" + ls2.indexOf("is")); System.out.println("Wang在ls2中最后一次出現的位置：" + ls2.lastIndexOf("Wang")); System.out.println("ls2中的所有元素："); //這里使用iterator遍歷 Iterator<String> it = ls2.listIterator(); while(it.hasNext()) { System.out.println(it.next()); } //我一般使用下面方法遍歷,或者基本的for循環(huán)遍歷 for(String tmp : ls2) { System.out.println(tmp); } }}LinkedList的特點(diǎn)、實(shí)現機制及使用方法
a) LinkedList的特點(diǎn)：
現在發(fā)現java中類(lèi)的命名真是太好了，比如這個(gè)吧，一看就知道它使用鏈表實(shí)現的。鏈表操作的優(yōu)點(diǎn)就是插入刪除比較快，但是不能按索引直接存取，所以執行更新操作比較快，執行查詢(xún)操作比較慢。它的整體特性由于A(yíng)rrayList。
b) LinkedList實(shí)現機制：
查看jdk源碼可以得知每個(gè)元素在LinkedList中都是一個(gè)LinkedList.Entry的實(shí)例對象。該類(lèi)定義如下：
private static class Entry<E> { E element; Entry<E> next; Entry<E> previous; Entry(E element, Entry<E> next, Entry<E> previous) { this.element = element; this.next = next; this.previous = previous; }}在構造方法中這樣的定義：
header.next = header.previous = header;
也就是說(shuō)LinkedList底層使用一個(gè)循環(huán)雙向鏈表實(shí)現的。
LinkedList實(shí)現了許多對first和last元素進(jìn)行操作的方法，比如set、get、remove等。
雖然LinkedList獲取指定位置的元素時(shí)較ArrayList按索引獲取較慢，但是JDK中對get方法做了優(yōu)化：
if (index < (size >> 1)) { for (int i = 0; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; }雖然還是順序挨個(gè)查找，但是已經(jīng)做了優(yōu)化。size>>1 == size/2，移位運算要比除法運算效率高的多。
c) LinkedList和ArrayList的使用方法類(lèi)似，只是看自己的需要進(jìn)行選擇了。除此之外LinkedList還實(shí)現了棧操作的所有方法。
Vector的特點(diǎn)、實(shí)現機制及使用方法
a) Vector的特點(diǎn)：
ArrayList實(shí)現的是一種動(dòng)態(tài)數組，LinkedList是一種雙向循環(huán)鏈表，Vector并未在前兩者的基礎上做實(shí)現，而是直接實(shí)現了List接口。Vector中的所有方法前面都有一個(gè)synchronized關(guān)鍵字做修飾。Vector是有序可重復的。
b) Vector的實(shí)現機制：
我暫時(shí)還不理解為什么要實(shí)現Vector這個(gè)類(lèi)，和ArrayList基本是一樣的，不一樣的是Vector是線(xiàn)程安全的，但是Collections里面提供了將非線(xiàn)程安全的集合轉換成線(xiàn)程安全的集合的方法。
c) Vector的使用方法(與ArrayList使用方法類(lèi)似)
Stack的特點(diǎn)、實(shí)現機制及使用方法
a) Stack的特點(diǎn)：
Stack（棧）是一種后進(jìn)先出的序列，主要操作有判空、壓棧、退棧、取棧頂元素等。
b) Stack的實(shí)現機制：
Stack繼承自Vector，同樣使用數組保存數據，根據該數據結構的特點(diǎn)進(jìn)行了限制性操作。JDK中共提供了6個(gè)方法用于實(shí)現特定要求的操作：
· Stack() : 構造一個(gè)空的棧
· empty() : 判斷棧是否為空
· peek() : 查看棧頂元素并返回棧頂對象
· pop() : 刪除棧頂元素并返回棧頂對象
· push(E element) : 將一個(gè)元素壓入當前棧中
· search(Object o) : 查看指定對象是否在當前棧中
c) Stack的使用方法
import java.util.Stack;public class ExampleForStack { /* * 這是一個(gè)非常簡(jiǎn)單的例子 * 用于展現棧的這種后進(jìn)先出的特性 * 逆序打印一個(gè)字符串 */ public static void main(String[] args) { String str = "abcdefghijklmnopqrstuvwxyz"; Stack<Character> stack = new Stack<Character>(); for(char ch : str.toCharArray()) { stack.push(ch); } while(!stack.empty()) { System.out.print(stack.pop()); } }}CopyOnWriteArrayList的特點(diǎn)、實(shí)現機制及使用方法
a) CopyOnWriteArrayList的特點(diǎn)：
CopyOnWriteArrayList是java.util.concurrent包中的一個(gè)類(lèi)，此類(lèi)是一個(gè)線(xiàn)程安全類(lèi)。由于用到了ReentrantLock（重入鎖）同步，所以在修改效率上較ArrayList差。
b) CopyOnWriteArrayList的實(shí)現機制：
剛開(kāi)始覺(jué)得這個(gè)名字好長(cháng)，并且感覺(jué)奇怪，為什么要這樣命名？首先這是一個(gè)為了實(shí)現并發(fā)同步而設計的類(lèi)，那么在所有與修改方法相關(guān)的地方均會(huì )使用lock來(lái)保證同步。Copy-on-write的英文釋義是“寫(xiě)時(shí)拷貝、寫(xiě)時(shí)復制”，現在看來(lái)覺(jué)得這個(gè)名字就更容易理解了，那么這個(gè)類(lèi)到底是怎么實(shí)現的呢？面試官說(shuō)：“踏踏實(shí)實(shí)看源碼”。-_-|||
首先說(shuō)一下寫(xiě)方法：
· public E set(int index, E element) : 將指定位置的元素使用element替換掉。JDK中的源碼如下：
public E set(int index, E element) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); Object oldValue = elements[index]; if (oldValue != element) { int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len); newElements[index] = element; setArray(newElements); } else { setArray(elements); } return (E)oldValue; } finally { lock.unlock(); }}在源碼中可以看出，首先執行寫(xiě)入（包括set,add,remove等）操作時(shí)，首先得到一把當前對象的重入鎖，其次獲得當前對象元素的一個(gè)拷貝（寫(xiě)時(shí)拷貝），再次用修改后的元素替換掉原來(lái)的元素，最終釋放鎖。
這里引用兩個(gè)常識：
1、JAVA中“=”操作只是將引用和某個(gè)對象關(guān)聯(lián)，假如同時(shí)有一個(gè)線(xiàn)程將引用指向另外一個(gè)對象，一個(gè)線(xiàn)程獲取這個(gè)引用指向的對象，那么他們之間不會(huì )發(fā)生ConcurrentModificationException，他們是在虛擬機層面阻塞的，而且速度非?？?，幾乎不需要CPU時(shí)間。
2、JAVA中兩個(gè)不同的引用指向同一個(gè)對象，當第一個(gè)引用指向另外一個(gè)對象時(shí)，第二個(gè)引用還將保持原來(lái)的對象。
· public void add(E e) : 向當前對象中加入指定元素。實(shí)現方式與set相同，均是copy-on-write。
· 還有remove等修改內容的操作。
除寫(xiě)方法（修改，刪除，添加）外，CopyOnWriteArrayList類(lèi)還提供了ArrayList相類(lèi)似和功能更齊全的方法供選擇使用。
· public ListIterator<E> listIterator() : 該方法返回一個(gè)ListIterator類(lèi)型的迭代器，但是該迭代器的真正類(lèi)型是COWIterator類(lèi)型的，不允許有插入、刪除、添加等方法。
使用方法與ArrayList類(lèi)似，只是用時(shí)選擇的問(wèn)題。因為在寫(xiě)操作時(shí)大量使用了System.arrayCopy方法，所以在效率上會(huì )有所降低。因此它適合使用在讀操作遠遠大于寫(xiě)操作的場(chǎng)景中。
聯(lián)系客服
