专栏首页Java系列文章JDK源码阅读(三):ArrayList源码解析

JDK源码阅读(三):ArrayList源码解析

温馨提示

如果你喜欢本文,请分享到朋友圈,想要获得更多信息,请关注我。

关注公众号 回复关键字领取免费学习资源

- 电子书 领取《Java并发》《Java编程思想等》

- SpringCloud 领取SpringCloud全套视频学习资源

- SpringBoot 领取SpringBoot 全套视频学习资源

正文共:4212字23图 预计阅读时间:11分钟

今天来看一下 ArrayList 的源码

  • 目录
    • 介绍
    • 继承结构
    • 属性
    • 构造方法
    • add 方法
    • remove 方法
    • 修改方法
    • 获取元素
    • size() 方法
    • isEmpty 方法
    • clear 方法
    • 循环数组

1. 介绍

一般来讲文章开始应该先介绍一下说下简介。这里就不介绍了 如果你不知道 ArrayList 是什么的话就没必要在看了。大致讲一下一些常用的方法

2. 继承结构

ArrayList 源码定义:

ArrayList 继承结构如下:

  • Serializable 序列化接口
  • Cloneable 前面我们在看 Object 源码中有提到这个类,主要表示可以进行克隆
  • List 主要定义了一些方法实现
  • RandomAccess 也是一个标记类,实现 RandomAccess 表示该类支持快速随机访问。

3. 属性

ArrayList 中的主要属性方法有:

初始化容量,默认为 10

private static final int DEFAULT_CAPACITY = 10;

空数组

private static final Object[] EMPTY_ELEMENTDATA = {};

也是一个空数组,和上面的数组相比主要的作用是在添加元素的时候知道数组膨胀了多少。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

ArrayList 的大小

private int size;

注意 ArrrayList 中有一个 modCount 成员变量,来记录修改次数,主要是在使用迭代器遍历的时候,用来检查列表中的元素是否发生结构性变化(列表元素数量发生改变)了,主要在多线程环境下需要使用,防止一个线程正在迭代遍历,另一个线程修改了这个列表的结构。好好认识下这个异常:ConcurrentModificationException。对了,ArrayList 是非线程安全的。

4. 构造方法

我们来看一下 ArrayList 的构造方法 无参构造方法:

可以看出无参构造会直接创建一个指定 DEFAULTCAPACITYEMPTYELEMENTDATA 的数组,而 DEFAULTCAPACITYEMPTYELEMENTDATA 数组默认是空的。

所以在执行一下代码的时候 ArrayList 默认创建的是一个初始化容量为 0 的数组。

ArrayList list = new ArrayList();

有参构造方法:

传入创建数组的大小,如果大于 0 就创建一个传入参数大小的数组,如果等于 0 就就指定为空数组。如果小于 0 就会抛异常。

看源码我们可以看到传入 Collection 的构造方法做的事情就是复制数组,将已有的集合复制到新的集合中。

5.add 方法

ArrayList 底层是用数组来实现的,那我们就一起来看以下 Add 方法是如何实现的

以下是 Add 方法的实现源码。

可以看到 ArrayList 在添加元素之前先检查一下集合的大小

在 ensureExplicitCapacity 方法中,首先对修改次数 modCount 加一,这里的 modCount 给 ArrayList 的迭代器使用的,在并发操作被修改时,提供快速失败行为(保证 modCount 在迭代期间不变,否则抛出 ConcurrentModificationException 异常,可以查看源码 865 行),接着判断 minCapacity 是否大于当前 ArrayList 内部数组长度,大于的话调用 grow 方法对内部数组 elementData 扩容,grow 方法代码如下:

上面的代码可以看出 ArrayList 的扩容。首先获得老数组的容量,然后 oldCapacity + (oldCapacity>> 1); 计算出老数组大小的 1.5 倍,判断 新容量小于参数指定容量,修改新容量,如果新容量大于最大容量的话就指定容量。

6.remove 方法

ArrayList 的删除操作一共有两种一种是根据索引删除,一种是根据内容删除。

根据索引删除元素

remove 方法表示删除索引 index 处的元素,首先通过 rangeCheck 方法判断给定索引的范围,超过集合大小则抛出异常;接着通过 System.arraycopy 方法对数组进行自身拷贝。 根据元素删除

我们可以看到首先判断一下是否为空。不为空的话就开始循环查找元素,用 equals 来判断元素是否相同,如果一致就调用 fastRemove 来删除元素。然后通过 System.arraycopy 进行自身复制。

7. 修改方法

 通过调用 set(int index, E element) 方法在指定索引 index 处的元素替换为 element。并返回原数组的元素。先通过 rangCheck 来检查索引的合法性,如果不合法(负数,或者其他值)会抛出异常。

8. 获取元素

因为本身 ArrayList 就是用数组来实现的,所以获取元素就相对的来说简单一点。

首先也是调用 rangeCheck 方法来判断索引是否合法,然后在直接根据索引回去元素

根据元素查找索引

直接返回第一次出现的元素。否则返回 - 1

9.size() 方法

直接返回的 size 大小。

9.isEmpty 方法

直接返回 size==0 的结果,是不是非常简单。

10.clear 方法

循环把元素赋值为空,便于 GC 回收

11. 循环数组

for 循环

for 循环可能在 java 中是最常用的遍历方法主要实现:

因为我们前面说过 get 方法可以通过索引来获取元素。同理。

迭代器 iterator

先看实现:

我们来看一下源码怎么实现的:

返回一个 Itr 对象,这个类是 属于 ArrayList 的内部类。

 /**     * An optimized version of AbstractList.Itr     */    private class Itr implements Iterator<E> {        //游标, 下一个要返回的元素的索引        int cursor;         // 返回最后一个元素的索引; 如果没有这样的话返回-1.        int lastRet = -1;         int expectedModCount = modCount;        Itr() {}        //通过 cursor != size 判断是否还有下一个元素        public boolean hasNext() {            return cursor != size;        }        @SuppressWarnings("unchecked")        public E next() {        //迭代器进行元素迭代时同时进行增加和删除操作,会抛出异常            checkForComodification();            int i = cursor;            if (i >= size)                throw new NoSuchElementException();            Object[] elementData = ArrayList.this.elementData;            if (i >= elementData.length)                throw new ConcurrentModificationException();                //游标向后移动一位            cursor = i + 1;            //返回索引为i处的元素,并将 lastRet赋值为i            return (E) elementData[lastRet = i];        }        public void remove() {            if (lastRet < 0)                throw new IllegalStateException();            checkForComodification();            try {            //调用ArrayList的remove方法删除元素                ArrayList.this.remove(lastRet);                //游标指向删除元素的位置,本来是lastRet+1的,这里删除一个元素,然后游标就不变了                cursor = lastRet;                //lastRet恢复默认值-1                lastRet = -1;                //expectedModCount值和modCount同步,因为进行add和remove操作,modCount会加1                expectedModCount = modCount;            } catch (IndexOutOfBoundsException ex) {                throw new ConcurrentModificationException();            }        }        @Override        @SuppressWarnings("unchecked")        public void forEachRemaining(Consumer<? super E> consumer) {            Objects.requireNonNull(consumer);            final int size = ArrayList.this.size;            int i = cursor;            if (i >= size) {                return;            }            final Object[] elementData = ArrayList.this.elementData;            if (i >= elementData.length) {                throw new ConcurrentModificationException();            }            while (i != size && modCount == expectedModCount) {                consumer.accept((E) elementData[i++]);            }            // update once at end of iteration to reduce heap write traffic            cursor = i;            lastRet = i - 1;            checkForComodification();        }        //前面在新增元素add() 和 删除元素 remove() 时,我们可以看到 modCount++。修改set() 是没有的        final void checkForComodification() {            if (modCount != expectedModCount)            //也就是说不能在迭代器进行元素迭代时进行增加和删除操作,否则抛出异常                throw new ConcurrentModificationException();        }    }

从上面的代码我们得出,在遍历的时候如果删除或者新增元素都会抛异常出来,而修改不会。看下方例子。

抛出异常:

小弟不才,如有错误请指出。喜欢请关注,慢慢更新 JDK 源码阅读笔记

本文分享自微信公众号 - 乱敲代码(gh_baf1250e9b02)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LintCode-204. 单例

    单例 是最为最常见的设计模式之一。对于任何时刻,如果某个类只存在且最多存在一个具体的实例,那么我们称这种设计模式为单例。例如,对于 class Mouse (不...

    悠扬前奏
  • 继承HibernateDaoSupport时遇到的问题

    都知道spring提供的有零配置功能,而且看见别人的一个项目使用spring+mybatis,只在applicationContext.xml里定义了sqlSe...

    用户1212940
  • Java架构体系学习路线图,第六点尤为重要!

    可以说,Java是现阶段中国互联网公司中,覆盖度最广的研发语言,掌握了Java技术体系,不管在成熟的大公司,快速发展的公司,还是创业阶段的公司,都能有立足之地。

    Java知音
  • Java基础学习

    http://www.runoob.com/java/java-environment-setup.html

    lilugirl
  • 新建NodeJS Web项目的几个最佳实践

    在项目建立初期引入一些最佳实践可以避免后期大量复杂的重构工作,本文总结了在使用Node JS构建Web服务时的一些最佳实践,同时涉及的具体的操作步骤。

    极客人
  • 11个简单的Java性能调优技巧

    大部分建议是针对Java的。但也有若干建议是与语言无关的,可以应用于所有应用程序和编程语言。

    Kindear
  • Java-ECJ和Javac在泛型类处理上的一点区别

    ECJ(Eclipse Compiler for Java)就是Eclipse自带的java编译器。 公司的项目都是在Eclipse上面做的。自己用了一段时间...

    悠扬前奏
  • Go语言入门——数组、切片和映射(下)

      不管是数组、切片还是映射结构,都是一种集合类型,要从这些集合取出元素就要查找或者遍历。

    JackieZheng
  • Java原子操作类,你知道多少?

    由于synchronized是采用的是悲观锁策略,并不是特别高效的一种解决方案。 实际上,在J.U.C下的atomic包提供了一系列的操作简单,性能高效,并能保...

    李红
  • Python 69个内置函数分类总结

    Python3解释器中内置了69个常用函数,属于底层的函数,它们到处可用。有些对大家来说比较熟悉,比如abs(), max(), sum()... 也有一些比较...

    double

扫码关注云+社区

领取腾讯云代金券