专栏首页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 条评论
登录 后参与评论

相关文章

  • JDK源码阅读(一):Object源码分析

      类构造器是创建Java对象的方法之一。一般我们都使用new关键字来进行实例,还可以在构造器中进行相应的初始化操作。   在一个Java类中必须存在一个构造器...

    乱敲代码
  • 如何使用Arrays工具类操作数组

    我们要先知道Arrays 是什么。 java.util.Arrays 类是 JDK 提供的一个工具类主要用来操作数组,比如数组的复制转换等各种方法,Arrays...

    乱敲代码
  • HashMap源码分析(二):看完彻底了解HashMap

    HashMap在上一篇源码分析的文章中,如果使用put的时候如果元素数量超过threshold就会调用resize进行扩容

    乱敲代码
  • JDK源码阅读(三):ArrayList源码解析

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

    码农小胖哥
  • 简单算法之冒泡排序

    外层循环控制循环次数,内层循环控制比对元素的个数,因为冒泡排序是两两比对,五个元素的数组只需要比对四次,因为最后一个元素没有可比对的元素,内层循环判断条件j <...

    萬物並作吾以觀復
  • 从哈希函数、哈希冲突、开散列出发,一文告诉你哈希思想与哈希表构造到底是什么!

    Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。

    区块链大本营
  • Python的堆操作,是不是要掌握一下

    Python的强大并不在于它的语法,而在于它的库,当你对各种数据结构感到苦恼时,Python提供了各种开箱即用的数据结构。

    疯狂软件李刚
  • delphi各个版本编译开关值

    delphi各个版本编译开关值 {$IFDEF VER80} - Delphi 1 {$IFDEF VER90} - Delphi 2 {$IFDEF V...

    战神伽罗
  • 2020年3月TIOBE编程语言排行榜来了!

    TIOBE公布了3月份编程语言排行榜。相比上个月编程语言Top 5并没有太大的变化,其中Java依旧稳坐榜首,随后分别是C、Python、C++、C#。

    老九君
  • Selenium系列(一) - 详细解读8种元素定位方式

    https://www.cnblogs.com/poloyy/category/1680176.html

    小菠萝测试笔记

扫码关注云+社区

领取腾讯云代金券