ArrayList源码浅析-阿里云开发者社区

开发者社区> 武汉-万洋> 正文

ArrayList源码浅析

简介: `ArrayList`作为我们开发中最常用的集合,作为极高频次使用的类,我们不妨阅读源码一谈究竟。
+关注继续查看

前言

ArrayList作为我们开发中最常用的集合,作为极高频次使用的类,我们不妨阅读源码一谈究竟。

介绍

ArrayList继承关系如下

image-20211021163318663-4805199.png

AaaryList主要实现了List接口,同时标记为可以序列化Serializable、可复制CloneAble、支持随机访问RandomAccess

几个重要的成员变量

    /**
     * 默认容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 用于空实例的共享空数组实例。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 用于默认大小的空实例的共享空数组实例。我们将其与空元素数据区分开来,以了解添加第一个元素时要膨胀多少。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存储ArrayList元素的数组缓冲区。ArrayList的容量是此数组缓冲区的长度。
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * ArrayList的大小(它包含的元素数)。
     */
    private int size;

数据结构

ArrayList底层就是一个数组,数组会随着数据的增长而扩容,数组的扩容就是建立一个新的容量大的数组,然后把旧数组上面的数据复制进新数组。关于扩容,后面会详细讲解。

因为是数组,所以支持随机访问,且有序。

常用方法

ArrayList()无参构造方法

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

初始化数组为一个空数组。与空元素数据区分开来,以了解添加第一个元素时要膨胀多少。

add(E e) 添加元素

将指定的元素追加到此列表的末尾

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

当添加元素,会先检查是否超出容量,如果超出,则需要扩容。

当第一次添加元素时,size为默认值0,会计算出一个最小容量minCapacity,如果是无参构造创建的,则会取默认的容量10

Math.max(DEFAULT_CAPACITY, minCapacity),这里传入的minCapacity为0,所以获取更大的10。

如果计算出的最小容量大于原容量minCapacity - elementData.length > 0,则会进行扩容。

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

扩容算法是,扩为老容量的1.5倍,如果扩容后的容量仍然小于需要的最小容量minCapacity,则新的容量就取最小容量。

如果扩容后的大小超过最大容量,则会进行下面的操作

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

计算出扩容后的容量后,进行扩容,也就是,新建一个数组初始化为新容量,然后复制旧元素到新数组。elementData = Arrays.copyOf(elementData, newCapacity);

    public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }
    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

为什么不能在forEach里面修改列表

ArrayList在新增、删除元素都会执行modCount++

modCount定义在ArrayList的父类AbstractList

    /**
     * 此列表在结构上被修改的次数。结构修改是指那些改变列表大小的修改,或者以某种方式干扰列表,使得正在进行的迭代可能产生不正确的结果。 迭代器和列表迭代器方法返回的迭代器和列表迭代器实现使用此字段。如果此字段的值意外更改,迭代器(或列表迭代器)将抛出ConcurrentModificationException以响应下一个、删除、上一个、设置或添加操作。这提供了快速失效行为,而不是在迭代过程中面对并发修改时的非确定性行为。 子类使用此字段是可选的。如果子类希望提供fail fast迭代器(和列表迭代器),那么它只需在add(int,E)和remove(int)方法(以及它重写的任何其他方法,这些方法会导致列表的结构修改)中增加该字段。对add(int,E)或remove(int)的单个调用只能向该字段添加一个,否则迭代器(和列表迭代器)将抛出虚假的ConcurrentModificationException。如果实现不希望提供故障快速迭代器,则可以忽略此字段。
     */
    protected transient int modCount = 0;

然后我们来看下forEach的实现。

    @Override
    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        final E[] elementData = (E[]) this.elementData;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            action.accept(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

在遍历前,会暂存modCount值,每次循环都判断下modCount是否有更改,若更改了,里面跳出循环,随后抛出异常。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
java ArrayList源码分析(转载)
1.ArrayList是一个相对来说比较简单的数据结构,最重要的一点就是它的自动扩容,可以认为就是我们常说的“动态数组”。  来看一段简单的代码: 12345 ArrayList list = new ArrayList();list.add("语文: 99");list.add("数学: 98");list.add("英语: 100");list.remove(0);   在执行这四条语句时,是这么变化的:其中,add操作可以理解为直接将数组的内容置位,remove操作可以理解为删除index为0的节点,并将后面元素移到0处。
18845 0
Java集合干货——ArrayList源码分析
ArrayList源码分析 前言 在之前的文章中我们提到过ArrayList,ArrayList可以说是每一个学java的人使用最多最熟练的集合了,但是知其然不知其所以然。关于ArrayList的具体实现,一些基本的都也知道,譬如数组实现,线程不安全等等,但是更加具体的就很少去了解了,例如:初始化的长度,扩容等。
924 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4505 0
ArrayList源码解析(基于Java8)
首先:执行List list1 = new ArrayList(); 在堆内存开辟了一块空间,既然是new出来的,那我们直接从构造函数入手 Object[]数组,也就是说该数组可以放任何对象(所有对象都继承自父类Object) 继续,执行list1.
889 0
ArrayList源码分析(基于JDK1.6)
不积跬步,无以至千里;不积小流,无以成江海。从基础做起,一点点积累,加油!     《Java集合类》中讲述了ArrayList的基础使用,本文将深入剖析ArrayList的内部结构及实现原理,以便更好的、更高效的使用它。
478 0
ArrayList 源码详细分析
1.概述 ArrayList 是一种变长的集合类,基于定长数组实现。ArrayList 允许空值和重复元素,当往 ArrayList 中添加的元素数量大于其底层数组容量时,其会通过扩容机制重新生成一个更大的数组。
889 0
Java集合源码学习(二)ArrayList分析
ArrayList直接继承AbstractList,实现了List、 RandomAccess、Cloneable、Serializable接口,为什么叫"ArrayList",因为ArrayList内部是用一个数组存储元素值,相当于一个可变大小的数组,也就是动态数组。
1270 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
3239 0
9
文章
0
问答
来源圈子
更多
阿里云GTS能力中心(浩鲸智能),从交付的视角探讨数字化转型过程中大型软件开发实践、以及阿里云产品在各行业被集成的案例分享、技术沉淀等内容。敬请关注!
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载