Collection淺析

一：Collection

二：List，有序, 可重複，有下标索引

1.ArrayList

底層動态數組，單線程，線程不安全，初始容量10，1.5倍擴容，查詢效率高，增/删/改效率低

public class ArrayList<E>
{

    transient Object[] elementData; 

    private int size;
}

           

• 擴容：

private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       //1.5倍擴容
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       // minCapacity is usually close to size, so this is a win:
       elementData = Arrays.copyOf(elementData, newCapacity);
   }
   private static int hugeCapacity(int minCapacity) {
       if (minCapacity < 0) // overflow
           throw new OutOfMemoryError();
       return (minCapacity > MAX_ARRAY_SIZE) ?
           Integer.MAX_VALUE :
           MAX_ARRAY_SIZE;
   }
           

2.LinkedList

雙向連結清單實作，單線程，線程不安全，無限擴容，增删快，查詢慢,

public class LinkedList<E>
{
    transient int size = 0;

    /**
     * 頭節點
     */
    transient Node<E> first;

    /**
     * 尾節點
     */
    transient Node<E> last;

    private static class Node<E> {
    	//目前節點
        E item;
        //下一個節點
        Node<E> next;
        //前一個節點
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}
           

3.Vector

底層動态數組，多線程(Synchronized同步方法)，線程安全，初始容量10，2倍擴容，查詢效率比LinkedList高，比ArrayList低(線程安全，消耗資源)

4.ArrayList比LinkedList查詢效率高的原因:

ArrayList在記憶體中是連續、成塊的，隻需要根據首位址+偏移量即可快速計算出查找節點的記憶體位址，LinkedList在記憶體中是不連續的，每一個節點都需要2個指針分别指向上一個節點和下一個節點，隻能通過周遊的方式擷取元素(源碼采用二分查找算法，以提高效率)

• ArrayList查找源碼：

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}
           

• LinkedList查找源碼：

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);
	//二分查找，先定位index的位置，再循環查找
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

           

5.ArrayList比LinkedList修改效率低的原因:

ArrayList在插入/删除元素時，該元素插入位置後的資料的記憶體位址要依次向後移動，而LinkedList是雙向連結清單最多隻會影響到插入/删除元素前後2個位置節點的資訊

• LinkedList插入/删除源碼：

/**
 * 節點尾部插入元素
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
}

/**
 * 删除元素
 */
E unlink(Node<E> x) {

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    return element;
}

           

• ArrayList插入/删除源碼：

// ensureCapacityInternal() 方法内部會調用 System.arraycopy()
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}

public void add(int index, E element) {
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

public E remove(int index) {
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; 

    return oldValue;
}

           

6.LinkedList比ArrayList占用更多的記憶體:

ArrayList每個節點存儲的是實際資料内容，而LinkedList每個節點存儲的是實際資料及前後節點的記憶體位址

7.擴容的目的:

減少連結清單的長度，元素配置設定更均勻

8.ArrayList是線程不安全的，請編寫一個不安全的案例，并給出解決方案？

• 故障現象
• 導緻原因
• 解決方案
• 優化建議

三：Set，無序, 不重複，無下标索引

1.HashSet

底層是HashMap，數組+連結清單結構，初始容量16，加載因子0.75，擴容1倍，存儲元素時先計算該元素的HashCode值，根據HashCode值和集合的長度計算出該元素在集合中的下标，如果該下标處沒有元素就直接存儲，如果有通過equals方法比較是否是同一個對象，如果是不存儲，如果不是通過連結的方式在該下标處存儲元素

2.LinkedHashSet

HashSet的子類，比HashSet多了一個存儲順序的維護

3.TreeSet

• 底層是TreeMap，根據元素的compareTo()方法或者是根據指定的比較器對象的compare()來決定元素的存儲的位置，資料結構使用樹的結構，
• 存儲到TreeSet的元素，要可比較的，要麼元素本身是實作了Comparable接口的，要麼為這個元素的類型單獨指定一個比較器，這個比較器實作了Comparator接口
• 元素如果實作了Comparable接口，重寫了compareTo()方法，那麼按照邏輯角度，應該也重寫equals方法，使得e1.compareTo(e2)==0，e1.equals(e2)==true保持一緻，那麼equals重寫，往往hashcode方法也要重寫

四：Map

1.HashMap

• 底層數組+連結清單結構，線程不安全，entry類型數組，初始容量16，加載因子0.75，擴容1倍，key、value允許為null值
• 存儲過程：計算key的HashCode值，根據HashCode值計算出該元素在entry數組中對應的索引下标，如果該下标處沒有元素就直接存儲，如果有通過equal方法比較，如果相同就不存儲，如果不相同就以連結的形式在該下标處存儲元素
• 擴容：可能造成無效擴容，在插入元素後再判斷是否需要擴容(有可能插入元素後擴容了，但不再有元素進來)
• index計算： hash & (tab.length – 1)

• 1.7和1.8差別

  1.7的資料結構為：動态數組+單連結清單，1.8的資料結構為：動态數組+(連結清單+紅黑樹)，連結清單長度>8轉換為紅黑樹

2.LinkedHashMap

• HashMap的子類，用一個連結清單維護了元素的存儲順序，可以按照存儲順序周遊取出存儲的元素

3.TreeMap

• 底層實作：紅黑樹

  線程非安全，不允許null，key不可以重複，value允許重複

• key類型必須是可排序的，

  （1）key類型本身或它的父類實作了Comparable接口，自然排序，實作了int compareTo(T t)；

  （2）為key類型實作了一個Comparator比較器，定制排序，實作了int compare(T t1,T t2)

• key調用compare或compareTo方法比較，決定存儲的位置

4.ConcurrentHashMap

• JDK1.7 實作
• 資料結構：分段數組+連結清單
• 底層實作：

  分段鎖機制

  ，Segment+ReentrantLock+HashEntyy

  将Map分為N個Segment，線程安全，但效率提升N倍，預設16倍

• 核心靜态内部類：Segment、HashEntry

  1）Segment繼承ReentrantLock充當鎖的角色

  2）HashEntry封裝表的鍵值對

• JDK1.8 實作
• 資料結構：接近HashMap的結構，動态數組+連結清單
• 底層實作：synchronized+cas+HashEntry+紅黑樹

• put 操作：

  1）如果沒有初始化，就調用initTable()進行初始化

  2）如果沒有Hash沖突，就直接cas插入

  3）如果存在hash沖突，synchronized加鎖保證線程安全(鎖住連結清單或紅黑樹的頭節點)，有2種情況，一種是連結清單形式直接周遊尾端插入，一種是紅黑樹結構插入

  4）如果連結清單的長度>8，就先轉換為紅黑樹

  5）添加成功，就調用addCount()方法，統計size()，并檢查是否需要擴容

• get 操作：

  1）計算hash值，定位到在數組中的下标，如果是下标處連結清單的首節點就傳回

  2）如果遇到擴容，會調用标志正在擴容節點ForwardingNode的find方法，查找該節點，比對就傳回

  3）以上都不符合，周遊連結清單，比對就傳回，不比對傳回null

• 差別：

• 鎖的粒度

  1.7鎖的粒度是segment，包含多個Hashentry，1.8隻鎖一個HashEntry，首節點

• 連結清單周遊效率

  1.8使用紅黑樹優化連結清單，當連結清單的長度>8，就轉換為紅黑樹，連結清單的查詢效率提高了

public V put(K key, V value) {
    return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode()); //兩次hash，減少hash沖突，可以均勻分布
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) { //對這個table進行疊代
        Node<K,V> f; int n, i, fh;
        //這裡就是上面構造方法沒有進行初始化，在這裡進行判斷，為null就調用initTable進行初始化，屬于懶漢模式初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//如果i位置沒有資料，就直接無鎖插入
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)//如果在進行擴容，則先進行擴容操作
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            //如果以上條件都不滿足，那就要進行加鎖操作，也就是存在hash沖突，鎖住連結清單或者紅黑樹的頭結點
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) { //表示該節點是連結清單結構
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            //這裡涉及到相同的key進行put就會覆寫原先的value
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {  //插傳入連結表尾部
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {//紅黑樹結構
                        Node<K,V> p;
                        binCount = 2;
                        //紅黑樹結構旋轉插入
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) { //如果連結清單的長度大于8時就會進行紅黑樹的轉換
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);//統計size，并且檢查是否需要擴容
    return null;
}
           

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode()); //計算兩次hash
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {//讀取首節點的Node元素
        if ((eh = e.hash) == h) { //如果該節點就是首節點就傳回
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //hash值為負值表示正在擴容，這個時候查的是ForwardingNode的find方法來定位到nextTable來
        //查找，查找到就傳回
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {//既不是首節點也不是ForwardingNode，那就往下周遊
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}
           

5.HashTable

• 底層實作：數組+連結清單，線程安全(相比ConcurrentHashMap效率低，鎖住整張表)，key和value不能為null，
• 擴容：初始容量11，2倍+1擴容
• index計算：(hash & 0x7FFFFFFF) % tab.length

6.HashTable與HashMap的差別

• 線程安全性

  HashTable線程安全(synchronized，1.5之後提供了ConcurrentHashMap，它是HashTable的替代，比HashTable擴充性更好)，HashMap線程不安全

• null值

  HashTable中key和value都不允許出現null值，HashMap中null可以作為主鍵(隻有一個)，當使用get()方法傳回null值，不一定表示該HashMap沒有該值，需要用containsKey()方法來判斷

• 性能

  當線程場景下，HashMap性能好于HashTable

• 哈希值的使用

  HashTable直接使用對象的HashCode值，HashMap重新計算

• 初始化大小和擴容方式不同，

  HashTable數組預設為11，old*2+1擴容，加載因子0.75，HashMap預設數組大小為16，2倍擴容，加載因子0.75