转载

Java集合源码分析之开篇

Java集合是我们使用最频繁的工具，也是面试的热点，但我们对它的理解仅限于使用上，而且大多数情况没有考虑过其使用规范。本系列文章将跟随源码的思路，分析实现的每个细节，以期在使用时避免各种不规范的坑。在这里，我们会惊艳于开发者优秀的设计，也会感激先辈们付出的艰辛努力，更重要的是知其所以然，少犯错误，写出优秀的代码。

许多人对集合类的理解是暴力的，当需要保存对象时就使用 ArrayList ，当需要保存键值对时就使用 HashMap ，当需要不可重复时就使用 HashSet ，等等。而且使用方式也比较单一：

List<String> list = new ArrayList<>();

Map<String, String> map = new HashMap<>();

Set<String> set = new HashSet<>();

// ...

这里我们先不考虑多线程安全问题，这个问题通常有专门的类实现，或者可以通过 Collections.synchronizedXXX 方法解决。除此之外，我们真的可以如此简单的使用集合吗？

假如数据只有几百、几千个，那么使用何种方式实现差别并不大。但当我们需要处理大数量级的数据时，采用不同的方式效率可能相差百倍甚至更多，这种情况下性能将变得格外重要。例如分别存储于 ArrayList 和 LinkedList 的100万条数据，要获取位于位置 i 的元素，前者可以瞬间完成，后者则可能需要数秒。这时，使用哪个集合类，怎样合理使用就是我们必须掌握的技能了。

为什么要读本系列文章

如果你也像以上这般使用集合，或者不知道如何优化集合的使用，你都应该读本系列文章。如果你仅有一些点不清晰，也可以在这里找到答案。或者你只是不想阅读枯燥的源码，却对原理很好奇，你也可以阅读本系列文章。如果你只是想应付面试，我想当你坚持把这些文章读完后，你会觉得面试好像也不那么重要了。

本系列文章立足于深刻理解Java集合的原理与实现，读完这些文章后你将获得以下知识：

大量的数据结构知识。
ArrayList有那么多构造函数，使用不同的构造函数会有区别吗？
ArrayList是如何扩容的？
LinkedList如何提供通过位置获取数据的功能的，它的查询效率真的非常低吗？
用数组可以实现队列吗？
影响HashMap性能的因素有哪些？
复杂的红黑树是如何实现的？
LRUCache的底层原理是什么？
……

基础知识概述

对数据的操作，大抵就是增、删、改、查，以及在某些时候根据位置获取数据，有时可能还需要进行排序。改和查又可以理解为一致的操作，因为要修改一条数据需要先找到它，然后替换即可。接下来我们就从增、删、查这三点简要分析下当前使用比较广泛的几种数据结构。

数组

数组在内存中占据一段连续的内存，所有的数据在内存中连续排列。它的大小是固定的，这一特性使得数组对于插入操作并不友好，我们分析 ArrayList 时就会看到这种操作的复杂。但数组对于位置的访问是极其友好的，它支持所谓 RandomAccess 特性，这使得基于位置的操作可以迅速完成，其时间复杂度为 O(1) 。数组的数据顺序与插入顺序一致，所以查询操作需要遍历，其时间复杂度为 O(n) 。

所以数组最大的优势在于基于位置的访问，在扩展性方面表现无力。

链表

不同于数组，链表是通过指针域来表示数据与数据之间的位置关系的，所以链表在头部或尾部插入数据的复杂度仅为 O(1) 。链表不具备 RandomAccess 特性，所以无法提供基于位置的访问。其查询操作也必须从从到尾遍历，复杂度为 O(n) 。

所以链表最大的优势在于插入，而查询的表现很一般。

那有没有一种结构能够结合数组和链表的优点，使得查询和插入都具有优秀的表现呢？答案是肯定的，这就是散列表。

散列表

散列表就是 Hash Table ，这种结构使用 key-value 形式存储数据，我们经常使用的 HashMap 、 HashTable 就基于它。

数组和链表在查询时表现一般的原因在于它们并不记得数据的位置，所以只能用待查询的数据和存储的数据依次比对。散列表使用一种巧妙的方式来减少甚至避免这种依次比对，它的原理是通过一个函数把任何的 key 转为 int ，每次查找时只需要执行一次这个函数便可以迅速定位。这个过程是不是像查字典呢？

散列表并不像上述那般完美，因为并不会有一个函数，能够保证所有的 key 转换结果都不同，也就是会发生所谓的 哈希碰撞 ，而且它必须依赖于其他的数据结构，这部分知识会在后续文章中详细介绍。

良好设计的散列表可以使增、删、查等操作的时间复杂度均为 O(1) 。

二叉排序树

二叉排序树是解决查询问题的另一方案，如果数据在插入时是有序的，在查询时就可以使用 二分法 。 二分法 的原理很简单，比如猜一个在0-100之间的数，第一次猜50就可以直接排除一半的数据，每次按照这个规则就可以很快的获取正确答案。 二分法 的时间复杂度为 O(lg n) 。

树的结构对二分法有天然的支持（但这不是树最重要的用途）。二叉排序树牺牲了一部分插入的时间，但提高了查询的速度，同时有序的数据也可以做些其他的操作。如果查询的操作重要性超过了插入，我们应该考虑这种结构。二叉排序树也存在一些不平衡导致效率下降的问题，所以有了 AVL树 、 红黑树 ，以及用于数据库索引的 B树、 B+树 等概念，关于二叉排序树的知识也会在后续文章中介绍。

分析过程

以上介绍的数据结构的知识是我们理解Java集合类的基础，掌握这些核心原理，我们分析集合类源码时才不会吃力，我们会先对这些数据结构进行简要介绍，其他和本系列文章无关的概念不会涉及，大家可以查阅相关专业书籍进行系统学习。

由于集合类的源码十分庞大，从接口抽象设计到具体实现涉及到数十个类，我们不可能每行代码都进行分析，一些在前面分析过的点在后续部分也会略过，但对于我们应该注意的点都会详细解读。有一些过于复杂的代码，还会用图示进行直观的演示，以帮助理解整个运行机制。

文章中会不可避免地粘贴大量源码，但所有部分都会加上详细的中文注释。另外，粘贴的代码不会截取（某些没必要的会删除），这样便于理解，而不用想看哪行代码再去源码中寻找了。

学习源码的实现仅是我们的目的之一，我们更应该掌握作者优秀的编程思想，理解这样做的初衷，站在更高的角度思考问题。

本系列文章的源码全部基于 JDK1.8 ，不同版本的实现代码可能稍有差别，但核心思想是一致的，希望大家不要被具体的实现带偏了路。

Java集合类分为两大部分： Collection 和 Map 。 Collection 又主要由 List 、 Queue 和 Set 三大模块组成。本系列文章也会基于这样的结构进行，我们会先了解一些用到的数据结构，然后按照从接口抽象到具体实现的顺序来一步步揭开集合的神秘面纱。

由于 Set 的结构与 Map 完全一致，且 Set 的内部都是基于对应的 Map 实现的，所以只需要知道 Set 是什么即可，其具体实现如果感兴趣可以自行阅读源码。

本系列文章不考虑多线程安全问题，与多线程相关的问题十分复杂，以后会对它专门研究。

本系列文章长达20多篇，全部读完需要一定的耐心，但是我相信读完对数据结构和集合一定会有更深的理解，在使用时需要注意哪些点也一定会胸有成竹。