目录
Collection
基础概念
Collection 是一个接口，定义了一些集合的通用方法（不做记录，自己查表）。在 Collection 中存放的是单列数据，即非 (key, value) 对形式的数据。
在 Collection 接口下有两类子接口：
-
List 接口
-
Set 接口
两者的区别 如下：
-
List 存放的数据是有序放入，有序取出，且元素可重复。Set 存放的数据是无序放入，不可重复（重复会覆盖掉）。虽然是无序，但决定元素位置的是其 HashCode 。
-
Set 元素检索效率低下，但插入和删除效率高，且插入删除后不会引起元素位置改变。
-
List 元素检索效率高，但插入和删除效率低，且会引起元素的位置改变。 List 的长度可以动态增长。
List
有一些重要点需要知道：
-
在未定义泛型的情况下，遍历 List 的任意实现类时，返回的都是
Object对象，此时需要注意的就是“向下转型问题”以及“编译类型和执行类型的区别”； -
在 List 的任意实现类中，存放的都是引用变量。即在任意实现类中，存放的的并非一个个对象，而是存放的对对象的引用。
List 是一个接口，其定义了一些常用的列表的方法。我们可以将 List 想象成一个容器，那么，这个时候就有人会问，数组不也是容器么？为什么要重复定义这么一个新的类呢？（这个问题针对底层实现是数组的实现类，如：ArrayList，Vector等）
它相对数组的不同之处在于其在数组的基础上封装了很多方法，例如数组无法实现自动扩容，在定义数组时，长度一旦设定，则无法继续扩大，除非是重定义一个更大的数组，然后遍历当前数组接收之前的数组。同时还有一些方法，添加元素，遍历元素等等。
其常用实现类有三种：
-
ArrayList
-
Vector：基本和 ArrayList 一样，只是方法前加了
synchronized关键字修饰，具有线程安全性。（就不具体分析 Vector 的内容了） -
LinkedList
其中，ArrayList 和 Vector 的底层数据实现是由 数组 实现的，而 LinkedList是使用 双向链表 实现的。
两者各自的优势：
-
ArrayList 适合改查
-
LinkedList 适合增删
接下来就是对这三个实现类进行一一解读。
1. ArrayList
1.1 ArrayList 的特点：
-
线程不安全（无
synchronized关键字修饰），在多线程的情况下不建议使用 -
执行效率高（因为没有线程控制的限制）
-
底层由数组来实现数据的存储
-
基本等同于 Vector，但 Vector 是线程安全的，其有关写入的方法都有
synchronized关键字修饰
1.2 ArrayList 构造源码分析:
ArrayList 的底层是使用数组存储数据，同时实现了自动扩容机制，在每次传入数据的时候都会做一次判定，判断当前的数组空间是否足够。如果够，则直接追加。
否则激发扩容机制。扩容后大小为当前容量的 1.5 倍。Vector 是默认按照 2 倍扩容，但可以自定义扩容大小。
// 从无参构造器进入。有参构造器的流程差不多
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
// DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个宏定义的空数组。
}
接下来是关于向集合中添加数据的源码过程。首先要明晰的一点是，容器中只接收对象，所以传入的值数据（ 例如 int, char 等 ）都被被自动装箱，打包成一个对象。
整个添加过程的流程如下所示：
addOp=>operation: add()
ensure1Op=>operation: ensureCapacityInternal()
ensure2Op=>operation: ensureExplicitCapacity()
ensure3Op=>operation: grow()
addOp(right)-->ensure1Op(right)-->ensure2Op(right)-->ensure3Op
然后进入 add() 方法：
public boolean add(E e) {
// ensureCapacityInternal() 是来保证当前数组的大小是否足够
// 如果不够，则激发扩容机制
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
进入 ensureCapacityInternal() 方法：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 判断当前数组是不是默认空数组，如果是，就返回默认容量大小(10)和需要容量大小的最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
进入 ensureExplicitCapacity() 方法：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
// 如果当前空间不够，则触发扩容
grow(minCapacity);
}
进入 grow():
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// >> 表示左边数据向右移动指定位数，右移一位相当于整除 2
// 所以扩容是每次 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);
}
2. LinedList
2.1 基本介绍
LinkedList 底层实现是使用双向链表进行的，并且做到了如下几个特点：
-
具有双向链表和双端队列的特点；
-
可以添加任意元素（包括 Null）；
-
没有实现同步；
究其原理，其是使用 Node 内部类，和引用数据类型的特点模拟出了一个双向链表。
2.2 LinkedList 源码分析
首先，我们需要了解一下 LinkedList 内部是如何实现双向链表的。
在 LinkedList 内部定义了一个名为 Node 的内部类，以它作为存储每一个数据的单元。这也是与 ArrayList 最大的不同之处。对于 ArrayList 而言，其就单纯使用数组作为元素的存储空间。但 LinkedList 中，为了模拟双向链表，将其套了一个壳，元素存储只是这个壳包含的空间中的一部分。当然，其实本质都差不多。
2.2.1 构造源码
在 LinkedList 中有如下两个属性：
transient Node<E> first;
transient Node<E> last;
这两个变量用来“存储/指向/标识”当前链表的首节点和尾节点。transient 关键字是用来防止被序列化的。
Node 内部类源码如下：
private static class Node<E> {
// 在这， E 是泛型. item 的作用是存储数据
// 可以看到，存储的数据的类并不是 Node，而是泛型指定的类，或者直接 Object
// 所以对于值类型还是要做一次装箱操作
E item;
// next 用来存储下一个 Node 的地址的引用变量；同理，prev 是指向上一个
Node<E> next;
Node<E> prev;
// Node 的构造函数，
// 要实例化一个 Node，出了当前节点对象要存储的数据，还必须要传入前后节点
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
2.2.2 添加方法源码
关于 LinkedList 如何添加数据的实现源码：
整个流程如下：
addF=>operation: addFirst()
linkF=>operation: linkFirst()
addF(right)->linkF(right)
addL=>operation: addLast()
linkL=>operation: linkLast()
addL(right)->linkL
首先是在首尾添加数据：
调用 addFirst() 或 addLast() 函数：
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
再让我们进入 linkFirst() 方法看看：
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
// 记录修改次数，主要作用就是判断该集合在被读取前有没有被修改
// 一般用于多线程的数据唯一性的判定
modCount++;
}
linkLast() ：
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++;
}
再看看再指定位置插入数据（这是 LinkedList 相对于 ArrayList 的优势）：
addI=>operation: addBefore()
linkB=>operation: linkBefore()
node=>operation: node()
addI(right)->linkB(right)->node
public void add(int index, E element) {
// 首先做一个索引越界检查
checkPositionIndex(index);
if (index == size)
// 如果索引刚好是在链表尾部，那么就直接调用 LinkLast()
linkLast(element);
else
// 否则调用在一个指定节点前插入的方法
linkBefore(element, node(index));
}
node(index) 是返回指定 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;
}
}
linkBefore() 源码：
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
2.2.3 删除方法
删除逻辑：
在 LinkedList 中的删除逻辑实现是使用了 Java 内存回收机制(GC) 的辅助。其具体逻辑为：
-
首先将连接到该节点的引用全部清除：
-
将 prev 节点的 next 引用指向它的 next，且将其 prev 引用置为 null
-
将 next 节点的 prev 引用指向它的 prev 节点，且将其 引用置为 null
-
-
然后该节点就无法被访问到，就会被内存回收机制自动回收
具体源码见：unlinkFirst()，unlinkLast()，unlink() 三个方法的源码
2.2.4 访问方法源码
访问（查询）逻辑：
链表的访问只能通过遍历进行：
get(int) 源码：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
而 node() 在插入部分的源码已经讲过。
Set
Set 接口是 Collection 接口的子接口，具有 Collection 接口定义的常用的方法。而 Set 接口的常用实现类有
-
HashSet
-
TreeSet
其接口常用方法为：
-
add()
-
remove()
-
iterator()
-
contains()
-
hashCode()
1. HashSet
HashSet 它无法向 List 的实现类一样使用 get() 方法访问指定元素。
说实话，个人暂时对 HashSet 的使用场景感到迷惑。
HashSet 的底层其实是一个 HashMap。
它具有如下特点：
-
可以存放 null 值；
-
不能存放重复值，包括空值也只能存放一个；
-
取出的顺序与存入的顺序并不一致
1.1 源码分析
1.1.1 构造源码
从构造函数的源码上分析就可以看出，HashSet 的底层其实是 HashMap，在 HashSet 中的保存了一个 HashMap 对象。（HashMap 的底层是 数组+链表+红黑树。）
private transient HashMap<E,Object> map;
public HashSet() {
map = new HashMap<>();
}
在 HashSet 中的很多方法其实只是对 HashMap 的方法做了一层包装。即在 HashSet 方法体中使用 map 对象调用对应功能的 HashMap 中的方法。例如下面即将分析的 HashSet 中的 add() 方法。
但在 HashSet 中的 map 对象的 value 是一个常量，也就是说其只用到了 HashMap 的节点中 key 的部分，不同部分也都是 key。同样，这样也正好利用了 key 不允许重复的特点。
这里需要表明一下 HashMap 中的结构：
-
由
Node[]数组组成一列排头； -
而每个
Node[i]都对应了一串链表或一颗树；
Node 节点的定义：
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;
}
}
1.1.2 add()方法过程
op1=>operation: map.put()
op2=>operation: putVal()
op1(right)->op2
首先，在 HashSet 的 add() 方法中，使用 map 调用了 HashSet 中的 add() 方法：
public boolean add(E e) {
// put() 方法若成功将对象加进去，就会返回 null
return map.put(e, PRESENT)==null;
}
// 其中 PRESENT 是个定义的空对象常量，用来占位，
// 以凑成 HashMap 所需要的节点形式
private static final Object PRESENT = new Object();
现在进入 put() 方法中（此时已经进入了 HashMap 的类定义中）：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
进入 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;
// 初次使用，会进入 resize() 方法，为其初始化一个长度为 16 的空间
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 接下来就是添加逻辑
// 第一次判定：要加入的 table 数组的位置是否有值
if ((p = tab[i = (n - 1) & hash]) == null)
// 1. 若为空：则直接加入当前位置
tab[i] = newNode(hash, key, value, null);
// 2. 若不为空，则进行下列步骤进行判定
else {
Node<K,V> e; K k; // 需要的临时变量，这种变量需要的时候再定义。
// 判定是否重复，若要加入的值与 p 直接重复，那么无法加入
// p 当前是 hashcode 对应的 table 位置的值
// 即树或链的起始节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 这就是未加入成功的标识，若成功，e == null
e = p;
// 判定当前位置是否已经树化，若已经树化，则使用树化的方法进行添加
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
// 树化方法中也有其判定：
// 1. 满足 table 长度到 64；2. 链条长度超过树化标准
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;
}
至此基本的添加逻辑已经走完，接下来需要细化 resize() 和 treeifyBin() 的逻辑
resize()的规则：
-
初始化大小为 16
-
每次扩容为之前容量的两倍，table 数组长度没有限制
-
触发扩容条件是 size 达到 \(加载因子 \times 现有容量\)
size 是指 element 的个数，而非 table 数组的长度
treeifyBin()：
-
如果 table 长度没超过 64，则选择继续扩容
-
如果超过了，则进行树化