“阅读本文大约需要 5 分钟
阅读源码是提升编程能力的一项基础技能，但是很多初学者在阅读源码过程中不得其法，往往花费了大量的时间却没有收到预期的效果。或者在阅读过程中无法了解作者的意图，白白错失了学习的机会，因此我希望借助这个系列，通过解读 Java Collections Framework 的源码，给大家归纳 Java Collections Framework 相关知识的同时也分享一些自己阅读源码的技巧
对于 Java 开发者而言，现今是个幸福的时代，开源文化的盛行让大家对于很多项目的源码可谓唾手可得。而十几年来 Java 技术体系的稳步发展，积累了许许多多基于 Java 语言的优秀开源框架。然而基础对于软件工程师的成长更为重要，在想深入某个框架之前，不如让我们把眼光转向 JDK 自带的源码中，来学习一些基础但是格外重要的知识。
要想成为一个合格的 Java 程序员，至少有两个框架的知识和源码是需要熟练掌握的，即 Java Collections Framework 和 Java Concurrency Framework，这个系列会带着大家分析 Collections Framework 的源码，从浅入深，抽丝剥茧的讲述相关知识。
本系列分析的源码以 OpenJDK 11 为主，希望每个读者可以在本机下载相关的源码，在看完每篇文章后再自己仔细的阅读相关的代码，并做好笔记。
概述
Java 是一门面向对象的语言，在使用中往往会采用继承，Delegate，组合等多种手法，或者是各种设计模式。因此一开始阅读源码时容易在复杂的类层次以及调用关系中迷失，所以在一开始建议大家先看一下总体的类图结构，了解大致的继承体系，并进一步找出几个核心的接口和实现类。而在阅读源码之前最好看看框架的文档，并手动写一些简单的实例代码，对框架的功能有一个大致的了解。下面是 Java Collections Framework 的类图:
来源: https://www.scientecheasy.com/2018/09/collection-hierarchy-in-java.html
从类图上来看 Java Collections Framework 分为两大部分，提供集合类操作接口的 Collection，和提供 Key-Value 接口访问的 Map。Collection 接口衍生了如下 3 大类型的数据结构:
提供随机访问，允许重复元素，有序的集合类型 List 及相关子类
提供一些特殊操作，例如 pop, push, peek 的 Queue 类型及其子类
不允许重复元素的集合类型 Set 及其子类
之后的文章会按照这个分类进行相关源码的分析，本篇则会分析上层的 Collection 的相关接口。
Iterator, Collection
在开始阅读代码之前，比较好的习惯是先看一下源码的注释。特别是 JDK 的源码，自带的注释是非常详细且有价值的，在注释中不仅解释了当前类或是接口作用和设计意图，还描述了相关 API 使用的注意事项等，对于理解源码是很有帮助的。
先来看一下 Collection 的注释和方法签名。Collection 代表了一系列元素的集合，作为它的具体实现，可以是各种不同的数据结构类型，也就是我们之前提到的 List, Queue, Set等类型。同时一个 Collection 类型的数据类型必须是「可迭代」的，即实现了 Iterable接口，Iterable接口最重要的方法是 iterator()，即返回一个 Iterator对象。Iterator对象上重要的方法分别为 hasNext(), next(), remove()，有一定经验的开发人员在 JDK8 之前的编程中应该都有使用过这个接口及其相关的方法。
从注释中我们还可以知道，Collection 的相关接口并没有保证线程安全性，需要开发人员显式的添加各种机制来保证多线程下的数据一致性。
再来看一下 Collection 的各个方法签名，都比较容易理解，大家应该在日常开发中都有用过，就不在这里赘述了。
AbstractCollection
为了方便开发人员实现自定义的集合类型数据结构，JDK 提供了一个对于 Collection 接口的抽象类实现: AbstractCollection ，对实现了部分 Collection方法的实现。
从注释上来看，有几点是值得注意的。如果需要实现一个不可修改的(unmodifiable)的类型，那只需要实现 size()和 iterator()方法即可。如果需要实现一个可修改的的类型，则需要额外实现 add()和 迭代器的 remove()方法。
从结构来看 AbstractCollection 采用了 Template Pattern，即「模版模式」，通过实现某些抽象方法的来控制具体的行为。同时在实现的方法方面，基本都是通过迭代器实现的，从而避免了耦合到具体的实现，参考如下代码:
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 remove(Object o) {
Iterator<E> it = iterator();
if (o==null) {
while (it.hasNext()) {
if (it.next()==null) {
it.remove();
return true;
}
}
} else {
while (it.hasNext()) {
if (o.equals(it.next())) {
it.remove();
return true;
}
}
}
return false;
}
其中比较有意思的方法是 toArray(T[] a)这个方法，先看下源码。
public <T> T[] toArray(T[] a) {
/// Estimate size of array; be prepared to see more or fewer elements/
int size = size();
T[] r = a.length >= size ? a :
(T[])java.lang.reflect.Array
.newInstance(a.getClass().getComponentType(), size);
Iterator<E> it = iterator();
for (int i = 0; i < r.length; i++) {
if (! it.hasNext()) { /// fewer elements than expected/
if (a == r) {
r[i] = null; /// null-terminate/
} else if (a.length < i) {
return Arrays.copyOf(r, i);
} else {
System.arraycopy(r, 0, a, 0, i);
if (a.length > i) {
a[i] = null;
}
}
return a;
}
r[i] = (T)it.next();
}
/// more elements than expected/
return it.hasNext() ? finishToArray(r, it) : r;
}
for 循环的段逻辑较为容易理解，即当数组的长度大于集合数据类型长度时，会将额外部分用 null 来填充。需要注意的情况是当集合数据类型长度大于数组长度时的处理方法。关键的方法是 finishToArray方法。
@SuppressWarnings("unchecked")
private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
int i = r.length;
while (it.hasNext()) {
int cap = r.length;
if (i == cap) {
int newCap = cap + (cap >> 1) + 1;
/// overflow-conscious code/
if (newCap - MAX_ARRAY_SIZE > 0)
newCap = hugeCapacity(cap + 1);
r = Arrays.copyOf(r, newCap);
}
r[i++] = (T)it.next();
}
/// trim if overallocated/
return (i == r.length) ? r : Arrays.copyOf(r, i);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) /// overflow/
throw new OutOfMemoryError
("Required array size too large");
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
可以看到当数据长度小的时候，会按照一定的逻辑进行扩容，有个值得注意的技巧是位运算，即这行代码 int newCap = cap + (cap >> 1) + 1每次会按照自身大小的 1/2 进行扩容，每次左移 1 位，等于除以 2，而除法运算的时间大于位移操作的消耗。这些位移技巧非常实用，在 JDK 中也比较常见，大家需要了解并熟悉。
而在数组扩容扩容的时候会调用一个 hugeCapacity()的方法，这个方法的逻辑也很简单，首先会考虑是否溢出的情况，这在系统编程时是个很好的习惯，其次检查了 MAX_ARRAY_SIZE这个常量，可以看到这个值的默认大小是 Integer.MAX_VALUE减去 8 ，具体的原因在注释里提及了，某些 JVM 的实现中数组对象可能会存放一些字头，因此需要预留一些空间。
其他的方法都较为简单，大家可以耐心阅读一下，应该很容易理解，就不赘述了。
小结/预告
本篇总体介绍了 Java Collections Framework 中类的层级关系，并着重介绍了 Collection, AbstractCollection两个类，并分析了几个核心的方法。下一篇我们会分析大家在日常编程中使用率最高的数据结构 **List** 和它的子类，如果大家有什么意见也可以联系我们的个人号，下期见！
15年从业经验，不仅在国内著名的大型金融集团做过甲方，担任高级系统架构专家角色，也在第一梯队的互联网公司金融部门做过数据智能相关工作。
也曾任职于大型系统集成商，负责保险，银行核心系统的落地和实施，也在创业团队从0到1研发产品，在业界获得很高的占有量。
如果感兴趣可以加我公众号，搜索“且把金针度与人”或个人微信
网友评论