Java Collections Framework 源码分析（1-总起）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?“阅读本文大约需要 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对象。*terator对象上重要的方法分别为?hasNext(),?next(),?remove()，有肯定经验的开发人员在 JDK8 之前的编程中应该都有使用过这个接口及其相关的方法。

从注释中我们还可以知道，Collection 的相关接口并没有保证线程安全性，需要开发人员显式的增加各种机制来保证多线程下的数据一致性。

再来看一下 Collection 的各个方法签名，都比较容易了解，大家应该在日常开发中都有用过，就不在这里赘述了。

AbstractCollection

为了方便开发人员实现自己设置的集合类型数据结构，JDK 提供了一个对于 Collection 接口的笼统类实现:?AbstractCollection?，对实现了部分?Collection方法的实现。

从注释上来看，有几点是值得注意的。假如需要实现一个不可修改的(unmodifiable)的类型，那只要要实现?size()和?iterator()方法就可。假如需要实现一个可修改的的类型，则需要额外实现?add()和 迭代器的?remove()方法。

从结构来看?AbstractCollection?采用了?Template Pattern，即「模版模式」，通过实现某些笼统方法的来控制具体的行为。同时在实现的方法方面，基本都是通过迭代器实现的，从而避免了耦合到具体的实现，参考如下代码:

其中比较有意思的方法是?toArray(T[] a)这个方法，先看下源码。

for 循环的段逻辑较为容易了解，即当数组的长度大于集合数据类型长度时，会将额外部分用 null 来填充。需要注意的情况是当集合数据类型长度大于数组长度时的解决方法。关键的方法是?finishToArray方法。

可以看到当数据长度小的时候，会按照肯定的逻辑进行扩容，有个值得注意的技巧是位运算，即这行代码?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** 和它的子类，假如大家有什么意见也可以联络我们的个人号，下期见！

假如感兴趣可以加我公众号，搜索“且把金针度与人”或者个人微信