highlight: agate
《向 JDK 学设计》系列第 1 篇，本系列会涉及一小部分源码，简单看看就行，重要的是学习源码背后的设计思想，然后运用到实际开发中
前言
Java 开发离不开 JDK，JDK 本身经过了精心的设计，具有出色的性能，并且支持向下兼容。可以说 JDK 是 Java 软件工程师的第一手学习资料，其中设计思想值得学习和借鉴
集合框架在日常开发中会频繁使用，这篇文章会探索集合框架中的设计原则与设计模式
Collection 接口
JDK1.2 引入了集合框架，由 Joshua Bloch 主导设计，集合框架的顶层设计是 Collection 接口，最核心的两个子接口为 List 和 Set。Map 接口虽然也是集合框架的一部分，但不是 Collection 的子接口
顶层设计
Collection 接口的核心子接口有 3 个，如下图所示
classDiagram
direction LR
class Iterable
class Collection~E~
class List~E~
class Set~E~
class Queue~E~
<<interface>> Iterable
<<interface>> Collection
<<interface>> List
<<interface>> Set
<<interface>> Queue
Iterable <|-- Collection
Collection <|-- List
Collection <|-- Set
Collection <|-- Queue
Collection 通用方法声明如下，其中 List 和 Set 也声明了 Collection 中的这些方法。其中不包含 Java 8 及以上的方法声明
classDiagram
class Collection~E~ {
+size() int
+isEmpty() boolean
+contains() boolean
+containsAll(Collection<?> c)
+iterator() Iterator
+toArray() Object[]
+toArray(T[] a) T[]
+add(E e) boolean
+addAll(Collection<? extends E> c)
+remove(Object o) boolean
+removeAll(Collection<?> c)
+retainAll(Collection<?> c)
+clear() void
}
class List~E~ {
+add(int index, E e) void
+set(int index, E e) E
+get(int index) E
+indexOf(E e) int
+lastIndexOf(E e) int
}
class Set~E~
class Queue~E~ {
+offer(E e) boolean
+poll() E
+peek() E
+element() E
}
<<interface>> Collection
<<interface>> List
<<interface>> Set
<<interface>> Queue
Collection <|-- List
Collection <|-- Set
Collection <|-- Queue
Java 中的集合与数学中的集合是相同的概念，数学中的集合具有互异性和无序性，和 Java 中的 Set 接口的特性相同
List 接口是列表的抽象，元素可重复，并且有序，因此方法声明中有一些带下标参数的方法
Queue 接口是队列的抽象，支持在队头进行操作，因此有一些特殊的方法声明
类图
首先看一下最常用的 ArrayList 和 HashSet 的体系结构
classDiagram
class Collection~E~
class List~E~
class Set~E~
class AbstractCollection~E~
class AbstractList~E~
class AbstractSet~E~
class ArrayList~E~
class HashSet~E~
<<interface>> Collection
<<interface>> List
<<interface>> Set
<<abstract>> AbstractCollection
<<abstract>> AbstractList
<<abstract>> AbstractSet
Collection <|-- List
Collection <|.. AbstractCollection
AbstractCollection <|-- AbstractList
List <|.. ArrayList
AbstractList <|-- ArrayList
AbstractCollection <|-- AbstractSet
Collection <|-- Set
Set <|.. HashSet
AbstractSet <|-- HashSet
可以看到，ArrayList 并不是直接实现的 Collection 接口，而是实现 List 接口，并且继承了 AbstractList 抽象类，AbstractList 又继承了 AbstractCollection 抽象类
同样 HashSet 实现 Set 接口，并且继承 AbstractSet 抽象类，AbstractSet 抽象类又继承了 AbstractCollection 抽象类
AbstractCollection 抽象类中有一些集合通用的实现，有如下方法
boolean contains(Object o)boolean containsAll(Collection<?> c)Object[] toArray()T[] toArray(T[] a)T[] finishToArray(T[] r, Iterator<?> it)addAll(Collection<? extends E> c)boolean remove(Object o)boolean removeAll(Collection<?> c)boolean retainAll(Collection<?> c)void clear()
以下是更详细的体系结构。对于 List 接口，只展示了常用的实现类 ArrayList 和 LinkedList。对于 Set 接口，只展示了常用的实现类 HashSet 和 TreeSet
classDiagram
class Collection
class AbstractCollection
class Queue
class Deque
class List
class AbstractList
class AbstractSequentialList
class ArrayList
class LinkedList
class Set
class AbstractSet
class HashSet
class SortedSet {
+comparator() Comparator
}
class NavigableSet
class TreeSet
<<interface>> Collection
<<interface>> List
<<interface>> Queue
<<interface>> Deque
<<interface>> Set
<<interface>> SortedSet
<<interface>> NavigableSet
<<abstract>> AbstractCollection
<<abstract>> AbstractList
<<abstract>> AbstractSet
<<abstract>> AbstractSequentialList
Collection <|-- List
List <|.. ArrayList
AbstractList <|-- ArrayList
AbstractList <|-- AbstractSequentialList
Collection <|.. AbstractCollection
AbstractCollection <|-- AbstractList
AbstractCollection <|-- AbstractSet
Collection <|-- Queue
Queue <|-- Deque
Deque <|.. LinkedList
AbstractSequentialList <|-- LinkedList
Collection <|-- Set
AbstractSet <|-- HashSet
Set <|.. HashSet
Set <|-- SortedSet
SortedSet <|-- NavigableSet
AbstractSet <|-- TreeSet
NavigableSet <|.. TreeSet
Map 架构
顶层设计
与 Map 接口相关的几个接口
classDiagram
class Map~K, V~
class SortedMap~K, V~
class NavigableMap~K, V~
<<interface>> Map
<<interface>> SortedMap
<<interface>> NavigableMap
Map <|-- SortedMap
SortedMap <|-- NavigableMap
类图
Map 接口的常用实现类如下
classDiagram
class Map~K, V~
class SortedMap~K, V~
class NavigableMap~K, V~
class AbstractMap~K, V~
class HashMap~K, V~
class TreeMap~K, V~
class WeakHashMap~K, V~
class LinkedHashMap~K, V~
class EnumMap~K, V~
class IdentityHashMap~K, V~
class Dictionary~K, V~
class HashTable~K, V~
<<interface>> Map
<<interface>> SortedMap
<<interface>> NavigableMap
<<abstract>> AbstractMap
<<abstract>> Dictionary
Map <|-- SortedMap
SortedMap <|-- NavigableMap
Map <|.. AbstractMap
AbstractMap <|-- HashMap
NavigableMap <|.. TreeMap
AbstractMap <|-- TreeMap
HashMap <|-- LinkedHashMap
AbstractMap <|-- EnumMap
AbstractMap <|-- WeakHashMap
AbstractMap <|-- IdentityHashMap
Map <|.. HashTable
Dictionary <|-- HashTable
Set 与 Map 的关系
HashSet 基于 HashMap 实现
classDiagram
class Collection
class Set~E~
class Map~K, V~
class HashSet~E~ {
- HashMap<E, Object> map
}
class HashMap~K, V~
<<interface>> Collection
<<interface>> Set
<<interface>> Map
Collection <|-- Set
Set <|.. HashSet
Map <|.. HashMap
HashSet *-- HashMap
HashSet 中使用组合关系关联了 HashMap，并且加上了 transient 修饰符，防止直接序列化 HashMap 对象，并且改写了序列化逻辑，只序列化 keySet
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
private transient HashMap<E, Object> map;
// HashSet 内部 HashMap 的所有 value 的共享变量
private static final Object PRESENT = new Object();
// ...
}
TreeSet 基于 TreeMap 实现
classDiagram
class Set~E~
class SortedSet~E~
class NavigableSet~E~
class Map~K, V~
class TreeSet~E~ {
- NavigableMap<E, Object> m
}
class TreeMap~K, V~
<<interface>> Set
<<interface>> SortedSet
<<interface>> NavigableSet
<<interface>> Map
Set <|-- SortedSet
SortedSet <|-- NavigableSet
NavigableSet <|.. TreeSet
Map <|.. TreeMap
TreeSet *-- TreeMap
TreeSet 中使用组合关系关联了 NavigableMap，一般是 TreeMap 实例，并且加上了 transient 修饰符，防止直接序列化 NavigableMap 实例对象，并且改写了序列化逻辑，只序列化 keySet
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
private transient NavigableMap<E, Object> m;
// TreeSet 内部 NavigableMap 的所有 value 的共享变量
private static final Object PRESENT = new Object();
// ...
}
集合框架中的设计规范
使用接口定义类型
前面已经分析过，Collection 接口的核心子接口有 3 个。对于 Set 接口，又定义了 SortedSet 和 NavigableSet 接口。优先使用接口定义类型，因为 Java 只支持单继承，但可以实现多个接口，使用接口定义类型更灵活
在接口的方法声明中，也是用接口定义方法参数，这让代码更灵活、可维护、易于扩展
巧用方法重载
Java 支持方法重载，可以声明多个不同参数列表的同名方法。当调用这些方法时，编译器会根据提供的参数类型和数量来确定应该调用哪个方法。这使得代码更加灵活和易于理解。此外，可以增加易用性
从 Java 8 开始，接口支持默认方法，从 Java 9 开始，集合框架的上层接口中增加了很多重载的 of 方法，以 List 为例
public interface List<E> extends Collection<E> {
static <E> List<E> of() {
return (List<E>) ImmutableCollections.EMPTY_LIST;
}
static <E> List<E> of(E e1) {
return new ImmutableCollections.List12<>(e1);
}
static <E> List<E> of(E e1, E e2) {
return new ImmutableCollections.List12<>(e1, e2);
}
static <E> List<E> of(E e1, E e2, E e3) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3);
}
static <E> List<E> of(E e1, E e2, E e3, E e4) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4);
}
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5);
}
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5, e6);
}
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5, e6, e7);
}
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5, e6, e7, e8);
}
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5, e6, e7, e8, e9);
}
static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) {
return ImmutableCollections.listFromTrustedArray(e1, e2, e3, e4, e5, e6, e7, e8, e9, e10);
}
static <E> List<E> of(E... elements) {
switch (elements.length) {
case 0:
@SuppressWarnings("unchecked")
var list = (List<E>) ImmutableCollections.EMPTY_LIST;
return list;
case 1:
return new ImmutableCollections.List12<>(elements[0]);
case 2:
return new ImmutableCollections.List12<>(elements[0], elements[1]);
default:
return ImmutableCollections.listFromArray(elements);
}
}
// ...
}
同样的，在 Set 和 Map 中也定义了很多 of 重载方法。这对于创建元素个数比较少的不可变集合非常方便
public static void main(String[] args) {
List<Integer> lists = List.of(1, 2, 3);
Set<Integer> sets = Set.of(1, 2, 3);
Map<Integer, Integer> maps = Map.of(1, 2, 3, 4);
}
复用
前面已经提到，Set 的实现类是基于 Map 实现类实现的，这体现了复用的思想，极大减少了重复代码
Set 和 Map 的 key 都不包含重复元素，并且无序，Map 底层数据结构中仅仅是多了 value，那么 Set 就只需要把不关注的 value 特殊处理一下，都指向一个单实例对象，避免占用额外的内存空间
不可变类
在 Java 中，设计不可变类的主要目的是创建后对象就不能被修改。这样设计有很多优点，比如线程安全。此外，不可变类可以更好地复用
集合框架中设计不可变集合的方法很简单，就是重写将所有会修改集合的方法，都抛出异常
class ImmutableCollections {
static UnsupportedOperationException uoe() { return new UnsupportedOperationException(); }
static abstract class AbstractImmutableCollection<E> extends AbstractCollection<E> {
// all mutating methods throw UnsupportedOperationException
@Override public boolean add(E e) { throw uoe(); }
@Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
@Override public void clear() { throw uoe(); }
@Override public boolean remove(Object o) { throw uoe(); }
@Override public boolean removeAll(Collection<?> c) { throw uoe(); }
@Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
@Override public boolean retainAll(Collection<?> c) { throw uoe(); }
}
// ...
}
工具类设计
对于工具类，一般以复数形式命名，将无参构造方法私有化，对外暴露的工具方法声明为静态方法，方便通过 ClassName.methodName 直接调用
public class Collections {
// 禁止实例化
private Collections() {}
public static void swap(List<?> list, int i, int j) {
final List l = list;
l.set(i, l.set(j, l.get(i)));
}
// 省略其他方法
}
集合框架中的设计模式
单例模式
示例 1
HashSet 是用 HashMap 来实现的，Map 是键值对的结构，而 Set 只需要用到其中的 key，值是什么不重要。因此 HashSet 定义了一个 Object 类型的单例 PRESENT，作为所有值的共享变量
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
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;
}
// ...
}
示例 2
在集合中，空集是一个特殊的集合，有许多应用场景，Collections 工具类中提供了如下方法返回空集合
public class Collections {
public static final List EMPTY_LIST = new EmptyList<>();
public static final <T> List<T> emptyList() {
return (List<T>) EMPTY_LIST;
}
private static class EmptyList<E>
extends AbstractList<E>
implements RandomAccess, Serializable {
// ...
}
// ...
}
Collections 内部定义了 EmptyList，然后使用静态初始化的方式初始化了 EMPTY_LIST，这里使用了单例模式，外部通过 Collections.EMPTY_LIST 或者 Collections.emptyList() 时，都指向内存中的同一个 EmptyList 实例
类似地，Collections 中还定义了 EmptyIterator, EmptyListIterator, EmptyEnumeration, EmptySet, EmptyMap 内部类，可以作为单例使用
使用时需要注意，这些集合是不可修改的，不支持增、删、改操作
模板方法模式
模板方法模式是一种行为型设计模式，它定义了一个操作中的算法骨架，而将一些步骤延迟到子类中实现。这使得子类可以在不改变算法结构的前提下，重新定义算法的某些特定步骤
在集合框架中模板方法模式的使用场景很多，如 contains(Object o) 方法
public abstract class AbstractCollection<E> implements Collection<E> {
// 声明钩子方法
public abstract Iterator<E> iterator();
/**
* 子类可以重写 contains 方法，因此也可以将 Collection 中的声明看作钩子方法
*/
public boolean contains(Object o) {
// 在模板方法中使用钩子方法
Iterator<E> it = iterator();
// 模板方法的其他骨架
if (o==null) {
while (it.hasNext())
if (it.next()==null)
return true;
} else {
while (it.hasNext())
if (o.equals(it.next()))
return true;
}
return false;
}
// 模板方法
public boolean containsAll(Collection<?> c) {
for (Object e : c)
// 在模板方法中使用钩子方法
if (!contains(e))
return false;
return true;
}
// ...
}
在 AbstractCollection 抽象类中定义了 contains(Object o) 方法的基本骨架，以及抽象钩子方法 iterator()，钩子方法需要在子类中实现
由于 JDK 中 List 和 Set 接口的实现类都重写了 contains(Object o) 方法，因此可以将 contains(Object o) 视为钩子方法
ArrayList 中 contains(Object o) 的实现如下
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
// ...
}
HashSet 中 contains(Object o) 的实现如下
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
private transient HashMap<E, Object> map;
public boolean contains(Object o) {
return map.containsKey(o);
}
// ...
}
ArrayList 和 HashSet 的实例可以调用 containsAll 方法判断是否包含某个集合的全部元素
装饰器模式
装饰器模式是一种结构型模式，可以在不改变原有对象的基础上，动态地给对象添加一些职责或功能
示例 1
ArrayList 是线程不安全的，在 JDK1.2 以前，如果想使用线程安全的有序集合，可以使用 Vector。但 JDK1.2 提供的 Collections 工具类提供了 synchronizedList(List<T> list) 方法，可以将 List 子类对象包装为线程安全的类 SynchronizedList
public class Collections {
public static <T> List<T> synchronizedList(List<T> list) {
return (list instanceof RandomAccess ?
new SynchronizedRandomAccessList<>(list) :
new SynchronizedList<>(list));
}
static class SynchronizedList<E>
extends SynchronizedCollection<E>
implements List<E> {
final List<E> list;
SynchronizedList(List<E> list) {
super(list);
this.list = list;
}
SynchronizedList(List<E> list, Object mutex) {
super(list, mutex);
this.list = list;
}
public E get(int index) {
synchronized (mutex) {
return list.get(index);
}
}
public E set(int index, E element) {
synchronized (mutex) {
return list.set(index, element);
}
}
// ...
}
// ...
}
抽象包装器 SynchronizedCollection 中包含互斥锁 mutex，默认的互斥锁为 Collection 实现类对应的类对象，可以通过参数传入自定义的互斥锁。在具体装饰器中，调用被装饰的方法之前，使用了 synchronized 关键字，需要获取到互斥锁才能进行操作
类似的具体装饰器还有 SynchronizedSet, SynchronizedMap 等
示例 2
Collections 工具类中还有一类装饰器，可以对 Collection 的实现类进行装饰，变成不可变集合
public class Collections {
public static <T> List<T> unmodifiableList(List<? extends T> list) {
if (list.getClass() == UnmodifiableList.class || list.getClass() == UnmodifiableRandomAccessList.class) {
return (List<T>) list;
}
return (list instanceof RandomAccess ?
new UnmodifiableRandomAccessList<>(list) :
new UnmodifiableList<>(list));
}
static class UnmodifiableList<E> extends UnmodifiableCollection<E>
implements List<E> {
public E set(int index, E element) {
throw new UnsupportedOperationException();
}
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
public E remove(int index) {
throw new UnsupportedOperationException();
}
// ...
}
// ...
}
UnmodifiableList 装饰器重写了那些修改集合的方法，抛出异常，实现了不可变的特性
总结
本文介绍了集合框架的顶层设计与其中优秀的设计思想，但这些只是很小的一部分。我们在实际开发中，也应该多思考、多学习，写出更优雅的代码