Collection集合
查看上面的結(jié)構(gòu)圖可以發(fā)現(xiàn)蜓肆，Collection接口繼承了Iterable接口鼎天，在Iterable接口中就擁有iterator()方法舀奶，可以和上面的Iterator接口聯(lián)系起來；往下看又存在Queue子接口斋射、Set子接口育勺、List子接口，同時(shí)還有集合抽象基礎(chǔ)類AbstractCollection罗岖，其余的抽象基礎(chǔ)類AbstractList涧至、AbstractSet、AbstractQueue都繼承集合抽象基礎(chǔ)類桑包，同時(shí)又實(shí)現(xiàn)自己內(nèi)部的接口List南蓬、Set、Queue哑了。故而理解這些抽象基礎(chǔ)類之后可以更容易的分析之后的具體類赘方。
List
SubList類
在java.util包下，可以找到幾個(gè)List類垒手，如ArrayList蒜焊、LinkedList和SubList。而這些類都是繼承于AbstractList類科贬，其中有個(gè)方法subList()很有趣，如下所示：
/**
**AbstractList類中subList方法源碼
**/
public List subList(int i, int j) {
return ((List) ((this instanceof RandomAccess) ? new RandomAccessSubList(this, i, j)
: new SubList(this, i, j)));
}
其中RandomAccess僅僅只是個(gè)標(biāo)記接口，內(nèi)部不存在任何的方法榜掌。在上面的方法運(yùn)行后會(huì)返回一個(gè)SubList對象优妙，很重要的一點(diǎn)：在new這個(gè)對象的時(shí)候，傳入的是當(dāng)前的this憎账，點(diǎn)開SubList類的源碼可知套硼，其擁有字段如下：
/**
**SubList類源碼 字段
**/
private AbstractList l;
private int offset;
private int size;
private int expectedModCount;
其中擁有的構(gòu)造器如下：
/**
**SubList類源碼 構(gòu)造器
**/
SubList(AbstractList abstractlist, int i, int j) {
if (i < 0)
throw new IndexOutOfBoundsException((new StringBuilder()).append("fromIndex = ").append(i).toString());
if (j > abstractlist.size())
throw new IndexOutOfBoundsException((new StringBuilder()).append("toIndex = ").append(j).toString());
if (i > j) {
throw new IllegalArgumentException((new StringBuilder()).append("fromIndex(").append(i)
.append(") > toIndex(").append(j).append(")").toString());
} else {
** l = abstractlist;**
** offset = i;**
** size = j - i;**
** expectedModCount = l.modCount;**
return;
}
}
如上所示，這里是直接把當(dāng)前類this傳給了SubList胞皱，而不是重新創(chuàng)建一個(gè)對象邪意。故而AbstractList類的subList方法返回的僅僅是一個(gè)視圖，對它的返回對象做的任何操作都會(huì)反映到原來的List中反砌，其中size=j-i雾鬼，表明它獲取的長度并不包括原數(shù)組下標(biāo)j的數(shù)據(jù)。當(dāng)然并不是說不好宴树，它還是有個(gè)很好的用法的策菜，如下所示：
/**
**subList的應(yīng)用
**/
public static void main(String[] arg0){
ArrayList<String> list = new ArrayList<String>();
list.add("test1");
list.add("test2");
list.add("test3");
list.add("test4");
list.add("test5");
list.add("test6");
list.subList(1, 4).clear();
for(String s:list){
System.out.println(s);
}
}
輸出：
test1
test5
test6
可以看到，這樣可以很方便的對list中間的部分?jǐn)?shù)據(jù)進(jìn)行處理酒贬，SubList還提供了一些常用的方法又憨，用來操作這個(gè)視圖的數(shù)據(jù)，相應(yīng)的可以自行去了解锭吨。
ArrayList類
這個(gè)類繼承AbstractList類蠢莺，同時(shí)實(shí)現(xiàn)List、RandomAccess零如、Cloneable浪秘、Serializable等四個(gè)接口。打開源碼可以看到埠况，這個(gè)類有如下幾個(gè)字段：
/**
**ArrayList源碼 字段
**/
private transient Object elementData[]; //容器數(shù)組
private int size; //List長度
protected transient int modCount; //父類繼承而來耸携，修改的次數(shù)
如上所示，這三個(gè)字段中辕翰，功能字段只有前兩個(gè)elementData[]和size夺衍。從這里也可以看出，ArrayList的底層是使用數(shù)組elementData來實(shí)現(xiàn)的喜命，這個(gè)數(shù)組存的對象為Object沟沙。同時(shí)，它提供了三個(gè)構(gòu)造器壁榕，如下所示：
/**
*ArrayList源碼 構(gòu)造器
**/
public ArrayList(int i) {
if (i < 0) {
throw new IllegalArgumentException((new StringBuilder()).append("Illegal Capacity: ").append(i).toString());
} else {
elementData = new Object[i];
return;
}
}
public ArrayList() {
this(10);
}
public ArrayList(Collection collection)
{
elementData = collection.toArray();
size = elementData.length;
if(((Object) (elementData)).getClass() != [Ljava/lang/Object;)
elementData = Arrays.copyOf(elementData, size, [Ljava/lang/Object;);
}
在構(gòu)造器這部分可以看到矛紫，它會(huì)初始化這個(gè)數(shù)組elementData，這里支持的三種構(gòu)造器前兩種會(huì)給數(shù)組初始化長度i或者默認(rèn)長度10牌里，最后一種則是使用了Collection接口中的方法toArray()直接轉(zhuǎn)成數(shù)組颊咬。
在這字段和構(gòu)造器看完之后务甥，根據(jù)數(shù)組結(jié)構(gòu)可知，數(shù)組本身是有下標(biāo)的存在喳篇，在ArrayList中也保留了數(shù)組下標(biāo)的作用敞临，故而使得操作會(huì)變的簡單很多，比如添加add(int i,Object obj)麸澜、設(shè)置set(int i,Object obj)挺尿、刪除remove(int i)等。除此之外炊邦，還有兩個(gè)方法如下：
/**
**ArrayList
**/
public void trimToSize() {
modCount++;
int i = elementData.length;
if (size < i)
elementData = Arrays.copyOf(elementData, size);
}
public void ensureCapacity(int i) {
modCount++;
int j = elementData.length;
if (i > j) {
Object aobj[] = elementData;
int k = (j * 3) / 2 + 1;
if (k < i)
k = i;
elementData = Arrays.copyOf(elementData, k);
}
}
其中trimToSize()方法縮小數(shù)組長度编矾，類似于String中的trim()方法，而ensureCapactity()方法用來擴(kuò)容數(shù)組馁害。至此窄俏，ArrayList內(nèi)部實(shí)現(xiàn)大體上梳理完全，從實(shí)現(xiàn)方面思考自然就可以解決一些面試問題蜗细。
LinkedList類
類LinkedList不同于ArrayList裆操，它的底層并不是使用數(shù)組來寫的；查看源碼可知它繼承了AbstractSequentialList炉媒，同時(shí)實(shí)現(xiàn)了List踪区、Deque、 Cloneable吊骤、 Serializable這四個(gè)接口缎岗，其中AbstractSequentialList類繼承了AbstractList類并使用ListIterator來實(shí)現(xiàn)了List中一些有需要下標(biāo)的操作，如add(i, E)白粉；而比較特別的是Deque接口传泊，在這個(gè)接口中定義了一系列雙端隊(duì)列的操作，即兩頭都可以操作鸭巴，還增加了poll(),peek(),push(),pop()操作眷细，所以LinkedList類的操作方法看起來相比ArrayList多了一些。
下面從字段開始鹃祖，查看源碼可知溪椎，它有兩個(gè)字段如下：
/**
**LinkedList類 字段
**/
private transient Entry header;
private transient int size;
這里可以看到，字段header的類型是Entry恬口，這是個(gè)LinkedList的內(nèi)部類校读，源碼如下：
/**
** LinkedList內(nèi)部類 Entry 源碼
**/
private static class Entry {
Object element;
Entry next;
Entry previous;
Entry(Object obj, Entry entry1, Entry entry2) {
element = obj;
next = entry1;
previous = entry2;
}
}
在靜態(tài)內(nèi)部類Entry中存在三個(gè)字段，這里就可以看出為什么叫LinkedList了祖能，類LinkedList內(nèi)部實(shí)現(xiàn)并不是用數(shù)組而是保存下一個(gè)元素的地址歉秫，形成像鐵鏈一樣的結(jié)構(gòu)。這里也是說明為什么說LinkedList便于插入或者刪除操作养铸。類LinkedList的構(gòu)造器如下所示：
/**
**LinkedList類的構(gòu)造器
**/
public LinkedList() {
header = new Entry(null, null, null);
size = 0;
header.next = header.previous = header;
}
public LinkedList(Collection collection) {
this();
addAll(collection);
}
可以看到雁芙，LinkedList的size默認(rèn)初始值是0轧膘，當(dāng)然，這里也提供了入?yún)⑹?code>Collection的構(gòu)造器却特，說明這個(gè)接口下的所有類都可以轉(zhuǎn)化為LinkedList扶供。在這之后筛圆，查看它的方法就知道裂明，它的操作脫離不了Entry實(shí)例和長度size，其中Entry類的next字段和previous字段是這個(gè)類的核心操作點(diǎn)太援，根據(jù)這點(diǎn)闽晦，源碼中方法就很清楚的展示出來了，通過常見的方法就可以完成對LinkedList的操作提岔，如下所示：
/**
**LinedList類的 entry()方法
**/
private Entry entry(int i) {
if (i < 0 || i >= size)
throw new IndexOutOfBoundsException(
(new StringBuilder()).append("Index: ").append(i).append(", Size: ").append(size).toString());
Entry entry1 = header;
if (i < size >> 1) {
for (int j = 0; j <= i; j++)
entry1 = entry1.next;
} else {
for (int k = size; k > i; k--)
entry1 = entry1.previous;
}
return entry1;
}
在這個(gè)方法中通過下標(biāo)i來獲取LinkedList的數(shù)據(jù)仙蛉，也就是普通的if或or操作。其他的方法碱蒙，或調(diào)用這個(gè)方法荠瘪，或進(jìn)行類似的操作，具體的其他方法就不在這里放了赛惩。
當(dāng)然哀墓，并不是說，List下就只有這三個(gè)類喷兼，其實(shí)這三個(gè)類只是三個(gè)并不是線程安全的類篮绰，如果要扯上線程安全的問題，那么還有類Vecter季惯、Stack棧吠各，只是這兩個(gè)類在使用中并不常見，而且在新版本中已經(jīng)對線程安全的List有了替代類勉抓，詳情查看java.util.concurrent包下的各個(gè)同步集合類贾漏。
Set
在結(jié)構(gòu)圖中可以發(fā)現(xiàn)，Set下面有個(gè)子類AbstractSet藕筋，一應(yīng)的Set類都繼承這個(gè)抽象類纵散。在Java.util包中可以找到的Set集合類有EnumSet、HashSet念逞、LinkedHashSet和TreeSet困食。在這里就從HashSet開始：
HashSet
在上篇文章中梳理過Map之后，那么Set就很簡單了翎承。在HashSet的源碼中可以看到其中有兩個(gè)字段硕盹，如下所示：
/**
**HashSet源碼 字段
**/
private transient HashMap map;
private static final Object PRESENT = new Object();
在這里就可以看到，HashSet的底層是使用HashMap實(shí)現(xiàn)的叨咖，看過HashMap源碼之后瘩例，這個(gè)HashSet就非常簡單了啊胶，只是HashMap的一層包裝，查看Set的方法add(obj)如下：
/**
**HashSet的add方法
**/
public boolean add(Object obj) {
return map.put(obj, PRESENT) == null;
}
在put方法內(nèi)部使用map.put()方法來實(shí)現(xiàn)垛贤，將靜態(tài)對象PRESENT置入焰坪，而我們的Set存放的對象則作為Key來存放，所以說Set是Map的一層包裝聘惦。
TreeSet
類似于HashSet某饰，TreeSet也是使用對于的Map來實(shí)現(xiàn)的。查看TreeMap中的源碼善绎，其字段如下所示：
/**
**TreeSet源碼 字段
**/
private transient NavigableMap map;
private static final Object PRESENT = new Object();
可以看到黔漂，其中的字段NavigableMap類型的map，查看構(gòu)造器如下：
/**
**TreeMap源碼 構(gòu)造器
**/
TreeSet(NavigableMap navigablemap) {
m = navigablemap;
}
public TreeSet() {
this(((NavigableMap) (new TreeMap())));
}
public TreeSet(Comparator comparator1) {
this(((NavigableMap) (new TreeMap(comparator1))));
}
public TreeSet(Collection collection) {
this();
addAll(collection);
}
public TreeSet(SortedSet sortedset) {
this(sortedset.comparator());
addAll(sortedset);
}
對于每個(gè)構(gòu)造器而言禀酱，最后都會(huì)new一個(gè)TreeMap炬守，并將這個(gè)TreeMap轉(zhuǎn)化為NavigableMap傳給被保護(hù)的構(gòu)造器。這樣就知道TreeSet內(nèi)使用的就是TreeMap來存儲TreeSet剂跟。
在TreeSet中的存儲和HashSet一樣减途，如下所示：
/**
**TreeSet的add方法
**/
public boolean add(Object obj) {
return m.put(obj, PRESENT) == null;
}
可以看到，這里使用的也是map的put方法曹洽，并將PRESENT字段存放在val中鳍置，整個(gè)的TreeSet相當(dāng)于是TreeMap包裝了一層。
到此為止衣洁，Set大體上就是這樣的墓捻，如果清楚了Map的內(nèi)部結(jié)構(gòu)，那么Set則沒有什么難點(diǎn)坊夫。
Queue
在Java中存在隊(duì)列這么一個(gè)結(jié)構(gòu)砖第，就像我們平常所知道的隊(duì)列一樣，它奉行的是先進(jìn)先出的原則环凿，可以看到在源碼中其定義如下：
/**
**Queue接口
**/
public interface Queue extends Collection {
public abstract boolean add(Object obj); //插入指定元素到容器中梧兼，成功返回true，失敗報(bào)異常智听。
public abstract boolean offer(Object obj); //插入到容器羽杰，失敗返回false。
public abstract Object remove(); //獲取元素并從容器中移除
public abstract Object poll(); //獲取元素并從容器中移除到推，為空則返回null
public abstract Object element(); //獲取頭元素考赛，但是不移除
public abstract Object peek(); //獲取頭元素，但是不移除莉测，為空則返回null
}
在Queue接口下颜骤，存在子類AbstractQueue，其中對幾個(gè)方法擁有簡單的實(shí)現(xiàn)捣卤，并沒有什么需要特別注意的點(diǎn)忍抽。在AbstractQueue下還則存在一個(gè)類PriorityQueue八孝，可以看它的實(shí)現(xiàn)：
PriorityQueue
在看了之前的那些之后，類PriorityQueue也能簡單的分析出來鸠项，首先可以查看它的結(jié)構(gòu)擁有一個(gè)內(nèi)部類Itr實(shí)現(xiàn)了Iterator接口干跛，就像之前看到的類似的內(nèi)部類一樣，它必定是用在Collection接口的Iterator()方法中祟绊。除此之外楼入，可以查看這個(gè)類的字段：
/**
** PriorityQueue源碼 字段
**/
private static final int DEFAULT_INITIAL_CAPACITY = 11; //初始化長度
private transient Object queue[]; //內(nèi)部容器
private int size; //大小
private final Comparator comparator; //比較器
private transient int modCount; //修改的次數(shù)
到這里的時(shí)候，這幾個(gè)字段相對來說已經(jīng)很熟悉了久免，相較于ArrayList類來說浅辙，字段方面很類似扭弧，PriorityQueue也是使用的數(shù)組來實(shí)現(xiàn)的阎姥。那么查看它的構(gòu)造器，如下：
/**
**PriorityQueue構(gòu)造器
**/
public PriorityQueue() {
this(11, null);
}
public PriorityQueue(int i){...}
public PriorityQueue(int i, Comparator comparator1) {
size = 0;
modCount = 0;
if (i < 1) {
throw new IllegalArgumentException();
} else {
queue = new Object[i];
comparator = comparator1;
return;
}
}
public PriorityQueue(Collection collection){...}
public PriorityQueue(PriorityQueue priorityqueue){...}
public PriorityQueue(SortedSet sortedset){...}
//構(gòu)造器內(nèi)部方法
private void initFromCollection(Collection collection)
{
Object aobj[] = collection.toArray();
if(((Object) (aobj)).getClass() != [Ljava/lang/Object;)
aobj = Arrays.copyOf(aobj, aobj.length, [Ljava/lang/Object;);
queue = aobj;
size = aobj.length;
}
如上所示鸽捻，在第一個(gè)構(gòu)造器中可知PriorityQueue內(nèi)部的數(shù)組默認(rèn)長度為11呼巴，它也能接受各種參數(shù)Collection參數(shù)，對于上面兩種類型的參數(shù)PriorityQueue和SortedSet而言御蒲，其中的差別在于使用的比較器不同衣赶，兩個(gè)都是有順序的Collection使用的也是它自身的Comparator。
對于類PriorityQueue內(nèi)部的實(shí)現(xiàn)而言厚满，其實(shí)是比較簡單的府瞄，如下所示offer()方法：
/**
**PriorityQueue源碼 offer方法
**/
public boolean offer(Object obj) {
if (obj == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = obj;
else
siftUp(i, obj);
return true;
}
private void siftUp(int i, Object obj) {
if (comparator != null)
siftUpUsingComparator(i, obj);
else
siftUpComparable(i, obj);
}
private void siftUpUsingComparator(int i, Object obj) {
do {
if (i <= 0)
break;
int j = i - 1 >>> 1;
Object obj1 = queue[j];
if (comparator.compare(obj, obj1) >= 0)
break;
queue[i] = obj1;
i = j;
} while (true);
queue[i] = obj;
}
從如上方法就可以看出，它的實(shí)現(xiàn)碘箍，只是簡單的比較遵馆，然后賦值，并沒有復(fù)雜的邏輯丰榴。而另一個(gè)添加方法add則是調(diào)用的offer()方法货邓。
至此，關(guān)于Collection這部分就簡單的梳理完成四濒，雖然并沒有細(xì)致的分析到每一個(gè)方法或者類换况，但是做到這些集合類的實(shí)現(xiàn)方式都清楚；如果需要重新設(shè)計(jì)集合類盗蟆，也可以根據(jù)現(xiàn)有的集合類或者類似的實(shí)現(xiàn)方式完成邏輯需要戈二。當(dāng)然，也有人說：不要局限于過去的所知有限的數(shù)據(jù)結(jié)構(gòu)喳资，設(shè)計(jì)出優(yōu)秀好用的集合類就是好的觉吭。
Collections和Arrays
在工具類中，Collections負(fù)責(zé)的是集合操作骨饿，包括沒有繼承Collection接口的Map集合亏栈，其中主要有如下幾個(gè)類型的操作：
- 排序
對list列表進(jìn)行排序操作台腥，如sort(list)、sort(list,comparator)
倒序reverse(list)
對List中的元素隨機(jī)排列shuffle(list)绒北、shuffle(list,random)
對比較器相反操作使得使用的集合倒序reverseOrder()黎侈、reverseOrder(comparator)- 查找
二分查找 如binarySearch(list,obj)、binarySearch(list,obj,comparator)
集合中的最大最小值min(collection)闷游、min(collection,comparator)峻汉、max(collection)、max(collection,comparator)
返回指定源列表中第一次出現(xiàn)指定目標(biāo)列表的起始位置脐往，如果沒有出現(xiàn)這樣的列表休吠，則返回-1indexOfSubList(list1, list2)
返回指定源列表中最后一次出現(xiàn)指定目標(biāo)列表的起始位置，如果沒有出現(xiàn)這樣的列表业簿，則返回-1lastIndexOfSubList()
返回指定collection中obj的個(gè)數(shù)frequency(collection,obj)
3.移位
交換列表中指定兩個(gè)元素的位置swap(list,i,j)
循環(huán)移動(dòng)rotate(list1,i)瘤礁，例：list包含[a,b,c,d,e]。在調(diào)用Collection.rotate(list, 1)或者Collection.rotate(list, -4)后梅尤， list將為[e, a, b, c, d]
4.替換
使用指定元素替換列表中的所有元素fill(list, obj)
使用另一個(gè)值替換列表中出現(xiàn)的所有某一指定值replaceAll(list1,obj,obj1)- 拷貝
拷貝列表list2copy(list,list2)
拷貝i個(gè)對象obj成為一個(gè)數(shù)組柜思，不可變nCopies(i,obj)
6.比較
判斷相等eq(obj1,obj2)
兩個(gè)集合是否有重復(fù)元素disjoint(collection1,collection2)
7.轉(zhuǎn)換
Collection集合轉(zhuǎn)Enumeration枚舉enumeration(collection)
枚舉Enumeration轉(zhuǎn)Listlist(enumeration)
Map轉(zhuǎn)SetnewSetFromMap(map)
Deq轉(zhuǎn)Queue ``asLifoQueue(deq)
8.添加
addAll(Collection,obj[])
9.只讀集合：這些集合一旦初始化以后就不能修改，任何修改這些集合的方法都會(huì)拋出UnsupportedOperationException異常
unmodifiableCollection(collection)
unmodifiableSet(set)
unmodifiableSortedSet(sortedset)
unmodifiableList(list1)
unmodifiableMap(map)
unmodifiableSortedMap(sortedmap)
10.同步集合：為集合加鎖巷燥，保證數(shù)據(jù)安全性
synchronizedCollection(collection)
synchronizedSet(set)
synchronizedSortedSet(sortedset)
synchronizedList(list1)
synchronizedMap(map)
synchronizedSortedMap(sortedmap)
11.檢查集合：在插入的同時(shí)檢查是否是這個(gè)類型：
checkedCollection(collection,class)
checkedSet(set,class1)
checkedSortedSet(sortedset,class1)
checkedList(list1,class1)
checkedMap(map,class1,class2)
checkedSortedMap(sortedMap,class1,class2)
12.無元素的空集合
emptySet()
emptyList()
emptyMap()
13.單一元素并且只讀
singleton(obj)
singletonList(obj)
singletonMap(obj)
相較于Collections來說赡盘，Arrays的方法會(huì)少很多，主要包括數(shù)組的排序sort1()缰揪、交換swap()陨享、查找binarySearch()、比較equals()和deepEquals()钝腺、填充fill()抛姑、拷貝copyOf()和copyOfRange()、hash值hashcode()拍屑、深度hash算法deepHashCode()途戒、toString()方法和deepToString()。其中包括基本數(shù)據(jù)類型和泛型方法僵驰，具體的使用還需要根據(jù)實(shí)際情況而定喷斋。
到此為止，集合已經(jīng)大體上梳理過了蒜茴，其中還有些很細(xì)節(jié)的東西需要注意星爪，比如asList()方法返回的list并不能被操作、保持compareTo和equals同步等粉私，其中的緣由在源碼中都可以找到顽腾。 基礎(chǔ)系列到這基本上也都寫了，如果其中有疑問或不解的地方請留言，我會(huì)認(rèn)真查看并修改解答抄肖，準(zhǔn)備下一個(gè)計(jì)劃吧~
參考：
java.utl.*
