概述

Java集合框架由Java類(lèi)庫(kù)的一系列接口、抽象類(lèi)以及具體實(shí)現(xiàn)類(lèi)組成固棚。我們這里所說(shuō)的集合就是把一組對(duì)象組織到一起寻咒，然后再根據(jù)不同的需求操縱這些數(shù)據(jù)常拓。集合類(lèi)型就是容納這些對(duì)象的一個(gè)容器。也就是說(shuō)怜械，最基本的集合特性就是把一組對(duì)象放一起集中管理颅和。根據(jù)集合中是否允許有重復(fù)的對(duì)象、對(duì)象組織在一起是否按某種順序等標(biāo)準(zhǔn)來(lái)劃分的話(huà)缕允，集合類(lèi)型又可以細(xì)分為許多種不同的子類(lèi)型峡扩。

Java集合框架為我們提供了一組基本機(jī)制以及這些機(jī)制的參考實(shí)現(xiàn)，其中基本的集合接口是Collection接口障本，其他相關(guān)的接口還有Iterator接口教届、RandomAccess接口等响鹃。這些集合框架中的接口定義了一個(gè)集合類(lèi)型應(yīng)該實(shí)現(xiàn)的基本機(jī)制，Java類(lèi)庫(kù)為我們提供了一些具體集合類(lèi)型的參考實(shí)現(xiàn)案训，根據(jù)對(duì)數(shù)據(jù)組織及使用的不同需求买置，只需要實(shí)現(xiàn)不同的接口即可。Java類(lèi)庫(kù)還為我們提供了一些抽象類(lèi)强霎，提供了集合類(lèi)型功能的部分實(shí)現(xiàn)忿项，我們也可以在這個(gè)基礎(chǔ)上去進(jìn)一步實(shí)現(xiàn)自己的集合類(lèi)型。

Collection接口

迭代器

我們先來(lái)看下這個(gè)接口的定義：

public interface Collection<E> extends Iterable<E>

首先城舞，它使用了一個(gè)類(lèi)型參數(shù)轩触；其次，它實(shí)現(xiàn)了Iterable<E>接口家夺，我們?cè)賮?lái)看下Iterable<E>接口的定義：

public interface Iterable<T> {
  Iterator<T> iterator();
}

我們可以看到這個(gè)接口只定義了一個(gè)方法怕膛，這個(gè)方法要求我們返回一個(gè)實(shí)現(xiàn)了Iterator<T>類(lèi)型的對(duì)象，所以我們看下Iterator<T>的定義：

public interface Iterator<E> { 
  boolean hasNext(); 
  E next(); 
  void remove();
}

說(shuō)到這里秦踪，我們簡(jiǎn)單地說(shuō)一下迭代器（Iterator）這個(gè)東西褐捻。上面我們一共提到了兩個(gè)和迭代器相關(guān)的接口：Iterable<E>接口和Iterator<E>接口，從字面意義上來(lái)看椅邓，前者的意思是“可迭代的”柠逞，后者的意思是“迭代器。所以我們可以這么理解這兩個(gè)接口：實(shí)現(xiàn)了Iterable<E>接口的類(lèi)是可迭代的景馁；實(shí)現(xiàn)了Iterator<E>接口的類(lèi)是一個(gè)迭代器板壮。

迭代器就是一個(gè)我們用來(lái)遍歷集合中的對(duì)象的東西。也就是說(shuō)合住，對(duì)于集合绰精，我們不是像對(duì)原始類(lèi)型數(shù)組那樣通過(guò)數(shù)組索引來(lái)直接訪問(wèn)相應(yīng)位置的元素，而是通過(guò)迭代器來(lái)遍歷透葛。這么做的好處是將對(duì)于集合類(lèi)型的遍歷行為與被遍歷的集合對(duì)象分離笨使，這樣一來(lái)我們無(wú)需關(guān)心該集合類(lèi)型的具體實(shí)現(xiàn)是怎樣的。只要獲取這個(gè)集合對(duì)象的迭代器, 便可以遍歷這個(gè)集合中的對(duì)象了僚害。而像遍歷對(duì)象的順序這些細(xì)節(jié)硫椰，全部由它的迭代器來(lái)處理。現(xiàn)在我們來(lái)梳理一下前面提到的這些東西：首先萨蚕，Collection接口實(shí)現(xiàn)了Iterable<E>接口靶草，這意味著所有實(shí)現(xiàn)了Collection接口的具體集合類(lèi)都是可迭代的。那么既然要迭代岳遥，我們就需要一個(gè)迭代器來(lái)遍歷相應(yīng)集合中的對(duì)象奕翔，所以Iterable<E>接口要求我們實(shí)現(xiàn)iterator方法，這個(gè)方法要返回一個(gè)迭代器對(duì)象浩蓉。一個(gè)迭代器對(duì)象也就是實(shí)現(xiàn)了Iterator<E>接口的對(duì)象派继，這個(gè)接口要求我們實(shí)現(xiàn)hasNext()帮坚、next()、remove()這三個(gè)方法互艾。其中hasNext方法判斷是否還有下一個(gè)元素（即是否遍歷完對(duì)象了）试和，next方法會(huì)返回下一個(gè)元素（若沒(méi)有下一個(gè)元素了調(diào)用它會(huì)引起拋出一個(gè)NoSuchElementException異常），remove方法用于移除最近一次調(diào)用next方法返回的元素（若沒(méi)有調(diào)用next方法而直接調(diào)用remove方法會(huì)報(bào)錯(cuò)）纫普。我們可以想象在開(kāi)始對(duì)集合進(jìn)行迭代前阅悍，有個(gè)指針指向集合第一個(gè)元素的前面，第一次調(diào)用next方法后昨稼，這個(gè)指針會(huì)”掃過(guò)"第一個(gè)元素并返回它节视，調(diào)用hasNext方法就是看這個(gè)指針后面還有沒(méi)有元素了。也就是說(shuō)這個(gè)指針始終指向剛遍歷過(guò)的元素和下一個(gè)待遍歷的元素之間假栓。通常寻行，迭代一個(gè)集合對(duì)象的代碼是這個(gè)樣子的：

Collection<String> c = ...;
Iterator<String> iter = c.iterator();
while (iter.hasNext()) {
  String element = iter.next();
  //do something with element
}

從Java SE 5.0開(kāi)始，我們可以使用與以上代碼段等價(jià)但是更加簡(jiǎn)潔的版本：

for (String element : c) {
  //do something with element
}

上面我們提到過(guò)Iterator接口的remove方法必須在next方法返回一個(gè)元素后才能調(diào)用匾荆，這對(duì)Java類(lèi)庫(kù)中為我們提供的實(shí)現(xiàn)了Collection接口的類(lèi)來(lái)說(shuō)是這樣的拌蜘。當(dāng)然我們可以通過(guò)自己定義一個(gè)實(shí)現(xiàn)Collection接口的集合類(lèi)來(lái)改變這一默認(rèn)行為（除非有充足的理由，否則最好不要這樣做）牙丽。

Collection接口

我們先來(lái)看一下它的官方定義：

The root interface in the collection hierarchy. A collection represents a group of objects, known as its elements. Some collections allow duplicate elements and others do not. Some are ordered and others unordered. The JDK does not provide any direct implementations of this interface: it provides implementations of more specific subinterfaces like Set
and List.

大概的意思就是：Collection接口是集合層級(jí)結(jié)構(gòu)的根接口简卧。一個(gè)集合代表了一組對(duì)象，這組對(duì)象被稱(chēng)為集合的元素烤芦。一些集合允許重復(fù)的元素而其他不允許举娩；一些是有序的而一些是無(wú)序的。Java類(lèi)庫(kù)中并未提供任何對(duì)這個(gè)接口的直接實(shí)現(xiàn)构罗，而是提供了對(duì)于它的更具體的子接口的實(shí)現(xiàn)（比如Set接口和List接口）铜涉。

我們知道，接口是一組對(duì)需求的描述遂唧，那么讓我們看看Collection接口提出了哪些需求芙代。Collection接口中定義了以下方法：

boolean add(E e) //向集合中添加一個(gè)元素，若添加元素后集合發(fā)生了變化就返回true蠢箩，若沒(méi)有發(fā)生變化链蕊，就返回false。(optional operation).
boolean addAll(Collection<? extends E> c) //添加給定集合c中的所有元素到該集合中(optional operation).
void clear() //(optional operation).
boolean contains(Object o) //判斷該集合中是否包含指定對(duì)象
boolean containsAll(Collection<?> c)
boolean equals(Object o)
int hashCode()
boolean isEmpty()
Iterator<E> iterator()
boolean remove(Object o) //移除給定對(duì)象的一個(gè)實(shí)例（有的具體集合類(lèi)型允許重復(fù)元素） (optional operation).
boolean removeAll(Collection<?> c) //(optional operation).
boolean retainAll(Collection<?> c) //僅保留給定集合c中的元素(optional operation).
int size()
Object[] toArray()
<T> T[] toArray(T[] a)

我們注意到有些方法后面注釋中標(biāo)注了“optional operation”谬泌，意思是Collection接口的實(shí)現(xiàn)類(lèi)究竟需不需要實(shí)現(xiàn)這個(gè)方法視具體情況而定。比如有些具體的集合類(lèi)型不允許向其中添加對(duì)象逻谦，那么它就無(wú)需實(shí)現(xiàn)add方法掌实。我們可以看到，Collection對(duì)象必須實(shí)現(xiàn)的方法有：contains方法邦马、containsAll方法贱鼻、isEmpty方法宴卖、iterator方法、size方法邻悬、兩個(gè)toArray方法以及equals方法症昏、hashCode方法，其中最后兩個(gè)方法繼承自O(shè)bject類(lèi)父丰。

我們來(lái)說(shuō)一下兩個(gè)toArray方法肝谭，它們的功能都是都是返回這個(gè)集合的對(duì)象數(shù)組。第二個(gè)方法接收一個(gè)arrayToFill參數(shù)蛾扇，當(dāng)這個(gè)參數(shù)數(shù)組足夠大時(shí)攘烛，就把集合中的元素都填入這個(gè)數(shù)組（多余空間填null）；當(dāng)arrayToFill不夠大時(shí)镀首，就會(huì)創(chuàng)建一個(gè)大小與集合相同坟漱，類(lèi)型與arrayToFill相同的數(shù)組，并填入集合元素更哄。

Collection接口的直接子接口主要有三個(gè)：List接口芋齿、Set接口和Queue接口。下面我們對(duì)它們進(jìn)行逐一介紹成翩。

List接口

我們同樣先看下它的官方定義：

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.Unlike sets, lists typically allow duplicate elements. More formally, lists typically allow pairs of elements e1 and e2 such that e1.equals(e2), and they typically allow multiple null elements if they allow null elements at all.

大概意思是：List是一個(gè)有序的集合類(lèi)型（也被
稱(chēng)作序列）沟突。使用List接口可以精確控制每個(gè)元素被插入的位置，并且可以通過(guò)元素在列表中的索引來(lái)訪問(wèn)它捕传。列表允許重復(fù)的元素惠拭，并且在允許null元素的情況下也允許多個(gè)null元素。

我們?cè)賮?lái)看下它定義了哪些方法：

ListIterator<E> listIterator();
void add(int i, E element);
E remove(int i);
E get(int i);
E set(int i, E element);
int indexOf(Object element);

我們可以看到庸论，列表支持對(duì)指定位置元素的讀寫(xiě)與移除职辅。我們注意到，上面有一個(gè)listIterator方法聂示，它返回一個(gè)列表迭代器域携。我們來(lái)看一看ListIterator<E>接口都定義了哪些方法：

void add(E e) //在當(dāng)前位置添加一個(gè)元素
boolean hasNext() //返回ture如果還有下個(gè)元素（在正向遍歷列表時(shí)使用）
boolean hasPrevious() //反向遍歷列表時(shí)使用
E next() //返回下一個(gè)元素并將cursor（也就是我們上文提到的”指針“）前移一個(gè)位置
int nextIndex() //返回下一次調(diào)用next方法將返回的元素的索引
E previous() //返回前一個(gè)元素并將cursor向前移動(dòng)一個(gè)位置
int previousIndex() //返回下一次調(diào)用previous方法將返回的元素的索引void remove() //從列表中移除最近一次調(diào)用next方法或previous方法返回的元素
void set(E e) //用e替換最近依次調(diào)用next或previous方法返回的元素

ListIterator<E>是Iterator<E>的子接口，它支持像雙向迭代這樣更加特殊化的操作鱼喉。綜合以上秀鞭，我們可以看到，List接口支持兩種訪問(wèn)元素的方式：使用列表迭代器順序訪問(wèn)或者使用get/set方法隨機(jī)訪問(wèn)扛禽。

Java類(lèi)庫(kù)中常見(jiàn)的實(shí)現(xiàn)了List<E>接口的類(lèi)有：ArrayList锋边， LinkedList，Stack编曼，Vector豆巨，AbstractList，AbstractSequentialList等等掐场。

ArrayList

ArrayList是一個(gè)可動(dòng)態(tài)調(diào)整大小的數(shù)組往扔，允許null類(lèi)型的元素贩猎。我們知道，Java中的數(shù)組大小在初始化時(shí)就必須確定下來(lái)萍膛，而且一旦確定就不能改變吭服，這會(huì)使得在很多場(chǎng)景下不夠靈活。ArrayList很好地幫我們解決了這個(gè)問(wèn)題蝗罗，當(dāng)我們需要一個(gè)能根據(jù)包含元素的多少來(lái)動(dòng)態(tài)調(diào)整大小的數(shù)組時(shí)艇棕，那么ArrayList正是我們所需要的。

我們先來(lái)看看這個(gè)類(lèi)的常用方法：

boolean add(E e) //添加一個(gè)元素到數(shù)組末尾
void add(int index, E element) //添加一個(gè)元素到指定位置
void clear()
boolean contains(Object o)
void ensureCapacity(int minCapacity) //確保ArrayList至少能容納參數(shù)指定數(shù)目的對(duì)象绿饵，若有需要會(huì)增加ArrayList實(shí)例的容量欠肾。
E get(int index) //返回指定位置的元素
int indexOf(Object o)
boolean isEmpty()
Iterator<E> iterator()
ListIterator<E> listIterator()
E remove(int index)
boolean remove(Object o)
E set(int index, E element)
int size()

當(dāng)我們插入了比較多的元素，導(dǎo)致ArrayList快要裝滿(mǎn)時(shí)拟赊，它會(huì)自動(dòng)增長(zhǎng)容量刺桃。ArrayList內(nèi)部使用一個(gè)Object數(shù)組來(lái)存儲(chǔ)元素，自動(dòng)增長(zhǎng)容量是通過(guò)創(chuàng)建一個(gè)新的容量更大的Object數(shù)組吸祟，并將元素從原Object數(shù)組復(fù)制到新Object數(shù)組來(lái)實(shí)現(xiàn)的瑟慈。若要想避免這種開(kāi)銷(xiāo)，在知道大概會(huì)容納多少數(shù)據(jù)時(shí)屋匕，我們可以在構(gòu)造時(shí)指定好它的大小以盡量避免它自動(dòng)增長(zhǎng)的發(fā)生葛碧；我們也可以調(diào)用ensureCapacity方法來(lái)增加ArrayList對(duì)象的容量到我們指定的大小。ArrayList有以下三個(gè)構(gòu)造器：

ArrayList()
ArrayList(Collection<? extends E> c)
ArrayList(int initialCapacity) //指定初始capacity过吻，即內(nèi)部Object數(shù)組的初始大小

LinkedList類(lèi)

LinkedList類(lèi)代表了一個(gè)雙向鏈表进泼，允許null元素。這個(gè)類(lèi)同ArrayList一樣纤虽，不是線程安全的乳绕。
這個(gè)類(lèi)中主要有以下的方法：

void addFirst(E element);
void addLast(E element);
E getFirst();
E getLast();
E removeFirst();
E removeLast();

這些方法的含義正如它們的名字所示。LinkedList作為L(zhǎng)ist接口的實(shí)現(xiàn)類(lèi)逼纸，自然包含了List接口中定義的add等方法洋措。LinkedList的add方法實(shí)現(xiàn)有以下兩種：

boolean add(E e) //把元素e添加到鏈表末尾
void add(int index, E element) //在指定索引處添加元素

LinkedList的一個(gè)缺陷在于它不支持對(duì)元素的高效隨機(jī)訪問(wèn)习勤，要想隨機(jī)訪問(wèn)其中的元素塞弊，需要逐個(gè)掃描直到遇到符合條件的元素。只有當(dāng)我們需要減少在列表中間添加或刪除元素操作的代價(jià)時(shí)腿准，可以考慮使用LinkedList贺嫂。

Set接口

Set接口與List接口的重要區(qū)別就是它不支持重復(fù)的元素滓鸠，至多可以包含一個(gè)null類(lèi)型元素。Set接口定義的是數(shù)學(xué)意義上的“集合”概念涝婉。
Set接口主要定義了以下方法：

boolean add(E e)
void clear()
boolean contains(Object o)
boolean isEmpty()
boolean equals(Object obj)
Iterator<E> iterator()
boolean remove(Object o)
boolean removeAll(Collection<?> c)
int size()
Object[] toArray()
<T> T[] toArray(T[] a)

Set接口并沒(méi)有顯式要求其中的元素是有序或是無(wú)序的哥力，它有一個(gè)叫做SortedSet的子接口，這個(gè)接口可以用來(lái)實(shí)現(xiàn)對(duì)Set元素的排序墩弯，SortedSet還有叫做NavigableSet的子接口吩跋，這個(gè)接口定義的方法可以在有序Set中進(jìn)行查找和遍歷。Java類(lèi)庫(kù)中實(shí)現(xiàn)了Set接口的類(lèi)主要有：AbstractSet渔工，HashSet锌钮，TreeSet，EnumSet引矩，LinkedHashSet等等梁丘。其中，HashSet與TreeSet都是AbstractSet的子類(lèi)旺韭。那么氛谜，為什么Java類(lèi)庫(kù)要提供AbstractSet這個(gè)抽象類(lèi)呢？答案是為了讓我們?cè)谧远x實(shí)現(xiàn)Set接口的類(lèi)時(shí)不必“從零開(kāi)始”区端，AbstractSet這個(gè)抽象類(lèi)已經(jīng)為我們實(shí)現(xiàn)了Set接口中的一些常規(guī)方法值漫，而一些靈活性比較強(qiáng)的方法可以由我們自己來(lái)定義，我們只需要繼承AbstractSet這個(gè)抽象類(lèi)即可织盼。類(lèi)似的抽象類(lèi)還有很多杨何，比如我們上面提到的實(shí)現(xiàn)了List接口的AbstractList抽象類(lèi)就是LinkedList和ArrayList的父類(lèi)。Java官方文檔中提到沥邻，HashSet和TreeSet分別基于HashMap和TreeMap實(shí)現(xiàn)（我們?cè)诤竺鏁?huì)簡(jiǎn)單介紹HashMap和TreeMap）危虱，他們的區(qū)別在于Set<E>接口是一個(gè)對(duì)象的集（數(shù)學(xué)意義上的”集合“），Map<K, V>是一個(gè)鍵值對(duì)的集合唐全。而且由于它們分別是對(duì)Set<E>和Map<K, V>接口的實(shí)現(xiàn)埃跷，相應(yīng)添加與刪除元素的方法也取決于具體接口的定義。

Queue接口

Queue接口是對(duì)隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)的抽象邮利。一般的隊(duì)列實(shí)現(xiàn)允許我們高效的在隊(duì)尾添加元素弥雹，在隊(duì)列頭部刪除元素（First in, First out)。Queue<E>接口還有一個(gè)名為Deque的子接口近弟，它允許我們高效的在隊(duì)頭或隊(duì)尾添加/刪除元素缅糟，實(shí)現(xiàn)了Deque<E>的接口的集合類(lèi)即為雙端隊(duì)列的一種實(shí)現(xiàn)（比如LinkedList就實(shí)現(xiàn)了Deque接口）。Queue接口定義了以下方法：

boolean add(E e) //添加一個(gè)元素到隊(duì)列中祷愉，若隊(duì)列已滿(mǎn)會(huì)拋出一個(gè)IllegalStateException異常
E element() //獲取隊(duì)頭元素
boolean offer(E e) //添加一個(gè)元素到隊(duì)列中窗宦，若隊(duì)列已滿(mǎn)返回false
E peek() //獲取隊(duì)頭元素，若隊(duì)列為空返回null
E poll() //返回并移除隊(duì)頭元素二鳄，若隊(duì)列為空返回null
E remove() //返回并移除隊(duì)頭元素

我們注意觀察下上面的方法：add與offer赴涵，element與peek，remove與poll看似是三對(duì)兒功能相同的方法订讼。它們之間的重要區(qū)別在于前者若操作失敗會(huì)拋出一個(gè)異常髓窜，后者若操作失敗會(huì)從返回值體現(xiàn)出來(lái)（比如返回false或null），我們可以根據(jù)具體需求調(diào)用它們中的前者或后者。

實(shí)現(xiàn)Queue接口的類(lèi)主要有：AbstractQueue寄纵， ArrayDeque鳖敷， LinkedList，PriorityQueue程拭，DelayQueue等等定踱。關(guān)于它們具體的介紹可參考官方文檔或相關(guān)的文章。

Map接口

我們先來(lái)看下它的定義：

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.The Map
interface provides three collection views, which allow a map's contents to be viewed as a set of keys, collection of values, or set of key-value mappings. The order of a map is defined as the order in which the iterators on the map's collection views return their elements. Some map implementations, like the TreeMap
class, make specific guarantees as to their order; others, like the HashMap
class, do not.

大概意思是這樣的：一個(gè)把鍵映射到值的對(duì)象被稱(chēng)作一個(gè)Map對(duì)象恃鞋。映射表不能包含重復(fù)的鍵崖媚，每個(gè)鍵至多可以與一個(gè)值關(guān)聯(lián)。Map接口提供了三個(gè)集合視圖（關(guān)于集合視圖的概念我們下面會(huì)提到）：鍵的集合視圖恤浪、值的集合視圖以及鍵值對(duì)的集合視圖畅哑。一個(gè)映射表的順序取決于它的集合視圖的迭代器返回元素的順序。一些Map接口的具體實(shí)現(xiàn)（比如TreeMap）保證元素有一定的順序水由，其它一些實(shí)現(xiàn)（比如HashMap）則不保證元素在其內(nèi)部有序荠呐。

也就是說(shuō)，Map接口定義了一個(gè)類(lèi)似于“字典”的規(guī)范绷杜，讓我們能夠根據(jù)鍵快速檢索到它所關(guān)聯(lián)的值直秆。我們先來(lái)看看Map接口定義了哪些方法：

void clear()
boolean containsKey(Object key) //判斷是否包含指定鍵
boolean containsValue(Object value) //判斷是否包含指定值
boolean isEmpty()
V get(Object key) //返回指定鍵映射的值
V put(K key, V value) //放入指定的鍵值對(duì)
V remove(Object key)
int size()
Set<Map.Entry<K,V>> entrySet() 
Set<K> keySet()
Collection<V> values()

后三個(gè)方法在我們下面介紹集合視圖時(shí)會(huì)具體講解。
Map接口的具體實(shí)現(xiàn)類(lèi)主要有：AbstractMap鞭盟，EnumMap圾结，HashMap，LinkedHashMap齿诉，TreeMap筝野。HashTable。

HashMap

我們看一下HashMap的官方定義：

HashMap<K, V>是基于哈希表這個(gè)數(shù)據(jù)結(jié)構(gòu)的Map接口具體實(shí)現(xiàn)粤剧，允許null鍵和null值歇竟。這個(gè)類(lèi)與HashTable近似等價(jià)，區(qū)別在于HashMap不是線程安全的并且允許null鍵和null值抵恋。由于基于哈希表實(shí)現(xiàn)焕议，所以HashMap內(nèi)部的元素是無(wú)序的。HashMap對(duì)與get與put操作的時(shí)間復(fù)雜度是常數(shù)級(jí)別的（在散列均勻的前提下）弧关。對(duì)HashMap的集合視圖進(jìn)行迭代所需時(shí)間與HashMap的capacity（bucket的數(shù)量）加上HashMap的尺寸（鍵值對(duì)的數(shù)量）成正比盅安。因此，若迭代操作的性能很重要世囊，不要把初始capacity設(shè)的過(guò)高（不要把load factor設(shè)的過(guò)低）别瞭。

有兩個(gè)因素會(huì)影響一個(gè)HashMap對(duì)象的性能：intial capacity（初始容量）和load factor（負(fù)載因子）。intial capacity就是HashMap對(duì)象剛創(chuàng)建時(shí)其內(nèi)部的哈希表的“桶”的數(shù)量（請(qǐng)參考哈希表的定義）株憾。load factor等于maxSize / capacity蝙寨，也就是HashMap所允許的最大鍵值對(duì)數(shù)與桶數(shù)的比值晒衩。增大load factor可以節(jié)省空間但查找一個(gè)元素的時(shí)間會(huì)增加，減小load factor會(huì)占用更多的存儲(chǔ)空間墙歪，但是get與put的操作會(huì)更快听系。當(dāng)HashMap中的鍵值對(duì)數(shù)量超過(guò)了maxSize（即load factor與capacity的乘積），它會(huì)再散列箱亿，再散列會(huì)重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)跛锌，桶數(shù)（capacity）大約會(huì)增加到原來(lái)的兩
倍弃秆。
HashMap默認(rèn)的load factor大小為0.75届惋，這個(gè)數(shù)值在時(shí)間與空間上做了很好的權(quán)衡。當(dāng)我們清楚自己將要大概存放多少數(shù)據(jù)時(shí)菠赚，也可以自定義load factor的大小脑豹。
HashMap的構(gòu)造器如下：

HashMap()
HashMap(int initialCapacity)
HashMap(int initialCapacity, float loadFactor)
HashMap(Map<? extends K,? extends V> m) //創(chuàng)建一個(gè)新的HashMap，用m的數(shù)據(jù)填充

常用方法如下：

void clear()
boolean containsKey(Object key)
boolean containsValue(Object value)
V get(Object key)
V put(K key, V value)
boolean isEmpty()
V remove(Object key)
int size()
Collection<V> values()
Set<Map.Entry<K,V>> entrySet()
Set<K> keySet()

它們的功能都很直觀衡查，更多的使用細(xì)節(jié)可以參考Java官方文檔瘩欺，這里就不貼上來(lái)了。這里簡(jiǎn)單地提一下WeakHashMap拌牲，它與HashMap的區(qū)別在于俱饿，存儲(chǔ)在其中的key是“弱引用”的，也就是說(shuō)塌忽，當(dāng)不再存在對(duì)WeakHashMap中的鍵的外部引用時(shí)拍埠，相應(yīng)的鍵值對(duì)就會(huì)被回收。關(guān)于WeakHashMap和其他類(lèi)的具體使用方法及注意事項(xiàng)土居，大家可以參考官方文檔枣购。下面我們來(lái)簡(jiǎn)單地介紹下另一個(gè)Map接口的具體實(shí)現(xiàn)——TreeMap。

TreeMap

它的官方定義是這樣的：

TreeMap<K, V>一個(gè)基于紅黑樹(shù)的Map接口實(shí)現(xiàn)擦耀。TreeMap中的元素的有序的棉圈，排序的依據(jù)是存儲(chǔ)在其中的鍵的natural ordering（自然序，也就是數(shù)字從小到大眷蜓，字母的話(huà)按照字典序）或者根據(jù)在創(chuàng)建TreeMap時(shí)提供的Comparator對(duì)象分瘾，這取決于使用了哪個(gè)構(gòu)造器。TreeMap的containsKey, get, put和remove操作的時(shí)間復(fù)雜度均為log(n)吁系。

TreeMap有以下構(gòu)造器：

TreeMap() //使用自然序?qū)ζ湓剡M(jìn)行排序
TreeMap(Comparator<? super K> comparator) //使用一個(gè)比較器對(duì)其元素進(jìn)行排序
TreeMap(Map<? extends K,? extends V> m) //構(gòu)造一個(gè)與映射表m含有相同元素的TreeMap德召，用自然序進(jìn)行排列
TreeMap(SortedMap<K,? extends V> m) //構(gòu)造一個(gè)與有序映射表m含有相同元素及元素順序的TreeMap 

它的常見(jiàn)方法如下：

Map.Entry<K,V> ceilingEntry(K key) //返回一個(gè)最接近且大于等于指定key的鍵值對(duì)。
K ceilingKey(K key)
void clear()
Comparator<? super K> comparator() //返回使用的比較器垮抗，若按自然序則返回null
boolean containsKey(Object key)
boolean containsValue(Object value)
NavigableSet<K> descendingKeySet() //返回一個(gè)包含在TreeMap中的鍵的逆序的NavigableSet視圖
NavigableMap<K,V> descendingMap()
Set<Map.Entry<K,V>> entrySet()
Map.Entry<K,V> firstEntry() //返回鍵最小的鍵值對(duì)
Map.Entry<K,V> floorEntry(K key) //返回一個(gè)最接近指定key且小于等于它的鍵對(duì)應(yīng)的鍵值對(duì)
K floorKey(K key)
V get(Object key)
Set<K> keySet()
Map.Entry<K,V> lastEntry() //返回與最大的鍵相關(guān)聯(lián)的鍵值對(duì)
K lastKey()

建議大家先了解下紅黑樹(shù)這個(gè)數(shù)據(jù)結(jié)構(gòu)的原理及實(shí)現(xiàn)（可參考算法（第4版） (豆瓣)）氏捞，然后再去看官方文檔中關(guān)于這個(gè)類(lèi)的介紹，這樣學(xué)起來(lái)會(huì)事半功倍冒版。

最后再簡(jiǎn)單地介紹下NavigableMap<K, V>這個(gè)接口：
實(shí)現(xiàn)了這個(gè)接口的類(lèi)支持一些navigation methods液茎，比如lowerEntry（返回小于指定鍵的最大鍵所關(guān)聯(lián)的鍵值對(duì)），floorEntry（返回小于等于指定鍵的最大鍵所關(guān)聯(lián)的鍵值對(duì)），ceilingEntry（返回大于等于指定鍵的最小鍵所關(guān)聯(lián)的鍵值對(duì)）和higerEntry（返回大于指定鍵的最小鍵所關(guān)聯(lián)的鍵值對(duì)）捆等。一個(gè)NavigableMap支持對(duì)其中存儲(chǔ)的鍵按鍵的遞增順序或遞減順序的遍歷或訪問(wèn)滞造。NavigableMap<K, V>接口還定義了firstEntry、pollFirstEntry栋烤、lastEntry和pollLastEntry等方法谒养，以準(zhǔn)確獲取指定位置的鍵值對(duì)。

總的來(lái)說(shuō)明郭，NavigableMap<K, V>接口正如它的名字所示买窟，支持我們?cè)谟成浔碇小弊杂傻暮叫小埃蚧蛘叻聪虻渲械脑夭@取我們需要的指定位置的元素薯定。TreeMap實(shí)現(xiàn)了這個(gè)接口始绍。

視圖（View）與包裝器

下面我們來(lái)解決一個(gè)上面遺留的問(wèn)題，也就是介紹一下集合視圖的概念话侄。Java中的集合視圖是用來(lái)查看集合中全部或部分?jǐn)?shù)據(jù)的一個(gè)”窗口“亏推，只不過(guò)通過(guò)視圖我們不僅能查看相應(yīng)集合中的元素，對(duì)視圖的操作還可能會(huì)影響到相應(yīng)的集合年堆。通過(guò)使用視圖可以獲得其他的實(shí)現(xiàn)了Map接口或Collection接口的對(duì)象吞杭。比如我們上面提到的TreeMap和HashMap的keySet()方法就會(huì)返回一個(gè)相應(yīng)映射表對(duì)象的視圖。也就是說(shuō)变丧，keySet方法返回的視圖是一個(gè)實(shí)現(xiàn)了Set接口的對(duì)象芽狗，這個(gè)對(duì)象中又包含了一系列鍵對(duì)象。

輕量級(jí)包裝器

Arrays.asList會(huì)發(fā)揮一個(gè)包裝了Java數(shù)組的集合視圖（實(shí)現(xiàn)了List接口）锄贷。請(qǐng)看以下代碼：

public static void main(String[] args) {
  String[] strings = {"first", "second", "third"};
  List<String> stringList = Arrays.asList(strings);
  String s1 = stringList.get(0);
  System.out.println(s1);
  stringList.add(0, "new first");
}

以上代碼會(huì)編譯成功译蒂，但是在運(yùn)行時(shí)會(huì)拋出一個(gè)UnsupportedOperationException異常，原因是調(diào)用了改變列表大小的add方法谊却。Arrays.asList方法返回的封裝了底層數(shù)組的集合視圖不支持對(duì)改變數(shù)組大小的方法（如add方法和remove方法）的調(diào)用（但是可以改變數(shù)組中的元素）柔昼。實(shí)際上，這個(gè)方法調(diào)用了以下方法：

Collections.nCopies(n, anObject);

這個(gè)方法會(huì)返回一個(gè)實(shí)現(xiàn)了List接口的不可修改的對(duì)象炎辨。這個(gè)對(duì)象包含了n個(gè)元素（anObject）捕透。

子范圍

我們可以為很多集合類(lèi)型建立一個(gè)稱(chēng)為子范圍（subrange）的集合視圖。例如以下代碼抽出group中的第10到19個(gè)元素（從0開(kāi)始計(jì)數(shù)）組成一個(gè)子范圍：

List subgroup = group.subList(10, 20); //group為一個(gè)實(shí)現(xiàn)了List接口的列表類(lèi)型

List接口所定義的操作都可以應(yīng)用于子范圍碴萧，包括那些會(huì)改變列表大小的方法乙嘀，比如以下方法會(huì)把subgroup列表清空，同時(shí)group中相應(yīng)的元素也會(huì)從列表中移除：

subgroup.clear();

對(duì)于實(shí)現(xiàn)了SortedSet<E>接口的有序集或是實(shí)現(xiàn)了SortedMap<K, V>接口的有序映射表破喻，我們也可以為他們創(chuàng)建子范圍虎谢。SortedSet接口定義了以下三個(gè)方法：

SortedSet<E> subSet(E from, E to); 
SortedSet<E> headSet(E to);
SortedSet<E> tailSet(E from);

SortedMap也定義了類(lèi)似的方法：

SortedMap<K, V> subMap(K from, K to);
SortedMap<K, V> headMap(K to);
SortedMap<K, V> tailMap(K from);

不可修改的視圖

Collections類(lèi)中的一些方法可以返回不可修改視圖（unmodifiable views)：

Collections.unmodifiableCollection
Collections.unmodifiableList
Collections.unmodifiableSet
Collections.unmodifiableSortedSet
Collections.unmodifiableMap
Collections.unmodifiableSortedMap

同步視圖

若集合可能被多個(gè)線程并發(fā)訪問(wèn)，那么我們就需要確保集合中的數(shù)據(jù)不會(huì)被破壞曹质。Java類(lèi)庫(kù)的設(shè)計(jì)者使用視圖機(jī)制來(lái)確保常規(guī)集合的線程安全婴噩。比如擎场，我們可以調(diào)用以下方法將任意一個(gè)實(shí)現(xiàn)了Map接口的集合變?yōu)榫€程安全的：

Map<String, Integer> map = Collections.synchronizedMap(new HashMap<String, Integer>());

被檢驗(yàn)視圖

我們先看一下這段代碼：

ArrayList<String> strings = new ArrayList<String>();
ArrayList rawList = strings;
rawList.add(new Date());

在以上代碼的第二行，我們把泛型數(shù)組賦值給了一個(gè)原始類(lèi)型數(shù)組几莽，這通常只會(huì)產(chǎn)生一個(gè)警告迅办。而第三行我們往rawList中添加一個(gè)Date對(duì)象時(shí)，并不會(huì)產(chǎn)生任何錯(cuò)誤章蚣。因?yàn)閞awList內(nèi)部存儲(chǔ)的實(shí)際上是Object對(duì)象站欺，而任何對(duì)象都可以轉(zhuǎn)換為Object對(duì)象。那么我們?cè)趺幢苊膺@一問(wèn)題呢纤垂，請(qǐng)看以下代碼：

ArrayList<String> strings = new ArrayList<String>();
List<String> safeStrings = Collections.checkedList(strings, String.class);
ArrayList rawList = safeStrings;
rawList.add(new Date()); //Checked list throws a ClassCastException

在上面矾策，我們通過(guò)包裝strings得到一個(gè)被檢驗(yàn)視圖safeStrings。這樣在嘗試添加非String對(duì)象時(shí)洒忧，便會(huì)拋出一個(gè)ClassCastException異常蝴韭。

集合視圖的本質(zhì)

集合視圖本身不包含任何數(shù)據(jù)，它只是對(duì)相應(yīng)接口的包裝熙侍。集合視圖所支持的所有操作都是通過(guò)訪問(wèn)它所關(guān)聯(lián)的集合類(lèi)實(shí)例來(lái)實(shí)現(xiàn)的。我們來(lái)看看HashMap的keySet方法的源碼：

public Set<K> keySet() {
  Set<K> ks;
  return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
} 

final class KeySet extends AbstractSet<K> {
  public final int size() { 
    return size; 
  }
  public final void clear() { 
    HashMap.this.clear(); 
  }
  public final Iterator<K> iterator() { 
    return new KeyIterator(); 
  }
  public final boolean contains(Object o) { 
    return containsKey(o); 
  }
  public final boolean remove(Object key) {
    return removeNode(hash(key), key, null, false, true) != null;
  }
  public final Spliterator<K> spliterator() {
    return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
  }
  public final void forEach(Consumer<? super K> action) {
    Node<K,V>[] tab;
    if (action == null) throw new NullPointerException();
    if (size > 0 && (tab = table) != null) {
      int mc = modCount;
      for (int i = 0; i < tab.length; ++i) {
        for (Node<K,V> e = tab[i]; e != null; e = e.next)
          action.accept(e.key);
        }
        if (modCount != mc) throw new ConcurrentModificationException();
      }
  }
}

我們可以看到履磨，實(shí)際上keySet()方法返回一個(gè)內(nèi)部final類(lèi)KeySet的實(shí)例蛉抓。我們可以看到KeySet類(lèi)本身沒(méi)有任何實(shí)例變量。我們?cè)倏碖eySet類(lèi)定義的size()實(shí)例方法剃诅，它的實(shí)現(xiàn)就是通過(guò)直接返回HashMap的實(shí)例變量size巷送。還有clear方法，實(shí)際上調(diào)用的就是HashMap對(duì)象的clear方法矛辕。

keySet方法能夠讓你直接訪問(wèn)到Map的鍵集笑跛，而不需要復(fù)制數(shù)據(jù)或者創(chuàng)建一個(gè)新的數(shù)據(jù)結(jié)構(gòu)，這樣做往往比復(fù)制數(shù)據(jù)到一個(gè)新的數(shù)據(jù)結(jié)構(gòu)更加高效聊品》甚澹考慮這樣一個(gè)場(chǎng)景：你需要把一個(gè)之前創(chuàng)建的數(shù)組傳遞給一個(gè)接收List參數(shù)的方法，那么你可以使用Arrays.asList方法返回一個(gè)包裝了數(shù)組的視圖（這需要的空間復(fù)雜度是常數(shù)級(jí)別的）翻屈，而不用創(chuàng)建一個(gè)新的ArrayList再把原數(shù)組中的數(shù)據(jù)復(fù)制過(guò)去陈哑。

Collections類(lèi)

我們要注意到Collections類(lèi)與Collection接口的區(qū)別：Collection是一個(gè)接口，而Collections是一個(gè)類(lèi)（可以看做一個(gè)靜態(tài)方法庫(kù)）伸眶。下面我們看一下官方文檔對(duì)Collections的描述：

Collections類(lèi)包含了大量用于操作或返回集合的靜態(tài)方法惊窖。它包含操作集合的多態(tài)算法，還有包裝集合的包裝器方法等等厘贼。這個(gè)類(lèi)中的所有方法在集合或類(lèi)對(duì)象為空時(shí)均會(huì)拋出一個(gè)NullPointerException界酒。

關(guān)于Collections類(lèi)中的常用方法，我們上面已經(jīng)做了一些介紹嘴秸，更加詳細(xì)的介紹大家可以參考Java官方文檔毁欣。

總結(jié)

關(guān)于Java集合框架售担，我們首先應(yīng)該把握住幾個(gè)核心的接口，請(qǐng)看下圖（下圖中LinkList拼寫(xiě)有誤署辉，應(yīng)為L(zhǎng)inkedList）：

參考資料

1. 《Java核心技術(shù)（卷一）》
2. What is a view of a collection?
3. Java SE 7 Docs

長(zhǎng)按或掃描二維碼關(guān)注我們欣簇，讓您利用每天等地鐵的時(shí)間就能學(xué)會(huì)怎樣寫(xiě)出優(yōu)質(zhì)app。