Java集合源码分析之开篇

综合编程 2018-05-16 阅读原文

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

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

List list = new ArrayList();

Map map = new HashMap();

Set 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多篇,全部读完需要一定的耐心,但是我相信读完对数据结构和集合一定会有更深的理解,在使用时需要注意哪些点也一定会胸有成竹。

另外由于个人能力有限,文章中若有表达不清晰或解释错误的部分,希望各位看官能够给予批评指正。

稀土掘金

责编内容by:稀土掘金阅读原文】。感谢您的支持!

您可能感兴趣的

Java Implementing Exception Handling I am trying to implement an OutOfStockException for when the user attempts to buy more items than there are available. I'm not sure if my implementati...
Redis 列表 简介 列表可以存储 多个 有序 可重复 的字符串。列表中的每个字符串称为元素(element),一个列表最多可以存储2 ^ 32 - 1个元素。在Redis中,可以对列表两端插入(push)和弹出(pop),还可以获取指定范围的元素列表、获取指定索引下标的元素等。列表是一...
2017 OWASP A8 Update: Insecure Deserialization Introduction 2017 saw a new addition to the Open Web Application Security Project’s (OWASP) Top Ten list of web application vulnerabilities — insecu...
Apk根据不同渠道更换SDK 需求是这样的 开发者接入sdk,接入成功之后提供apk,拆包对里面的sdk内容进行更替,得以实现不同渠道接入不同的SDK 实现步骤拆解如下: apk接入jar包 将其他渠道的jar包通过dx.jar 转化成 dex 将dex通过baksm...
给零基础学网页小伙伴的一封信 图片发自简书App 作者:苗大叔 当太阳开始升起的时候,她把温暖照向每一片可以接收能量的土地。一样的道理,当一个新的求知欲萌发在你心里时,你身体里的每一个细胞也将感受一种能量的驱动。 互联网时代,无论是打开电脑,还是手机,网络技术服务都无时无刻不伴随在我们左右。当...