各種集合、對象初始創建默認大小
- 2020 年 4 月 1 日
- 筆記
一、字元串類別（只詳細說了StringBuffer）
StringBuffer
1、StringBuffer為執行緒安全的類，所有方法都使用synchronized修飾（如：public synchronized int length() {return count;}）。StringBuffer的構造器有4種，底層為創建指定大小的char數組。
1）、無參的構造器，默認大小為16
public StringBuffer() { super(16); }
其中父類為AbstractStringBuilder，構造器為：
/** * Creates an AbstractStringBuilder of the specified capacity. */ AbstractStringBuilder(int capacity) { value = new char[capacity]; }
2）、指定大小的構造器
/** * Constructs a string buffer with no characters in it and * the specified initial capacity. * * @param capacity the initial capacity. * @exception NegativeArraySizeException if the <code>capacity</code> * argument is less than <code>0</code>. */ public StringBuffer(int capacity) { super(capacity); }
3）、指定字元創的構造器，底層char數組長度為字元串長度+16（及最小16）
/** * Constructs a string buffer initialized to the contents of the * specified string. The initial capacity of the string buffer is * <code>16</code> plus the length of the string argument. * * @param str the initial contents of the buffer. * @exception NullPointerException if <code>str</code> is <code>null</code> */ public StringBuffer(String str) { super(str.length() + 16); append(str); }
4）、指定CharSequence 的構造器，底層char數組長度為CharSequence串長度+16（及最小16）
/** * Constructs a string buffer that contains the same characters * as the specified <code>CharSequence</code>. The initial capacity of * the string buffer is <code>16</code> plus the length of the * <code>CharSequence</code> argument. * <p> * If the length of the specified <code>CharSequence</code> is * less than or equal to zero, then an empty buffer of capacity * <code>16</code> is returned. * * @param seq the sequence to copy. * @exception NullPointerException if <code>seq</code> is <code>null</code> * @since 1.5 */ public StringBuffer(CharSequence seq) { this(seq.length() + 16); append(seq); }
2、StringBuffer和StringBuilder的擴容，兩者的append(String value)都是使用父類AbstractStringBuilder的append方法：
public synchronized StringBuffer append(String str) { super.append(str); return this; }
父類中append的方法（下面的count表示當前數組已經存有數據的個數）
public AbstractStringBuilder append(String str) { if (str == null) str = "null"; int len = str.length(); ensureCapacityInternal(count + len); str.getChars(0, len, value, count); count += len; return this; }
在存儲數據的時候會檢查ensureCapacityInternal()當前數組的容量
/** * This method has the same contract as ensureCapacity, but is * never synchronized. */ private void ensureCapacityInternal(int minimumCapacity) { // overflow-conscious code if (minimumCapacity - value.length > 0) expandCapacity(minimumCapacity); }
如果當前數據已有值的長度加上需要append的值的長度大於當前數組的長度（value.length表示當前數組的總長度），那麼就會擴容。擴容後的大小為當前的2倍加2
/** * This implements the expansion semantics of ensureCapacity with no * size check or synchronization. */ void expandCapacity(int minimumCapacity) { int newCapacity = value.length * 2 + 2; if (newCapacity - minimumCapacity < 0) newCapacity = minimumCapacity; if (newCapacity < 0) { if (minimumCapacity < 0) // overflow throw new OutOfMemoryError(); newCapacity = Integer.MAX_VALUE; } value = Arrays.copyOf(value, newCapacity); }
在擴容過程中，擴容後的長度如果還是沒有當前需要存入新字元後的長度大，那麼直接使用當前需要的長度。然後下一步在判斷是否已經超過了int的最大長度（2的31次方-1，最大正int整數） ，操作該長度就會變成一個負整數，所以是通過<0來判斷，如果超過最大正的int整數，那麼就報記憶體溢出。否則則將舊數組的內容複製到擴容後新數組中來。
總結：
1）同類型的StringBuilder和StringBuffer的實現原理一樣，其父類都是AbstractStringBuilder。StringBuffer是執行緒安全的，StringBuilder是JDK 1.5新增的，其功能和StringBuffer類似，但是非執行緒安全。因此，在沒有多執行緒問題的前提下，使用StringBuilder會取得更好的性能。
2）String是不可變對象，每次對String類型進行操作都等同於產生了一個新的String對象，然後指向新的String對象。所以盡量不要對String進行大量的拼接操作，否則會產生很多臨時對象，導致GC開始工作，影響系統性能。StringBuffer是對象本身操作，而不是產生新的對象，因此在有大量拼接的情況下，我們建議使用StringBuffer(執行緒安全)。
二、Map集合類別
HashTable
執行緒安全，默認長度為11，擴容為2*length+1，及在默認長度情況下，第一次擴容長度為23，第二次擴容長度為47。
源碼解讀略。
HashMap
非執行緒安全，默認長度為16，擴容為當前數組長度的2倍。
具體擴容可以參考我另一篇文章：https://www.cnblogs.com/yanzige/p/8392142.html
ConcurrentHashMap
執行緒安全，默認長度為16，擴容為當前數組長度的2倍。
JDK8源碼解讀：https://blog.csdn.net/ddxd0406/article/details/81389583
LinkedHashMap
非執行緒安全，父類是HashMap，所以默認長度為16，負載引子為0.75，擴容為原來長度的2倍。
因為父類是HashMap，故很多方法都和父類一樣，底層也是一個維護了一個數組，每一個位置有一個Entry鏈表，但是需要注意的是，每一個位置的Entry對象（因為LinkedHashMap中了的Entry繼承於HashMap的Entry，但是在繼承過程中新增了兩個Entry對象，用來記錄每個Entry對象的上一個和下一個Entry對象）會保存插入前後的其他Entry對象的位置（該位置可能不是同一個數組下標的Entry），通過這種方式，可以將不同數據的Entry鏈表串成一整個鏈表，也就是一個雙向鏈表。
註：下面Entry的源碼是使用的JDK8，故LinkedHashMap中的Entry繼承HashMap中的Node對象，其實可以直接將JDK8中Node對象理解為JDK7中的Entry對象（兩者結構完全一樣，都是由final int hash;final K key;V value;Node<K,V> next;組成，只是名字叫法不同而已），所以文字統稱Entry。
/** * HashMap.Node subclass for normal LinkedHashMap entries. */ static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }
由上面的Entry程式碼可以看到，LinkedHashMap中的Entry除了和HashMap中的Entry一樣的int hash, K key, V value, Node<K,V> next 四個對象（用來記錄同一個數組下標的鏈表資訊），還多了Entry<K,V> before, after兩個前後的Entry，用來記錄新增數據的前後Entry(新增數據時，可能hash衝突在同一個鏈表上新增，也可能在其他數據位置或者數組其他位置的鏈表上新增)。通過該方式維護了一個雙向的鏈表。
相對HashMap，因為LinkedHashMap將數組下標每一個位置的鏈錶鏈接起來了，維護了一個雙向的鏈表，故LinkedHashMap可以記錄數據的插入順序，而HashMap則不能記錄插入順序。
總結：
1、HashMap 和LinkedHashMap 是非執行緒安全的。
2、HashTable 是執行緒安全的，但是加鎖的方式是在方法上加synchronized，及對整個需要操作的對象HashTable加鎖，可以理解為全表鎖，只有有任意一個執行緒訪問HashTable對象，其他執行緒都需要等待。故並發效率很低。
3、HashMap 和ConcurrentHashMap 繼承於AbstractMap 類，HashTable 是繼承於Dictionary 類，而LinkedHashMap 是繼承於HashMap 類，他們4者都實現了Map介面。
4、LinkedHashMap 繼承於HashMap，底層實現原理和基本操作和HashMap 一樣，只是多維護了一個雙向的鏈表，使得LinkedHashMap 能夠記錄數據的插入順序。
5、ConcurrentHashMap默認長度也為16，擴容方式也和HashMap一樣。
1）ConcurrentHashMap在JDK7中使用分段鎖，相比於HashTable的全表鎖，多個執行緒訪問ConcurrentHashMap對象，只要不是同一段的數據，可以多執行緒同時操作。
2）ConcurrentHashMap在JDK8中使用原子操作(CAS)和程式碼塊synchronized，故加鎖的粒度更細，並發效果更好。
三、List集合類別
ArrayList
非執行緒安全，除指定大小外默認長度為10，擴容為上次長度的1.5倍。若第一次創建對象使用無參構造器，則在put的時候將空數組（0）擴容到默認長度10。
1、ArrayList有三種構造器
0）首先看類中定義的變數
/** * 初始容量大小 */ private static final int DEFAULT_CAPACITY = 10; /** * 初始化數組 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * ArrayList對象存放數據的對象 底層為Object數組 */ private transient Object[] elementData; /** * ArrayList存放數據量的大小 */ private int size;
1）無參構造器
/** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { super(); this.elementData = EMPTY_ELEMENTDATA; }
在無參構造器創建對象的時候，並沒有指定容器大小，指定容器大小是在第一次add()的時候
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
在ensureCapacityInternal(size + 1)方法中，放入數據的時候，會檢查該數組（ArrayList對象是否為初始化數組），如果為初始化對象的話，則將當前長度1和默認長度10比較，取最大值，然後執行ensureExplicitCapacity(minCapacity)
private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }
進入ensureExplicitCapacity()會比較當前大小和elementData.length大小，如果當前大於ArrayList中的數據長度，則進行擴容。第一次進來肯定擴容grow(minCapacity)，因為當前elementData.length的值為0
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
下面為擴容的程式碼，默認將新數組長度擴充到原數組長度的1.5倍，下面程式碼使用原來的長度加上原長度右移1位（>>1），即新長度=（1+0.5）原長度，並將原數組數據copy到新的數組中。如果為第一次新增add()數據的時候，oldCapacity 為0，則newCapacity = minCapacity即newCapacity =10。
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; 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); }
在上面擴容過程中，並對長度進行校驗，判斷擴容的長度是否操作最大數組長度和最大整型（int）正整數長度，及2的31次方-1
/** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 最大整型正整數 2的31次方-1，16進位為0x7fffffff; */ public static final int MAX_VALUE = 0x7fffffff;
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）指定容量的構造器
/** * Constructs an empty list with the specified initial capacity. * * @param initialCapacity the initial capacity of the list * @throws IllegalArgumentException if the specified initial capacity * is negative */ public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; }
3）指定上限的集合構造器
/** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); size = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }
總結：
1）ArrayList底層是一個Object數組，在初始化對象的時候，如果使用無參構造器，則默認大小為10，在第一次添加數據的時候設置初始大小。
2）ArrayList擴容就是將原來的數組的數據複製到新的數組中，除第一次外，每次擴容都變成之前容量的1.5倍
3）ArrayList底層是數組，所以數據存儲是連續的，所以它們支援用下標來訪問元素，索引數據的速度比較快。
Vector
執行緒安全，該類基本上所有的方法都是使用synchronized修飾（如：public synchronized boolean isEmpty() {return elementCount == 0;}），故執行緒安全。和ArrayList一樣繼承於AbstractList<E>類，無參構造器默認容量大小為10，Vector構造器有4個，一個無參構造器，一個指定容量大小的構造器，一個指定容量大小和超過存儲量後按指定大小擴容的構造器，還有一個指定上限的集合構造器。
1、前三個構造器底層都是調用兩個參數的構造器：一個指定容量大小和超過存儲量後按指定大小擴容的構造器
/** * Constructs an empty vector with the specified initial capacity and * capacity increment. * * @param initialCapacity the initial capacity of the vector * @param capacityIncrement the amount by which the capacity is * increased when the vector overflows * @throws IllegalArgumentException if the specified initial capacity * is negative */ public Vector(int initialCapacity, int capacityIncrement) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; this.capacityIncrement = capacityIncrement; } /** * Constructs an empty vector with the specified initial capacity and * with its capacity increment equal to zero. * * @param initialCapacity the initial capacity of the vector * @throws IllegalArgumentException if the specified initial capacity * is negative */ public Vector(int initialCapacity) { this(initialCapacity, 0); } /** * Constructs an empty vector so that its internal data array * has size {@code 10} and its standard capacity increment is * zero. */ public Vector() { this(10); }
2、指定上限的集合構造器
/** * Constructs a vector containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this * vector * @throws NullPointerException if the specified collection is null * @since 1.2 */ public Vector(Collection<? extends E> c) { elementData = c.toArray(); elementCount = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, elementCount, Object[].class); }
3、在擴容的時候，如果沒有使用指定擴容大小，即沒有使用上面構造器public Vector(int initialCapacity, int capacityIncrement)初始化對象，那麼在擴容的時候直接擴容為原來的2倍
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }
LinkedList
非執行緒安全，LinkedList 底層維護了一個雙向鏈表，該鏈表有一個前向節點Node<E> first和一個後向節點Node<E> last。每次新增數據add()的時候，會在最後一個節點last後添加新節點，並且把剛添加的新節點賦值給last。如果為第一次新增，那麼該新增的節點既是first節點，又是last節點。
註：Node<E>節點裡面會存一個前節點的數據、後節點的數據以及自身的值。每次新增節點後，新增節點的上一個節點數據則為新增前的last節點，新增節點的後一個節點則為空，同時會將當前新增節點的數據存入上一個節點中的下節點資訊中。這樣就串為了一整個鏈表，鏈表中除了first和last節點外，每一個節點都包含上一個節點和下一個節點的資訊。因為Node節點中存有前一節點和後一節點的數據，所以只要打開任意一個Node節點數據，向前可以查看該節點前的所有數據，向後可以查看該節點後的所有數據。如果該節點處於頭部，那麼向後可以查看鏈表的所有數據，如果該節點處於尾部，向前可以查看該鏈表的所有數據。
如下圖處於鏈表尾部，該節點下一個節點為空，但是向前可以查看所有數據：
1、add()添加數據的方法
add()添加數據使用方法linkLast(),將該鏈表中last數據存入當前Node節點的前一個節點資訊，當前Node節點的下一個節點為空，並將當前Node替換為last節點。從添加流程程式碼可以看出來，LinkedList 在添加的時候並沒有對重複數據進行處理，所以LinkedList 中是可以存儲重複數據的。添加完成後，最後將鏈表長度數據size大小加1，然後將操作次數modCount數據加1.
public boolean add(E e) { linkLast(e); return true; }
/** * Links e as last element. */ 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; size++; modCount++; }
2、下面我們看幾個remove()方法
public E remove() { return removeFirst(); } public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); }
remove方法通過調用unlinkFirst(f)和unlinkLast(l)進行刪除，無論是刪除頭部還是尾部，或者是中間位置的元素，都需要把鏈表前後位置進行連接。
/** * 刪除頭部數據first，先將該頭部數據fist的下一個數據為新的first節點，然後將first節點中的prev節點設置為空，
* 再將原firt頭部節點數據刪除，再將原頭部節點的next數據置空。最後將鏈表長度數據size減一，將操作次數modCount加一 */ private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; } /** * 刪除尾部數據last,先將該尾部節點數據的prev取出來，並且將取出的上一個節點設置為last,在設置的同時將其中的next設置為空，
* 然後將該尾部數據以及該節點中的prev置空。最後將鏈表長度數據size減一和操作次數modCount加一 */ private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; } /** * 刪除中間節點數據，取出該節點的next節點和prev節點數據，然後將前一個節點prev的next設置為刪除數據中的next,將後一個節點的prev節點數據的next數據設置為即將刪除數據的next數據，
* 然後將被刪除的數據的所有數據都置空，最後將鏈表長度數據size減一和操作次數modCount加一 */ E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; 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; size--; modCount++; return element; }
CopyOnWriteArrayList
執行緒安全，在並發包concurrent包下，使用了ReentrantLock鎖來保證讀寫數據安全，同一時刻只能有一個執行緒進行寫操作，但是可以有多個執行緒進行並發讀數據，同時通過關鍵字volatile來保證讀數據時候的可見性，及每次數據在主記憶體中修改後，工作記憶體中讀取的數據會跟新為最新的數據，來保證讀數據的執行緒安全。CopyOnWriteArrayList沒有初始容量大小。
底層也是通過維護數組來存儲數據，該數組使用volatile修飾的，保證數據的可見性
private transient volatile Object[] array;
CopyOnWriteArrayList 在讀寫的時候使用ReentrantLock來保證執行緒安全，為什麼卻說CopyOnWriteArrayList 非絕對執行緒安全啦？原因在於CopyOnWriteArrayList在於為保證讀寫效率，在寫和修改的時候可以進行數據的讀取，那麼在數據刪除的時候就會存在執行緒安全（報錯）問題，當數據在進行刪除的時候，同時在讀取該數據，刪除完成的瞬間，然後讀數據發生，就會報錯：數組下標越界。可以參考：https://www.jianshu.com/p/fc0ee3aaf2df
關於更多CopyOnWriteArrayList的相關解讀可以查考：https://www.cnblogs.com/myseries/p/10877420.html
總結，關於ArrayList，Vector，LinkedList和CopyOnWriteArrayList 的對比：
1、 ArrayList和Vector底層原理一樣，都是使用Object數據，都是繼承於AbstractList<E>類，未指定初始容量的話默認都為10，擴容的時候ArrayList為原來的1.5倍，而Vector擴容為原來的2倍。其次ArrayList為執行緒不安全的類，而Vector為執行緒安全的。因為Vector使用synchronize來保證執行緒安全，所以在效率上和ArrayList相比要低。
2、CopyOnWriteArrayList底層也為數組，但是沒有初始容量。CopyOnWriteArrayList執行緒安全，和執行緒安全的Vector相比，因為CopyOnWriteArrayList使用ReentrantLock鎖對指定程式碼塊枷鎖，能滿足多執行緒讀的需求，並且在寫的過程中可以進行讀數據，相比於Vector類中的synchronize對整個方法進行加鎖的方式，並發效率更高。
3、LinkedList底層使用一個雙向鏈表，和上面兩個原理不一樣，是執行緒不安全的。因為LinkedList底層是鏈表，所以LinkedList在新增和刪除數據的時候效率很高，但是在查詢的時候需要依次遍歷，所以查詢效率較低。相反，ArrayList和Vector底層使用數組，記憶體地址是連續的，所以在查詢的時候效率很高，但是在新增和刪除的時候設計擴容（數組的複製），所以效率相比LinkedList要低。
特此說明：
上面所有類的相關特性對比描述，都是根據源碼進行總結的，當然在總結之前也有看過網上一些資料，所以可能存在總結不完整或者總結有誤的地方，還請大牛和心細的網友批評指正。此文章目的主要通過對比總結，便於記憶，並沒有對每一個集合類進行深入完整的剖析。如果想要深入理解某個類底層原理和邏輯，還是需要查看源碼和網上相應的說明文章。
此外，如果問題也可以留言交流….
