Java 集合框架
文章目录
本文主要对 Java 的集合进行学习，包含对类源码解析。
一、集合概述
1.1. 介绍
Java 集合，也叫作容器，可以理解为 “可以容纳其它 Java 对象的对象”。“Java Collections Framework（JCF）” 为 Java 开发者提供了通用的容器，起始于 JDK1.2，具有以下优点：
- 降低编程难度；
- 提高程序性能；
- 提高 API 间的互操作性；
- 降低学习难度；
- 降低设计和实现相关 API 的难度；
- 增加程序的重用性。
Java 集合里只能存放对象，对于基本类型（int、long、float、double等），需要将其包装成对象类型后（Integer、Long、Float、Double 等）才能添加到集合里。很多时候拆包和解包能够自动完成。这虽然会导致额外的性能和空间开销，但简化了设计和编程。
Java 集合主要由两大接口派生而来：一个是 Collection 接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。
1.2. Collection
对于 Collection 接口，下面有三个主要的子接口：List、Set、Queue。
- Set
- TreeSet：基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet。HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。
- HashSet：基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
- LinkedHashSet：具有 HashSet 的查找效率，且内部使用双向链表维护元素的插入顺序。
- List
- ArrayList：基于动态数组实现，支持随机访问。
- Vector：和 ArrayList 类型，但它是线程安全的。
- LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。
- Queue
- LinkedList：可以用它来实现双向队列。
- PriorityQueue：基于堆结构实现，可以用它来实现优先队列。
1.3. Map
- TreeMap：基于红黑树实现。
- HashMap：基于哈希表实现。
- HashTable：和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类，不应该去使用它。现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 效率会更高，因为 ConcurrentHashMap 引入了分段锁。
- LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序或最近最少使用（LRU）顺序。
二、Collection 解析
2.1. ArrayList 源码解析
2.1.1. 概述
ArrayList 是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入 null 元素，底层通过数组实现。除该类未实现同步外，其余跟 Vector1 大致相同。每个 ArrayList 都有一个容量（capacity），表示底层数组的大小，容量内存储元素的个数不能多于当前容量。当向容量中添加元素时，如果容量不足，容器会自动增大底层数组的大小。Java 泛型只是编译器提供的语法糖，所以这里的数组是一个 Object 数组，以便能够容纳任何类型的对象。
因此，size()、isEmpty()、get()、set() 方法均能在常数时间内完成，add() 方法的时间开销跟插入位置有关，addAll() 方法的时间开销与添加元素的个数成正比。其余方法大都是线性时间。
为追求效率，ArrayList 没有实现同步（synchronized），如果需要多个线程并发访问，用户可以手动同步，也可以使用 Vector 替代。
2.1.2. 实现
JDK 版本为 1.8
ArrayList 继承了 AbstractList，实现了 List、RanomAccess、Cloneable、java.io.Serializable 接口。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
}
List：表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问；RandomAccess：这是一个标志接口，表明实现这个接口的List集合是支持快速随机访问的。在ArrayList中，即可以通过元素的序号快速获取元素对象；Cloneable：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作；Serializable：表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输。
① 数据结构
底层数据结构
/**
* 保存 ArrayList 数据的数组
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList 所包含的元素个数
*/
private int size;
② 初始化
构造函数
ArrayList 有三种初始化方式，构造方法如下：
/**
* 默认初始化容量大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空数组（用于空实例）
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 用于默认大小空实例的共享空数组实例
* * 把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 带初始容量参数的构造函数（用户可以在创建 ArrayList 对象时自己指定集合的初始大小）
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 如果传入的参数大于 0，创建 initialCapacity 大小的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 如果传入的参数等于 0，创建空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 其它情况，抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 默认无参构造函数
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序
*/
public ArrayList(Collection<? extends E> c) {
// 将指定集合转换为数组
Object[] a = c.toArray();
// 如果 elementData 数组的长度不为 0
if ((size = a.length) != 0) {
// 如果 elementData 不是 Object 类型数据（c.toArray 可能返回的不是 Object 类型的数组，所以加上下面的语句用于判断）
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
// 将原来不是 Object 类型的 elementData 数组的内容，赋值给新的 Object 类型的 elementData 数组
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// 其它情况，用空数组代替
elementData = EMPTY_ELEMENTDATA;
}
}
通过以上代码，我们可以了解到：以无参构造器方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10.
补充：JDK6 通过无参构造器创建对象时，直接创建了长度为 10 的
Object[]数组 elementData
③ 添加元素
add 方法
与 C++ 的 vector 不同，ArrayList 没有 push_back() 方法，对应的方法是 add(E e)，ArrayList 也没有 insert() 方法，对应的方法是 add(int index, E e)。这两个方法都是向容器中添加新元素，这可能会导致 capacity 不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过 grow() 方法完成的。
/**
* 将指定的元素追加到此列表的末尾
*/
public boolean add(E e) {
// 添加元素之前，先调用 ensureCapacityInternal 方法
ensureCapacityInternal(size + 1); // Increments modCount!!
// 这里看到 ArrayList 添加元素的实质就相当于为数组赋值
elementData[size++] = e;
return true;
}
/**
* 在此列表中的指定位置插入指定的元素
* 先调用 rangeCheckForAdd 对 index 进行界限检查；然后调用 ensureCapacityInternal 方法保证 capacity 足够大；
* 再将从 index 开始之后的所有成员后移一个位置；将 element 插入 index 位置；最后 size 加 1
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
注意：JDK11 移除了
ensureCapacityInternal()和ensureExplicitCapacity()方法
ensureCapacityInternal 方法的源码如下：
/**
* 根据给定的最小容量和当前数组元素来计算所需容量
*/
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));
}
ensureCapacityInternal 方法非常简单，内部直接调用了 ensureExplicitCapacity 方法：
/**
* 判断是否需要扩容
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 判断当前数组容量是否以存储 minCapacity 个元素
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
grow 方法
/**
* 要分配的最大数组大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* ArrayList 扩容的核心方法
*/
private void grow(int minCapacity) {
// oldCapacity 为旧容量，newCapacity 为新容量
int oldCapacity = elementData.length;
// 将 oldCapacity 右移一位，其效果相当于 oldCapacity / 2
// 位运算的速度远快于整除运算，整句运算式的结果就是将 newCapacity 更新为 oldCapacity 的 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 检查 newCapactiy 是否小于最小需要容量；若小于最小需要容量，那么就把最小需要容量作为 newCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 检查 newCapacity 是否大于 MAX_ARRAY_SIZE（最大容量）；若大于最大容量，则进入 hugeCapacity() 方法
// 如果 minCapacity 大于 MAX_ARRAY_SIZE，则返回 Integer 最大值，反之返回 MAX_ARRAY_SIZE
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);
}
/**
* 比较minCapacity和 MAX_ARRAY_SIZE
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
“>>” （位移运算符）：>>1 右移一位相当于除 2，右移 n 位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了 1 位所以相当于 oldCapacity / 2。对于大数据的二进制运算，位移运算符比那些普通运算符的运算要快很多，因为程序仅仅移动一下而已，不去计算，这样提高了效率，节省了资源。
自动扩容
每当向数组中添加元素时，都要去检查添加后元素的个数是否会超过当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法 ensureCapacity(int minCapacity) 来实现。在实际添加大量元素前，我们也可以使用 ensureCapacity 来手动增加 ArrayList 实例的容量，以减少递增式再分配的数量。
数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的 1.5 倍。这种操作的代码是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造 ArrayList 实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用 ensureCapacity 方法来手动增加 ArrayList 实例的容量。
/**
* 如果有必要，增加此 ArrayList 实例的数量，以确保它至少能容纳元素的数量
* @param minCapacity 所需的最小容量
*/
public void ensureCapacity(int minCapacity) {
// 如果是 true，minExpand 的值为 0，反之为 10；
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
// 如果最小容量大于已有的最大容量
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
addAll 方法
addAll() 方法能够一次添加多个元素，根据位置不同也有两个版本，一个是在末尾添加的 addAll(Collection<? extends E> c) 方法，一个是从指定位置开始插入的 addAll(int index, Collection<? extends E) c) 方法。与 add() 方法类似，在插入之前也需要进行空间检查，如果需要则自动扩容；如果从指定位置插入，也会存在移动元素的情况。addAll() 的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关。
/**
* 按指定集合的 Iterator 返回的顺序将指定集合中的所有元素追加到此列表的末尾
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* 将指定集合中的所有元素插入到此列表中，从指定的位置开始
*/
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
④ 修改元素
既然底层是一个数组，那么 set() 方法也就变得非常简单，直接对数组的指定位置赋值即可。
/**
* 用指定的元素替换此列表中指定位置的元素
*/
public E set(int index, E element) {
// 对 index 进行界限检查
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
// 返回原来在这个位置的元素
return oldValue;
}
⑤ 获取元素
get() 方法同样很简单，唯一要注意的是由于底层数组是 Object[]，得到元素后需要进行类型转换。
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index]; // 注意类型转换
}
/**
* 返回此列表中指定位置的元素
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
⑥ 删除元素
remove() 方法也有两个版本，一个是 remove(int index) 删除指定位置的元素，另一个是 remove(Object o) 删除第一个满足 o.equals(elementData[index]) 的元素。删除操作是 add() 操作的逆操作，需要将删除点之后的元素向前移动一个位置。需要注意的是为了让 GC 起作用，必须显式的为最后一个位置赋 null 值。
/**
* 删除该列表中指定位置的元素。将任何后续元素移动到左侧（从其索引中减去一个元素）
*/
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // 清除该位置的引用，让 GC 起作用
// 从列表中删除的元素
return oldValue;
}
/**
* 从列表中删除指定元素的第一个出现（如果存在）。如果列表不包含该元素，则它不会更改
* * 返回 true，如果此列表包含指定的元素
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
关于 java GC 这里需要特别说明一下，有了垃圾收集器并不意味着一定不会有内存泄漏。对象能够被 GC 的依据之一是是否还有引用指向它，上面代码中如果不手动赋 null 值，除非对应的位置被其它元素覆盖，否则原来的对象就一直不会被回收。详情请看：Java 垃圾回收
⑦ trimToSize 方法
ArrayList 还提供了将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过 trimToSize 方法来实现。
/**
* 修改这个 ArrayList 实例的容量为列表的当前大小。
* * 应用程序可以使用此操作来最小化 ArrayList 实例的存储
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
⑧ 查找操作
indexOf 方法、lastIndexOf 方法
获取元素的第一次出现的 index：
/**
* 返回此列表中指定元素的首次出现的索引，如果此列表不包含此元素，则为 -1
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
获取元素的最后一次出现的 index：
/**
* 返回此列表中指定元素的最后一次出现的索引，如果此列表不包含此元素，则返回 -1
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
⑨ Fail-Fast 机制
Fail-Fast 机制是 Java 集合（Collection）中的一种错误机制。在用迭代器遍历一个集合，遍历过程中对集合的结构进行了修改（增加、删除），则会抛出 Concurrent Modification Exception（并发修改异常）。
ArrayList 也采用了快速失败的机制，通过记录 modCount 参数来实现。在面对并发修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
2.1.3. 补充
阅读源码时，我们发现 ArrayList 中大量调用了 System.arraycopy() 和 Arrays.copeOf() 这两个方法。下面分别看一下它们的源码：
① System.arraycopy 方法
/**
* 复制数组（从指定的源数组的指定位置开始，将数组复制到目标数组的指定位置）
* @param src 源数组
* @param srcPos 源数组中的起始位置
* @param dest 目标数组
* @param destPost 目标数组中的起始位置
* @param length 要复制的源数组元素的数量
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
通过以上代码，我们可以知道，这个方法是本地方法，将 src 数组从 srcPos 到 （srcPos + length -1）下标的子序列复制到 dest 数组（从 destPost 下标处开始复制）。
因此，这里有几条事项需要注意：
-
src 和 dest 参数必须是引用类型相同的数组对象。（若 src 为空或 dest 为空，抛出 NullPointerException，并且不会进行修改）
-
如果存在以下任一情况，则抛出 ArraysStoreException：
- src 或 dest 参数指向不是数组的对象；
- src 和 dest 参数引用的数组的组件类型不同；
- src 指向一个具有基本类型的数组，dest 指向一个具有引用类型的数组；反之，一样。
-
如果存在以下任一情况，则抛出 IndexOutOfBoundsException：
- srcpos 或 destPos 或 length 参数为负值；
- srcPos + length 大于 src.length；
- destPos + length 大于 dest.length
-
如果源数组子序列的任一元素不能通过赋值转换为目标数组的组件类型，则抛出 ArrayStoreException（前提：两个数组的组件类型为引用类型）。
② Arrays.copeOf 方法
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
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，将源数组中的数据进行拷贝
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
// 返回新数组
return copy;
}
因此，使用该方法的主要作用是为了给原数组进行扩容。
2.2. LinkedList 源码解析
2.2.1. 概述
LinkedList 是一个基于双向链表实现的集合类，经常被拿来和 ArrayList 做比较。关于 LinkedList 和 ArrayList 的详细对比，后边再进行分析。
不过，我们在项目中一般是不会使用到 LinkedList 的，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好！（LinkedList 的作者 Joshua Bloch 自己都说从来不会使用 LinkedList。文章地址）
此外，不要下意识地认为 LinkedList 作为链表就最适合元素增删的场景。LinkedList 仅在头尾插入或者删除元素的时候时间复杂度近似 O(1)，其它情况增删元素的平均时间复杂度都是 O(n)。
为了追求效率，LinkedList 也没有实现同步（synchronized），如果需要多个线程并发访问 ，可以先采用 Collections.synchronizedList() 方法对其进行包装。
2.2.2. 实现
LinkedList 继承了 AbstractSequetialList，而 AbstractSequetialList 又继承于 AbstractList。又同时实现了 List、Deque、Cloneable、Serializable 接口。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
}
List：表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问；Deque：继承自Queue接口，具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据结构；Cloneable：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作；Serializable：表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输。
① 数据结构
底层数据结构
双向链表的每个节点用内部类 Node 表示。当链表为空时，first 和 last 都指向 null。
/**
* 链表长度
*/
transient int size = 0;
/**
* 第一个节点的指针
*/
transient Node<E> first;
/**
* 最后一个节点的指针
*/
transient Node<E> last;
其中 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;
}
}
② 初始化
构造函数
LinkedList 有两种初始化方式，构造方法如下：
/**
* 无参构造器
*/
public LinkedList() {
}
/**
* 接收一个集合类型作为参数，会创建一个与传入集合相同元素的链表对象
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
③ 添加元素
LinkedList 除了实现 List 接口相关方法，还实现了 Deque 接口的很多方法，所以有很多种方式添加元素。这里主要对 List 接口中相关的插入方法进行解析，对应的是 add() 方法及 addAll() 方法。
add方法
/**
* 在链表尾部插入元素
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 在链表指定位置插入元素
*/
public void add(int index, E element) {
// 下标越界检查
checkPositionIndex(index);
// 判断 index 是不是链表尾部位置
if (index == size)
// 如果 index 是链表末尾，直接调用 linkLast 方法将元素节点插入链表末尾即可
linkLast(element);
else
// 如果 index 不是链表末尾，则调用 linkBefore 方法将其插入指定元素之前
linkBefore(element, node(index));
}
/**
* 将元素节点插入到链表尾部
*/
void linkLast(E e) {
// 将最后一个节点赋值给节点节点 l
final Node<E> l = last;
// 创建节点，并指定节点前驱为链表尾节点 last，后继引用为空
final Node<E> newNode = new Node<>(l, e, null);
// 将 last 引用指向新节点
last = newNode;
// 判断尾节点是否为空
// 如果 l 是 null 意味着这是第一次添加元素
if (l == null)
// 如果是第一次添加，将 first 赋值为新节点，此时链表只有一个元素
first = newNode;
else
// 如果不是第一次添加，将新节点赋值给 l（添加前最后一个元素）的next
l.next = newNode;
size++;
modCount++;
}
/**
* 在指定元素之前插入元素
*/
void linkBefore(E e, Node<E> succ) {
// 断言 succ 不为 null
// assert succ != null;
// 定义一个节点元素保存 succ 的 prev 引用，也就是它的前一节点信息
final Node<E> pred = succ.prev;
// 初始化节点，并指明前驱和后继节点
final Node<E> newNode = new Node<>(pred, e, succ);
// 将 succ 节点前驱引用 prev 指向新节点
succ.prev = newNode;
// 判断前驱节点是否为空，为空表示 succ 是第一个节点
if (pred == null)
// 新节点成为第一个节点
first = newNode;
else
// succ 节点前驱的后继引用指向新节点
pred.next = newNode;
size++;
modCount++;
}
根据以上代码，我们可知：
add(E e)：用于在 LinkedList 的尾部插入元素，即将新元素作为链表的最后一个元素，时间复杂度为 O(1)；add(int index,E element)：用于在指定位置插入元素。这种插入方式需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此平均需要移动 n/2 个元素，时间复杂度为 O(n)。
addAll 方法
addAll(index, c)实现方法并不是直接调用add(index, e)来实现，主要是因为效率的问题，另一个是 fail-fast 中 modCount 只会增加一次。
/**
* 将指定集合中所有元素追加到链表末尾
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
* 从指定位置开始，将指定集合中所有元素插入此列表
* * 将当前位置元素（如果存在）及后续元素向右移动
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 下标越界检查
checkPositionIndex(index);
// 获取集合元素
Object[] a = c.toArray();
int numNew = a.length;
// 集合元素个数判断
if (numNew == 0)
// 如果集合元素个数为 0 直接返回 false
return false;
// 声明前驱节点、后继节点
Node<E> pred, succ;
// 判断 index 与 size 关系
if (index == size) {
// 如果 index 等于 size，前驱节点引用指向链表末尾，后继引用为 null
succ = null;
pred = last;
} else {
// 如果 index 不等于 size，后继节点引用原 index 处节点，前驱节点引用为后继节点的前驱节点（后继节点为 index 处节点）
succ = node(index);
pred = succ.prev;
}
// 将集合元素构建为双向链表
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
// 声明后继节点空值判断
if (succ == null) {
// 如果声明后继节点为 null，则 index 等于 size，将链表末尾节点引用声明前驱节点
last = pred;
} else {
// 如果声明后继节点不为 null，声明前驱节点的后继节点引用为声明后继节点，声明后继节点的前驱节点引用为声明前驱节点
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
④ 修改元素
基于链表的实现，修改元素也比较简单，只需要先找到指定位置节点，修改节点 item 成员变量。
/**
* 修改指定位置元素，并返回源元素
*/
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
⑤ 获取元素
获取元素相关的方法一共有 3 个：
getFirst()：获取链表第一个元素getLast()：获取链表的最后一个元素get(int index)：获取链表指定位置的元素
/**
* 获取链表指定位置的元素
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* 获取链表第一个元素
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
/**
* 获取链表的最后一个元素
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
所有操作的核心在于 node(int index) 这个方法：
/**
* 返回指定下标的非空节点
*/
Node<E> node(int index) {
// 断言下标未越界
// assert isElementIndex(index);
// 如果 index 小于 size 的二分之一，从前开始查找（向后查找），反之向前查找
if (index < (size >> 1)) {
Node<E> x = first;
// 遍历，循环向后查找，直至 i == index
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;
}
}
大部分方法内部都调用了该方法来获取对应的节点。
从这个方法的源码可以看出，该方法通过比较索引值与链表 size 的一半大小来确定从表头还是表尾开始遍历。如果索引值小于 size 的一半，就从链表头开始遍历，反之从链表尾开始遍历。这样可以在较短的时间内找到目标节点，充分利用了双向链表的特性来提高效率。
⑥ 删除元素
remove()方法内部调用的是removeFirst()
删除元素相关的方法一共有 5 个：
removeFirst()：删除并返回链表的第一个元素。removeLast()：删除并返回链表的最后一个元素。remove(Object o)：删除链表中首次出现的指定元素，如果不存在该元素则返回 false。remove(int index)：删除指定索引处的元素，并返回该元素的值。void clear()：移除此列表中的所有元素。
/**
* 删除并返回链表的第一个元素
*/
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);
}
/**
* 删除链表中首次出现的指定元素，如果不存在该元素则返回 false
*/
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
/**
* 删除指定索引处的元素，并返回该元素的值
*/
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/**
* 移除此列表中的所有元素
*/
public void clear() {
// 清除所有节点间的链接是 ”不必要的“，但是：
// - 如果丢弃的节点位于多个代，则帮助分代 GC
// - 即使存在可访问的迭代器，也一定会释放内存
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
对于 clear 方法不必要，可以学习 Java 垃圾回收 中可达性分析。
但是为了让 CG 更快可以回收元素，也是必要的。
这里的核心在于 unlink(Node<E> x) 这个方法：
/**
* 解除非空节点链接
*/
E unlink(Node<E> x) {
// 断言 x 不为 null
// 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;
// 将当前节点的前驱指针置为 null，方便 GC 回收
x.prev = null;
}
// 如果后继节点为空，则说明当前节点为尾节点
if (next == null) {
// 将链表尾指针指向当前节点的前驱节点
last = prev;
} else { // 如果后继节点不为空
// 将后继节点的前驱节点指向当前节点的前驱节点
next.prev = prev;
// 将当前节点的后继节点置为 null，方便 GC 回收
x.next = null;
}
// 将当前节点元素置为 null，方便 GC 回收
x.item = null;
size--;
modCount++;
return element;
}
⑦ 查找操作
查找操作本质是为了查找元素对应节点下标。LinkedList 提供了两个方法：
indexOf：元素第一次出现的节点下标。如果找不到，则返回 -1；lastIndexOf：元素最后一次出现的节点下标。如果找不到，则返回 -1；
/**
* 查找指定元素的第一次出现节点下标
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
/**
* 查找指定元素的最后一次出现节点下标
*/
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
2.3. Stack & Queue 源码
2.3.1. 概述
Java 里有一个叫做 Stack 的类，却没有叫做 Queue 的类（它是一个接口名字）。当需要使用栈时，Java 已不推荐使用 Stack，而是推荐使用更高效的 ArrayDeque；既然 Queue 只是一个接口，当需要使用队列时也就首选 ArrayDeque 了（其次是 LinkedList）。
2.3.2. Queue
Queue 接口继承自 Collection 接口，除了最基本的 Collection 的方法之外，它还支持额外的 insertion，extraction 和 inspenction 接口。这里有两组格式，共 6 个方法，一组是抛出异常的实现；另一组是返回值的实现（没有则返回 null）。
| Throws excepiton | Special Value | |
|---|---|---|
| Insert | add(e) | offer(e) |
| Remove | remove() | poll() |
| Examine | element() | peek() |
2.3.3. Deque
Deque（double ended queue），表示双向队列。
Deque 继承自 Queue 接口，除了支持 Queue 的方法之外，还支持 insert、remove 和 examine 操作，由于 Deque 是双向的，所以可以对队列的头和尾都进行操作，它同时也支持两组格式，一组是抛出异常的实现；另一组是返回值的实现（没有则返回 null）。共 12 个方法：
| First Element - Head | Last Element - Tail | |||
|---|---|---|---|---|
| Throws exception | Special value | Throws exception | Special value | |
| Insert | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
| Remove | removeFirst() | pollFirst() | removeLast() | pollLast() |
| Examine | getFirst() | peekFirst() | getLast() | peekLast() |
当把 Deque 当作 FIFO 的 queue 来使用时，元素是从 deque 的尾部添加，从头进行删除的；所以
deque 的部分方法是和 queue 是等同的。具体如下：
| Queue Method | Equivalent Deque Method | 说明 |
|---|---|---|
| add(e) | addLast(e) | 向队尾插入元素，失败则抛出异常 |
| offer(e) | offerLast(e) | 向队尾插入元素，失败则返回 false |
| remove() | removeFirst() | 获取并删除队首元素，失败则抛出异常 |
| poll() | pollFirst() | 获取并删除队首元素，失败则返回 null |
| element() | getFirst() | 获取但不删除队首元素，失败则抛出异常 |
| peek() | peekFirst() | 获取但不删除队首元素，失败则返回 null |
由于 Deque 是双向队列，它也可以当作栈使用。具体如下：
| Stack Method | Equivalent Deque Method | 说明 |
|---|---|---|
| push(e) | addFirst(e) | 向栈顶插入元素，失败则抛出异常 |
| 无 | offerFirst(e) | 向栈顶插入元素，失败则返回 false |
| pop() | removeFirst() | 获取并删除栈顶元素，失败则抛出异常 |
| 无 | pollFirst() | 获取并删除栈顶元素，失败则返回 null |
| peek() | getFirst() | 获取但不删除栈顶元素，失败则抛出异常 |
| 无 | peekFirst() | 获取但不删除栈顶元素，失败则返回 null |
上面两个表共定义了 Deque 的 12 个接口。添加、删除、取值 都有两套接口，它们功能相同，区别是对失败情况的处理不同。
一套接口遇到失败就会抛出异常，另一套遇到失败就会返回特殊值（false 或 null）。除非某种实现对容量有限制，大多数情况下，添加操作是不会失败的。
虽然 Deque 的接口有 12 个之多，但无非就是对容器的两端进行操作，或添加，或删除，或查看。明白了着一点理解起来就会简单。
ArrayDeque 和 LinkedList 是 Deque 的两个通用实现，由于官方更推荐使用 ArrayDeque 用作栈和队列，加上上一篇已经解析过 LinkedList，下节将着重解析 ArrayDeque的具体实现。
2.4. ArrayDeque 源码
2.4.1. 概述
从 ArrayDeque 名字可以看出底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，为了提高空间利用率，该数组应该是循环的，即循环数组（circular array）。
ArrayDeque 是非线程安全的，当多个线程同时使用时，需要手动同步；另外该容器不允许放入 null 元素。
2.4.2. 实现
ArrayDeque 继承了 AbstractCollection，又同时实现了 Deque、Cloneable、Seriallizable 接口。
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable {
}
Deque：继承自Queue接口，具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据结构；Cloneable：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作；Serializable：表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输。
① 数据结构
底层数据结构
/**
* 保存元素的数组
*/
transient Object[] elements; // non-private to simplify nested class access
/**
* 队列第一个元素的下标
*/
transient int head;
/**
* 队尾下一次元素插入的下标
*/
transient int tail;
② 初始化
构造函数
ArrayDeque 有三种初始化方式，构造方法如下：
/**
* 默认无参构造器
*/
public ArrayDeque() {
elements = new Object[16];
}
/**
* 构造一个指定队列容量的双向队列
*/
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
/**
* 构造一个包含指定集合的元素的双向队列，按照它们由集合的迭代器返回的顺序
*/
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
其中的 allocateElements() 方法都被能指定容量的有参构造器调用，它的主要作用是通过 位运算符 调整容量大小为指定大小的最小 2 的幂。实现如下：
/**
* 最小初始化容量大小
*/
private static final int MIN_INITIAL_CAPACITY = 8;
/**
* 调整大小为最小 2 的幂
*/
private static int calculateSize(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// 比较指定容量大小与最小初始化容量大小
if (numElements >= initialCapacity) { // 如果指定容量大小大于最小初始化容量大小
// 指定容量调整为最小 2 的幂
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
// 越界判断
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
return initialCapacity;
}
③ 添加元素
addFirst 方法
/**
* 队首添加元素
*/
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
// 扩容
doubleCapacity();
}
addLast 方法
/**
* 队首添加元素
*/
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
这里的下标越界处理较为简单，(head - 1) & (elements.length - 1) 就可以了，这段代码相当于取余，同时解决了 head 为负数的情况。因为 elements.length 为 2 的指数倍，elements.length - 1 就是二进制位低位全 1，跟 head - 1 相与智慧就起到了取模的作用；如果head - 1为负数(其实只可能是-1)，则相当于对其取相对于elements.length的补码。tail 的处理也同理。
下面来看一下扩容函数：
doubleCapacity 方法
/**
* Object[] 两倍扩容
*/
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
扩容方法也比较简单，先申请双倍容量的数组，将头指针右边元素拷贝至新数组，再将头指针左边元素拷贝至新数组后。
以下方法内部均调用了上述方法：
add、offer、offerFirst、offerLast、Push 方法
public boolean add(E e) {
addLast(e);
return true;
}
public boolean offer(E e) {
return offerLast(e);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
public void push(E e) {
addFirst(e);
}
④ 删除元素
poolFirst 方法
/**
* 删除队首元素并返回
*/
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
elements[h] = null; // Must null out slot
head = (h + 1) & (elements.length - 1);
return result;
}
poolLast 方法
/**
* 删除队尾元素并返回
*/
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}
下面方法内部均调用了上述方法：
pop、remove、removeFirst、removeLast 方法
/**
* 删除队首元素并返回
*/
public E pop() {
return removeFirst();
}
/**
* 删除队首元素并返回
*/
public E remove() {
return removeFirst();
}
/**
* 删除队首元素并返回，存在异常判断
*/
public E removeFirst() {
E x = pollFirst();
if (x == null)
throw new NoSuchElementException();
return x;
}
/**
* 删除队尾元素并返回，存在异常判断
*/
public E removeLast() {
E x = pollLast();
if (x == null)
throw new NoSuchElementException();
return x;
}
⑤ 获取元素
peekFirst、PeekLast 方法
/**
* 获取队首元素
*/
public E peekFirst() {
// elements[head] is null if deque empty
return (E) elements[head];
}
public E getFirst() {
@SuppressWarnings("unchecked")
E result = (E) elements[head];
if (result == null)
throw new NoSuchElementException();
return result;
}
/**
* 获取队尾元素
*/
public E peekLast() {
return (E) elements[(tail - 1) & (elements.length - 1)];
}
public E getLast() {
@SuppressWarnings("unchecked")
E result = (E) elements[(tail - 1) & (elements.length - 1)];
if (result == null)
throw new NoSuchElementException();
return result;
}
public E peek() {
return peekFirst();
}
以上代码实现也比较简单，这里就不过多解释了。
2.5. PriorityQueue 源码
2.5.1. 概述
PriorityQueue 是 Java 中的一个基于优先级堆的优先队列实现，它能够在 O(log n) 的时间复杂度内实现元素的插入和删除操作，并且能够自动维护队列中元素的优先级顺序。
除了 element、peek 方法是常数时间，add、offer、无参数 remove 以及 poll 方法的时间复杂度都是 log(N)。
优先队列的作用是能保证每次取出的元素都是队列中权值最小的（Java 优先队列每次取最小元素，C++ 的优先队列每次取最大元素）。这里牵扯到了大小关系，元素大小的评判可以通过元素本身的自然排序，也可以通过构造时传入的比较器（Comparator，类似于 C++ 的仿函数）。
父子节点下标存在一下关系：
leftNo = parentNo * 2 + 1
rightNo = parentNo * 2 + 2
parentNo = （nodeNo - 1）/ 2
通过这三个公式，可以反映出节点下标，从而存储至数组中。
2.5.2. 实现
PriorityQueue 继承了 AbstractQueue，实现了 Serializable 接口。
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
}
Serializable：表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输。
① 数据结构
底层数据结构
/**
* 保存元素的数组
*/
transient Object[] queue; // non-private to simplify nested class access
/**
* 元素个数
*/
private int size = 0;
/**
* 比较器，如果使用元素的自然排序，则为空
*/
private final Comparator<? super E> comparator;
/**
* 结构修改次数
*/
transient int modCount = 0; // non-private to simplify nested class access
、
② 初始化
/**
* 默认初始化容量
*/
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
* 默认无参构造器
*/
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
/**
* 构建指定初始化容量的优先队列
*/
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
/**
* 构建指定比较器的优先队列
*/
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
/**
* 构建指定初始化容量及比较器的优先队列
*/
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
/**
* 构建指定集合为 SortedSet 的实例或另一个 PriorityQueue 相同的顺序队列，否则根据元素自然顺序进行排序
*/
@SuppressWarnings("unchecked")
public PriorityQueue(Collection<? extends E> c) {
if (c instanceof SortedSet<?>) {
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
this.comparator = (Comparator<? super E>) ss.comparator();
initElementsFromCollection(ss);
}
else if (c instanceof PriorityQueue<?>) {
PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
this.comparator = (Comparator<? super E>) pq.comparator();
initFromPriorityQueue(pq);
}
else {
this.comparator = null;
initFromCollection(c);
}
}
/**
* 创建指定队列相同的顺序的队列
*/
@SuppressWarnings("unchecked")
public PriorityQueue(PriorityQueue<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initFromPriorityQueue(c);
}
/**
* 创建按照指定元素顺序的队列
*/
@SuppressWarnings("unchecked")
public PriorityQueue(SortedSet<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initElementsFromCollection(c);
}
其中从不同的集合中元素初始化的方式不同：
/**
* 从指定队列中初始化队列
*/
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
if (c.getClass() == PriorityQueue.class) {
this.queue = c.toArray();
this.size = c.size();
} else {
initFromCollection(c);
}
}
/**
* 从指定集合中初始化队列元素
*/
private void initElementsFromCollection(Collection<? extends E> c) {
Object[] a = c.toArray();
if (c.getClass() != ArrayList.class)
a = Arrays.copyOf(a, a.length, Object[].class);
int len = a.length;
if (len == 1 || this.comparator != null)
for (int i = 0; i < len; i++)
if (a[i] == null)
throw new NullPointerException();
this.queue = a;
this.size = a.length;
}
/**
* 从指定集合中初始化队列
*/
private void initFromCollection(Collection<? extends E> c) {
// 初始化队列元素
initElementsFromCollection(c);
// 调整为小顶堆
heapify();
}
如何调整为小顶堆呢？
/**
* 调整为小顶堆（用于初始化调整）
*/
private void heapify() {
// 从 (size / 2) - 1 到 0 节点依次向下移动来保持小顶堆
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
/**
* 根据不同比较器对指定下标依次向下比较调整
*/
private void siftDown(int k, E x) {
if (comparator != null)
// 指定比较器
siftDownUsingComparator(k, x);
else
// 默认比较器
siftDownComparable(k, x);
}
/**
* 采用默认比较器对指定下标依次向下比较调整
*/
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}
/**
* 采用指定比较器对指定下标依次向下比较调整
*/
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
可以结合以下图解进行理解 siftDown(0, 10)；
除了这种方法（一般用于删除）还有 shiftUp 方法（一般用于插入元素）：
/**
* 根据不同比较器对指定下标依次向上比较调整
*/
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
/**
* 根据不同比较器对指定下标依次向上比较调整
*/
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
/**
* 采用指定比较器对指定下标依次向上比较调整
*/
@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
可以结合以下图解进行理解：
③ 添加操作
Queue 接口规定对插入失败的处理不同，add 方法 抛出异常，offer 方法返回 false。
向队列中添加元素的方法有两种：add() 和 offer()，对于 PriorityQueue 来讲并没什么差别。
add、offer 方法
/**
* 添加元素
*/
public boolean add(E e) {
return offer(e);
}
/**
* 添加元素
*/
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
上一部分已经对 siftUp 方法进行解析，这里就不进行解析了。
接下来看一下扩容方法 grow：
/**
* 队列最大容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 指定最小容量进行扩容
*/
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, 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;
}
扩容方法也比较简单，就不再赘述。
④ 删除元素
向队列中删除元素的方法有三种：remove() 、poll()、remove(Object e)；前两个方法的语义完全相同，都是获取并删除队首元素，区别是对失败的处理不同，前者抛出异常，后者返回 null，最后一个方法是删除第一次出现的指定元素。
由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整。
remove、poll 方法
/**
* 删除队首元素，失败抛出异常
*/
public E remove() {
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
/**
* 删除队首元素
*/
@SuppressWarnings("unchecked")
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
以上代码理解为：队列删除队首元素后，将队尾元素提至队首，再向下调整来维护小顶堆的性质。
remove(Object o) 方法
/**
* 删除第一次出现的指定元素，不存在返回 false
*/
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
/**
* 删除指定下标元素
*/
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
这个方法与删除队首元素相似，只不过是将队尾元素提至指定下标，再向下调整。
⑤ 获取元素
向队列中获取元素的方法有两种：element()、peek()；两者语义完全相同，都是获取但不删除队首元素，也就是队列中权值最小的元素，唯一区别就是对方法失败的处理不同，前者抛出异常，后者返回 null。
element、peek 方法
/**
* 获取队首元素，失败抛出异常
*/
public E element() {
E x = peek();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
/**
* 获取队首元素，失败返回 null
*/
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
实现比较简单，就不过多赘述。
三、Map 解析
3.1. HashMap 源码
3.1.1. 概述
由于 JDK1.8 前后底层数据结构不同，后边再进行解析。
HashMap 主要用来存放键值对，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。
HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个。
3.1.2. 实现
HashMap 继承了 AbstractMap，实现了 Map、Clonebale、Serializable。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
}
-
Map：表明它是键值对集合； -
Cloneable：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作； -
Serializable：表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输。
① 数据结构
JDK1.8 之前
JDK1.8 之前 HashMap 底层是 数组 + 链表 结合在一起使用的也就是链表散列（链表主要是为了解决哈希冲突）。
JDK 1.8 之后
JDK1.8 之后，为了减少长链表的搜索时间，当链表长度大于阈值（8）并数组长度超过 64 时，会转换为红黑树。因此，此时 HashMap 的底层数据结构是 数组 + 链表 + 红黑树。
类属性：
// 序列号
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于等于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于等于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，总是2的幂次倍
transient Node<k,v>[] table;
// 一个包含了映射中所有键值对的集合视图
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 阈值(容量*负载因子) 当实际大小超过阈值时，会进行扩容
int threshold;
// 负载因子
final float loadFactor;
- loadFactor 负载因子
loadFactor 负载因子是控制数组存放数据的疏密程度，loadFactor 越趋近于 1，那么数组中存放的数据也就越多，也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于 0，数组中存放的数据也就越少，也就越稀疏。
loadFactor 太大导致查找效率低，太小导致数组的利用率低，存放的数组会很分散，loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值
给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量超过了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、赋值数组等操作，所以非常消耗性能。
- threshold
threshold = capacity * loadFactor，当 size 大于 threshold 的时候，那么就要考虑对数组的扩增了，也就是说，它衡量数组是否需要扩增的一个标准。
Node 节点类源码
// 继承自 Map.Entry<K,V>
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;// 哈希值，存放元素到hashmap中时用来与其他元素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; }
// 重写hashCode()方法
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 重写 equals() 方法
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;
}
}
树节点类源码
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父
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);
}
// 返回根节点
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
......
}
② 初始化
构造函数
HashMap 有四种初始化方式，构造方法如下：
/**
* 默认无参构造函数
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* 包含另一个 "Map" 的构造函数
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false); // 下面进行分析
}
/**
* 指定 "容量大小" 的构造函数
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 指定 "容量大小" 和 "负载因子" 的构造函数
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
// 初始容量暂时存放到 threshold，在 resize 中再赋值给 newCap 进行 table 初始化
this.threshold = tableSizeFor(initialCapacity);
}
值得注意的是上述四个构造方法中，都初始化了负载因子 loadFactor，由于 HashMap 中没有 capacity 这样的字段，即使指定了初始化容量 initialCapacity，也只是通过 tableSizeFor 将其扩容到与 initialCapactity 最接近的 2 的幂次方大小，然后暂时赋值给 threshold，后续通过 resize 方法将 threshold 赋值给 newCap 进行 table 的初始化。
putMapEntries 方法
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
// 判断 table 是否已初始化
if (table == null) { // 未初始化
// 计算所需最小容量
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 比较 最小容量与实际初始化容量
if (t > threshold) // 最小容量大小 大于 实际容量
threshold = tableSizeFor(t);
}
else if (s > threshold) // 已初始化并 m 元素个数超过阈值
resize();
// 将 m 中元素添加到 hashMap 中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
// 如 table 未初始化， 该方法会调用 resize 初始化或扩容
putVal(hash(key), key, value, false, evict);
}
}
}
③ 添加元素
HashMap 只提供了 put 方法用于添加元素。源码如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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 未初始化或者长度为 0，进行扩容
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 的关系
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) // 相同
// 将节点进行替换
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
// 尝试将链表转为红黑树（数组长度大于等于 64，才会进行转换）
treeifyBin(tab, hash);
break;
}
// 判断链表中节点与插入元素的关系
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相同，跳出循环
break;
p = e;
}
}
// 表示在桶中找到 key、hash 均与插入元素相等的节点
if (e != null) { // existing mapping for key
// 记录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;
}
通过以上代码，我们可以知道：
- 如果定位到的数组位置没有元素，则直接插入；
- 如果定位到的数组位置有元素就和插入的 key 比较，如果相同就直接覆盖，不同就判断 p 是否为一个树节点，如果是就调用
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)将元素添加进去，如果不是就遍历链表尾部插入。
再看一下 JDK1.7 的实现：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) { // 先遍历
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i); // 再插入
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//自动扩容，并重新哈希
hash = (null != key) ? hash(key) : 0;
bucketIndex = hash & (table.length-1);//hash%table.length
}
//在冲突链表头部插入新的entry
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
通过以上代码，我们可以知道 JDK1.7 的实现：
- 如果定位到的数组位置没有元素，就直接插入；
- 如果定位到的数组有元素，遍历以这个元素为头结点的链表，依次和插入的 key 比较，如果相同就直接覆盖，不同就先扩容，再采用头插法插入元素。
④ resize 方法
进行扩容，会伴随着一次重新 hash 分配，并且会遍历 hash 表中的所有元素，非常耗时。因此，在编写程序时，要尽量避免 resize。
resize 方法用于初始化数组或数组扩容，每次扩容，容量为原来的 2 倍，并进行数据迁移。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { // 对应数组扩容
// 判断数组长度大小关系
if (oldCap >= MAXIMUM_CAPACITY) { // 超过最大值
// 直接返回
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 未超过最大值，扩充为原来的 2 倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 阈值扩大一倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 对应使用 new HashMap(int initialCapacity) 初始化后，第一次 put 的时候
// 此时只需要将其作为新的数组容量
newCap = oldThr;
else { // 对应使用 new HashMap() 初始化后，第一次 put 的时候
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 创建时指定了初始化容量或者负载因子，在这里进行阈值初始化，
// 或者扩容前的旧容量小于16，在这里计算新的resize上限
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
⑤ 获取元素
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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) {
// 在树中get
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在链表中get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
相较于 put 方法来说，get 方法比较简单：
- 计算 key 的 hash 值，找到对应数组下标；
- 判断数组该位置处的元素是否恰好是相应元素，若不是，进行下一步；
- 判断元素类型是否为红黑树，如果是则用红黑树方式获取数据，若不是，进行下一步；
- 遍历链表，查找相应元素。
⑥ 删除元素
remove 方法
/**
* 删除元素
*/
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* 删除节点
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
方法的主要逻辑与添加元素相似，就不进行过多赘述。
3.1.3 HashSet
HashSet 与 HashMap 有着相同的实现，HashSet 仅仅对 HashMap 进行了一层包装。
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
...
}
3.2. TreeMap 源码
3.2.1. 概述
TreeMap 底层通过红黑树实现，containKey()、get()、put、remove() 都有着 log(n) 的时间复杂度。
上图中，每个节点代表一个 TreeMap 的 Entry，图中只画出了 key，未画出 value。
出于性能考虑，TreeMap 也是非同步的，如果需要在多线程环境使用，需要程序员手动同步。
下面简单说一下红黑树：
红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍。具体来说，红黑树是满足如下条件的二叉查找树(binary search tree):
- 每个节点要么是红色，要么是黑色。
- 根节点必须是黑色
- 红色节点不能连续(也即是，红色节点的孩子和父亲都不能是红色)。
- 对于每个节点，从该点至
null(树尾端)的任何路径，都含有相同个数的黑色节点。
在树的结构发生改变时(插入或者删除操作)，往往会破坏上述条件3或条件4，需要通过调整使得查找树重新满足红黑树的约束条件。
3.2.2. 实现
TreeMap 继承了 AbstractMap，实现了 NavigableMap、Cloneable、Serializable 接口。
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
...
}
NavigableMap：拓展了相关导航方法，返回给定搜索目标的最接近匹配项。Cloneable：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作；Serializable：表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输。
① 数据结构
底层数据结构
每个节点都是一个 Entry 类实例：
// 比较器
private final Comparator<? super K> comparator;
// 根对象
private transient Entry<K,V> root;
// 实例数
private transient int size = 0;
// 结构修改次数
private transient int modCount = 0;
Entry 类：
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
...
}
② 初始化
构造函数
/**
* 默认无参构造器
*/
public TreeMap() {
comparator = null;
}
/**
* 指定比较器
*/
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
/**
* Map 转换为 TreeMap
*/
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
/**
* 已排序集合转换为 TreeMap
*/
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
其中 buildFromSorted 方法通过获取中间元素，先后递归构建左右子树。
③ 添加元素
由于添加或删除元素可能需要调整树结构，这里先提前解释一下当破坏树结构后调整的两种方式：
- 颜色调整
这种情况一般对应着一种情况：父节点和叔节点均为红色，而祖父节点为黑色。
此时只需要将父节点与叔节点变为黑色，祖父节点变为红色即可。但是由于祖父节点位置的不确定，调整后会产生两种情况：
祖父节点的父节点为根节点（此时，需要将祖父节点更改为黑色）；祖父节点不是根节点（当 祖父节点的父节点为黑色时则调整结束，否则继续向上迭代调整）。
如下图所示（cur 表示新增节点）：
- 旋转（结构调整）
当父节点为红色，叔节点与祖父节点为黑色时，就无法通过颜色调整解决，此时需要通过旋转来调整树结构。
此时也存在两种情况：新增节点、父节点与祖父节点在同一直线上；新增节点、父节点与祖父节点不在同一直线上。
当位于同一直线时，通过左旋或右旋进行调整，如下图所示：
这里省略了左旋…
当不位于同一直线时，只需要先左旋或右旋一下，即可调整至上一情况，如下图所示:
put 方法
/**
* 添加指定 key，value
*/
public V put(K key, V value) {
// 获取根对象
Entry<K,V> t = root;
if (t == null) { // 根对象为空
// 检查比较器
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// 获取比较器
Comparator<? super K> cpr = comparator;
if (cpr != null) { // 指定比较器
// 从 root 根依次比较至合适插入位置
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
// 替换比较器认为相同的对象
return t.setValue(value);
} while (t != null);
}
else { // 元素的自然顺序
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
// 从 root 根依次比较至合适插入位置
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
// 替换比较器认为相同的对象
return t.setValue(value);
} while (t != null);
}
// 构建新 Entry 对象
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 调整树结构
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
/**
* 左旋
*/
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
Entry<K,V> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
/**
* 右旋
*/
private void rotateRight(Entry<K,V> p) {
if (p != null) {
Entry<K,V> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
通过以上代码，可以了解到 TreeMap 元素添加过程，其中最重要的是 fixAfterInsertion 方法，下面看一下其具体实现：
/**
* 调整树结构
*/
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) { // x 不是根节点且父节点为红色
// 判断父节点与祖父节点左子节点关系
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { 父节点对应祖父节点左子节点
// 获取叔节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
// 判断叔节点颜色
if (colorOf(y) == RED) { // 叔节点为红色
// 将父节点与叔节点换为黑色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
// 将祖父节点换为红色
setColor(parentOf(parentOf(x)), RED);
// 获取祖父节点
x = parentOf(parentOf(x));
} else { // 叔节点为黑色
// 判断 x 与其父节点的右子节点关系
if (x == rightOf(parentOf(x))) { // x 是其父节点的右子节点
// 将 x 的父节点进行左旋
x = parentOf(x);
rotateLeft(x);
}
// 将父节点设为黑色
setColor(parentOf(x), BLACK);
// 祖父节点设为红色，再进行右旋
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else { // 父节点对应祖父节点右子节点
// 获取叔节点
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
// 判断叔节点颜色
if (colorOf(y) == RED) { // 叔节点为红色
// 将父节点与叔节点换为黑色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
// 将祖父节点换为红色
setColor(parentOf(parentOf(x)), RED);
// 获取祖父节点
x = parentOf(parentOf(x));
} else { // 叔节点为黑色
// 判断 x 与其父节点的左子节点关系
if (x == leftOf(parentOf(x))) {
// 父节点进行右旋
x = parentOf(x);
rotateRight(x);
}
// 父节点设置为黑色
setColor(parentOf(x), BLACK);
// 祖父节设置为红色
setColor(parentOf(parentOf(x)), RED);
// 左旋父节点
rotateLeft(parentOf(parentOf(x)));
}
}
}
// 根节点设置为黑色
root.color = BLACK;
}
putAll 方法
/**
* 插入集合
*/
public void putAll(Map<? extends K, ? extends V> map) {
// 获取当前树上元素
int mapSize = map.size();
// 判断是否为空树及 map 是否为 SortedMap 实例
if (size==0 && mapSize!=0 && map instanceof SortedMap) { // 空树，并且 map 为 SortedMap 实例
// 获取 map 的比较器
Comparator<?> c = ((SortedMap<?,?>)map).comparator();
// 判断 map 比较器与当前指定比较器关系
if (c == comparator || (c != null && c.equals(comparator))) { // 比较器相等
// 构建树
++modCount;
try {
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
// 采用 fro 循环依次 put
super.putAll(map);
}
④ 获取元素
get 方法
/**
* 获取 key 所对应 value
*/
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
/**
* 获取 key 所对应 Entry 实例
*/
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
// 默认元素的自然比较器
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
/**
* 通过指定比较器获取 key 所对应 Entry 实例
*/
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}
由于红黑树的特性，获取元素实现也比较简单，就不展开叙述了（偷个懒，嘿嘿_）。
⑤ 删除元素
remove 方法
/**
* 删除 key 所对应 Entry 实例
*/
public V remove(Object key) {
// 获取 key 所对应 Entry 实例
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
// 删除 Entry 实例
deleteEntry(p);
return oldValue;
}
/**
* 删除指定实例
*/
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
if (p.left != null && p.right != null) { // p 节点的左右子树都非空
Entry<K,V> s = successor(p); // 获取后继节点
p.key = s.key;
p.value = s.value;
p = s;
}
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) { // p 只有一棵子树为空
// Link replacement to parent
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
p.left = p.right = p.parent = null;
if (p.color == BLACK) // 调整树结构
fixAfterDeletion(replacement);
} else if (p.parent == null) {
root = null;
} else { // p 左右子树都为空
if (p.color == BLACK) // 调整树结构
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
/**
* 调整树结构
*/
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) { // x 不是根节点且 x 为黑色
if (x == leftOf(parentOf(x))) { // x 是父节点的左子节点
Entry<K,V> sib = rightOf(parentOf(x));
if (colorOf(sib) == RED) { // 父节点的右子节点为红色
// 进行颜色交换，并左旋
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
// 更新 sib
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) { // sib 的左右节点都为黑色
// sib 设为 红色
setColor(sib, RED);
// x 移动到父节点
x = parentOf(x);
} else {
// sib 左子节点为黑色
if (colorOf(rightOf(sib)) == BLACK) {
// sib 与 左子节点进行颜色交互，并右旋
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // x 是父节点的右子节点
Entry<K,V> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
x 对应父节点的右子节点的处理情况，与另一种情况对称，处理逻辑相同，就不进行过多赘述。
3.2.3 TreeSet
TreeSet 与 TreeMap 的关系和 HashSet 与 HashMap 的关系相同，前者是对后者的简单包装。
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
...
}
3.3. LinkedHashMap
3.3.1. 概述
LinkedHashMap 在 HashMap 的基础上维护了一条双向链表，使得其具备一些特性：
- 支持遍历时按照插入顺序进行迭代；
- 支持按照元素访问顺序排序，适用于封装 LRU 缓存工具；
- 由于内部使用双向链表维护各个基点，所以遍历效率与元素个数成正比，相较于和容量成正比的 HashMap 来说，迭代效率会高很多。
3.3.2. 实现
LinkedHashMap 继承了 HashMap，实现了 Map 接口。
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V> {
...
}
Map：表明它是键值对集合；
① 数据结构
/**
* 链表头节点
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* 链表尾节点
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* 迭代排序方式（默认为 false）：访问顺序为 true，插入顺序为 false
*/
final boolean accessOrder;
下面来看一下 Entry 类：
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);
}
}
② 初始化
构造函数
/**
* 默认无参构造器
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
/**
* 指定初始容量
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* 指定初始容量及负载因子
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
/**
* 指定初始容量、负载因子及迭代排序方式
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
③ 获取元素
get 方法
/**
* 获取 key 所对应元素
*/
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
与 HashMap 的实现差不多，唯一有区别的地方是：在 accessOrder 为 true 的情况下，会在查询完成后，将当前元素移动到链表的末尾。下面看一下 afterNodeAccess 方法实现。
/**
* 节点移动至链表末尾
*/
void afterNodeAccess(Node<K,V> e) {
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) { // 迭代排序为访问顺序，且节点 e 不为链表末尾
// 获取节点 e 的前驱节点和后继节点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 节点 p 的后继节点置为空
p.after = null;
// 判断前驱节点是否为空
if (b == null) // 前驱节点为空，说明节点 p 为首节点
// 头节点置为节点 p 的后继节点
head = a;
else // 前驱节点不为空
// 节点 p 前驱节点的后继节点置为节点 p 的后继节点
b.after = a;
// 判断节点 p 的后继节点是否为空
if (a != null) // 节点 p 的后继节点不为空
// 节点 p 后继节点的前驱节点置为节点 p 的前驱节点
a.before = b;
else // 节点 p 的后继节点为空，说明节点 p 为链表末尾（前边已经确定节点 p 不为链表末尾，因此这个 else 无意义）
last = b;
// 判断原链表末尾节点是否为空
if (last == null) // 原链表末尾节点为空，说明当前链表只有一个节点 p
// 链表末尾节点置为 p
head = p;
else { // 原链表末尾节点不为空
// 节点 p 的前驱节点置为原链表末尾节点
p.before = last;
// 原链表末尾节点的后继节点置为 p
last.after = p;
}
// 链表末尾节点置为 p
tail = p;
++modCount;
}
}
④ 删除元素
remove 后置操作 – afterNodeRemoval
LinkedHashMap 并没有对 remove 方法进行重写，而是直接继承 HashMap 的 remove 方法，为了保证键值对移除后双向链表中的节点也会同步被移除，LinkedHashMap 重写了 HashMap 的空实现方法 afterNodeRemoval。
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
//略
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
//HashMap 的 removeNode 完成元素移除后会调用 afterNodeRemoval 进行移除后置操作
afterNodeRemoval(node);
return node;
}
}
return null;
}
//空实现
void afterNodeRemoval(Node<K,V> p) { }
我们可以看到从 HashMap 继承的 remove 方法内部调用的 removeNode 方法将节点从 bucket 删除后，调用了 afterNodeRemoval。
void afterNodeRemoval(Node<K,V> e) { // unlink
// 获取当前节点 p、以及 e 的后继节点 b 和前驱节点 a
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// p 的前驱节点和后继节点都置为 null
p.before = p.after = null;
// 判断节点 p 的前驱节点是否为空
if (b == null) // p 的前驱节点为空，说明节点 p 为链表首节点
// head 指针置为节点 p 的后继节点
head = a;
else // p 的前驱节点不为空
// 节点 p 前驱节点的后继节点置为 p 的后继节点
b.after = a;
// 判断节点 p 的后继节点是否为空
if (a == null) // 节点 p 的后继节点为空，说明节点 p 位于链表末尾
// 链表末尾置为节点 p 的前驱节点
tail = b;
else // 节点 p 的后继节点不为空
// 链表 p 后继节点的前驱节点置为 链表 p 的前驱节点
a.before = b;
}
⑤ 添加元素
put 方法后置操作 – afterNodeInsertion
同样 LinkedHashMap 并没有实现插入方法，而是直接继承 HashMap 的所有插入方法交由用户使用，但为了维护双向链表访问的有序性，它做了这样两件事：
- 重写
afterNodeAccess（上文也提到过），如果当前被插入的 key 已存在于map中，由于需要将插入元素追加至链表末尾，因此对于存在的 key 则调用afterNodeAccess将其放到链表末尾。 - 重写
HashMap的afterNodeInsertion方法，当removeEldestEntry返回 true 时，会将链表首节点移除。
这一点可以在 HashMap 的插入操作核心方法 putVal 中看到。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//如果当前的key在map中存在，则调用afterNodeAccess
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
//调用插入后置方法，该方法被LinkedHashMap重写
afterNodeInsertion(evict);
return null;
}
上面代码已经解释了，下面看一下 afterNodeInsertion 代码。
void afterNodeInsertion(boolean evict) { // 可能去掉头节点
LinkedHashMap.Entry<K,V> first;
// evict 为 true 且头节点不为空及 removeEldestEntry 返回 true
if (evict && (first = head) != null && removeEldestEntry(first)) {
// 获取链表头节点的键值对 key
K key = first.key;
// 删除头节点
removeNode(hash(key), key, null, false, true);
}
}
这里也比较简单，就不过多概述了。
后边再学习与并发相关的集合。
Vector 是 List 的古老实现类，底层使用 Object[] 存储，线程安全。 ↩︎
原文地址：https://blog.csdn.net/m0_74816185/article/details/143608890
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！