1、集合概述

　　現(xiàn)實(shí)生活中集合：很多事物湊在一起。

　　數(shù)學(xué)中的集合：具有共同屬性的事物的總體。

　　Java中的集合類：是一種工具類，就像是容器，儲(chǔ)存任意數(shù)量的具有共同屬性的對(duì)象。在編程時(shí)，常常需要集中存放多個(gè)數(shù)據(jù)，當(dāng)然我們可以使用數(shù)組來保存多個(gè)對(duì)象。但數(shù)組長(zhǎng)度不可變化，一旦初始化數(shù)組時(shí)指定了數(shù)組長(zhǎng)度，則這個(gè)數(shù)組長(zhǎng)度是不可變的，如果需要保存?zhèn)€數(shù)變化的數(shù)據(jù)，數(shù)組就有點(diǎn)無能為力了；而且數(shù)組無法保存具有映射關(guān)系的數(shù)據(jù)，如成績(jī)表：語文—79，數(shù)學(xué)—80，這種數(shù)據(jù)看上去像兩個(gè)數(shù)組，但這個(gè)兩個(gè)數(shù)組元素之間有一定的關(guān)聯(lián)關(guān)系。

　　為了保存數(shù)量不確定的數(shù)據(jù)，以及保存具有映射關(guān)系的數(shù)據(jù)（也被稱為關(guān)聯(lián)數(shù)組），Java提供集合類。集合類主要負(fù)責(zé)保存其他數(shù)據(jù)，因此集合類也被稱為容器類。所有容器類都位于Java.util包下。集合類和數(shù)組不一樣，數(shù)組元素既可以是基本類型的值，也可以是對(duì)象（實(shí)際上保存的是對(duì)象的引用）；而集合里只能保存對(duì)象（實(shí)際上也是保存對(duì)象的引用，但通常習(xí)慣上認(rèn)為集合里保存的是對(duì)象）。

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

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

　　Java集合框架的優(yōu)勢(shì)有以下幾點(diǎn)：

　　1）這種框架是高性能的。對(duì)基本類集（動(dòng)態(tài)數(shù)組，鏈接表，樹和散列表）的實(shí)現(xiàn)是高效率的。一般很少需要人工去對(duì)這些“數(shù)據(jù)引擎”編寫代碼（如果有的話）。
　　2）框架允許不同類型的類集以相同的方式和高度互操作方式工作。
　　3）類集是容易擴(kuò)展和/或修改的。為了實(shí)現(xiàn)這一目標(biāo)，類集框架被設(shè)計(jì)成包含一組標(biāo)準(zhǔn)的接口。對(duì)這些接口，提供了幾個(gè)標(biāo)準(zhǔn)的實(shí)現(xiàn)工具（例如LinkedList，HashSet和TreeSet），通常就是這樣使用的。如果你愿意的話，也可以實(shí)現(xiàn)你自己的類集。為了方便起見，創(chuàng)建用于各種特殊目的的實(shí)現(xiàn)工具。一部分工具可以使你自己的類集實(shí)現(xiàn)更加容易。
　　4）增加了允許將標(biāo)準(zhǔn)數(shù)組融合到類集框架中的機(jī)制。

2、集合接口和迭代器接口

　　Java的容器類主要由兩個(gè)接口派生而出：Collection和Map，Collection和Map是Java集合框架的根接口，這兩個(gè)接口又包含了一些子接口或?qū)崿F(xiàn)類。通過Collection與Map接口導(dǎo)出其他子接口及實(shí)現(xiàn)類的框架示意圖如下圖所示：

　　查看jdk中Collection類的源碼后會(huì)發(fā)現(xiàn)如下內(nèi)容:

public interface Collection<E> extends Iterable<E> { //實(shí)現(xiàn)Collection接口的通用方法 int size(); boolean isEmpty(); boolean contains(Object o); Iterable<E> iterable(); Object[] toArray(); <T> T[] toArray(T[] a); boolean add(E e); boolean remove(Object o); boolean containsAll(Collection<?> c); boolean addAll(Collection<? extends E> c); boolean removeAll(Collection<?> c); boolean retainAll(Collection<?> c); void clear(); boolean equals(Object o); int hashCode(); }

　　通過源碼發(fā)現(xiàn)Collection是一個(gè)接口類，其繼承了Java迭代器接口Iterable。

　　Collection接口有三個(gè)主要的子接口：List、Set和Queue，注意Map不是Collection的子接口，這個(gè)要牢記。Collection中可以存儲(chǔ)無序元素，可以重復(fù)組和各自獨(dú)立的元素，即其內(nèi)的每個(gè)位置僅持有一個(gè)元素，同時(shí)允許有多個(gè)null元素對(duì)象。

　　JDK不提供Collection接口的具體實(shí)現(xiàn)，而是提供了更加具體的子接口（如Set、List和Queue）的實(shí)現(xiàn)。那么Collection接口的存在有何作用呢？存在即是道理。

　　原因在于：為所有容器的實(shí)現(xiàn)類（如ArrayList實(shí)現(xiàn)了List接口，HashSet實(shí)現(xiàn)了Set接口）提供了兩個(gè)“標(biāo)準(zhǔn)”的構(gòu)造函數(shù)來實(shí)現(xiàn)：一個(gè)無參的構(gòu)造方法；一個(gè)帶有Collection類型參數(shù)的單參數(shù)構(gòu)造方法。實(shí)際上，因?yàn)樗型ㄓ玫娜萜黝惗甲駨腃ollection接口，用第二種構(gòu)造方法允許了容器之間相互的復(fù)制。

　　Collection接口中的方法如下：

　　其中，iterator方法用于返回一個(gè)實(shí)現(xiàn)了Iterator接口的對(duì)象，可以使用這個(gè)迭代器對(duì)象依次訪問集合中的元素。Iterator接口包含3個(gè)方法：

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

　　通過反復(fù)調(diào)用next方法，可以逐個(gè)訪問集合中的每個(gè)元素。但是，如果到達(dá)了集合的末尾，next方法將拋出一個(gè)NoSuchElementException異常，因此，需要在調(diào)用next之前調(diào)用hasNext方法。如果迭代器對(duì)象還有多個(gè)供訪問的元素，這個(gè)方法就返回true。如果要查看集合中的所有元素，就請(qǐng)求一個(gè)迭代器，并在hasNext返回true后反復(fù)調(diào)用next方法。例如：

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

　　從Java SE5.0起，這個(gè)循環(huán)可以采用一種更優(yōu)雅的縮寫方式。用for each循環(huán)可以更加簡(jiǎn)練地表示同樣的循環(huán)操作：

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

　　上面我們一共提到了兩個(gè)和迭代器相關(guān)的接口：Iterable接口和Iterator接口，從字面意義上來看，前者的意思是“可迭代的”，后者的意思是“迭代器”。所以我們可以這么理解這兩個(gè)接口：實(shí)現(xiàn)了Iterable接口的類是可迭代的；實(shí)現(xiàn)了Iterator接口的類是一個(gè)迭代器。

　　迭代器就是一個(gè)我們用來遍歷集合中的對(duì)象的東西。也就是說，對(duì)于集合，我們不是像對(duì)原始類型數(shù)組那樣通過直接訪問元素來迭代，而是通過迭代器來遍歷對(duì)象。這么做的好處是將對(duì)于集合類型的遍歷行為與被遍歷的集合對(duì)象分離，這樣一來我們無需關(guān)心該集合類型的具體實(shí)現(xiàn)是怎樣的。只要獲取這個(gè)集合對(duì)象的迭代器，便可以遍歷這個(gè)集合中的對(duì)象了。而像遍歷對(duì)象的順序這些細(xì)節(jié)，全部由它的迭代器來處理。現(xiàn)在我們來梳理一下前面提到的這些東西：首先，Collection接口實(shí)現(xiàn)了Iterable<E>接口，這意味著所有實(shí)現(xiàn)了Collection接口的具體集合類都是可迭代的。那么既然要迭代，我們就需要一個(gè)迭代器來遍歷相應(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è)元素（若已經(jīng)沒有下一個(gè)元素了，調(diào)用它會(huì)拋出一個(gè)NoSuchElementException異常），remove方法用于移除最近一次調(diào)用next方法返回的元素（若沒有調(diào)用next方法而直接調(diào)用remove方法會(huì)報(bào)錯(cuò)）。我們可以想象在開始對(duì)集合進(jìn)行迭代前，有一個(gè)指針指向集合第一個(gè)元素的前面，第一次調(diào)用next方法后，這個(gè)指針會(huì)“掃過”第一個(gè)元素并返回它，調(diào)用hasNext方法就是看這個(gè)指針后面還有沒有元素了。也就是說這個(gè)指針始終指向剛遍歷過的元素和下一個(gè)待遍歷的元素之間。

　　由于Collection與Iterator都是泛型接口，可以編寫操作任何集合類型的實(shí)用方法。Java類庫的設(shè)計(jì)者認(rèn)為：這些實(shí)用方法中的某些方法非常有用，應(yīng)該將它們提供給用戶使用，這樣，類庫的使用者就不必自己重構(gòu)這些方法了。當(dāng)然如果實(shí)現(xiàn)Collection接口的每一個(gè)類都提供如此多的例行方法將是一件很煩人的事情，為了能夠讓實(shí)現(xiàn)者更容易地實(shí)現(xiàn)這個(gè)接口，Java類庫提供了一個(gè)抽象類AbstractCollection，它將基礎(chǔ)方法size和iterator抽象化了，但是提供了通用例行方法。例如：

public abstract class AbstractCollection<E> implements Collection<E> { public abstract Iterator iterator(); public abstract int size(); public boolean isEmpty() { return size() == 0; } public boolean contains(Object o) { Iterator e = iterator(); if (o==null) { while (e.hasNext()){ if (e.next()==null) return true; } } else { while (e.hasNext()) { if (o.equals(e.next())) return true; } } return false; } public Object[] toArray() { Object[] result = new Object[size()]; Iterator e = iterator(); for (int i=0; e.hasNext(); i++) { result[i] = e.next(); } return result; } public boolean remove(Object o) { Iterator e = iterator(); if (o==null) { while (e.hasNext()) { if (e.next()==null) { e.remove(); return true; } } } else { while (e.hasNext()) { if (o.equals(e.next())) { e.remove(); return true; } } } return false; } ...... }

　　AbstractCollection的直接子類有：AbstractList、AbstractQueue、AbstractSet。

3、Collection接口層次結(jié)構(gòu)

　　下圖是關(guān)于Collection的類的層次結(jié)構(gòu)：

　　Set接口：

　　一個(gè)不包括重復(fù)元素（包括可變對(duì)象）的Collection，是一種無序的集合。Set不包含滿足a.equals(b)的元素對(duì)a和b，并且最多有一個(gè)null。實(shí)現(xiàn)了Set接口的類有：EnumSet、HashSet、TreeSet等。有一種眾所周知的數(shù)據(jù)結(jié)構(gòu)，可以快速查找所需要的對(duì)象，這就是散列表（hash table）。散列表為每個(gè)對(duì)象計(jì)算一個(gè)整數(shù)，稱為散列碼（hash code）。散列碼由對(duì)象的實(shí)例域產(chǎn)生的一個(gè)整數(shù)。準(zhǔn)確地說，具有不同數(shù)據(jù)域的對(duì)象將產(chǎn)生不同的散列碼。如果自定義類，就要負(fù)責(zé)這個(gè)類的hashCode方法，注意，自己實(shí)現(xiàn)的hashCode方法應(yīng)該與equals方法兼容，即若a.equals(b)為true，a與b必須具有相同的散列碼。散列碼可以是任何整數(shù)，包括整數(shù)或負(fù)數(shù)。在Java中，散列表用鏈表數(shù)組實(shí)現(xiàn)，每個(gè)列表稱為桶。計(jì)算對(duì)象的散列碼并對(duì)桶數(shù)取余，得到的結(jié)果就是保存這個(gè)對(duì)象的桶的索引。如果想要更多地控制散列表的性能，就要指定一個(gè)初始的桶數(shù)。通常，將桶數(shù)設(shè)置為預(yù)計(jì)元素個(gè)數(shù)的75%~150%。有些研究人員認(rèn)為：盡管還沒有確鑿的證據(jù)，但最好將桶數(shù)設(shè)置為素?cái)?shù)，以防鍵的集聚。

　　當(dāng)然，并不是總能夠知道需要存儲(chǔ)多少個(gè)元素的，也有可能最初的估計(jì)過低。如果散列表太滿，就需要再散列（rehashed）。如果要對(duì)散列表再散列，就需要?jiǎng)?chuàng)建一個(gè)桶數(shù)更多的表，并將所有元素插入新表中，廢棄舊表。裝填因子（load factor）決定何時(shí)對(duì)散列表進(jìn)行再散列。例如，如果裝填因子為0.75（默認(rèn)值），而表中超過75%的位置已經(jīng)填入元素，這個(gè)表就會(huì)用雙倍的桶數(shù)自動(dòng)地進(jìn)行再散列。

　　Java集合類庫提供了一個(gè)HashSet類，它實(shí)現(xiàn)了基于散列表的集。可以用add方法添加元素。contains方法已經(jīng)被重新定義，用來快速查看是否某個(gè)元素已經(jīng)出現(xiàn)在集中，它只在某個(gè)桶中查找元素，而不必查看集合中的所有元素。樹集（TreeSet）是一個(gè)有序集合，當(dāng)前使用的數(shù)據(jù)結(jié)構(gòu)是紅黑樹。將一個(gè)元素添加到樹中要比添加到散列表中慢，但是，與將元素添加到數(shù)組或鏈表的正確位置上相比還是快很多的。TreeSet中的對(duì)象需要實(shí)現(xiàn)Comparable接口，這樣才能進(jìn)行元素之間的比較，如果一個(gè)類的創(chuàng)建者沒有實(shí)現(xiàn)Comparable接口，可以創(chuàng)建一個(gè)Comparator類來規(guī)定原類對(duì)象之間的比較規(guī)則，將一個(gè)Comparator對(duì)象實(shí)例傳遞給TreeSet的構(gòu)造器即可。

　　List接口：

　　一個(gè)有序的Collection（也稱序列），元素可以重復(fù)。列表通常允許滿足e1.equals(e2)的元素對(duì)e1和e2，并且列表允許多個(gè)null元素。實(shí)現(xiàn)List的類有：ArrayList、LinkedList、Vector、Stack等。其中，最常用的是ArrayList和LinkedList。List接口是有序集合、元素可以重復(fù)，次序是List接口最重要的特點(diǎn)，它是以元素的添加的順序作為集合的順序，因此List的實(shí)現(xiàn)類中有可以通過來操作集合元素的方法。其中ArrayList底層是通過數(shù)組實(shí)現(xiàn)的，數(shù)組的初始長(zhǎng)度為10，可以擴(kuò)展數(shù)組。LinkedList底層是通過雙向鏈表實(shí)現(xiàn)的，因此LinkedList可以在首尾添加刪減元素，因此可以作為棧、隊(duì)列、雙端隊(duì)列使用。

　　Queue接口：

　　Queue接口的實(shí)現(xiàn)類在使用時(shí)要盡量避免Collection的add()和remove()方法，而是要使用offer()來加入元素，使用poll()來獲取并移出元素。它們的優(yōu)點(diǎn)是通過返回值可以判斷成功與否，add()和remove()方法在失敗的時(shí)候會(huì)拋出異常。offer()方法向隊(duì)列中加入元素，不成功時(shí)返回false。而直接使用add()方法插入，若隊(duì)列已滿則拋出異常。remove()和poll()方法刪除并返回隊(duì)列一端的元素。前者隊(duì)列為空時(shí)拋出異常，后者返回null。

　　Java SE 6中引入了Deque接口，它是Queue接口的子接口，Deque的實(shí)現(xiàn)類為ArrayDeque，可以實(shí)現(xiàn)雙端隊(duì)列，底層是通過數(shù)組實(shí)現(xiàn)，ArrayDeque有兩個(gè)標(biāo)志位分別指向數(shù)組的頭與尾，因此才可以實(shí)現(xiàn)雙端隊(duì)列。

　　當(dāng)需要使用LIFO（后進(jìn)先出）堆棧時(shí)。應(yīng)優(yōu)先使用Deque接口而不是遺留Stack類。在將雙端隊(duì)列用作堆棧時(shí)，元素被推入雙端隊(duì)列的開頭并從雙端隊(duì)列開頭彈出。堆棧的方法完全可以等效成Deque的某些方法，對(duì)應(yīng)關(guān)系如下：

push(e)---addFirst(e) pop()---removeFrist() top()-----peekFirst()

　　優(yōu)先級(jí)隊(duì)列（priority queue）中的元素可以按照任意的順序插入，卻總是按照排序的順序進(jìn)行檢索。也就是說，無論何時(shí)調(diào)用remove方法，總會(huì)獲得當(dāng)前的優(yōu)先級(jí)隊(duì)列中最小的元素。優(yōu)先級(jí)隊(duì)列并沒有對(duì)所有的元素進(jìn)行排序。優(yōu)先級(jí)隊(duì)列使用了堆，堆是一個(gè)可以自我調(diào)整的二叉村，對(duì)樹執(zhí)行添加和刪除操作時(shí)，總能保證最小的元素移動(dòng)到根，而不必花費(fèi)時(shí)間對(duì)元素進(jìn)行排序。與TreeSet一樣，一個(gè)優(yōu)先級(jí)隊(duì)列既可以保存實(shí)現(xiàn)了Comparable接口的類對(duì)象，也可以保存在構(gòu)造器提供比較器的類對(duì)象。

　　優(yōu)先級(jí)隊(duì)列的典型應(yīng)用是任務(wù)調(diào)度。每一個(gè)任務(wù)有一個(gè)優(yōu)先級(jí)，將優(yōu)先級(jí)最高的任務(wù)從隊(duì)列中刪除（由于習(xí)慣上將1設(shè)為“最高”優(yōu)先級(jí)，所以會(huì)將最小的元素刪除）。與TreeSet迭代不同，這里的迭代并不是按照元素的排列順序迭代的。刪除時(shí)總是刪掉剩余元素中優(yōu)先級(jí)數(shù)最小的元素。

　　還有一種隊(duì)列是阻塞式隊(duì)列，隊(duì)列滿了以后再插入元素則會(huì)拋出異常，主要實(shí)現(xiàn)類包括：ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。雖然接口并未定義阻塞方法，但是實(shí)現(xiàn)類擴(kuò)展了父接口，實(shí)現(xiàn)了阻塞方法。

4、Map接口的層次結(jié)構(gòu)

　　下面的圖是Map接口的層次結(jié)構(gòu)圖

　　Map是一個(gè)鍵值對(duì)的集合。也就是說，一個(gè)映射不能包含重復(fù)的鍵，每個(gè)鍵最多映射到一個(gè)值。該接口取代了Dictionary抽象類。實(shí)現(xiàn)map接口的類有：HashMap、TreeMap、HashTable、Properties、EnumMap。

　　散列映射表對(duì)鍵進(jìn)行散列，樹映射表用鍵的整體順序?qū)υ剡M(jìn)行排序，并將其組織成搜索村。散列或比較函數(shù)只能作用于鍵，與鍵關(guān)聯(lián)的值不能進(jìn)行散列或比較。

　　如何選擇散列映射表與樹映射表。散列稍微快一些，如果不需要按照排列順序訪問鍵，就最好選擇散列。映射表中鍵必須是唯一的，不能對(duì)同一個(gè)鍵存放兩個(gè)值。如果對(duì)同一個(gè)鍵兩次調(diào)用put方法，第二個(gè)值就會(huì)取代第一個(gè)值。實(shí)際上，put方法會(huì)返回用這個(gè)鍵參數(shù)存儲(chǔ)的上一個(gè)值。

　　集合框架并沒有將映射表本身視為一個(gè)集合（其他的數(shù)據(jù)結(jié)構(gòu)框架則將映射表視為對(duì)pairs的集合，或者視為用鍵作為索引的值的集合）。然而，可以獲得映射表的視圖，這是一組實(shí)現(xiàn)了Collection接口或者它的子接口的視圖。有3個(gè)視圖，它們分別是：鍵集、值集和鍵/值對(duì)集，鍵與鍵/值對(duì)形成了一個(gè)集，這是因?yàn)樵谟成浔碇幸粋€(gè)鍵只能有一個(gè)副本。下列方法將返回這3個(gè)視圖（條目集的元素是靜態(tài)內(nèi)部類Map.Entry的對(duì)象）。

Set<K> keyset(); Collection<K> values(); Set<Map.Entry<K,V>> entrySet();

　　注意，keySet既不是HashSet，也不是TreeSet，而是實(shí)現(xiàn)了Set接口的某個(gè)其他類的對(duì)象。初看起來，keyset方法創(chuàng)建了一個(gè)新集，并將映射表中的所有鍵都填進(jìn)去，然后返回這個(gè)集。但是，情況并非如此。取而代之的是：keySet方法返回一個(gè)實(shí)現(xiàn)了Set接口的某個(gè)類的對(duì)象，這個(gè)類的方法對(duì)原映射表進(jìn)行操作。Set接口擴(kuò)展了Collection接口，因此可以與使用任何集合一樣使用keySet。例如，可以杖舉映射表中的所有鍵：

Set<String> keys = map.keySet(); for(String key: keys){ System.out.println(key); }

　　如果想要同時(shí)查看鍵與值，可以通過杖舉各個(gè)條目（entries）查看，以避免對(duì)值進(jìn)行查找。

for(Map.Entry<String, Employee> entry : staff.entrySet()){ String key = entry.getKey(); Employee value = entry.getValue(); System.out.println("key = " + key + ", value = " + value); }

5、數(shù)組與集合之間的轉(zhuǎn)換

　　由于Java平臺(tái)API中大部分內(nèi)容都是在集合框架創(chuàng)建之前設(shè)計(jì)的，所以，有時(shí)候需要在傳統(tǒng)的數(shù)組與現(xiàn)代的集合之間進(jìn)行轉(zhuǎn)換。如果數(shù)組要轉(zhuǎn)換為集合，Arrays.asList的包裝器就可以實(shí)現(xiàn)這個(gè)目的。例如：

String[] values = ...; HashSet<String> staff = new HashSet<String>(Arrays.asList(values));

　　反過來，將集合轉(zhuǎn)換為數(shù)組采用toArray()方法。轉(zhuǎn)化為Object[]類型數(shù)組方法如下：

Object[] listArray = list.toArray(); Object[] setArray = set.toArray();

　　轉(zhuǎn)化為具體類型數(shù)組：

String[] array1 = (String[])list.toArray(new String[list.size()]); String[] array2 = (String[])list.toArray(new String[0]);

　　在轉(zhuǎn)化為其它類型的數(shù)組時(shí)需要強(qiáng)制類型轉(zhuǎn)換，并且要使用帶參數(shù)的toArray方法，參數(shù)為對(duì)象數(shù)組，將list中的內(nèi)容放入?yún)?shù)數(shù)組中，當(dāng)參數(shù)數(shù)組的長(zhǎng)度小于list的元素個(gè)數(shù)時(shí)，會(huì)自動(dòng)擴(kuò)充數(shù)組的長(zhǎng)度以適應(yīng)list的長(zhǎng)度。因此，最好在數(shù)組構(gòu)造時(shí)指明其長(zhǎng)度。

6、List接口實(shí)現(xiàn)類

　　List接口繼承了Collection接口，并對(duì)父接口進(jìn)行了簡(jiǎn)單的擴(kuò)充：同時(shí)List接口又有三個(gè)常用的實(shí)現(xiàn)類ArrayList、LinkedList和Vector。

　　1）ArrayList（數(shù)組線性表）

　　ArrayList數(shù)組線性表的特點(diǎn)為：用類似數(shù)組的形式進(jìn)行存儲(chǔ)，因此它的隨機(jī)訪問速度極快。ArrayList數(shù)組線性表的缺點(diǎn)為：不適合于在線性表中間頻繁地進(jìn)行插入和刪除操作。因?yàn)槊看尾迦牒蛣h除都需要移動(dòng)數(shù)組中的元素。可以這樣理解ArrayList就是基于數(shù)組的一個(gè)線性表，只不過數(shù)組的長(zhǎng)度可以動(dòng)態(tài)改變而已。

　　對(duì)于使用ArrayList的開發(fā)者而言，下面幾點(diǎn)內(nèi)容一定要注意啦，尤其找工作面試的時(shí)候經(jīng)常會(huì)被問到。

　　①如果在初始化ArrayList的時(shí)候沒有指定初始化長(zhǎng)度的話，默認(rèn)的長(zhǎng)度為10，源碼中就是這樣設(shè)置的：

/* * Constructs an empty list with an initial capacity of ten. **/ public ArrayList() { this(10); }

　　②ArrayList在增加新元素的時(shí)候如果超過了原始的容量的話，ArrayList擴(kuò)容的方案為：上一次的容量*1.5+1。代碼如下（Java1.8中ArrayList的擴(kuò)容代碼已經(jīng)變了，這里暫時(shí)沒有更新）：

public void ensureCapacity(int minCapacity){ modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } }

　　③ArrayList是線程不安全的，在多線程的情況下不要使用。如果一定在多線程使用List，可以使用Vector，因?yàn)閂ector和ArrayList基本一致，區(qū)別在于Vector中的絕大部分方法都使用了同步關(guān)鍵字修飾，這樣在多線程的情況下不會(huì)出現(xiàn)并發(fā)錯(cuò)誤，還有就是它們的擴(kuò)容方案不同，ArrayList是擴(kuò)容方案是：原始容量*3/2+1，而Vector允許設(shè)置默認(rèn)的增長(zhǎng)長(zhǎng)度，Vector的默認(rèn)擴(kuò)容方式為原來的2倍。切記Vector是ArrayList的多線程的一個(gè)替代品。

　　④ArrayList實(shí)現(xiàn)遍歷的幾種方法

public class Test{ public static void main(String[] args) { List<String> list=new ArrayList<String>(); list.add("Hello"); list.add("World"); list.add("HAHAHAHA"); //第一種遍歷方法使用foreach遍歷List,這是推薦的通用方法for (String str : list) { System.out.println(str); } //第二種遍歷，把list變?yōu)閿?shù)組相關(guān)的內(nèi)容進(jìn)行遍歷 String[] strArray=new String[list.size()]; list.toArray(strArray); for(int i=0;i<strArray.length;i++) { System.out.println(strArray[i]); } //第三種遍歷 使用迭代器進(jìn)行遍歷 Iterator<String> ite=list.iterator(); while(ite.hasNext()){ System.out.println(ite.next()); } } }

　　2）LinkedList（鏈?zhǔn)骄€性表）

　　LinkedList的鏈?zhǔn)骄€性表的特點(diǎn)為：適用于需要在鏈表中間頻繁進(jìn)行插入和刪除操作的場(chǎng)合。LinkedList的鏈?zhǔn)骄€性表的缺點(diǎn)為：隨機(jī)訪問速度較慢。查找一個(gè)元素需要從頭開始一個(gè)一個(gè)的找。LinkedList是用雙向循環(huán)鏈表實(shí)現(xiàn)的。對(duì)于使用LinkedList的開發(fā)者而言，下面幾點(diǎn)內(nèi)容一定要注意啦，尤其找工作面試的過程時(shí)候經(jīng)常會(huì)被問到。

　　①簡(jiǎn)述LinkedList和ArrayList的區(qū)別和聯(lián)系。
　　ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，LinkedList是基于鏈表的數(shù)據(jù)結(jié)構(gòu)。ArrayList數(shù)組線性表的特點(diǎn)為：類似數(shù)組的形式進(jìn)行存儲(chǔ)，內(nèi)存連續(xù)，因此它的隨機(jī)訪問速度極快。ArrayList數(shù)組線性表的缺點(diǎn)為：不適合于在線性表中間需要頻繁進(jìn)行插入和刪除操作。因?yàn)槊看尾迦牒蛣h除都需要移動(dòng)數(shù)組中的元素。LinkedList的鏈?zhǔn)骄€性表的特點(diǎn)為：適合于在鏈表中間需要頻繁進(jìn)行插入和刪除操作。LinkedList的鏈?zhǔn)骄€性表的缺點(diǎn)為:隨機(jī)訪問速度較慢。查找一個(gè)元素需要從頭開始一個(gè)一個(gè)的找。

　　②LinkedList的內(nèi)部實(shí)現(xiàn)是怎樣的
　　對(duì)于這個(gè)問題，最好看一下jdk中LinkedList的源碼。這樣會(huì)醍醐灌頂?shù)摹inkedList的內(nèi)部是用基于雙向循環(huán)鏈表的結(jié)構(gòu)來實(shí)現(xiàn)的。在LinkedList中有一個(gè)類似于C語言中結(jié)構(gòu)體的Entry內(nèi)部類。在Entry的內(nèi)部類中包含了前一個(gè)元素的地址引用和后一個(gè)元素的地址引用類似于C語言中指針

　　③LinkedList不是線程安全的
　　注意LinkedList和ArrayList一樣也不是線程安全的，如果要在多線程并發(fā)環(huán)境中使用LinkedList，需要在要求同步的方法上加上同步關(guān)鍵字synchronized。

　　3）Vector（向量）

　　Vector和ArrayList幾乎是完全相同的，唯一的區(qū)別在于Vector是同步類(synchronized)，即線程安全的。因此，開銷就比ArrayList要大，正常情況下，大多數(shù)的Java程序員使用ArrayList而不是Vector，因?yàn)橥酵耆梢杂沙绦騿T自己來控制。

　　引申：線程安全就是多線程訪問時(shí)，采用了加鎖機(jī)制，當(dāng)一個(gè)線程訪問該類的某個(gè)數(shù)據(jù)時(shí)，進(jìn)行保護(hù)，其他線程不能進(jìn)行訪問直到該線程讀取完，其他線程才可使用。不會(huì)出現(xiàn)數(shù)據(jù)不一致或者數(shù)據(jù)污染。線程不安全就是不提供數(shù)據(jù)訪問保護(hù)，有可能出現(xiàn)多個(gè)線程先后更改數(shù)據(jù)造成所得到的數(shù)據(jù)是臟數(shù)據(jù)。

7、HashMap與HashTable

　　HashMap和HashTable的比較是Java面試中的常見問題，用來考驗(yàn)程序員是否能夠正確使用集合類以及是否可以隨機(jī)應(yīng)變使用多種思路解決問題。HashMap的工作原理、ArrayList與Vector的比較是有關(guān)Java集合框架的最經(jīng)典的問題。HashTable是個(gè)過時(shí)的集合類，存在于Java API中很久了。在Java 4中被重寫了，它實(shí)現(xiàn)了Map接口，所以自此以后也成了Java集合框架中的一部分。HashTable和HashMap在Java面試中相當(dāng)容易被問到，甚至成為了集合框架面試題中最常被考的問題。Key-Value鍵值存儲(chǔ)的示意圖如下圖所示：

　　Hashtable和HashMap的內(nèi)部數(shù)據(jù)結(jié)構(gòu)相似，如下圖所示：

　　其基本內(nèi)部數(shù)據(jù)結(jié)構(gòu)是一個(gè)Entry數(shù)組和鏈表的結(jié)合體。Entry數(shù)組的元素為實(shí)現(xiàn)了Map.Entry

Map map = new HashMap(); map.put("Rajib Sarma","100"); map.put("Rajib Sarma","200"); //The value "100" is replaced by "200". map.put("Sazid Ahmed","200"); Iterator iter = map.entrySet().iterator(); while (iter.hasNext()) { Map.Entry entry = (Map.Entry) iter.next(); Object key = entry.getKey(); Object val = entry.getValue(); }

　　HashTable和HashMap區(qū)別主要集中在線程安全性、同步（synchronization）和速度上，分別有以下幾點(diǎn)：

　　1）繼承層次不同，二者都實(shí)現(xiàn)了Map接口，但HashTable繼承了Dictionary類，而HashMap繼承了AbstractMap類。

public class Hashtable extends Dictionary implements Map public class HashMap extends AbstractMap implements Map

　　2）在HashTable中，key和value都不允許出現(xiàn)null值。在HashMap中，null可以作為鍵，這樣的鍵只有一個(gè)；可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為null。當(dāng)get()方法返回null值時(shí)，既可以表示HashMap中沒有該鍵，也可以表示該鍵所對(duì)應(yīng)的值就是null。因此，在HashMap中不能由get()方法來判斷HashMap中是否存在某個(gè)鍵，而應(yīng)該用containsKey()方法來判斷。

　　3）HashMap是非synchronized，而HashTable是synchronized，這意味著HashTable是線程安全的，多個(gè)線程可以共享一個(gè)HashTable；而如果程序員沒有手工進(jìn)行正確的同步的話，多個(gè)線程是不能共享HashMap的。由于HashTable是線程安全的也是synchronized，所以在單線程環(huán)境下它比HashMap要慢。如果你不需要同步，只應(yīng)用于單線程，那么使用HashMap性能要好過HashTable。HashMap可以通過下面的語句進(jìn)行同步：

Map m = Collections.synchronizeMap(hashMap);

　　4）哈希值的使用不同，HashTable直接使用對(duì)象的HashCode，根據(jù)key值計(jì)算index的代碼是這樣的：

int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length;

　　當(dāng)hash數(shù)組的長(zhǎng)度較小，并且Key的hashCode低位數(shù)值分散不均勻時(shí)，不同的hash值計(jì)算得到相同下標(biāo)值的幾率較高。HashMap不直接使用對(duì)象的HashCode，而是重新計(jì)算hash值，而且用與運(yùn)算代替了求模運(yùn)算，代碼如下：

static int indexFor(int h，int length) { return h & (length-1); } static int hash(Object x) { int h = x.hashCode(); h += ~(h << 9); h ^= (h >>> 14); h += (h << 4); h ^= (h >>> 10); return h; } int hash = hash(k); int i = indexFor(hash, table.length);

　　這種計(jì)算方式優(yōu)于HashTable，通過對(duì)Key的hashCode做移位運(yùn)算和位的與運(yùn)算，使其能更廣泛地分散到數(shù)組的不同位置上去。

　　5）HashTable中hash數(shù)組默認(rèn)大小是11，初始化時(shí)可以指定initial capacity（數(shù)組初始長(zhǎng)度），擴(kuò)容方式是old*2+1。HashMap中hash數(shù)組的默認(rèn)大小是16，而且長(zhǎng)度始終保持為2的n次方，初始化時(shí)同樣可以指定initial capacity（數(shù)組初始長(zhǎng)度），若不是2的次方，HashMap將選取第一個(gè)大于initial capacity的2n次方值作為其初始長(zhǎng)度。

　　6）遍歷方式的內(nèi)部實(shí)現(xiàn)上不同。HashTable與HashMap都使用了Iterator。而由于歷史原因（HashTable繼承了Dictionary類），HashTable還使用了Enumeration的方式。一般單線程情況下，HashMap能夠比HashTable工作得更好、更快，主要得益于它的散列算法，以及沒有作線程同步。應(yīng)用程序一般在更高的層面上實(shí)現(xiàn)了保護(hù)機(jī)制，而不是依賴于這些底層數(shù)據(jù)結(jié)構(gòu)的同步，因此，HashMap能夠在大多數(shù)應(yīng)用中滿足需要。推薦使用HashMap，如果需要同步，可以使用同步工具類將其轉(zhuǎn)換成支持同步的HashMap。

總結(jié)

以上是生活随笔為你收集整理的Java集合框架完全解析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。