ArrayList:

ArrayList(int initialCapacity) 是ArrayList實(shí)現(xiàn)的比較重要的構(gòu)造函數(shù)，雖然，我們不常用它，但是某認(rèn)的構(gòu)造函數(shù)正是調(diào)用的該帶參數(shù)：initialCapacity 的構(gòu)造函數(shù)來實(shí)現(xiàn)的。 其中參數(shù)：initialCapacity 表示我們構(gòu)造的這個(gè)ArrayList列表的初始化容量是多大。如果調(diào)用默認(rèn)的構(gòu)造函數(shù)，則表示默認(rèn)調(diào)用該參數(shù)為initialCapacity =10 的方式，來進(jìn)行構(gòu)建一個(gè)ArrayList列表對(duì)象。

為了更好的理解這個(gè)initialCapacity 參數(shù)的概念，我們先看看ArrayList在Sun 提供的源碼中的實(shí)現(xiàn)方式。先看一下它的屬性有哪些：

ArrayList 繼承了AbstractList 我們主要看看ArrayList中的屬性就可以了。

ArrayList中主要包含2個(gè)屬性：

u       private transient Object elementData[];

u       private int size;

其中數(shù)組:：elementData[] 是列表的實(shí)現(xiàn)核心屬性：數(shù)組。 我們使用該數(shù)組來進(jìn)行存放集合中的數(shù)據(jù)。而我們的初始化參數(shù)就是該數(shù)組構(gòu)建時(shí)候的長(zhǎng)度，即該數(shù)組的length屬性就是initialCapacity 參數(shù)。

Keys：transient表示被修飾的屬性不是對(duì)象持久狀態(tài)的一部分，不會(huì)自動(dòng)的序列化。

第2個(gè)屬性：size表示列表中真實(shí)數(shù)據(jù)的存放個(gè)數(shù)。

我們?cè)賮砜匆幌翧rrayList的構(gòu)造函數(shù),加深一下ArrayList是基于數(shù)組的理解。

從源碼中可以看到默認(rèn)的構(gòu)造函數(shù)調(diào)用的就是帶參數(shù)的構(gòu)造函數(shù)： 

public ArrayList(int initialCapacity)

不過參數(shù)initialCapacity＝10　。

我們主要看ArrayList(int initialCapacity)　這個(gè)構(gòu)造函數(shù)。可以看到：

this.elementData = new Object[initialCapacity];

我們就是使用的initialCapacity　這個(gè)參數(shù)來創(chuàng)建一個(gè)Object數(shù)組。而我們所有的往該集合對(duì)象中存放的數(shù)據(jù)，就是存放到了這個(gè)Object數(shù)組中去了。

我們?cè)诳纯戳硗庖粋€(gè)構(gòu)造函數(shù)的源碼：

這里，我們先看size() 方法的實(shí)現(xiàn)形式。它的作用即是返回size屬性值的大小。然后我們?cè)倏戳硗庖粋€(gè)構(gòu)造函數(shù)public ArrayList(Collection c)　，該構(gòu)造函數(shù)的作用是把另外一個(gè)容器對(duì)象中的元素存放到當(dāng)前的List 對(duì)象中。

可以看到，首先，我們是通過調(diào)用另外一個(gè)容器對(duì)象C 的方法size()來設(shè)置當(dāng)前的List對(duì)象的size屬性的長(zhǎng)度大小。

    接下來，就是對(duì)elementData　數(shù)組進(jìn)行初始化，初始化的大小為原先容器大小的1.1倍。最后，就是通過使用容器接口中的Object[] toArray(Object[] a)　方法來把當(dāng)前容器中的對(duì)象都存放到新的數(shù)組elementData　中。這樣就完成了一個(gè)ArrayList 的建立。

    可能大家會(huì)存在一個(gè)問題，那就是，我們建立的這個(gè)ArrayList　是使用數(shù)組來實(shí)現(xiàn)的，但是數(shù)組的長(zhǎng)度一旦被定下來，就不能改變了。而我們?cè)诮oArrayList對(duì)象中添加元素的時(shí)候，卻沒有長(zhǎng)度限制。這個(gè)時(shí)候，ArrayList　中的elementData　屬性就必須存在一個(gè)需要?jiǎng)討B(tài)的擴(kuò)充容量的機(jī)制。我們看下面的代碼，它描述了這個(gè)擴(kuò)充機(jī)制：

這個(gè)方法的作用就是用來判斷當(dāng)前的數(shù)組是否需要擴(kuò)容，應(yīng)該擴(kuò)容多少。其中屬性：modCount是繼承自父類，它表示當(dāng)前的對(duì)象對(duì)elementData數(shù)組進(jìn)行了多少次擴(kuò)容，清空，移除等操作。該屬性相當(dāng)于是一個(gè)對(duì)于當(dāng)前List 對(duì)象的一個(gè)操作記錄日志號(hào)。　我們主要看下面的代碼實(shí)現(xiàn)：

1.      首先得到當(dāng)前elementData　屬性的長(zhǎng)度oldCapacity。

2.      然后通過判斷oldCapacity和minCapacity參數(shù)誰大來決定是否需要擴(kuò)容

n         如果minCapacity大于oldCapacity，那么我們就對(duì)當(dāng)前的List對(duì)象進(jìn)行擴(kuò)容。擴(kuò)容的的策略為：取(oldCapacity * 3)/2 + 1和minCapacity之間更大的那個(gè)。然后使用數(shù)組拷貝的方法，把以前存放的數(shù)據(jù)轉(zhuǎn)移到新的數(shù)組對(duì)象中

n         如果minCapacity不大于oldCapacity那么就不進(jìn)行擴(kuò)容。

下面我們看看上的那個(gè)ensureCapacity方法的是如何使用的:

上的兩個(gè)ａｄｄ方法都是往List 中添加元素。每次在添加元素的時(shí)候，我們就需要判斷一下，是否需要對(duì)于當(dāng)前的數(shù)組進(jìn)行擴(kuò)容。

我們主要看看  public boolean add(Object o)方法，可以發(fā)現(xiàn)在添加一個(gè)元素到容器中的時(shí)候，首先我們會(huì)判斷是否需要擴(kuò)容。因?yàn)橹辉黾右粋€(gè)元素，所以擴(kuò)容的大小判斷也就為當(dāng)前的size+1來進(jìn)行判斷。然后，就把新添加的元素放到數(shù)組elementData中。

第二個(gè)方法public boolean addAll(Collection c)也是同樣的原理。將新的元素放到elementData數(shù)組之后。同時(shí)改變當(dāng)前List 對(duì)象的size屬性。

    類似的List 中的其他的方法也都是基于數(shù)組進(jìn)行操作的。大家有興趣可以看看源碼中的更多的實(shí)現(xiàn)方式。

    最后我們?cè)倏纯慈绾闻袛嘣诩现惺欠褚呀?jīng)存在某一個(gè)對(duì)象的：

由源碼中我們可以看到，public boolean contains(Object elem)方法是通過調(diào)用public int indexOf(Object elem)方法來判斷是否在集合中存在某個(gè)對(duì)象elem。我們看看indexOf方法的具體實(shí)現(xiàn)。

u       首先我們判斷一下elem　對(duì)象是否為null　，如果為null的話，那么遍歷數(shù)組elementData　把第一個(gè)出現(xiàn)null的位置返回。

u       如果elem不為null 的話，我們也是遍歷數(shù)組elementData　，并通過調(diào)用elem對(duì)象的equals()方法來得到第一個(gè)相等的元素的位置。

這里我們可以發(fā)現(xiàn)，ArrayList中用來判斷是否包含一個(gè)對(duì)象，調(diào)用的是各個(gè)對(duì)象自己實(shí)現(xiàn)的equals()方法。在前面的高級(jí)特性里面，我們可以知道：如果要判斷一個(gè)類的一個(gè)實(shí)例對(duì)象是否等于另外一個(gè)對(duì)象，那么我們就需要自己覆寫Object類的public boolean equals(Object obj) 方法。如果不覆寫該方法的話，那么就會(huì)調(diào)用Object的equals()方法來進(jìn)行判斷。這就相當(dāng)于比較兩個(gè)對(duì)象的內(nèi)存應(yīng)用地址是否相等了。

    在集合框架中，不僅僅是List，所有的集合類，如果需要判斷里面是否存放了的某個(gè)對(duì)象，都是調(diào)用該對(duì)象的equals()方法來進(jìn)行處理的。

HASHMAP。

因?yàn)?/span>HashMap里面使用Hash算法，所以在理解HashMap之前，我們需要先了解一下Hash算法和Hash表。

Hash，一般翻譯做“散列”，也有直接音譯為"哈希"的，就是把任意長(zhǎng)度的輸入（又叫做 預(yù)映射， pre-image），通過散列算法，變換成固定長(zhǎng)度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能 會(huì)散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。

說的通俗一點(diǎn)，Hash算法的意義在于提供了一種快速存取數(shù)據(jù)的方法,它用一種算法建立鍵值與真實(shí)值之間的對(duì)應(yīng)關(guān)系,(每一個(gè)真實(shí)值只能有一個(gè)鍵值,但是一個(gè)鍵值可以對(duì)應(yīng)多個(gè)真實(shí)值),這樣可以快速在數(shù)組等里面存取數(shù)據(jù)。

看下圖：

我們建立一個(gè)HashTable（哈希表），該表的長(zhǎng)度為N，然后我們分別在該表中的格子中存放不同的元素。每個(gè)格子下面存放的元素又是以鏈表的方式存放元素。

u       當(dāng)添加一個(gè)新的元素Entry 的時(shí)候，首先我們通過一個(gè)Hash函數(shù)計(jì)算出這個(gè)Entry元素的Hash值hashcode。通過該hashcode值，就可以直接定位出我們應(yīng)該把這個(gè)Entry元素存入到Hash表的哪個(gè)格子中，如果該格子中已經(jīng)存在元素了，那么只要把新的Entry元存放到這個(gè)鏈表中即可。

u       如果要查找一個(gè)元素Entry的時(shí)候，也同樣的方式，通過Hash函數(shù)計(jì)算出這個(gè)Entry元素的Hash值hashcode。然后通過該hashcode值，就可以直接找到這個(gè)Entry是存放到哪個(gè)格子中的。接下來就對(duì)該格子存放的鏈表元素進(jìn)行逐個(gè)的比較查找就可以了。

 舉一個(gè)比較簡(jiǎn)單的例子來說明這個(gè)算法的運(yùn)算方式：

假定我們有一個(gè)長(zhǎng)度為8的Hash表（可以理解為一個(gè)長(zhǎng)度為8的數(shù)組）。在這個(gè)Hash表中存放數(shù)字：如下表

0	1	2	3	4	5	6	7
32	9		11	44	45	6	23
	57			12
	89

假定我們的Hash函數(shù)為：

Hashcode = X%8    -------- 對(duì)8 取余數(shù)

其中X就是我們需要放入Hash表中的數(shù)字，而這個(gè)函數(shù)返回的Hashcode就是Hash碼。

假定我們有下面10個(gè)數(shù)字需要依次存入到這個(gè)Hash表中：

11 , 23 , 44 , 9 , 6 , 32 , 12 , 45 , 57 , 89

通過上面的Hash函數(shù)，我們可以得到分別對(duì)應(yīng)的Hash碼：

11――3 ; 23――7　；44――4　；9――1；6――6；32――0；12――4；45――5；57――1；89――1；

計(jì)算出來的Hash碼分別代表，該數(shù)字應(yīng)該存放到Hash表中的哪個(gè)對(duì)應(yīng)數(shù)字的格子中。如果改格子中已經(jīng)有數(shù)字存在了，那么就以鏈表的方式將數(shù)字依次存放在該格子中，如下表：

0	1	2	3	4	5	6	7
32	9		11	44	45	6	23
	57			12
	89

Hash表和Hash算法的特點(diǎn)就是它的存取速度比數(shù)組差一些，但是比起單純的鏈表，在查找和存儲(chǔ)方面卻要好很多。同時(shí)數(shù)組也不利于數(shù)據(jù)的重構(gòu)而排序等方面的要求。

更具體的說明，讀者可以參考數(shù)據(jù)結(jié)構(gòu)相關(guān)方面的書籍。

簡(jiǎn)單的了解了一下Hash算法后，我們就來看看HashMap的屬性有哪些：

里面最重要的3個(gè)屬性：

n         transient Entry[] table: 用來存放鍵值對(duì)的對(duì)象Entry數(shù)組，也就是Hash表

n         transientint size：當(dāng)前Map中存放的鍵值對(duì)的個(gè)數(shù)

n         finalfloat loadFactor：負(fù)載因子，用來決定什么情況下應(yīng)該對(duì)Entry進(jìn)行擴(kuò)容

我們Entry對(duì)象是Map接口中的一個(gè)內(nèi)部接口。即是使用它來保存我們的鍵值對(duì)的。

我們看看這個(gè)Entry內(nèi)部接口在HashMap中的實(shí)現(xiàn)：

通過查看源碼，我們可以看到Entry類有點(diǎn)類似一個(gè)單向鏈表。其中：

        final Object key　和　Object value;存放的就是我們放入Map中的鍵值對(duì)。

而屬性Entry next;表示當(dāng)前鍵值對(duì)的下一個(gè)鍵值對(duì)是哪個(gè)Entry。

接下來，我們看看HashMap的主要的構(gòu)造函數(shù)：

我們主要看看public HashMap(int initialCapacity, float loadFactor)

因?yàn)椋硗鈨蓚€(gè)構(gòu)造函數(shù)實(shí)行也是同樣的方式進(jìn)行構(gòu)建一個(gè)HashMap 的。

該構(gòu)造函數(shù)：

1.         首先是判斷參數(shù)int initialCapacity和float loadFactor是否合法

2.         然后確定Hash表的初始化長(zhǎng)度。確定的策略是：通過傳進(jìn)來的參數(shù)initialCapacity來找出第一個(gè)大于它的2的次方的數(shù)。比如說我們傳了18這樣的一個(gè)initialCapacity參數(shù)，那么真實(shí)的table數(shù)組的長(zhǎng)度為2的5次方，即32。之所以采用這種策略來構(gòu)建Hash表的長(zhǎng)度，是因?yàn)?/span>2的次方的運(yùn)算對(duì)于現(xiàn)代的處理器來說，可以通過一些方法得到更加好的執(zhí)行效率。

3.         接下來就是得到重構(gòu)因子（threshold）了，這個(gè)屬性也是HashMap中的一個(gè)比較重要的屬性，它表示，當(dāng)Hash表中的元素被存放了多少個(gè)之后，我們就需要對(duì)該Hash表進(jìn)行重構(gòu)。

4.         最后就是使用得到的初始化參數(shù)capacity 來構(gòu)建Hash表：Entry[] table。

下面我們看看一個(gè)鍵值對(duì)是如何添加到HashMap中的。

該put方法是用來添加一個(gè)鍵值對(duì)（key-value）到Map中，如果Map中已經(jīng)存在相同的鍵的鍵值對(duì)的話，那么就把新的值覆蓋老的值，并把老的值返回給方法的調(diào)用者。如果不存在一樣的鍵，那么就返回null。我們看看方法的具體實(shí)現(xiàn)：

1.         首先我們判斷如果key為null則使用一個(gè)常量來代替該key值，該行為在方法maskNull（）終將key替換為一個(gè)非null的對(duì)象k。

2.         計(jì)算key值的Hash碼：hash

3.         通過使用Hash碼來定位，我們應(yīng)該把當(dāng)前的鍵值對(duì)存放到Hash表中的哪個(gè)格子中。indexFor()方法計(jì)算出的結(jié)果：i 就是Hash表（table）中的下標(biāo)。

4.         然后遍歷當(dāng)前的Hash表中table[i]格中的鏈表。從中判斷已否已經(jīng)存在一樣的鍵(Key)的鍵值對(duì)。如果存在一樣的key的鍵，那么就用新的value覆寫老的value，并把老的value返回

5.         如果遍歷后發(fā)現(xiàn)沒有存在同樣的鍵值對(duì)，那么就增加當(dāng)前鍵值對(duì)到Hash表中的第i個(gè)格子中的鏈表中。并返回null。

最后我們看看一個(gè)鍵值對(duì)是如何添加到各個(gè)格子中的鏈表中的：

我們先看void addEntry(int hash, Object key, Object value, int bucketIndex)方法，該方法的作用就用來添加一個(gè)鍵值對(duì)到Hash表的第bucketIndex個(gè)格子中的鏈表中去。這個(gè)方法作的工作就是：

1.         創(chuàng)建一個(gè)Entry對(duì)象用來存放鍵值對(duì)。

2.         添加該鍵值對(duì) ---- Entry對(duì)象到鏈表中

3.         最后在size屬性加一，并判斷是否需要對(duì)當(dāng)前的Hash表進(jìn)行重構(gòu)。如果需要就在void resize(int newCapacity)方法中進(jìn)行重構(gòu)。

之所以需要重構(gòu)，也是基于性能考慮。大家可以考慮這樣一種情況，假定我們的Hash表只有4個(gè)格子，那么我們所有的數(shù)據(jù)都是放到這4個(gè)格子中。如果存儲(chǔ)的數(shù)據(jù)量比較大的話，例如100。這個(gè)時(shí)候，我們就會(huì)發(fā)現(xiàn)，在這個(gè)Hash表中的4個(gè)格子存放的4個(gè)長(zhǎng)長(zhǎng)的鏈表。而我們每次查找元素的時(shí)候，其實(shí)相當(dāng)于就是遍歷鏈表了。這種情況下，我們用這個(gè)Hash表來存取數(shù)據(jù)的性能實(shí)際上和使用鏈表差不多了。

但是如果我們對(duì)這個(gè)Hash表進(jìn)行重構(gòu)，換為使用Hash表長(zhǎng)度為200的表來存儲(chǔ)這100個(gè)數(shù)據(jù)，那么平均2個(gè)格子里面才會(huì)存放一個(gè)數(shù)據(jù)。這個(gè)時(shí)候我們查找的數(shù)據(jù)的速度就會(huì)非常的快。因?yàn)榛旧厦總€(gè)格子中存放的鏈表都不會(huì)很長(zhǎng)，所以我們遍歷鏈表的次數(shù)也就很少，這樣也就加快了查找速度。但是這個(gè)時(shí)候又存在了另外的一個(gè)問題。我們使用了至少200個(gè)數(shù)據(jù)的空間來存放100個(gè)數(shù)據(jù)，這樣就造成至少100個(gè)數(shù)據(jù)空間的浪費(fèi)。在速度和空間上面，我們需要找到一個(gè)適合自己的中間值。在HashMap中我們通過負(fù)載因子（loadFactor）來決定應(yīng)該什么時(shí)候應(yīng)該重構(gòu)我們的Hash表，以達(dá)到比較好的性能狀態(tài)。

我們?cè)倏纯粗貥?gòu)Hash表的方法：void resize(int newCapacity)是如何實(shí)現(xiàn)的：

它的實(shí)現(xiàn)方式比較簡(jiǎn)單：

1.      首先判斷如果Hash表的長(zhǎng)度已經(jīng)達(dá)到最大值，那么就不進(jìn)行重構(gòu)了。因?yàn)檫@個(gè)時(shí)候Hash表的長(zhǎng)度已經(jīng)達(dá)到上限，已經(jīng)沒有必要重構(gòu)了。

2.      然后就是構(gòu)建新的Hash表

3.      把老的Hash表中的對(duì)象數(shù)據(jù)全部轉(zhuǎn)移到新的Hash表newTable中，并設(shè)置新的重構(gòu)因子threshold

對(duì)于HashMap中的實(shí)現(xiàn)原理，我們就分析到這里。大家可能會(huì)發(fā)現(xiàn)，HashCode的計(jì)算，是用來定位我們的鍵值對(duì)應(yīng)該放到Hash表中哪個(gè)格子中的關(guān)鍵屬性。而這個(gè)HashCode的計(jì)算方法是調(diào)用的各個(gè)對(duì)象自己的實(shí)現(xiàn)的hashCode()方法。而這個(gè)方法是在Object對(duì)象中定義的，所以我們自己定義的類如果要在集合中使用的話，就需要正確的覆寫hashCode() 方法。下面就介紹一下應(yīng)該如何正確覆寫hashCode()方法

覆寫hashCode()

在明白了HashMap具有哪些功能，以及實(shí)現(xiàn)原理后，了解如何寫一個(gè)hashCode()方法就更有意義了。當(dāng)然，在HashMap中存取一個(gè)鍵值對(duì)涉及到的另外一個(gè)方法為equals ()，

    設(shè)計(jì)hashCode（）時(shí)最重要的因素就是：無論何時(shí)，對(duì)同一個(gè)對(duì)象調(diào)用hashCode()都應(yīng)該生成同樣的值。如果在將一個(gè)對(duì)象用put（）方法添加進(jìn)HashMap時(shí)產(chǎn)生一個(gè)hashCode()值，而用get()取出時(shí)卻產(chǎn)生了另外一個(gè)hashCode()值，那么就無法重新取得該對(duì)象了。所以，如果你的hashCode()方法依賴于對(duì)象中易變的數(shù)據(jù)，那用戶就要小心了，因?yàn)榇藬?shù)據(jù)發(fā)生變化時(shí)，hashCode()就會(huì)產(chǎn)生一個(gè)不同的hash碼，相當(dāng)于產(chǎn)生了一個(gè)不同的“鍵”。

此外，也不應(yīng)該使hashCode()依賴于具有唯一性的對(duì)象信息，尤其是使用this的值，這只能產(chǎn)生很糟糕的hashCode()。因?yàn)檫@樣做無法生成一個(gè)新的“鍵”，使之與put()種原始的“鍵值對(duì)”中的“鍵”相同。例如，如果我們不覆寫Object的hashCode()方法，那么調(diào)用該方法的時(shí)候，就會(huì)調(diào)用Object的hashCode()方法的默認(rèn)實(shí)現(xiàn)。Object的hashCode（）方法，返回的是當(dāng)前對(duì)象的內(nèi)存地址。下次如果我們需要取一個(gè)一樣的“鍵”對(duì)應(yīng)的鍵值對(duì)的時(shí)候，我們就無法得到一樣的hashCode值了。因?yàn)槲覀兒髞韯?chuàng)建的“鍵”對(duì)象已經(jīng)不是存入HashMap中的那個(gè)內(nèi)存地址的對(duì)象了。