Java 集合框架分析-概述

yespon 2017-03-21

展開全文

首先來看下java集合框架的總圖，在網(wǎng)上找了兩張關(guān)于集合框架的架構(gòu)圖：

以下內(nèi)容是基于以上架構(gòu)圖進行分析總結(jié)：

集合框架主要分為兩大類:Collection和Map,。

Collection

Collection是List,、Set等集合高度抽象出來的接口，它包含了這些集合的基本操作,，它主要又分為兩大部分：List和Set,。

List接口通常表示一個列表（數(shù)組、隊列,、鏈表,、棧等），其中的元素可以重復(fù),，常用實現(xiàn)類為ArrayList和LinkedList,，另外還有不常用的Vector。另外,，LinkedList還是實現(xiàn)了Queue接口,，因此也可以作為隊列使用。

Set接口通常表示一個集合,，其中的元素不允許重復(fù)（通過hashcode和equals函數(shù)保證）,，常用實現(xiàn)類有HashSet和TreeSet，HashSet是通過Map中的HashMap實現(xiàn)的,，而TreeSet是通過Map中的TreeMap實現(xiàn)的,。另外，TreeSet還實現(xiàn)了SortedSet接口,，因此是有序的集合（集合中的元素要實現(xiàn)Comparable接口,，并覆寫Compartor函數(shù)才行）。

我們看到,，抽象類AbstractCollection,、AbstractList和AbstractSet分別實現(xiàn)了Collection、List和Set接口,，這就是在Java集合框架中用的很多的適配器設(shè)計模式,，用這些抽象類去實現(xiàn)接口，在抽象類中實現(xiàn)接口中的若干或全部方法,，這樣下面的一些類只需直接繼承該抽象類,，并實現(xiàn)自己需要的方法即可,，而不用實現(xiàn)接口中的全部抽象方法。

AbstractList繼承AbstractCollection實現(xiàn)List

/** * {@code AbstractList} is an abstract implementation of the {@code List} interface, optimized * for a backing store which supports random access. This implementation does * not support adding or replacing. A subclass must implement the abstract * methods {@code get()} and {@code size()}, and to create a * modifiable {@code List} it's necessary to override the {@code add()} method that * currently throws an {@code UnsupportedOperationException}. * * @since 1.2 */public abstract class AbstractListE> extends AbstractCollectionE> implements ListE> {}

AbstractSet 繼承AbstractCollection實現(xiàn)Set

/** * An AbstractSet is an abstract implementation of the Set interface. This * implementation does not support adding. A subclass must implement the * abstract methods iterator() and size(). * * @since 1.2 */public abstract class AbstractSet extends AbstractCollection implements Set {}

AbstractCollection實現(xiàn)Collection

/** * Class {@code AbstractCollection} is an abstract implementation of the {@code * Collection} interface. A subclass must implement the abstract methods {@code * iterator()} and {@code size()} to create an immutable collection. To create a * modifiable collection it's necessary to override the {@code add()} method that * currently throws an {@code UnsupportedOperationException}. * * @since 1.2 */public abstract class AbstractCollectionE> implements CollectionE>{}

Map

Map是一個映射接口,，其中的每個元素都是一個key-value鍵值對,，同樣抽象類AbstractMap通過適配器模式實現(xiàn)了Map接口中的大部分函數(shù)，TreeMap,、HashMap,、WeakHashMap等實現(xiàn)類都通過繼承AbstractMap來實現(xiàn)，另外,，不常用的HashTable直接實現(xiàn)了Map接口,，它和Vector都是JDK1.0就引入的集合類。

TreeMap繼承AbstractMap實現(xiàn)NavigableMap

/** @since 1.2 */public class TreeMap<>, V> extends AbstractMap<>, V>        implements SortedMapK, V>, NavigableMapK, V>, Cloneable, Serializable {}

NavigableMap繼承SortedMap

public interface NavigableMapK,V> extends SortedMapK,V> {}

SortedMap接口繼承Map接口

/** * A map that has its keys ordered. The sorting is according to either the * natural ordering of its keys or the ordering given by a specified comparator. */public interface SortedMapK,V> extends MapK,V> {}

HashMap繼承AbstractMap

public class HashMap<>, V> extends AbstractMap<>, V> implements Cloneable, Serializable {}

WeakHashMap繼承AbstractMap

/* * @since 1.2 * @see HashMap * @see WeakReference */public class WeakHashMap<>, V> extends AbstractMap<>, V> implements Map<>, V> {}

Iterator

Iterator是遍歷集合的迭代器（不能遍歷Map,，只用來遍歷Collection）,，Collection的實現(xiàn)類都實現(xiàn)了iterator()函數(shù)，它返回一個Iterator對象,，用來遍歷集合,，ListIterator則專門用來遍歷List。而Enumeration則是JDK1.0時引入的,，作用與Iterator相同,，但它的功能比Iterator要少，它只能再Hashtable,、Vector和Stack中使用,。

ListIterator繼承Iterator

/** * An ListIterator is used to sequence over a List of objects. ListIterator can * move backwards or forwards through the list. */public interface ListIteratorE> extends IteratorE> {}

相關(guān)使用總結(jié)

1、HashMap的總結(jié)

基于哈希表的一個Map接口實現(xiàn),，存儲的對象是一個鍵值對對象(Entry),；值得注意的是HashMap不是線程安全的，如果想要線程安全的HashMap,，可以通過Collections類的靜態(tài)方法synchronizedMap獲得線程安全的HashMap,。
HashMap實際上是一個“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體,。
HashMap的底層主要是基于數(shù)組和鏈表來實現(xiàn)的,，它之所以有相當快的查詢速度主要是因為它是通過計算散列碼來決定存儲的位置。HashMap中主要是通過key的hashCode來計算hash值的,，只要hashCode相同,，計算出來的hash值就一樣。如果存儲的對象對多了,，就有可能不同的對象所算出來的hash值是相同的,，這就出現(xiàn)了所謂的hash沖突。學過數(shù)據(jù)結(jié)構(gòu)的同學都知道,，解決hash沖突的方法有很多，HashMap底層是通過鏈表來解決hash沖突的。圖中,，左邊部分即代表哈希表,，也稱為哈希數(shù)組，數(shù)組的每個元素都是一個單鏈表的頭節(jié)點,，鏈表是用來解決沖突的,，如果不同的key映射到了數(shù)組的同一位置處，就將其放入單鏈表中,。

2,、LinkedHashMap的總結(jié)

由于LinkedHashMap繼承自HashMap，所以它不僅像HashMap那樣對其進行基于哈希表和單鏈表的Entry數(shù)組+next鏈表的存儲方式,，而且還結(jié)合了LinkedList的優(yōu)點,，為每個Entry節(jié)點增加了前驅(qū)和后繼，并增加了一個為header頭結(jié)點,，構(gòu)造了一個雙向循環(huán)鏈表,。（多一個以header為頭結(jié)點的雙向循環(huán)鏈表，也就是說,，每次put進來KV,，除了將其保存到對哈希表中的對應(yīng)位置外，還要將其插入到雙向循環(huán)鏈表的尾部,。）
LinkedHashMap的屬性比HashMap多了一個accessOrder屬性,。當它false時，表示雙向鏈表中的元素按照Entry插入LinkedHashMap到中的先后順序排序,，即每次put到LinkedHashMap中的Entry都放在雙向鏈表的尾部,，這樣遍歷雙向鏈表時，Entry的輸出順序便和插入的順序一致,，這也是默認的雙向鏈表的存儲順序,；當它為true時，表示雙向鏈表中的元素按照訪問的先后順序排列,，可以看到,，雖然Entry插入鏈表的順序依然是按照其put到LinkedHashMap中的順序，但put和get方法均有調(diào)用recordAccess方法（put方法在key相同,，覆蓋原有的Entry的情況下調(diào)用recordAccess方法）,，該方法判斷accessOrder是否為true，如果是,，則將當前訪問的Entry（put進來的Entry或get出來的Entry）移到雙向鏈表的尾部（key不相同時,，put新Entry時，會調(diào)用addEntry,，它會調(diào)用creatEntry,，該方法同樣將新插入的元素放入到雙向鏈表的尾部,，既符合插入的先后順序，又符合訪問的先后順序,，因為這時該Entry也被訪問了）,，否則，什么也不做,。
構(gòu)造函數(shù)中有設(shè)置accessOrder的方法,，如果我們需要實現(xiàn)LRU算法時，就需要將accessOrder的值設(shè)定為TRUE,。
在HashMap的put方法中,，如果key不為null時且哈希表中已經(jīng)在存在時，循環(huán)遍歷table[i]中的鏈表時會調(diào)用recordAccess方法,，而在HashMap中這個方法是個空方法,，在LinkedHashMap中則實現(xiàn)了該方法，該方法會判斷accessOrder是否為true,，如果為true,，它會將當前訪問的Entry（在這里指put進來的Entry）移動到雙向循環(huán)鏈表的尾部，從而實現(xiàn)雙向鏈表中的元素按照訪問順序來排序（最近訪問的Entry放到鏈表的最后,，這樣多次下來,，前面就是最近沒有被訪問的元素，在實現(xiàn),、LRU算法時,，當雙向鏈表中的節(jié)點數(shù)達到最大值時，將前面的元素刪去即可,，因為前面的元素是最近最少使用的）,，否則什么也不做。

3,、ArrayList的總結(jié)

ArrayList底層是基于數(shù)組來實現(xiàn)的,，可以通過下標準確的找到目標元素，因此查找的效率高,；但是添加或刪除元素會涉及到大量元素的位置移動,，效率低。

ArrayList提供了三種不同的構(gòu)造方法,，無參數(shù)的構(gòu)造方法默認在底層生成一個長度為10的Object類型的數(shù)組,，當集合中添加的元素個數(shù)大于10，數(shù)組會自動進行擴容,，即生成一個新的數(shù)組,，并將原數(shù)組的元素放到新數(shù)組中。
ensureCapacity方法對數(shù)組進行擴容,，它會生成一個新數(shù)組,，長度是原數(shù)組的1.5倍+1,，隨著向ArrayList中不斷添加元素，當數(shù)組長度無法滿足需要時,，重復(fù)該過程,。
ArrayList不是同步的（也就是說不是線程安全的，同HashMap,、LinkedHashMap一樣），如果多個線程同時訪問一個ArrayList實例,，而其中至少一個線程從結(jié)構(gòu)上修改了列表,，那么它必須保持外部同步，在多線程環(huán)境下,，可以使用Collections.synchronizedList方法聲明一個線程安全的ArrayList,，例如：List arraylist = Collections.synchronizedList(new ArrayList());

4、LinkedList的總結(jié)

從源碼中可以看出,，LinkedList的實現(xiàn)是基于雙向循環(huán)鏈表的,。卻別與ArrayList的數(shù)組，以及HashMap的線性表和散列表以及LinkedHashMap的線性表和散列表以及雙向循環(huán)鏈表,。
我們在搜索鏈表中的數(shù)據(jù)時,，都會進行判斷是否為null的情況，所以LinkedList是允許元素為null的情況的,。
LinkedList是基于鏈表實現(xiàn)的,，因此不存在容量不足的問題，所以這里沒有擴容的方法,。
源碼中還實現(xiàn)了棧和隊列的操作方法,，因此也可以作為棧、隊列和雙端隊列來使用,。
LinkedList 是一個繼承于AbstractSequentialList的雙向鏈表,。它也可以被當作堆棧、隊列或雙端隊列進行操作,。實現(xiàn) List 接口,，能對它進行隊列操作。實現(xiàn) Deque 接口,，即能將LinkedList當作雙端隊列使用,。實現(xiàn)了Cloneable接口，即覆蓋了函數(shù)clone(),，能克隆,。實現(xiàn)java.io.Serializable接口，這意味著LinkedList支持序列化,，能通過序列化去傳輸,。同時LinkedList 是非同步的,。

Arrays和Collections是用來操作數(shù)組、集合的兩個工具類,。

以上內(nèi)容是針對開頭的那張圖進行概括,，下面一系列文章進行相關(guān)源碼的分析，敬請期待,！