1. ArrayList
情況一：不指定容量，預設大小是十個數組的大小。在建立的時候不會配置設定十個數組，在第一次add 元素的時候才會進行擴容至預設的十個大小。
接下來容量超出的時候擴容機制如下：
比如放第11個的時候：
add 源碼如下： java.util.ArrayList#add(E)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
} 1》 先擴容
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
} (1)ensureCapacityInternal 確定容量滿足目前size + 1, 也就是確定能放下下一個元素
第一步先調用calculateCapacity擷取大小，如果數組中沒元素是個空數組就拿預設的大小10傳回去； 否則傳回上面的size + 1
第二步調用 ensureExplicitCapacity 如果minCapacity大于目前數組的大小，則需要擴容。
第三步 調用grow 方法進行擴容：(擴容為原來大小的1.5倍)
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);
} 第四步擴容的時候調用到 java.util.Arrays#copyOf(U[], int, java.lang.Class<? extends T[]>)
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
} java.lang.System#arraycopy 是一個native 方法
2》 後放置元素
情況二： 建立的時候指定大小， 預設會開辟指定大小的數組， 擴容機制同上
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
} Vector 和 ArrayList 一樣是基于數組，隻不過Vectror 的add 方法和 remove 方法加了synchronized 修飾， 變成了同步方法； 而且擴容預設是成倍的擴容。
2. LinkedList 源碼
我們知道LinkedList 是基于連結清單的結構(雙向連結清單)，連結清單的結構查找元素的時間複雜度為O(n), ArrayList 是基于數組，查找元素的時間複雜度為O(1)， 這裡說的查找都是根據下标進行查找。
關于增删元素其空間複雜度，ArrayList 從尾部插入的時候空間複雜度是O(1)--這也是很多架構查出來對象之後直接映射成ArrayList 的原因直接， 中間插入和删除元素時空間複雜度是O(n)，需要進行元素的移動；LinkedList 的空間複雜度是O(1)。
其繼承關系如下，可以作為一個隊列來使用
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{ 其内部類Node 用來存放元素，其結構如下：
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;
}
} 檢視其add 方法：java.util.LinkedList#add(E)
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
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++;
} 可以看到插入元素就是添加了一個節點，并且作為last 元素存到成員屬性中。
java.util.LinkedList#get 根據下标擷取元素的源碼如下：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(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;
}
} 可以看到先檢查需要擷取的元素是否存在越界；然後這裡大概是用了個二分查找的思想，分成兩半從前從後找。這裡也是需要周遊一半的元素進行連結清單的周遊擷取元素。
補充：ArrayList 和 LinkedList 的差別
1. 底層資料結構不同，ArrayList 是基于數組，LinkedList 是基于連結清單(雙向)實作的。
2. 适用場景不同，Arraylist适合随機查找，LinkedList 适合删除和添加。查詢、添加、删除的時間複雜度不同。
連結清單的結構查找元素的時間複雜度為O(n), ArrayList 是基于數組，查找元素的時間複雜度為O(1)， 這裡說的查找都是根據下标進行查找。
關于增删元素其空間複雜度，ArrayList 從尾部插入的時候空間複雜度是O(1)--這也是很多架構查出來對象之後直接映射成ArrayList 的原因直接， 中間插入和删除元素時空間複雜度是O(n)，需要進行元素的移動；LinkedList 的空間複雜度是O(1)。
3. Arraylist 和linkedList 都實作了List 接口，但是LinkedList 還實作了Deque 接口，是以LinkedList 還可以當作隊列來使用。
Queue的方法也非常簡單，就是三組(一個會抛出異常，一個傳回特殊值):
補充：棧和隊列的基本使用
Java 也有棧結構，比如：java.util.Stack
package java.util;
/**
* The <code>Stack</code> class represents a last-in-first-out
* (LIFO) stack of objects. It extends class <tt>Vector</tt> with five
* operations that allow a vector to be treated as a stack. The usual
* <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a
* method to <tt>peek</tt> at the top item on the stack, a method to test
* for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt>
* the stack for an item and discover how far it is from the top.
* <p>
* When a stack is first created, it contains no items.
*
* <p>A more complete and consistent set of LIFO stack operations is
* provided by the {@link Deque} interface and its implementations, which
* should be used in preference to this class. For example:
* <pre> {@code
* Deque<Integer> stack = new ArrayDeque<Integer>();}</pre>
*
* @author Jonathan Payne
* @since JDK1.0
*/
public
class Stack<E> extends Vector<E> {
/**
* Creates an empty Stack.
*/
public Stack() {
}
/**
* Pushes an item onto the top of this stack. This has exactly
* the same effect as:
* <blockquote><pre>
* addElement(item)</pre></blockquote>
*
* @param item the item to be pushed onto this stack.
* @return the <code>item</code> argument.
* @see java.util.Vector#addElement
*/
public E push(E item) {
addElement(item);
return item;
}
/**
* Removes the object at the top of this stack and returns that
* object as the value of this function.
*
* @return The object at the top of this stack (the last item
* of the <tt>Vector</tt> object).
* @throws EmptyStackException if this stack is empty.
*/
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
/**
* Looks at the object at the top of this stack without removing it
* from the stack.
*
* @return the object at the top of this stack (the last item
* of the <tt>Vector</tt> object).
* @throws EmptyStackException if this stack is empty.
*/
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
/**
* Tests if this stack is empty.
*
* @return <code>true</code> if and only if this stack contains
* no items; <code>false</code> otherwise.
*/
public boolean empty() {
return size() == 0;
}
/**
* Returns the 1-based position where an object is on this stack.
* If the object <tt>o</tt> occurs as an item in this stack, this
* method returns the distance from the top of the stack of the
* occurrence nearest the top of the stack; the topmost item on the
* stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
* method is used to compare <tt>o</tt> to the
* items in this stack.
*
* @param o the desired object.
* @return the 1-based position from the top of the stack where
* the object is located; the return value <code>-1</code>
* indicates that the object is not on the stack.
*/
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = 1224463164541339165L;
} 測試：
package com.xm.ggn.test;
import java.util.LinkedList;
import java.util.Stack;
public class PlainTest {
public static void main(String[] args) {
/**
* 棧和隊列的簡單使用(stack 内部繼承自Vector, push 是調用add 向尾部追加元素； pop是調用peek 拿出最後一個元素，然後調用remove 删除最後一個元素)
*/
// 1. 棧的使用
Stack<String> strings = new Stack<>();
strings.push("1");
strings.push("2");
strings.push("3");
System.out.println(strings);
// peek 方法不彈出，隻拿棧頂的元素
System.out.println(strings.peek());
System.out.println(strings.peek());
// pop 方法棧頂的元素, 相當于peek + remove 方法
System.out.println(strings.pop());
System.out.println(strings.pop());
System.out.println(strings.pop());
System.out.println(strings.isEmpty());
System.out.println("==========");
// 隊列的使用:
/**
* 對應的三組API：左邊會抛出異常，右邊不會抛出異常
* add offer 插入(入隊列)
* remove poll 移除且傳回頭元素
* element peek 檢查但是不傳回頭元素
*/
LinkedList<String> queue = new LinkedList<>();
// offer内部調用add 方法， 實際是向數組尾部添加元素，類似于向queue 對尾部添加元素
queue.offer("1");
queue.offer("2");
queue.offer("3");
queue.add("4");
queue.addLast("5");
queue.addFirst("0");
System.out.println(queue);
// peek 是拿隊列頭部的元素，不會移除元素
System.out.println(queue.peek()); // 0
// poll是彈出隊列頭部的元素并且删除去掉和後面元素的引用關系
System.out.println(queue.poll()); // 0
System.out.println(queue.pollFirst()); // 1
System.out.println(queue.pollLast()); // 5
System.out.println(queue.poll()); // 2
System.out.println(queue.poll()); // 3
System.out.println(queue.poll()); // 4
}
} 3. Map
關于map 的主要有HashMap， HashTable， LinkedHashMap， TreeMap。
關于HashMap 和 Hashtable 的差別：
1. hashTable的初始容量為11， 負載因子：0.75； hashMap的初始容量為16，負載因子為：0.75
2. hashTable擴容的方式： old容量*2 +1； hashMap擴容的方式：2的次幂的最靠近的那個數，或者原容量的兩倍
3. hashTable線程安全(put、get、size 等方法都加了synchronized)，hashMap線程不安全
4. hashTable中key value的值都不允許為空；hashMap的key或者value都允許為空
補充下java.util.Collections#synchronizedMap 是傳回了一個自己的内部同步Map， 這個Map 也是基于synchronized 進行同步， 在讀方法或者size()方法加鎖是為了保證記憶體的可見性，保證多線程讀取到的資料是一緻的。
這裡說下HashMap的簡單原理。
JDK1.7 是基于數組加連結清單， 且hash 碰撞之後會采用頭插法解決沖突。
JDK1.8 之後引入了紅黑樹的概念。 在連結清單的長度達到8之後會變為紅黑樹，連結清單長度變為6之後又變為連結清單。 原因是轉為紅黑樹是為了解決周遊查詢慢的問題。8和6數字的出現是因為： 6之前，周遊連結清單的平均時間複雜度要小于紅黑樹，是以采用連結清單； 8之後紅黑樹的時間複雜度為O(logn)， 要小于連結清單的時間複雜度O(n)。 插入的話，連結清單快于紅黑樹。是以引入紅黑樹重點是為了解決查詢慢的問題。
關于擴容： JDK7 是先擴容，後頭插法插入元素； JDK8 是先放元素，後尾插法插入元素。
紅黑樹是一種平衡二叉查找樹的變體，它的左右子樹高差有可能大于 1，是以紅黑樹不是嚴格意義上的平衡二叉樹（AVL），但 對之進行平衡的代價較低， 其平均統計性能要強于 AVL
紅黑樹：每個結點都帶有顔色屬性的二叉查找樹，顔色或紅色或黑色。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:
性質1. 結點是紅色或黑色。
性質2. 根結點是黑色。
性質3. 所有葉子都是黑色。（葉子是NIL結點）
性質4. 每個紅色結點的兩個子結點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續的紅色結點，黑節點的父親必紅）
性質5. 從任一節結點其每個葉子的所有路徑都包含相同數目的黑色結點。
這些限制強制了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結果是這個樹大緻上是平衡的。因為操作比如插入、删除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。
1. HashMap 中幾個重要的屬性：
/**
* The default initial capacity - MUST be a power of two. (預設容量大小，預設16， 擴容時成倍擴容)
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 預設的加載因子， 加載因子用于計算門檻值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 轉為樹的門檻值(也就是連結清單長度超過8轉為紅黑樹)
static final int TREEIFY_THRESHOLD = 8;
// 反轉為連結清單的門檻值(長度打到6 之後再次轉為連結清單)
static final int UNTREEIFY_THRESHOLD = 6;
// 最小樹形化容量門檻值，當哈希表中的容量 > 該值時，才允許樹形化連結清單
// 否則，若桶内元素太多時，則直接擴容，而不是樹形化 (也就是如果容量不到64，即使連結清單長度達到8，也不會進行樹形化，首先進行擴容操作)
// 為了避免進行擴容和樹形化選擇的沖突，這個值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
// 存放具體的元素的數組
transient Node<K,V>[] table;
// 存儲元素的數組，總是2的幂次倍
transient Node<k,v>[] table;
// 存放具體元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的個數（不是數組的長度）
transient int size;
// 擴容和修改的計數變量
transient int modCount;
// 臨界值 當實際大小(容量*填充因子)超過臨界值時，會進行擴容
int threshold;
// 加載因子
final float loadFactor; threshold 臨界值： 其計算方式是加載因子乘以容量，加載因子預設是0.75， 可以在構造方法中指定。 當放完元素之後，判斷目前map的size，如果大于該臨界值會進行擴容。
loadFactor加載因子：預設是0.75；加載因子就是表示哈希表中元素填滿的程度，當表中元素過多，超過加載因子的值時，哈希表會自動擴容，一般是一倍，這種行為可以稱作rehashing（再哈希）。
加載因子的值設定的越大，添加的元素就會越多，确實空間使用率的到了很大的提升，但是毫無疑問，就面臨着哈希沖突的可能性增大，反之，空間使用率造成了浪費，但哈希沖突也減少了，是以我們希望在空間使用率與哈希沖突之間找到一種我們所能接受的平衡，經過一些試驗，定在了0.75f。
2. 兩個重要的節點：
Node 單連結清單結構： hash 是儲存上面計算出的hash 值， 用來查找位置以及比對元素是否相同
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
} treeNode 節點: 紅黑樹節點， 新建立的樹節點預設是紅色。 繼承LinkedHashMap.Entry，Entry<K,V> extends HashMap.Node<K,V> 間接繼承自上面的Node 連結清單節點
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
} 3. put 方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} hash 方法中的代碼可以被稱為擾動函數，如果key 是null 直接傳回0； 否則計算得到其hashCode值并指派給一個臨時變量h， 然後向右移動16位(int 是32 位，相當于右移16位然後高位補0)之後進行按位進行異或運算(異或運算是相同為0，不同為1)。相當于是将hashcode值的高16位與低16位進行按位異或運算(相同為0，相異為1)。
java.util.HashMap#putVal 如下：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table未初始化（為null）或者長度為0，調用 resize 進行擴容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 若桶為空，即無發生碰撞
// (n - 1) & hash 用來确定元素存放在哪個位置，即哪個桶中
if ((p = tab[i = (n - 1) & hash]) == null)
// 新生成結點放入桶中(數組中)
tab[i] = newNode(hash, key, value, null);
// 若桶中已經存在元素
else {
Node<K,V> e; K k;
// 若節點 key 存在，就和要插入的key比較
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 如果key相同就直接覆寫 value
e = p;
// hash值不相等，即key不相等，轉為紅黑樹結點
else if (p instanceof TreeNode)
// 插入到樹中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 若是為連結清單結點
else {
// 周遊找到尾節點插入
for (int binCount = 0; ; ++binCount) {
// 到達連結清單的尾部
if ((e = p.next) == null) {
// 在尾部插入新結點
p.next = newNode(hash, key, value, null);
// 結點數量達到門檻值，轉化為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
// 跳出循環
break;
}
// 周遊的過程中，遇到相同 key 則覆寫 value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循環
break;
// 用于周遊桶中的連結清單，與前面的e = p.next組合，可以周遊連結清單
p = e;
}
}
// 在桶中找到key值、hash值與插入元素相等的結點
if (e != null) {
// 記錄e的value
V oldValue = e.value;
// onlyIfAbsent 為 false 或者舊值為 null
if (!onlyIfAbsent || oldValue == null)
// 用新值替換舊值
e.value = value;
// 通路後回調
afterNodeAccess(e);
// 傳回舊值
return oldValue;
}
}
// 結構性修改
++modCount;
// 超過最大容量，擴容
if (++size > threshold)
resize();
// 插入後回調
afterNodeInsertion(evict);
return null;
} 為了使得元素的下标落在數組的大小範圍内，需要根據數組的大小進行運算，JDK7 是 hash % (length - 1)； 在這裡的計算應該存放的數組下标的方法是： hash值 & (tab.length - 1), 進行與運算之後相當于確定元素坐落在數組的範圍内。
這也是HashMap 的大小要求是2的N次幂的好處之一， 比如16是 10000, 減一之後是 1111。 這也可以確定數組的散列性，碰撞機率就低了。
這裡也有個注意點： key的hashCode 用于計算數組的下标，key 的equals 方法用于hash 沖突之後判斷是否需要覆寫元素。
Put大緻流程如下：
先定位到具體的數組位置，例如叫做 A
若A 處沒有元素就直接插入
若A處有元素就和待插入的 key 比較
若key相同就直接覆寫
若key不相同，就判斷 p 是否是一個樹節點
如果是就調用putTreeVal 方法将元素添加進入
如果不是就周遊連結清單插入（尾插法） 4. get 方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
} hash(key) 方法同上，用于得到一個hash 值。java.util.HashMap#getNode方法如下： 這裡就是根據hash 和 key 去擷取節點Node， 分為直接從數組拿， 從樹拿和從連結清單拿。
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
} 補充：Hash沖突的解決辦法
(1)開放定址法：以發生沖突的哈希位址為自變量，通過哈希沖突函數得到一個新的空閑的哈希位址的方法。
線性探查：從沖突開始，找下一個位址，直到找到為空的位址
平方探查法：采用平方算法，假設do位址沖突，則找下一個位址為 d0 + （1^2）、d0 - （1^2）、d0 + （2^2）、d0 - （2^2）
僞随機序列和雙哈希函數
(2)鍊位址法：再哈希方法。
(3)再哈希法：計算另一個哈希函數，直到不沖突為止
(4)公共溢出區域法：建立一個公共溢出區域，就是把沖突的都放在另一個地方，不在表裡面。
HashMap 分析參考： https://juejin.cn/post/6931521369209470989#heading-19