摘要：包含两个重要的成员和。对于多线程环境，且可能同时被多个线程操作，此时，应该使用同步的类如。小于等于且大于，代表用户创建了一个，但是使用的构造函数为或或，导致为，为，为用户指定的的初始容量。本质上是数组单向链表红黑树的数据结构如下图。
一、List 1、ArrayList
① 关键源码
// 默认初始化为空数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 添加元素
public boolean add(E e) {
// 增加modCount, 判断扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// 扩容函数
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);
}
② 特点
空集合第一次添加元素时默认初始容量为10
线程不安全(在单线程中才使用ArrayList，而在多线程中可以选择Vector[方法加了sync关键字]或者CopyOnWriteArrayList[juc包])
遍历时，使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低
fail-fast 机制
fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。
AbstractList 源码中，每修改一次(添加/删除等操作)，将modCount+1
由于 实现的 Itr 类中， next() 和 remove()都会执行 checkForComodification()
若 “modCount 不等于expectedModCount”，则抛出ConcurrentModificationException异常，产生fail-fast事件。
所以当多个线程同时操作时，会抛出ConcurrentModificationException异常
① 关键源码
// 初始化空列表
public LinkedList() {
}
// 在列表末尾添加一个节点
public boolean add(E e) {
linkLast(e);
return true;
}
// linkLast函数
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
// last为空说明是个空列表，插入的则为第一个节点
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
// Node类
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
② 特点
LinkedList的本质是双向链表。
LinkedList包含两个重要的成员：Node
Node是双向链表节点所对应的类的实例。Node中包含成员变量： prev, next, item
prev是该节点的上一个节点，next是该节点的下一个节点，item是该节点所包含的值。size是双向链表中节点的个数。
3、LinkedList和ArrayList使用场景和性能分析1、ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低(涉及到复制)。
2、LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率高。
(01) 对于需要快速插入，删除元素，应该使用LinkedList。
(02) 对于需要快速随机访问元素，应该使用ArrayList。
(03) 对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。
对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如CopyOnWriteArrayList)。
二、Map
1、HashMap
① 关键源码
// 加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 初始的加载因子默认为0.75，此时还没有初始化容量，在put的时候会进行resize()将容量初始化为16
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* key 的 hash值的计算是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)
* 这么做可以在数组table的length比较小的时候
* 也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 重点的putVal逻辑
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
// 如果table为null或者0，则进行resize()操作 resize()方法在下面再说
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 确定插入table的位置，算法是(n - 1) & hash，在n为2的幂时，相当于除模取余操作。(这也是为什么长度要取2的幂次方的原因之一)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 在table的i位置发生hash碰撞或者除模取余后相同结果，有两种情况：
// 1、key值是一样的，就替换成value值
// 2、key值不一样的有两种处理方式：a、存储在i位置的链表(链表长度达到8时转成红黑树); b、存储在红黑树中
else {
Node e; K k;
// key值是一样的，替换value值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 是红黑树结构就putTreeVal
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
// 不是TreeNode,即为链表,遍历链表并且去跟链表的每一个key做比较
for (int binCount = 0; ; ++binCount) {
// 直到链表的下一个节点为null，就进去新建个节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 根据binCount去记录链表的长度，超过8就转红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
final Node[] resize() {
// 保存当前table
Node[] oldTab = table;
// 保存当前table的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 保存当前阈值
int oldThr = threshold;
// 初始化新的table容量和阈值
int newCap, newThr = 0;
/*
1. resize（）函数在size > threshold时被调用。oldCap大于 0 代表原来的 table 表非空，
oldCap 为原表的大小，oldThr（threshold） 为 oldCap × load_factor
*/
if (oldCap > 0) {
// 若旧table容量已超过最大容量，更新阈值为Integer.MAX_VALUE（最大整形值），这样以后就不会自动扩容了。
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 容量翻倍，使用左移，效率更高
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
/*
2. resize（）函数在table为空被调用。oldCap 小于等于 0 且 oldThr 大于0，代表用户创建了一个 HashMap，但是使用的构造函数为
HashMap(int initialCapacity, float loadFactor) 或 HashMap(int initialCapacity)
或 HashMap(Map m)，导致 oldTab 为 null，oldCap 为0， oldThr 为用户指定的 HashMap的初始容量。
*/
else if (oldThr > 0) // initial capacity was placed in threshold
//当table没初始化时，threshold持有初始容量。还记得threshold = tableSizeFor(t)么;
newCap = oldThr;
/*
3. resize（）函数在table为空被调用。oldCap 小于等于 0 且 oldThr 等于0，用户调用 HashMap()构造函数创建的 HashMap，所有值均采用默认值，oldTab（Table）表为空，oldCap为0，oldThr等于0，
*/
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新阈值为0
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 初始化table
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把 oldTab 中的节点 reHash 到 newTab 中去
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 若节点是单个节点，直接在 newTab 中进行重定位
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 若节点是 TreeNode 节点，要进行 红黑树的 rehash 操作
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
// 若是链表，进行链表的 rehash 操作
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
// 将同一桶中的元素根据(e.hash & oldCap)是否为0进行分割（代码后有图解，可以回过头再来看），分成两个不同的链表，完成rehash
do {
next = e.next;
// 根据算法 e.hash & oldCap 判断节点位置rehash 后是否发生改变
// 最高位==0，这是索引不变的链表。
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//最高位==1 （这是索引发生改变的链表）
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原bucket位置的尾指针不为空(即还有node)
if (loTail != null) {
// 链表最后得有个null
loTail.next = null;
// 链表头指针放在新桶的相同下标(j)处
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
// rehash 后节点新的位置一定为原来基础上加上 oldCap，具体解释看下图
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
② 特点
HashMap 的实现不是线程安全的。它的key、value都可以为null。
初始化时加载因子为0.75，有put操作时将容量初始化为16(哈希表的桶数，即entry的数量)
当哈希表中的条目数超出了加载因子与容量的乘积时(如0.75 * 16)，则要对该哈希表进行resize操作（同时会进行rehash操作，重建内部数据结构），从而哈希表将具有两倍的容量。
HashMap是通过拉链法实现的散列表。本质上是数组 + 单向链表 + 红黑树的数据结构(如下图)。
HashMap使用链表法避免哈希冲突(相同hash值)，当链表长度大于TREEIFY_THRESHOLD（默认为8，设为8是因为达到8的概率为0.00000006，概率低）时，将链表转换为红黑树(在转红黑树之前会再进行一次判断map的容量是否小于64，是的话不会进行转红黑树，而是先resize()扩容)，如果之后小于UNTREEIFY_THRESHOLD（默认为6）时，又会转回链表以达到性能均衡。
HashMap的数据结构(图片源自网络，侵删)
① 关键源码
