集合接口：6個(gè)接口（短虛線(xiàn)表示），表示不同集合類(lèi)型，是集合框架的基礎?！ 〕橄箢?lèi)：5個(gè)抽象類(lèi)（長(cháng)虛線(xiàn)表示），對集合接口的部分實(shí)現?？蓴U展為自定義集合類(lèi)?！ ?shí)現類(lèi)：8個(gè)實(shí)現類(lèi)（實(shí)線(xiàn)表示），對接口的具體實(shí)現。
迭代器
對于鏈表、集合來(lái)說(shuō)，可以使用find()方法來(lái)查找一個(gè)給定的元素，這個(gè)方法從頭開(kāi)始考察每個(gè)元素，直到找到一個(gè)元素的值和給定的值匹配。但是，我們并沒(méi)有在上面遍歷的任何手段，可以查找指定節點(diǎn)。
在數組中，查找元素很容易，可以用下標去跟蹤元素的位置，在鏈表和集合中，反復的使用find()方法查找是不合理的，如果有一種方式，能從連接點(diǎn)到下一個(gè)節點(diǎn)，是比較合理的。
假如我們保存一個(gè)元素，表示當前的元素，并且它可以移動(dòng)的，訪(fǎng)問(wèn)下面的元素，那么這個(gè)引用放在哪里比較合適呢？比如鏈表或者集合本身的一個(gè)字段，但是如果放在內部，那么意味著(zhù)，一個(gè)實(shí)例只能有一個(gè)迭代中的引用，如果我們想多重的去遍歷，那么就會(huì )無(wú)能為力。所以需要在用戶(hù)想要遍歷的時(shí)候，那么便需要創(chuàng )建一個(gè)引用保存在外部，這樣，用戶(hù)就可以創(chuàng )建任意個(gè)引用。
Class ListIterator{
Private Link current;
}
Current字段包含迭代器當前指向的連接點(diǎn)的一個(gè)引用。迭代器需要遍歷集合或者鏈表，所以通常，他需要下面幾個(gè)方法：
Reset():把迭代器設在表頭
nextLink：把迭代器移動(dòng)到下一個(gè)鏈節點(diǎn)
getCurrent：返回迭代器當前指向的節點(diǎn)
atEnd：如果迭代器到達末尾，返回true
insertAfter：在迭代器后面插入一個(gè)新節點(diǎn)
insertBefore：在迭代器前插入一個(gè)新節點(diǎn)
deleteCurrent：刪除迭代器所指向連接點(diǎn)
| boolean | hasNext() |
| next() | |
| void | remove() |
另外，還可以看到，實(shí)現了List接口的元素，需要實(shí)現下面兩個(gè)方法：
| listIterator() | |
| listIterator(int index) |
ListIterator：除了允許 Iterator 接口提供的正常操作外，該迭代器還允許元素插入和替換，以及雙向訪(fǎng)問(wèn)。還提供了一個(gè)方法來(lái)獲取從列表中指定位置開(kāi)始的列表迭代器
ArrayList al=new ArrayList();
al.add("123");
al.add("456");
al.add("789");
al.add("111");
al.add("222");
ListIterator it=al.listIterator();
it.add("123aa");
//該操作返回到next元素的下一個(gè)元素之前，所以第一次不能打印出123aa
while(it.hasNext())
{
System.out.println(it.next());
/*
* 這會(huì )引發(fā)一個(gè)快速失敗恢復java.util.ConcurrentModificationException
*/
//al.add("1234");
}
it.remove();
System.out.println("------------------");//可以看出123aa再最頂部
while(it.hasPrevious()){
System.out.println(it.previous());
}
System.out.println("------------------");//現在能夠打印了
while(it.hasNext()){
System.out.println(it.next());
}
結果：
123
456
789
111
222
------------------
111
789
456
123
123aa
------------------
123aa
123
456
789
111
集合
對于任意對象或者元素，想要盡可能以常規方式處理一組元素時(shí)候，就是用這個(gè)接口，他有一些集合的基本方法，比如add、remove、size、iterator等等。
而AbstractorCollection類(lèi)提供了具體“集合框架”類(lèi)的基本功能雖然我們可以自己去實(shí)現Collection接口的所有方法，但是那樣將會(huì )要做大量的工作。如果只是要實(shí)現一個(gè)不可修改的collection，那么只需要擴展這個(gè)類(lèi)，并提供方iterator和szie方法實(shí)現，其他方法，比如，contains toArray finishToArray remove containsAll addAll removeAll，都已經(jīng)有實(shí)現。
如果要實(shí)現可修改的collection，那么還得重寫(xiě)add，并且iterator方法返回的迭代器必須另外實(shí)現其remove方法。
剩下的兩個(gè)就是比較重要的List和Set。
List接口，允許用戶(hù)在列表中每個(gè)元素的位置進(jìn)行精確的控制，并且可以根據元素的整數索引，訪(fǎng)問(wèn)元素，并搜索列表中的元素。并且他允許重復的元素和null元素，它是有序的，順序就是插入順序。List中有4中對元素進(jìn)行定位(索引)的訪(fǎng)問(wèn)方法，比如基于索引的get方法，某些實(shí)現，可能get方法和迭代的執行時(shí)間差不多，不過(guò)，在不知道實(shí)現的時(shí)候，通常，迭代遍歷列表，優(yōu)于索引遍歷列表。
public static void main(String[] args){
List list=new ArrayList();
list.add("a");
list.add("b");
list.add("c");
list.add("c");
Iterator it=list.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
}
輸出結果：
a
b
c
c
AbstractList
List的骨干實(shí)現，就像AbstractCollection是Collection的骨干實(shí)現，要實(shí)現一些隨機訪(fǎng)問(wèn)存儲，繼承他，我們可以少寫(xiě)很多代碼。（比如ArrayList，是用數組實(shí)現的）
/**
*返回迭代器已經(jīng)有實(shí)現、indexOf等也已經(jīng)通過(guò)迭代器實(shí)現
* 要實(shí)現不可修改的列表，程序員只需要擴展此類(lèi)，并提供get(int)和size()方法實(shí)現。
* 要實(shí)現可修改的列表，還必須另寫(xiě)set、add、remove等方法。
*
*/
public class MyAbstractListTest extends AbstractList<Test1>{
private Test1[] t1=new Test1[10];
@Override
public Test1 get(int index) {
//可以檢查下范圍
return t1[index];
}
@Override
public int size() {
return t1.length;
}
}
可以參考下ArrayList的代碼。
AbstractSequentialList
從某種意義上說(shuō)，此類(lèi)與在列表的列表迭代器上實(shí)現“隨機訪(fǎng)問(wèn)”方法（get(int index)、set(int index, Object element)、set(int index, Object element)、add(int index, Object element) 和 remove(int index)）的 AbstractList 類(lèi)相對立，而不是其他關(guān)系。
ArrayList
如果要支持隨機訪(fǎng)問(wèn)（因為他內部是數組實(shí)現的），而不必在除尾部的任何位置插入或除去元素，那么，ArrayList 提供了可選的集合。
ArrayList類(lèi)封裝了一個(gè)動(dòng)態(tài)再分配的Object[]數組。每個(gè)ArrayList對象有一個(gè)capacity。這個(gè)capacity表示存儲列表中元素的數組的容量。當元素添加到ArrayList時(shí)，它的capacity在常量時(shí)間內自動(dòng)增加?！ ?strong style="mso-bidi-font-weight: normal">在向一個(gè)ArrayList對象添加大量元素的程序中，可使用ensureCapacity方法增加capacity。這可以減少增加重分配的數量。
如果list的容量小的話(huà)，則會(huì )進(jìn)行數組的copy。這樣原來(lái)的數組 就被廢棄了，又新建了一個(gè)數組。
所以，如果進(jìn)行大量元素的添加，為了效率考慮，構造時(shí)指定容量，或者調用
ensureCapacity()
具體解釋?zhuān)?jiàn)以下代碼(JDK1.6update18)：
public Object get(int index) {
RangeCheck(index);
return elementData[index];
}
可以看隨機訪(fǎng)問(wèn)效率是很高的，和數組的索引訪(fǎng)問(wèn)是一樣的，方式設計到索引值都會(huì )先檢查邊界。
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
arraycopy(Object src,
int srcPos, Object dest, int destPos, int length) 源數組中位置在 srcPos 到 srcPos+length-1 之間的組件被分別復制到目標數組中的 destPos 到 destPos+length-1 位置。
另外，還有一個(gè)writeObject和readObject方法，因為elementData聲明為transient，所以必須手動(dòng)串行化化。
LinkedList
但如果，您不要頻繁的從列表的中間位置添加和除去元素，而只要順序的訪(fǎng)問(wèn)列表元素，那么，LinkedList 實(shí)現更好。LinkedList源碼分析：
主要實(shí)現了List,Queue接口，通過(guò)繼承一個(gè)模板類(lèi)AbstractSequentialList來(lái)實(shí)現鏈表
有兩個(gè)成員變量，一個(gè)是Entry-靜態(tài)內部類(lèi),還有一個(gè)size，代表鏈表的實(shí)際大小，看下Entry:
private static class Entry<E> {
是一個(gè)靜態(tài)內部類(lèi)，包含三個(gè)成員變量，element-數據項，next-指向下一條數據項，previous-指向前一條數據項，可以看出這是一個(gè)雙向鏈接，每個(gè)節點(diǎn)
都會(huì )指向前一個(gè)節點(diǎn)和后一個(gè)節點(diǎn)。
這里簡(jiǎn)要說(shuō)明一下為什么要使用靜態(tài)內部類(lèi)：
摘自網(wǎng)絡(luò )：
· 靜態(tài)內部類(lèi)的實(shí)例不會(huì )自動(dòng)持有外部類(lèi)的特定實(shí)例的引用, 因此在創(chuàng )建內部類(lèi)的實(shí)例時(shí), 不必創(chuàng )建外部類(lèi)的實(shí)例.
· 靜態(tài)內部類(lèi)可以直接訪(fǎng)問(wèn)外部類(lèi)的靜態(tài)成員, 如果要訪(fǎng)問(wèn)外部類(lèi)的實(shí)例成員, 就必須通過(guò)外部類(lèi)的實(shí)例去訪(fǎng)問(wèn)
· 靜態(tài)內部類(lèi)中可以定義靜態(tài)成員和實(shí)例成員
· 客戶(hù)類(lèi)可以通過(guò)完整的類(lèi)名直接訪(fǎng)問(wèn)靜態(tài)內部類(lèi)的靜態(tài)成員.
獲取數據,get(int index)：
Java代碼
public E get(int index) {
return entry(index).element;
}
我們看下entry方法：
private Entry<E> entry(int index) {
//判斷邊界--前置條件判斷
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
//如果index小于size，則向前遍歷，否則向后遍歷
Entry<E> e = header;
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;
}
return e;
}
這里我們看到在鏈表中取值時(shí)，需要遍歷整個(gè)鏈表，相對于ArrayList的隨機訪(fǎng)問(wèn)，會(huì )有所緩慢
4，優(yōu)點(diǎn)與缺點(diǎn)
優(yōu)點(diǎn)：
LinkedList的中間插入或刪除一個(gè)元素的開(kāi)銷(xiāo)是固定的
缺點(diǎn)：
LinkedList不支持高效的隨機元素訪(fǎng)問(wèn)
LinkedList類(lèi)添加了一些處理列表兩端元素的方法。
http://www.javaeye.com/topic/553199 Java集合框架之LinkedList及 ListIterator實(shí)現源碼分析
現在：
Multiset<String> m =TreeMultiset.create(Arrays.asList(args));
System.out.println(m);
Set
Set接口，無(wú)序的，不允許包含重復元素，并且最多包含一個(gè)null元素，模仿的是數學(xué)上的Set（集合）抽象。它并沒(méi)有List的基于索引的訪(fǎng)問(wèn)方法。Set接口沒(méi)有引入新方法，所以Set就是一個(gè)Collection，只不過(guò)其行為不同。
@SuppressWarnings("unchecked")
public static void main(String[] args){
Set set=new HashSet();
set.add("a");
set.add("c");
set.add("c");
set.add("b");
Iterator it=set.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
}
輸出：
b
c
a
SortedSet
“集合框架”提供了個(gè)特殊的Set接口：SortedSet，它保持元素的有序順序。SortedSet接口為集的視圖(子集)和它的兩端（即頭和尾）提供了訪(fǎng)問(wèn)方法。當您處理列表的子集時(shí)，更改視圖會(huì )反映到源集。此外，更改源集也會(huì )反映在子集上。發(fā)生這種情況的原因在于視圖由兩端的元素而不是下標元素指定。
插入有序集合的所有元素都必須實(shí)現 Comparable 接口（或者被指定的 Comparator 所接受）。另外，所有這些元素都必須是可相互比較的：e1.compareTo(e2)（或 comparator.compare(e1, e2)）對于有序集合中的任意元素 e1 和 e2 都不能拋出 ClassCastException。試圖違反這些限制將導致違反規則的方法或者構造方法調用拋出 ClassCastException。TreeSet類(lèi)是它的唯一一份實(shí)現
AbstractSet抽象類(lèi)
AbstractSet類(lèi)覆蓋了Object類(lèi)的equals()和hashCode()方法，以確保兩個(gè)相等的集返回相同的哈希碼。若兩個(gè)集大小相等且包含相同元素，則這兩個(gè)集相等。按定義，集的哈希碼是集中元素哈希碼的總和。因此，不論集的內部順序如何，兩個(gè)相等的集會(huì )有相同的哈希碼。
HashSet類(lèi)類(lèi)和TreeSet類(lèi)
HashSet是通過(guò)HashMap實(shí)現的,TreeSet是通過(guò)TreeMap實(shí)現的,只不過(guò)Set用的只是Map的key。Map的key和Set都有一個(gè)共同的特性就是集合的唯一性.TreeMap更是多了一個(gè)排序的功能。
考慮到效率，添加到 HashSet 的對象需要采用恰當分配哈希碼的方式來(lái)實(shí)現hashCode()方法。雖然大多數系統類(lèi)覆蓋了 Object中缺省的hashCode()和equals()實(shí)現，但創(chuàng )建您自己的要添加到HashSet的類(lèi)時(shí)，別忘了覆蓋 hashCode()和equals()。
鏈接的哈希集合有兩個(gè)影響其性能的參數：初始容量 和加載因子。容量 是哈希表中桶的數量，初始容量只是哈希表在創(chuàng )建時(shí)的容量。加載因子 是哈希表在其容量自動(dòng)增加之前可以達到多滿(mǎn)的一種尺度。當哈希表中的條目數超出了加載因子與當前容量的乘積時(shí)，通過(guò)調用 rehash 方法將容量翻倍。
看下HashSet的源碼（內部用Map實(shí)現）：
private transient HashMap<E,Object> map;
// 定義一個(gè)虛擬的 Object 對象作為 HashMap 的 value
private static final Object PRESENT = new Object();
TreeSet內部其實(shí)是SortedMap實(shí)現，不過(guò)現在Java6又多了個(gè)NavigableMap接口，暫時(shí)不知道干嘛的。。。。。
LinkedHashSet
LinkedHashSet擴展HashSet。如果想跟蹤添加給HashSet的元素的順序，LinkedHashSet實(shí)現會(huì )有幫助。LinkedHashSet的迭代器按照元素的插入順序來(lái)訪(fǎng)問(wèn)各個(gè)元素。它提供了一個(gè)可以快速訪(fǎng)問(wèn)各個(gè)元素的有序集合。同時(shí)，它也增加了實(shí)現的代價(jià)，因為哈希表元中的各個(gè)元素是通過(guò)雙重鏈接式列表鏈接在一起的。
此實(shí)現與 HashSet 的不同之外在于，后者維護著(zhù)一個(gè)運行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，即按照將元素插入到集合中的順序（插入順序）進(jìn)行迭代。注意，插入順序不 受在集合中重新插入的 元素的影響。（如果在 s.contains(e) 返回 true 后立即調用 s.add(e)，則元素 e 會(huì )被重新插入到集合 s 中。）
看下LinkedHashSet的源碼，可以看到他繼承了HashSet：
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable
聯(lián)系客服
