（二十一）Java集合框架源码深度解析

一、集合框架概述

Java集合框架(Java Collections Framework, JCF)是Java语言中用于存储和操作数据集合的一套标准架构。它提供了一组接口、实现类和算法，使开发者能够高效地处理各种数据结构。

1.1 集合框架的历史演变

在Java 1.2之前，Java只有几种简单的集合类：

• Vector

• Hashtable

• 数组

• Properties

这些早期集合类存在诸多问题：

• 命名不规范

• 方法命名不一致

• 缺乏统一的接口

• 性能不佳

Java 1.2引入了全新的集合框架，主要设计者为Joshua Bloch。这个新框架具有以下特点：

• 统一的接口层次结构

• 高性能实现

• 可扩展性

• 类型安全(通过泛型)

1.2 集合框架的核心接口

Java集合框架的核心接口构成了一个层次结构：

Iterable
└── Collection├── List├── Set│   └── SortedSet└── Queue└── Deque

此外还有独立的Map接口及其子接口SortedMap。

二、Collection接口解析

Collection接口是集合框架的根接口之一，定义了所有集合类共有的基本操作。

2.1 核心方法分析

java

public interface Collection<E> extends Iterable<E> {// 基本操作int size();boolean isEmpty();boolean contains(Object o);Iterator<E> iterator();Object[] toArray();<T> T[] toArray(T[] a);// 修改操作boolean add(E e);boolean remove(Object o);// 批量操作boolean containsAll(Collection<?> c);boolean addAll(Collection<? extends E> c);boolean removeAll(Collection<?> c);boolean retainAll(Collection<?> c);void clear();// 比较和哈希boolean equals(Object o);int hashCode();// JDK 8新增的默认方法default boolean removeIf(Predicate<? super E> filter) {Objects.requireNonNull(filter);boolean removed = false;final Iterator<E> each = iterator();while (each.hasNext()) {if (filter.test(each.next())) {each.remove();removed = true;}}return removed;}// 其他默认方法...
}

2.2 设计模式应用

Collection接口体现了多种设计模式：

1. 迭代器模式：通过iterator()方法提供遍历集合的标准方式

2. 模板方法模式：默认方法removeIf()提供了基于条件删除的通用实现

3. 策略模式：通过传递Predicate实现不同的删除策略

三、List接口及其实现

List代表有序集合（序列），允许重复元素和null值。

3.1 ArrayList源码分析

ArrayList是基于动态数组的实现，是List最常用的实现类。

3.1.1 核心字段

java

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable {// 默认初始容量private static final int DEFAULT_CAPACITY = 10;// 空数组实例，用于空实例private static final Object[] EMPTY_ELEMENTDATA = {};// 默认大小的空数组实例private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 存储ArrayList元素的数组缓冲区transient Object[] elementData;// ArrayList的大小（包含的元素数量）private int size;// 修改计数器，用于快速失败机制protected transient int modCount = 0;
}

3.1.2 扩容机制

ArrayList的核心扩容方法grow()：

java

private void grow(int minCapacity) {// 溢出安全的代码int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// 最小容量通常接近size，所以这是扩容操作elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容过程：

1. 计算新容量为旧容量的1.5倍

2. 检查是否满足最小容量要求

3. 检查是否超过最大数组大小限制

4. 使用Arrays.copyOf()创建新数组并复制元素

3.1.3 添加元素

java

public boolean add(E e) {modCount++;add(e, elementData, size);return true;
}private void add(E e, Object[] elementData, int s) {if (s == elementData.length)elementData = grow();elementData[s] = e;size = s + 1;
}

3.1.4 删除元素

java

public E remove(int index) {Objects.checkIndex(index, size);final Object[] es = elementData;@SuppressWarnings("unchecked") E oldValue = (E) es[index];fastRemove(es, index);return oldValue;
}private void fastRemove(Object[] es, int i) {modCount++;final int newSize;if ((newSize = size - 1) > i)System.arraycopy(es, i + 1, es, i, newSize - i);es[size = newSize] = null;
}

3.2 LinkedList源码分析

LinkedList是基于双向链表的实现，同时实现了List和Deque接口。

3.2.1 节点结构

java

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;}
}

3.2.2 核心字段

java

transient int size = 0;
transient Node<E> first; // 头节点
transient Node<E> last;  // 尾节点

3.2.3 添加元素

java

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;elsel.next = newNode;size++;modCount++;
}

3.2.4 删除元素

java

public E remove(int index) {checkElementIndex(index);return unlink(node(index));
}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;
}

3.3 Vector与ArrayList对比

Vector是线程安全的ArrayList，但性能较差。主要区别：

1. 同步机制：Vector所有方法都是同步的

2. 扩容策略：Vector默认增长一倍，ArrayList增长50%

3. 遗留类：Vector是Java 1.0的遗留类

四、Set接口及其实现

Set是不包含重复元素的集合，最多包含一个null元素。

4.1 HashSet源码分析

HashSet是基于HashMap的实现，使用对象的hashCode()和equals()方法来确保唯一性。

4.1.1 核心字段

java

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

4.1.2 构造方法

java

public HashSet() {map = new HashMap<>();
}public HashSet(int initialCapacity) {map = new HashMap<>(initialCapacity);
}

4.1.3 添加元素

java

public boolean add(E e) {return map.put(e, PRESENT)==null;
}

4.2 LinkedHashSet源码分析

LinkedHashSet继承自HashSet，但内部使用LinkedHashMap维护插入顺序。

4.2.1 构造方法

java

public LinkedHashSet(int initialCapacity) {super(initialCapacity, .75f, true);
}// HashSet中的特殊构造方法
HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

4.3 TreeSet源码分析

TreeSet是基于TreeMap的NavigableSet实现，元素按照自然顺序或Comparator排序。

4.3.1 核心字段

java

private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();

4.3.2 构造方法

java

public TreeSet() {this(new TreeMap<E,Object>());
}public TreeSet(Comparator<? super E> comparator) {this(new TreeMap<>(comparator));
}

五、Map接口及其实现

Map是键值对的集合，每个键最多映射到一个值。

5.1 HashMap源码分析

HashMap是基于哈希表的Map实现，允许null键和null值。

5.1.1 核心字段

java

// 默认初始容量 - 必须是2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;// 链表转红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;// 红黑树转链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;// 最小树化容量
static final int MIN_TREEIFY_CAPACITY = 64;// 哈希表
transient Node<K,V>[] table;// 键值对集合
transient Set<Map.Entry<K,V>> entrySet;// 元素数量
transient int size;// 修改计数器
transient int modCount;// 扩容阈值 (capacity * load factor)
int threshold;// 负载因子
final float loadFactor;

5.1.2 节点结构

java

static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;// 构造方法和其他实现...
}

5.1.3 哈希计算

java

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

5.1.4 put方法实现

java

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) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 替换值if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

5.1.5 扩容机制

java

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; // 双倍扩容}else if (oldThr > 0) // 初始容量设为阈值newCap = oldThr;else {               // 零初始阈值表示使用默认值newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})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;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;
}

5.2 LinkedHashMap源码分析

LinkedHashMap继承自HashMap，通过维护一个双向链表来保持插入顺序或访问顺序。

5.2.1 节点结构

java

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);}
}

5.2.2 核心字段

java

// 双向链表的头节点
transient LinkedHashMap.Entry<K,V> head;// 双向链表的尾节点
transient LinkedHashMap.Entry<K,V> tail;// 访问顺序(false=插入顺序, true=访问顺序)
final boolean accessOrder;

5.2.3 访问顺序维护

java

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;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;++modCount;}
}

5.3 TreeMap源码分析

TreeMap是基于红黑树的NavigableMap实现，按键的自然顺序或Comparator排序。

5.3.1 节点结构

java

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;// 构造方法和其他实现...
}

5.3.2 红黑树操作

TreeMap实现了完整的红黑树操作，包括旋转、插入平衡和删除平衡等。

六、并发集合类

Java还提供了一系列线程安全的集合类，位于java.util.concurrent包中。

6.1 ConcurrentHashMap

ConcurrentHashMap是线程安全的HashMap实现，采用分段锁技术(JDK 7)或CAS+synchronized(JDK 8)。

6.1.1 JDK 8实现改进

JDK 8的ConcurrentHashMap摒弃了分段锁，改用：

• CAS操作

• synchronized锁单个桶

• 更细粒度的并发控制

6.1.2 核心方法

java

public V put(K key, V value) {return putVal(key, value, false);
}final V putVal(K key, V value, boolean onlyIfAbsent) {if (key == null || value == null) throw new NullPointerException();int hash = spread(key.hashCode());int binCount = 0;for (Node<K,V>[] tab = table;;) {Node<K,V> f; int n, i, fh;if (tab == null || (n = tab.length) == 0)tab = initTable();else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))break;                   // no lock when adding to empty bin}else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f);else {V oldVal = null;synchronized (f) {if (tabAt(tab, i) == f) {if (fh >= 0) {binCount = 1;for (Node<K,V> e = f;; ++binCount) {K ek;if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {oldVal = e.val;if (!onlyIfAbsent)e.val = value;break;}Node<K,V> pred = e;if ((e = e.next) == null) {pred.next = new Node<K,V>(hash, key,value, null);break;}}}else if (f instanceof TreeBin) {Node<K,V> p;binCount = 2;if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,value)) != null) {oldVal = p.val;if (!onlyIfAbsent)p.val = value;}}}}if (binCount != 0) {if (binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);if (oldVal != null)return oldVal;break;}}}addCount(1L, binCount);return null;
}

6.2 CopyOnWriteArrayList

CopyOnWriteArrayList是线程安全的List实现，采用写时复制技术。

6.2.1 核心思想

• 读操作无锁

• 写操作复制底层数组

• 适用于读多写少的场景

6.2.2 添加元素

java

public boolean add(E e) {final ReentrantLock lock = this.lock;lock.lock();try {Object[] elements = getArray();int len = elements.length;Object[] newElements = Arrays.copyOf(elements, len + 1);newElements[len] = e;setArray(newElements);return true;} finally {lock.unlock();}
}

七、集合框架的性能比较

7.1 List实现性能比较

操作	ArrayList	LinkedList
get(int)	O(1)	O(n)
add(E)	O(1) 摊销	O(1)
add(int, E)	O(n)	O(1)
remove(int)	O(n)	O(1)
remove(E)	O(n)	O(n)

7.2 Set实现性能比较

操作	HashSet	LinkedHashSet	TreeSet
add(E)	O(1)	O(1)	O(log n)
contains(E)	O(1)	O(1)	O(log n)
remove(E)	O(1)	O(1)	O(log n)
迭代顺序	无	插入顺序	排序顺序

7.3 Map实现性能比较

操作	HashMap	LinkedHashMap	TreeMap
put(K,V)	O(1)	O(1)	O(log n)
get(K)	O(1)	O(1)	O(log n)
remove(K)	O(1)	O(1)	O(log n)
迭代顺序	无	插入/访问顺序	排序顺序

八、集合框架的最佳实践

1. 选择合适的集合类：

   • 需要快速随机访问：ArrayList

   • 频繁插入删除：LinkedList

   • 去重：HashSet

   • 键值对：HashMap

   • 排序：TreeSet/TreeMap

2. 初始化合适容量：

   • 对于已知大小的集合，指定初始容量避免扩容开销

   • ArrayList: new ArrayList(100)

   • HashMap: new HashMap(256, 0.75f)

3. 合理使用泛型：

   java

   // 好
   List<String> list = new ArrayList<>();// 不好
   List list = new ArrayList();

4. 遍历集合的选择：

   • 随机访问列表：for循环

   • 顺序访问列表：增强for循环或迭代器

   • 并行处理：Java 8 Stream API

5. 线程安全考虑：

   • 单线程：普通集合类

   • 多线程读多写少：CopyOnWriteArrayList

   • 高并发Map：ConcurrentHashMap

   • 同步包装：Collections.synchronizedXXX()

6. 避免在迭代中修改集合：

   • 使用迭代器的remove()方法

   • 或使用CopyOnWriteArrayList

7. 重写hashCode()和equals()：

   • 作为HashMap键或HashSet元素的类必须正确实现这两个方法

   • 遵循约定：相等对象必须有相同hashCode

8. 利用Java 8新特性：

   java

   map.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
   list.removeIf(e -> e == null);

九、常见问题与解决方案

9.1 集合与数组转换

java

// 集合转数组
List<String> list = new ArrayList<>();
String[] array = list.toArray(new String[0]);// 数组转集合
List<String> list = Arrays.asList(array); // 固定大小
List<String> list = new ArrayList<>(Arrays.asList(array)); // 可变

9.2 集合的不可变视图

java

List<String> immutableList = Collections.unmodifiableList(list);
Set<String> immutableSet = Collections.unmodifiableSet(set);
Map<K,V> immutableMap = Collections.unmodifiableMap(map);

9.3 空集合与单元素集合

java

List<String> emptyList = Collections.emptyList();
Set<String> singletonSet = Collections.singleton("item");
Map<String,String> singletonMap = Collections.singletonMap("key", "value");

9.4 集合排序

java

// 自然排序
Collections.sort(list);// 自定义排序
Collections.sort(list, (a, b) -> a.length() - b.length());// Java 8方式
list.sort(Comparator.comparing(String::length));

十、总结

Java集合框架是Java语言中最重要、最常用的API之一。通过深入理解其源码实现，我们可以：

1. 更高效地使用集合类

2. 根据场景选择最合适的实现

3. 避免常见的陷阱和性能问题

4. 编写更健壮、更高效的代码

从设计角度看，集合框架体现了多种优秀的设计原则和模式：

• 接口与实现分离

• 算法与数据结构分离

• 迭代器模式

• 策略模式

• 模板方法模式

随着Java版本的演进，集合框架也在不断优化和改进，如Java 8引入的Stream API和Lambda表达式使集合操作更加简洁和强大。作为Java开发者，深入理解集合框架的内部机制是提升编程能力的重要一步。