# Java进阶集合框架
# 1. Collection 类关系图
Collection整体架构图
Java集合框架 (JCF)
│
├── Collection (接口)
│ ├── List (接口，有序、可重复)
│ │ ├── ArrayList (实现类，动态数组)
│ │ ├── LinkedList (实现类，双向链表)
│ │ ├── Vector (实现类，线程安全的动态数组，已过时)
│ │ └── Stack (实现类，栈，继承自Vector，已过时)
│ │
│ ├── Set (接口，无序、不重复)
│ │ ├── HashSet (实现类，基于HashMap)
│ │ │ └── LinkedHashSet (实现类，基于LinkedHashMap，保持插入顺序)
│ │ └── TreeSet (实现类，基于TreeMap，排序)
│ │
│ └── Queue (接口，队列)
│ ├── LinkedList (同时实现List和Deque)
│ ├── PriorityQueue (实现类，优先级队列，堆实现)
│ ├── ArrayDeque (实现类，双端队列，循环数组)
│ └── BlockingQueue (接口，阻塞队列，在java.util.concurrent包中)
│
└── Map (接口)
├── HashMap (实现类，数组+链表/红黑树)
│ └── LinkedHashMap (实现类，保持插入/访问顺序)
├── TreeMap (实现类，红黑树，排序)
├── Hashtable (实现类，线程安全，已过时)
└── WeakHashMap (实现类，弱引用键，适合缓存)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
重要接口说明
Collection接口 定义了集合的基本操作，如添加、删除、遍历等。
Map接口 是独立的，不继承Collection，用于键值对存储。
迭代器模式：Collection接口继承Iterable，提供iterator()方法，支持foreach循环。
# 2. ArrayList源码解析
# 2.1 内部结构
ArrayList基于数组实现，可以动态扩容。
// 内部数组，存储元素
transient Object[] elementData;
// 元素个数
private int size;
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 空数组常量，用于空实例
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 2.2 构造方法
// 无参构造，初始为空数组，第一次添加元素时扩容为10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 指定初始容量
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);
}
}
// 用另一个集合构造
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray可能返回的不是Object[]类型
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 2.3 扩容机制(grow方法)
private void grow(int minCapacity) {
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);
elementData = Arrays.copyOf(elementData, newCapacity);
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
扩容过程图示：
初始：elementData = [], size = 0
添加第一个元素：
minCapacity = size + 1 = 1
oldCapacity = 0
newCapacity = 0 + (0 >> 1) = 0
newCapacity < minCapacity，所以newCapacity = 1
创建大小为1的数组，拷贝(无)元素
当容量不足时，假设当前容量为10，需要添加第11个元素：
minCapacity = 11
oldCapacity = 10
newCapacity = 10 + (10 >> 1) = 15
创建大小为15的数组，拷贝10个元素到新数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 2.4 添加元素
add(E e)：添加到末尾，时间复杂度O(1)(不考虑扩容)
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
1
2
3
4
5
2
3
4
5
add(int index, E element)：插入到指定位置，需要移动元素，时间复杂度O(n)
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
// 将index及之后的元素向后移动一位
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
插入元素图示：
原数组：[A, B, C, D, E, _, _, _] (size=5, capacity=8)
在索引2处插入X：
1. 检查容量，足够则继续
2. 将C, D, E向后移动一位：
System.arraycopy(elementData, 2, elementData, 3, 3) // 3 = size - index = 5-2
移动后：[A, B, C, C, D, E, _, _] // 注意索引2和3都是C
3. elementData[2] = X
结果：[A, B, X, C, D, E, _, _]
4. size = 6
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 2.5 删除元素
remove(int index)：删除指定位置元素，需要移动元素，时间复杂度O(n)
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;
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
删除元素图示：
原数组：[A, B, X, C, D, E, _, _] (size=6)
删除索引2处的X：
1. 计算需要移动的元素个数：numMoved = 6 - 2 - 1 = 3
2. 将[C, D, E]向前移动一位：
System.arraycopy(elementData, 3, elementData, 2, 3)
移动后：[A, B, C, D, E, E, _, _]
3. 将最后一个元素置null：elementData[5] = null
结果：[A, B, C, D, E, _, _, _]
4. size = 5
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 2.6 随机访问
ArrayList实现了RandomAccess接口，支持快速随机访问。
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 3. LinkedList源码解析
# 3.1 内部结构
LinkedList是基于双向链表实现的。
// 节点定义
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;
}
}
// 头节点和尾节点
transient Node<E> first;
transient Node<E> last;
transient int size = 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 3.2 添加元素
add(E e)：添加到链表末尾
public boolean add(E e) {
linkLast(e);
return true;
}
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++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
添加元素图示：
初始链表：first → [A] ← last
添加B：
1. 创建新节点：newNode(prev=A, item=B, next=null)
2. 更新last指向newNode
3. 原last节点A的next指向newNode
结果：first → [A] ↔ [B] ← last
1
2
3
4
5
6
2
3
4
5
6
add(int index, E element)：插入到指定位置
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
1
2
3
4
5
6
7
2
3
4
5
6
7
linkBefore方法：
void linkBefore(E e, Node<E> succ) {
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++;
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
插入元素图示：
原链表：first → [A] ↔ [C] ← last
在索引1处(C节点之前)插入B：
1. 找到C节点：succ = node(1) = C
2. 找到C的前驱：pred = succ.prev = A
3. 创建新节点：newNode(prev=A, item=B, next=C)
4. 更新C的前驱为newNode：succ.prev = newNode
5. 更新A的后继为newNode：pred.next = newNode
结果：first → [A] ↔ [B] ↔ [C] ← last
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 3.3 删除元素
remove(int index)：
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
1
2
3
4
2
3
4
unlink方法：
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next; // 删除的是头节点
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev; // 删除的是尾节点
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
删除元素图示：
原链表：first → [A] ↔ [B] ↔ [C] ← last
删除节点B：
1. 获取B的前驱A和后继C
2. 将A的next指向C：A.next = C
3. 将C的prev指向A：C.prev = A
4. 将B的prev和next置null，item置null
结果：first → [A] ↔ [C] ← last
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 3.4 查找元素
node(int index)：根据索引找到节点，通过判断索引在前半部分还是后半部分来提高效率。
Node<E> node(int 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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
二分查找图示：
链表：[A, B, C, D, E, F, G] (size=7)
查找索引4的元素E：
因为 index=4 > size/2=3.5，所以从尾部开始向前查找：
1. x = last = G, i=6
2. i>4, x = x.prev = F, i=5
3. i>4, x = x.prev = E, i=4
4. i=4 不满足 i>index，返回E
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 4. Stack & Queue 源码解析
# 4.1 Stack
Stack继承自Vector，是线程安全的，但已过时，推荐使用Deque接口的实现类(如ArrayDeque)作为栈。
主要方法：
public class Stack<E> extends Vector<E> {
public E push(E item) {
addElement(item); // 调用Vector的方法
return item;
}
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
栈操作图示：
栈底 栈顶
↓ ↓
[A, B, C, D, E]
push(F) → [A, B, C, D, E, F]
pop() → 返回F，栈变为 [A, B, C, D, E]
peek() → 返回E，栈不变
1
2
3
4
5
6
7
2
3
4
5
6
7
# 4.2 Queue
Queue是一个接口，定义了队列的基本操作。
public interface Queue<E> extends Collection<E> {
boolean add(E e); // 添加元素，失败时抛出异常
boolean offer(E e); // 添加元素，失败时返回false
E remove(); // 移除并返回头部元素，失败时抛出异常
E poll(); // 移除并返回头部元素，失败时返回null
E element(); // 返回头部元素，失败时抛出异常
E peek(); // 返回头部元素，失败时返回null
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 4.3 ArrayDeque
ArrayDeque是基于循环数组实现的双端队列，既可以作为栈，也可以作为队列。
内部结构：
transient Object[] elements; // 存储元素的数组
transient int head; // 头指针
transient int tail; // 尾指针
1
2
3
2
3
循环数组图示：
初始状态：head=0, tail=0, capacity=8
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ │ │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┘
添加元素A, B, C, D, E, F, G, H 后：head=0, tail=0(已满)
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │ F │ G │ H │
└───┴───┴───┴───┴───┴───┴───┴───┘
移除两个元素后：head=2, tail=0
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ │ │ C │ D │ E │ F │ G │ H │
└───┴───┴───┴───┴───┴───┴───┴───┘
↑ ↑
head tail
再添加两个元素I, J：head=2, tail=2
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ J │ │ C │ D │ E │ F │ G │ H │
└───┴───┴───┴───┴───┴───┴───┴───┘
↑ ↑
tail head
注意：tail指向下一个插入位置，head指向第一个元素。
当head==tail时，数组为空；当(tail+1)%capacity==head时，数组已满。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
添加元素(addLast)：
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head )
doubleCapacity();
}
1
2
3
4
5
6
7
2
3
4
5
6
7
这里(tail + 1) & (elements.length - 1)相当于(tail + 1) % elements.length，因为elements.length是2的幂。
扩容(doubleCapacity)：
private void doubleCapacity() {
int p = head;
int n = elements.length;
int r = n - p; // 头指针右边的元素个数
int newCapacity = n << 1; // 双倍
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r); // 复制head右边的元素
System.arraycopy(elements, 0, a, r, p); // 复制head左边的元素
elements = a;
head = 0;
tail = n;
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
作为栈使用：
// 压栈
public void push(E e) {
addFirst(e);
}
// 出栈
public E pop() {
return removeFirst();
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
作为队列使用：
// 入队
public boolean offer(E e) {
return offerLast(e);
}
// 出队
public E poll() {
return pollFirst();
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 5. PriorityQueue源码解析
# 5.1 内部结构
PriorityQueue基于二叉堆实现，默认是小顶堆。
transient Object[] queue; // 存储元素的数组
int size; // 元素个数
private final Comparator<? super E> comparator; // 比较器
1
2
3
2
3
# 5.2 堆的上浮和下沉
上浮(siftUp)：插入元素时，将新元素放在末尾，然后向上调整。
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
上浮图示：
插入元素3：
初始堆：[2, 4, 6, 8, 9, 7, 10](小顶堆)
2
/ \
4 6
/ \ / \
8 9 7 10
插入3到末尾：
2
/ \
4 6
/ \ / \
8 9 7 10
/
3
上浮调整：
1. 3与父节点8比较，3<8，交换：
2
/ \
4 6
/ \ / \
3 9 7 10
/
8
2. 3与父节点4比较，3<4，交换：
2
/ \
3 6
/ \ / \
4 9 7 10
/
8
3. 3与父节点2比较，3>2，停止。
最终堆：[2, 3, 6, 4, 9, 7, 10, 8]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
下沉(siftDown)：删除堆顶元素时，将最后一个元素移到堆顶，然后向下调整。
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; // 非叶子节点数量
while (k < half) {
int child = (k << 1) + 1; // 左子节点
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
下沉图示：
删除堆顶元素2：
初始堆：[2, 3, 6, 4, 9, 7, 10, 8]
2
/ \
3 6
/ \ / \
4 9 7 10
/
8
用最后一个元素8替换堆顶：
8
/ \
3 6
/ \ / \
4 9 7 10
下沉调整：
1. 8与子节点3、6比较，3较小，交换8和3：
3
/ \
8 6
/ \ / \
4 9 7 10
2. 8与子节点4、9比较，4较小，交换8和4：
3
/ \
4 6
/ \ / \
8 9 7 10
3. 8与子节点(无)比较，停止。
最终堆：[3, 4, 6, 8, 9, 7, 10]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 5.3 添加和删除元素
添加元素(offer)：
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
删除堆顶元素(poll)：
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 6. HashSet & HashMap 源码解析
# 6.1 HashSet
HashSet是基于HashMap实现的，只使用了HashMap的键，值用一个固定的Object对象填充。
public class HashSet<E> extends AbstractSet<E> implements Set<E> {
private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object(); // 虚拟值
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 6.2 HashMap(Java 8)
6.2.1 内部结构
HashMap是数组+链表+红黑树的结构。
// 链表节点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
// 构造函数、getter、setter等
}
// 树节点
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;
boolean red;
// 树操作相关方法
}
// 哈希表
transient Node<K,V>[] table;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
6.2.2 哈希函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1
2
3
4
2
3
4
6.2.3 查找元素
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 && ((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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
查找过程图示：
哈希表(数组)：
索引0: 空
索引1: 链表 A → B → C
索引2: 红黑树 (根节点为D)
索引3: 空
查找key：
1. 计算hash，定位到索引1
2. 第一个节点A不是目标，遍历链表找到B
3. 返回B的值
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
6.2.4 插入元素
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;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; // 第一次插入，初始化数组
if ((p = tab[i = (n - 1) & hash]) == null) // 桶为空
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
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) // 链表长度达到8
treeifyBin(tab, hash); // 转换为红黑树
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break; // 找到目标节点
p = e;
}
}
if (e != null) { // 更新已有键的值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
return oldValue;
}
}
++modCount;
if (++size > threshold) // 超过阈值，扩容
resize();
return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
插入过程图示：
插入键值对 (K, V)：
1. 计算hash，定位到桶索引i
2. 如果table[i]为空，直接创建新节点放入
3. 否则，遍历链表或树：
a. 如果找到相同key，更新value
b. 如果没找到，在链表尾部插入新节点
- 如果链表长度达到8，转换为红黑树
4. 如果size超过阈值，扩容
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
6.2.5 扩容机制
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;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 双倍扩容
}
// ... 计算新容量和阈值
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 { // 链表
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 { // 原索引+oldCap位置
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
扩容图示：
旧表容量16，新表容量32：
旧表索引5的链表：A → B → C → D
扩容时，根据 (hash & oldCap) 将链表分为两组：
- (hash & 16) == 0 的节点：A, C -> 新索引5
- (hash & 16) != 0 的节点：B, D -> 新索引21 (5+16)
结果：
新表索引5：A → C
新表索引21：B → D
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 7. LinkedHashSet & LinkedHashMap 源码解析
# 7.1 LinkedHashSet
LinkedHashSet继承自HashSet，但内部使用LinkedHashMap实现。
public class LinkedHashSet<E> extends HashSet<E> implements Set<E> {
public LinkedHashSet() {
super(16, .75f, true); // 调用HashSet的构造方法，底层创建LinkedHashMap
}
}
1
2
3
4
5
2
3
4
5
# 7.2 LinkedHashMap
LinkedHashMap继承自HashMap，在HashMap的基础上维护了一个双向链表来记录插入顺序或访问顺序。
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
// 双向链表的头节点和尾节点
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
// 访问顺序模式
final boolean accessOrder;
// 节点继承自HashMap.Node，并增加了前后指针
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);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
7.2.1 维护插入顺序
在插入元素时，除了调用HashMap的put方法，还会调用afterNodeInsertion和afterNodeAccess方法，将节点链接到双向链表的尾部。
void afterNodeInsertion(boolean evict) {
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
void afterNodeAccess(Node<K,V> e) {
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
插入顺序维护图示：
初始：head=null, tail=null
插入A：head → [A] ← tail
插入B：head → [A] ↔ [B] ← tail
插入C：head → [A] ↔ [B] ↔ [C] ← tail
1
2
3
4
2
3
4
7.2.2 访问顺序模式
当accessOrder=true时，每次访问(get或put)一个节点，都会将该节点移动到链表尾部，从而实现LRU缓存。
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;
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
LRU缓存实现：
class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true); // 访问顺序模式
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity; // 超过容量时移除最老的节点
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
LRU缓存图示：
容量为3的LRU缓存：
插入A： [A]
插入B： [A, B]
插入C： [A, B, C]
访问A： [B, C, A] // A被移到尾部
插入D： [C, A, D] // B被移除(最久未访问)
1
2
3
4
5
6
2
3
4
5
6
# 8. TreeSet & TreeMap 源码解析
# 8.1 TreeSet
TreeSet基于TreeMap实现，只使用键，值用一个固定的Object对象填充。
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E> {
private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();
public TreeSet() {
this(new TreeMap<E,Object>());
}
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 8.2 TreeMap
TreeMap基于红黑树实现，保证了键的有序性。
8.2.1 内部结构
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V> {
private final Comparator<? super K> comparator; // 比较器
private transient Entry<K,V> root; // 根节点
private transient int size = 0;
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; // 颜色
// 构造函数等
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
8.2.2 插入元素
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // 检查key是否可比较
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) { // 使用比较器
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();
Comparable<? super K> k = (Comparable<? super K>) key;
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<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e); // 插入后调整红黑树
size++;
modCount++;
return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
插入过程图示：
插入键：5, 3, 7, 2, 4, 6, 8
步骤1：插入5
5(B)
步骤2：插入3
5(B)
/
3(R)
步骤3：插入7
5(B)
/ \
3(R) 7(R)
步骤4：插入2
5(B)
/ \
3(R) 7(R)
/
2(R) // 连续两个红色节点，需要调整
调整后：
5(B)
/ \
3(B) 7(B)
/
2(R)
步骤5：插入4
5(B)
/ \
3(B) 7(B)
/ \
2(R)4(R)
步骤6：插入6
5(B)
/ \
3(B) 7(B)
/ \ /
2(R)4(R)6(R)
步骤7：插入8
5(B)
/ \
3(B) 7(B)
/ \ / \
2(R)4(R)6(R)8(R)
调整后(可能根据红黑树规则进行调整)：
最终红黑树结构略。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
8.2.3 查找元素
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
查找过程图示：
红黑树：
5(B)
/ \
3(B) 7(B)
/ \ / \
2(R)4(R)6(R)8(R)
查找键6：
1. 从根节点5开始，6>5，进入右子树7
2. 6<7，进入左子树6
3. 找到6，返回
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
8.2.4 范围查询
TreeMap提供了丰富的范围查询方法，如subMap、headMap、tailMap等。
public SortedMap<K,V> subMap(K fromKey, K toKey) {
return subMap(fromKey, true, toKey, false);
}
public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive) {
return new AscendingSubMap<>(this, false, fromKey, fromInclusive,
false, toKey, toInclusive);
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 9. WeakHashMap源码解析
# 9.1 弱引用概念
WeakHashMap的键是弱引用(WeakReference)，当键不再被强引用时，会被垃圾回收器回收，相应的条目也会被自动移除。
Java引用类型：
- 强引用(StrongReference)：普通的引用，只要存在就不会被GC回收。
- 软引用(SoftReference)：内存不足时会被GC回收。
- 弱引用(WeakReference)：GC运行时就会被回收。
- 虚引用(PhantomReference)：最弱的引用，主要用于跟踪对象被回收的状态。
# 9.2 内部结构
WeakHashMap内部使用数组+链表存储数据，键被包装成WeakReference。
public class WeakHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V> {
// 哈希表
Entry<K,V>[] table;
// 引用队列，用于存储被回收的键
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
// 条目继承自WeakReference，持有一个弱引用键
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
V value;
int hash;
Entry<K,V> next;
Entry(Object key, V value, ReferenceQueue<Object> queue,
int hash, Entry<K,V> next) {
super(key, queue); // 将key包装成弱引用
this.value = value;
this.hash = hash;
this.next = next;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 9.3 自动清理机制
WeakHashMap通过expungeStaleEntries方法清理被回收的键对应的条目。
private void expungeStaleEntries() {
for (Object x; (x = queue.poll()) != null; ) {
synchronized (queue) {
Entry<K,V> e = (Entry<K,V>) x;
int i = indexFor(e.hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> p = prev;
while (p != null) {
Entry<K,V> next = p.next;
if (p == e) {
if (prev == e)
table[i] = next;
else
prev.next = next;
e.value = null; // 帮助GC
size--;
break;
}
prev = p;
p = next;
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
在每次操作(如get、put、size)时，都会调用expungeStaleEntries方法清理无效条目。
使用示例
WeakHashMap<Object, String> map = new WeakHashMap<>();
Object key1 = new Object();
Object key2 = new Object();
map.put(key1, "value1");
map.put(key2, "value2");
System.out.println(map.size()); // 2
// 移除强引用
key1 = null;
System.gc(); // 建议GC，但不保证立即执行
// 等待GC完成
Thread.sleep(100);
System.out.println(map.size()); // 可能为1，key1被回收，对应条目被移除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
WeakHashMap适用场景：
- 缓存系统：当内存不足时，自动清理不再使用的缓存。
- 监听器列表：自动移除已被回收的监听器。
- 临时映射：不需要长期保持的映射关系。
注意事项
- 不要使用基本类型或字符串常量作为键：因为字符串常量池中的字符串有强引用，不会被回收。
- 弱引用只针对键：值对象仍然有强引用，需要手动置null或使用弱引用值。
- 性能影响：每次操作都需要清理无效条目，可能影响性能。
# 10. 总结
Java集合框架提供了丰富的数据结构，每种集合都有其特定的应用场景和实现原理：
- ArrayList：动态数组，适合随机访问，扩容机制是1.5倍增长。
- LinkedList：双向链表，适合频繁插入删除，实现了栈和队列接口。
- ArrayDeque：循环数组实现的双端队列，适合作为栈和队列。
- PriorityQueue：二叉堆实现，适合优先级调度。
- HashMap：数组+链表+红黑树，哈希表实现，性能优异。
- LinkedHashMap：在HashMap基础上维护双向链表，支持顺序遍历。
- TreeMap：红黑树实现，支持排序和范围查询。
- WeakHashMap：弱引用键，适合缓存等场景。
理解这些集合的内部实现和设计思想，有助于我们在实际开发中选择合适的数据结构，编写高效、健壮的代码。同时，集合框架中体现的算法思想(如分治、空间换时间、懒惰处理等)也值得我们学习和借鉴。
Reference:
Java 集合框架:https://www.pdai.tech/md/java/collection/java-collection-all.html