摘要：加載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了加載因子與當前容量的乘積時，則要對該哈希表進行操作即重建內部數據結構，從而哈希表將具有大約兩倍的桶數。成員變量每個對由封裝，存在了對象數組中。

雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/
.. 拒絕伸手復制黨

LinkedList 與 ArrayList 一樣實現 List 接口，只是 ArrayList 是 List 接口的大小可變數組的實現，LinkedList 是 List 接口鏈表的實現。
LinkedList 可以被當做堆棧、隊列（實現List接口）或雙端隊列（實現Deque接口）進行操作。
LinkedList 是非同步的。

屬性：

transient int size = 0;
transient Node first;
transient Node last;

構造函數
LinkedList提供了2種構造函數，默認的 和 使用另外一個 collection 來初始化的方式。
使用Collection來初始化，實際上是調用了addAll函數將Collection全部添加到鏈表中。

indexOf

    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

與ArrayList對比，這兩個類的indexOf方法足以說明這兩個類的區別，以及兩個容器類操作的精華。

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

在分析ArrayList的源代碼之前，先學習一下Collection接口及其繼承體系，畢竟ArrayList是Collection的一種實現，了解Collection定義的接口和實現，對整體把握Collection的功能總是有幫助的。

首先，看看Collection接口的定義：
public interface Collection extends Iterable
Collection接口繼承了Iterable，回顧一下迭代器模式，這就說明Collection的各種實現必須提供一個迭代器的功能，讓用戶可以在不知道Collection內部元素的情況下，獲取一種訪問內部元素的方法，具體的訪問順序由迭代器的實現決定，比如List內常用的iterator支持順序的訪問，LinkedList的listIterator支持雙向訪問。

Collection 統一定義的結構包括：
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator iterator();
Object[] toArray();
T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
booelan containsAll(Collection c);
boolean addAll(Collection c);
boolean removeAll(Collection c);
boolean retainAll(Collection c);
void clear();
boolean equals();
int hashCode();

這些接口的功能顧名思義，不再一一介紹，值得注意的是當添加一個元素時，使用的是模板參數E，而contain和remove時，提供的確實Object類型對象，類似的情況在HashMap的源碼中put(K key, V value), get(Object key)也有出現，參考stackoverflow上的相關解答，覺得可以接受的原因描述為：
當對一個參數進行的contains， remove操作在Collection內部都需要調用equals()函數來判斷參數和Colletion內元素的相等關系，但是equals()函數是屬于Object類的方法，并不要求進行比較的兩個元素是同一個類的對象，所以當傳入參數的過程中也就不要求和Collection內部泛型參數類型相同。但是對于put，add等操作，編譯器會在編譯過程中進行類型檢查，需要保證插入的對象是同一個類或者其子類的對象。

說完了Collection接口，下面看看繼承和實現該接口的一些相關類：
抽象類AbstractCollection：
public abstract class AbstractCollection implements Collection
對Collection接口進行最簡單而且必要的實現(iterator()接口仍然保持為抽象，沒有提供實現)，類似AbstractMap。
接口List：
public interface List extends Collection
定義了一種有序的結合，也就是我們所知的序列，與Set不同的是，List允許元素重復。

Collection的簡要繼承結構可以描述為：
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│　└Stack
└Set

下面進入正題，ArrayList源碼分析：
public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable
ArrayList類只有兩個私有屬性：
private transient Object[] elementData，存儲元素的數組
private int size，數組中存儲的元素個數
關于transient關鍵字的說明，參見博文transient關鍵字

ArrayList提供了三種構造函數，默認的，指定數組大小的以及使用另外一個collection來初始化的方式。重點來看第三種，首先將參數集合轉換成數組，賦值給當前集合的數組，設置數組元素個數。如果參數集合返回的不是Object數組，這調用 Arrays.copyOf將數組轉換為Object類型。

contains()


判斷一個元素是否在集合內，根據參數指定的對象在對象數組的索引位置來判斷。

get()



獲取參數位置指定的元素，首先檢查參數的合法性，然后直接使用索引作為數組下標訪問目標元素

set()

替換指定位置的元素

add()






添加一個元素，首先判斷添加一個元素之后是否需要對數組進行擴容，如果需要則創建一個新的數組，并把原來數組的元素拷貝到新數組內，再將待添加的元素放在數組的末尾，也就是add添加元素是將元素插入數組的尾端。添加一個元素會觸發對ArrayList修改次數的增加，即modCount++, 這個步操作的作用是用來“同步”對ArrayList的修改。最常見的使用是在迭代器中，當我們使用迭代器訪問一個ArrayList的過程中，如果意外更改了此字段的值，則迭代器將拋出ConcurrentModificationException來響應next, remove, previous, set和add操作，在迭代期間面臨并發修改時，它提供了快速失敗行為，而不是非確定性行為。

remove()



移除一個元素，提供了兩種移除元素的方法，首先是移除指定位置的元素，并將index后的元素前移一位。然后是移除指定元素，先確定參數指定的元素在ArrayList的索引位置，再調用fastRemove方法按照索引移除一個元素，這邊沒有直接調用remove是為了避免索引位置的越界檢查過程。

iterator()

剩下基本的操作功能還有addAll, removeAll, retainAll等在集合之間進行的操作，不再一一描述。除了這些在集合上的操作，ArrayList還提供了兩種迭代器來訪問List內的元素：Iterator和ListIterator, 前一種迭代器的實現是從List頭部開始順序的訪問內部元素，而ListIterator提供了一種更靈活的實現，支持從指定位置開始訪問、訪問前驅節點的功能。

subList()

除此之外，ArrayList實現了一個私有內部類SubList，支持對List上獲取子序列的操作
從類的屬性和構造函數我們也發現，子序列沒有在內容上作出拷貝，而是通過在原始序列上的偏移量來控制元素的訪問，獲取原始序列的一小段視圖。所以，在SubList執行的修改序列結構的操作比如add,set都將映射到原始序列上。

toArray
ArrayList 提供了 2 個 toArray() 函數：

Object[] toArray()
 T[] toArray(T[] contents)

調用 toArray() 函數會拋出 “java.lang.ClassCastException” 異常，但是調用 toArray(T[] contents) 能正常返回 T[]。

toArray() 會拋出異常是因為 toArray() 返回的是 Object[] 數組，將 Object[] 轉換為其它類型 (如如，將 Object[] 轉換為的 Integer[]) 則會拋出 “java.lang.ClassCastException” 異常，因為 Java 不支持向下轉型。具體的可以參考前面 ArrayList.java 的源碼介紹部分的 toArray()。
解決該問題的辦法是調用 T[] toArray(T[] contents) ， 而不是 Object[] toArray()。

調用 toArray(T[] contents) 返回 T[] 的可以通過以下幾種方式實現。

// toArray(T[] contents)調用方式一
public static Integer[] vectorToArray1(ArrayList v) {
    Integer[] newText = new Integer[v.size()];
    v.toArray(newText);
    return newText;
}

// toArray(T[] contents)調用方式二。最常用！
public static Integer[] vectorToArray2(ArrayList v) {
    Integer[] newText = (Integer[])v.toArray(new Integer[0]);
    return newText;
}

// toArray(T[] contents)調用方式三
public static Integer[] vectorToArray3(ArrayList v) {
    Integer[] newText = new Integer[v.size()];
    Integer[] newStrings = (Integer[])v.toArray(newText);
    return newStrings;
}

Some other thing

從ArrayList的源碼中我們不難發現，當我們插入，刪除元素的過程都將觸發對象數組elementData內容的復制，這是比較耗時的操作，所以ArrayList在元素的插入刪除方面沒有優勢，而元素的隨機訪問就很快。ArrayList上元素的拷貝常用到的函數是Arrays.copyOf() 和System.arrayCopy(), 而Arrays.copyOf在創建了新的數組之后，最終也是要調用System.arrayCopy()進行內容的拷貝，所以System.arrayCopy就直接決定的數組拷貝的效率，在 java的實現中，這個函數是一個native方法，也就是通過其他語言比如C++來獲取更高的執行效率。

trimToSize()， 由于elementData的長度會被拓展，size標記的是其中包含的元素的個數。所以會出現size很小但elementData.length很大 的情況，將出現空間的浪費。trimToSize將返回一個新的數組給elementData，元素內容保持不變，length很size相同，節省空間。

圖片摘自

blog1
blog2
HashMap 實現原理是基于數組+鏈表。
HashMap 就是一個大數組，在這個數組中，通過key的哈希值來尋找存儲在數組的index; 如果遇到多個元素的 hash 值一樣，那么怎么保存，這就引入了鏈表，在同一個 hash 的位置，保存多個元素（通過鏈表關聯起來）。HashMap 所實現的基于 的鍵值對形式，是由其內部內 Entry 實現。

關于 容量和裝載因子

從HashMap 成員變量的定義中可以看到這么幾個定義：
1. capacity 數組容量（hashmap容量）
2. size 數組中實際填充的鍵值對數量 （size 超過 thesold 就數組擴容）
3. thesold 數組中能夠填充的元素最大值 thesold = capacity * loadfactor
4. 裝載因子 loadfactor

HashMap的對象有兩個參數影響其性能：初始容量和裝載因子。初始容量只是哈希表在創建時的容量。加載因子 是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了加載因子與當前容量的乘積時，則要對該哈希表進行 rehash 操作（即重建內部數據結構），從而哈希表將具有大約兩倍的桶數。

HashMap 在擴容的時候，會重新計算 hash 值，并對 hash 的位置進行重新排列，因此，為了效率，盡量給 HashMap 指定合適的容量，避免多次擴容。

成員變量：Entry[] table

每個對由Entry封裝，存在了 Entry對象數組table中。這也是hashmap的bucket.

put方法

尋找鏈表插入位置：
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
Map的key可以是任意類型的，比如如果一個key是基本的數據類型比如int這些，==可以直接比較，而如果使用一些自定義類作為key，需要自己提供equals功能來判斷兩個key對象是不是一致的。

put 方法流程是：
看以table[i]為首的鏈表是否存在插入節點的key的entry;
如果存在：替換value；如果不存在：使用頭插法插入在table[i]位置;
還需要判斷hashmap的數組是否滿了，若滿，table數組擴容2倍。

HashMap 之所以不能保持元素的順序有以下幾點原因：第一，插入元素的時候對元素進行哈希處理，不同元素分配到 table 的不同位置；第二，容量拓展的時候又進行了 hash 處理；第三，復制原表內容的時候鏈表被倒置

HashMap 只允許一個為 null 的 key。

get方法

get(Object key) 根據 key 對應的 hash 值計算在 table 數組中的索引位置，然后遍歷該鏈表判斷是否存在相同的 key 值

for (Entry e = table[indexFor(hash, table.length)];

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

key 的定位

在HashMap中，在獲取一個鍵的hash碼后在查找對應bucket的過程中使用到了一個indexFor函數
static int indexFor(int h, int length) {
return h&(length-1);
}
參考他人分析，弄懂了indexFor函數計算數組下標的原理，過程如下：
根據HashMap的源碼，我們知道HashMap要求長度必須為2的冥，這里就是關鍵所在。它通過h&（length-1）確定hash值的索引下標，這是因為，當length是2的冥時，length-1就是全1的數字，h&(length-1)就是h%(length)，顯然位運算更具有效率。同時如果長度不是2的冥，（length-1）的二進制位表示中叫出現部分0值，與h按位與的時候，這些位永遠是0，那么這些為1的位置將會永遠閑置，導致hash的分布不均勻，降低了查找效率。 比如假設length是15，length-1就是14，其二進制位表示為： 1110。最后一位是1，所有的hash與1110按位與的時候得到的結果最后一位都是0，也就是說Entry[] table內0001,0011，0101， 0111,1001,1011，1101這些位置將永遠不會被填充上數據，導致其他bucket內數據集中，鏈表過長，影響查找效率。

方法列表：

想更一進步的支持我，請掃描下方的二維碼，你懂的~