AI实践哪家强?来 AICon, 解锁技术前沿,探寻产业新机! 了解详情
写点什么

java 集合之 ArrayList 源码解读

  • 2019-09-27
  • 本文字数:9206 字

    阅读完需:约 30 分钟

java集合之ArrayList源码解读

一、综述

1.1 简介

ArrayList 是一个大小可以调整的动态数组,适应于查询为主的场景(备注:对应删除为主的是 LinkedList),并提供了添加、删除、更改、遍历的方式。


ArrayList 不是一个线程安全的集合。并发修改时,可能会抛出 ConcurrentModificationException 或者得到无法预料的结果。因此如果并发处理,要么更换线程安全的集合,要么依赖线程安全机制去保证 ArrayList 的并发处理。

1.2 继承关系


ArrayList


描述下各个抽象类、接口的作用:


RandomAccess 是一个标记接口,用于标记实现该接口的集合支持快速随机访问。


Serializable 是一个标记接口,用于标记实现该接口的类可以序列化。


Cloneable 是一个标记接口,用于标记实现该接口的类可以调用 clone 方法,否则会抛异常。


Iterable 是一个遍历接口,内部提供了支持不同遍历方式的方法,比如顺序遍历迭代器、函数式的 foreach 遍历、并行遍历迭代器。


Collection 是 java 集合体系的根接口,包含了通用的遍历、修改方法,例如 addAll、removeAll。


AbstractCollection 是一个抽象类,重写了 Collection 中最基础的方法,减少具体集合类的实现成本,比如 contains、isEmpty、toArray,iterator,但是 add 等需要具体集合类自我实现。


List 是 java 有序集合的基础接口,除了 Collection 的方法,还有支持倒序遍历的 listIterator 方法、子列表 subList 方法,另外重写 spliterator 方法的实现。


AbstractList 是一个抽象类,重写了 List 的大部分方法,作用跟 AbstractCollection 类似。

二、剖析

剖析以源码注释为主,以流程图为辅,解释 ArrayList 的字段定义、方法实现与设计思路。内容包含 ArrayList 的字段、构造、修改、遍历、序列化、线程安全六大部分,下面一一详解。

2.1 字段

    /**    * 序列化版本标识,序列化和反序列化时使用    */    private static final long serialVersionUID = 8683452581122892189L;
/** * 默认的数据容量 */ private static final int DEFAULT_CAPACITY = 10;
/** * 用于ArrayList空实例的共享空数组实例 */ private static final Object[] EMPTY_ELEMENTDATA = {};
/** * 用于默认大小空实例的共享空数组实例。 * 我们将DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA区别开来 * 以便在添加第一个元素时知道要膨胀多少。 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/** * 存放元素的数组 * 备注:字段不设置为私有,是为了方便内部类的访问 * 思考:为什么不是E[]呢? */ transient Object[] elementData;
/** * 数组元素个数 */ private int size;
复制代码

2.2 构造方法

    /**    * 1、创建ArrayList强制使用范型,避免使用原生类型引起类型不安全的问题    * 2、java7之后的jdk增强了类型推导,建议使用new ArrayList<>(),最好不使用new ArrayList<E>    */   // 创建一个特定长度的ArrayList   // 如果可以预估容量,请使用本方法构建实例,避免扩容时数组拷贝带来的性能消耗    public ArrayList(int initialCapacity) {        if (initialCapacity > 0) {            this.elementData = new Object[initialCapacity];        } else if (initialCapacity == 0) {             // 如果容量为0,则都指向同一个共享的空数组             // 减少内存的占用            this.elementData = EMPTY_ELEMENTDATA;        } else {            throw new IllegalArgumentException("Illegal Capacity: "+                                               initialCapacity);        }    }
复制代码


     // 创建一个容量为10的ArrayList     public ArrayList() {        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;    }      // 使用Collection的实现比如Set,List创建一个ArrayList     // 通常是Collection的实现进行相互转换    public ArrayList(Collection<? extends E> c) {        elementData = c.toArray();        if ((size = elementData.length) != 0) {            // c.toArray返回类型不一定Object[],具体见https://bugs.java.com/bugdatabase/view_bug.do?bug_id=JDK-6260652            if (elementData.getClass() != Object[].class)                elementData = Arrays.copyOf(elementData, size, Object[].class);        } else {            // 使用空数组替换            this.elementData = EMPTY_ELEMENTDATA;        }    }
复制代码

2.3 添加

添加可以分为两种:单个添加(添加特定元素)、批量添加(添加集合)。


单个添加



流程


/**  * 在ArrayList结尾添加元素  */public boolean add(E e) {    // 根据size处理容量    ensureCapacityInternal(size + 1);     elementData[size++] = e;    return true;}private void ensureCapacityInternal(int minCapacity) {    // 如果使用ArrayList()创建,默认容量=DEFAULT_CAPACITY=10    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);    }    // minCapacity为此时elementData必须的最小长度    ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {    // 修改次数+1,用于fail-fast处理    modCount++;    // 如果minCapacity大于elementData的长度,则进行扩容处理    if (minCapacity - elementData.length > 0)        // 扩容,可能会引起溢出问题        grow(minCapacity);}// ArrayList动态扩容机制的核心private void grow(int minCapacity) {    // 可能存在整型溢出    int oldCapacity = elementData.length;    // 容量默认扩大1.5倍    int newCapacity = oldCapacity + (oldCapacity >> 1);    if (newCapacity - minCapacity < 0)        // 可能1:newCapacity<0整型溢出        // 可能2:newCapacity<minCapacity        newCapacity = minCapacity;    if (newCapacity - MAX_ARRAY_SIZE > 0)        newCapacity = hugeCapacity(minCapacity);    // 数组深拷贝    elementData = Arrays.copyOf(elementData, newCapacity);}
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // 说明已经整型溢出 throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}/** * 在ArrayList特定位置添加单个元素 * 思考:add(E e)没有调用add(int index, E element),个人猜测是出于性能的考虑 * 毕竟基于数组进行插入操作可能存在性能问题 */public void add(int index, E element) { // 检查位置是否合法 rangeCheckForAdd(index);
// 跟add(E e)中处理方式类似 ensureCapacityInternal(size + 1); // 将elementData中位置为index位置及其后面的元素都向后移动一个下标(底层是native方法,使用cpp直接操作内存。) System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++;}
复制代码


批量添加


    //    public boolean addAll(Collection<? extends E> c) {        // 集合转化成数组        Object[] a = c.toArray();        int numNew = a.length;        // 跟add(E e)中处理方式类似        ensureCapacityInternal(size + numNew);         // 将集合内的元素复制到elementData中,覆盖[size, size+numNew)的元素        System.arraycopy(a, 0, elementData, size, numNew);        size += numNew;        return numNew != 0;    }    public boolean addAll(int index, Collection<? extends E> c) {        // 检查位置是否合法        rangeCheckForAdd(index);
Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew);
int numMoved = size - index; if (numMoved > 0) // 将elementData中位置为index及其以后的元素都向后移动numNew个位置 System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
// 将集合内的元素复制到elementData中,覆盖[index, index+numNew)的元素 System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; }
复制代码

2.3 删除

删除可以分为两种:单个删除(删除特定元素、特定下标)、批量删除(删除集合中的元素)、批量保留(批量删除除集合外的元素)、清空。


单个删除


    // 删除ArrayList中第一次出现的特定元素    public boolean remove(Object o) {        if (o == null) {            for (int index = 0; index < size; index++)                if (elementData[index] == null) {                    fastRemove(index);                    return true;                }        } else {            for (int index = 0; index < size; index++)                // 比较对象时依赖equals方法                // 因此类型变量E对应的类注意重写equlas方法                // 重写时注意遵守规范,具体参考effective java第三版的第10、11两条规则                if (o.equals(elementData[index])) {                    fastRemove(index);                    return true;                }        }        return false;    }    // 根据下标删除元素    private void fastRemove(int index) {        modCount++;        int numMoved = size - index - 1;        if (numMoved > 0)            // 将elemenData中index+1及其后面的元素都向前移动一个下标            System.arraycopy(elementData, index+1, elementData, index,                             numMoved);        // 根据上一步的操作, size-1位置的对象向前移动了一个下标        // 如果没有elementData[--size]==null,可能会导致内存泄漏        // 试想,ArrayList被add了100个对象,然后被remove了100次。按照GC的机制来说,100个对象应该可以被GC掉(假设没有对象对象),但是由于还存在ArrayList的实例引用,对应的100个对象就无法删除        elementData[--size] = null;     }
// 根据下标删除元素 // 注意:java5后引入自动装箱、拆箱的机制,因此产生了一个有趣的问题: // 当类型变量为Integer的ArrayList调用remove时,可能调用remove(Object),也可能调用remove(Index) // 一定要注意测试是否符合自己的预期 public E remove(int index) { rangeCheck(index);
modCount++; E oldValue = elementData(index);
int numMoved = size - index - 1; // 如果被删除元素不是ArrayList的最后一个元素 if (numMoved > 0) // 对应下标之后的元素向前移动一个下标 System.arraycopy(elementData, index+1, elementData, index, numMoved); // 最后一个元素只为null,方便GC elementData[--size] = null;
return oldValue; }
复制代码


批量删除


    // 批量删除ArrayList和集合c都存在的元素    public boolean removeAll(Collection<?> c) {        // 非空校验        Objects.requireNonNull(c);        // 批量删除        return batchRemove(c, false);    }
private boolean batchRemove(Collection<?> c, boolean complement){ final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) if (c.contains(elementData[r]) == complement) // 把需要保留的元素前置 elementData[w++] = elementData[r]; } finally { // 即使c.contains抛异常,也要保持跟AbstractCollection行为的兼容性 // 备注:ArrayList重写了AbstractCollection中的removeAll方法,removeAll调用了batchRemove if (r != size) { // 备注1:可能是上面的for循环出现了异常 // 备注2:可能是其它线程添加了元素。 System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { for (int i = w; i < size; i++) // 跟fastRemove(int index)里面的操作类似,防止内存泄漏 elementData[i] = null; // 思考:为什么addAll的modCount+1,而removeAll的modCoun+size-w // 个人以为modCount只是做标记做了结构的修改并且用来做校验。 // 因此+1,+2 +size-w并没有本质区别 modCount += size - w; size = w; modified = true; } } return modified; }
// 思考:上面是按照元素进行批量删除,如何按照下标区间进行批量删除呢?批量保留
public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); // 批量保留 return batchRemove(c, true); }
复制代码


清空


    public void clear() {        modCount++;        // 清空ArrayList里面所有的元素        for (int i = 0; i < size; i++)            elementData[i] = null;
size = 0; }
复制代码


更改


    // 修改特定下标的值    public E set(int index, E element) {        rangeCheck(index);
E oldValue = elementData(index); elementData[index] = element; return oldValue; }
@SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }
复制代码


查找


    // 返回元素第一次出现的下标    public int indexOf(Object o) {        if (o == null) {            for (int i = 0; i < size; i++)                if (elementData[i]==null)                    return i;        } else {            for (int i = 0; i < size; i++)                if (o.equals(elementData[i]))                    return i;        }        return -1;    }    // 返回最后一次出现的位置    public int lastIndexOf(Object o) {        if (o == null) {            for (int i = size-1; i >= 0; i--)                if (elementData[i]==null)                    return i;        } else {            for (int i = size-1; i >= 0; i--)                if (o.equals(elementData[i]))                    return i;        }        return -1;    }
复制代码


遍历方式


ArrayList 可以通过 for、foreach、foreach-lambda、iterator 进行遍历,iterator 又可以分为 Iterator(只能按照 index 从 0 到 size 进行遍历)、ListIterator(可以按照 index 从小到大进行遍历,也可以从大到小进行遍历)、Spliterator(并行遍历,充份发挥多核优势),下面依次进行演示。


        List<String> strList = new ArrayList<String>(4);                   strList.add("1");                   strList.add("2");                   strList.add("3");
// for遍历 for (int i = 0; i < strList.size(); i++) { System.out.println(strList.get(i)); }
// foreach // 备注:只要实现Iterable接口,就能使用foreach for (String s : strList) { System.out.println(s); }
// foreach-lambda遍历 strList.forEach(System.out::println);
// iterator遍历 Iterator<String> iterator = strList.iterator(); while (iterator.hasNext()){ String str = iterator.next(); System.out.println(str); // 下一次出现ConcurrentModificationException // 问题是因为list的iterator方法返回的是ArrayList的内部类Itr // Itr里面的expectedModCount会与ArrayList的modCount进行比较 // 剩下的就不言而喻 strList.remove(str); // 进行iterator遍历时,如果进行remove等操作,调用iterator的方法 // 而不是ArrayList的方法 // iterator.remove(); }
// ListIterator可以进行顺序、逆序遍历,可以指定index位置开始遍历 ListIterator<String> iterator = strList.listIterator(); while (iterator.hasNext()){ System.out.println(iterator.next()); } iterator = strList.listIterator(strList.size()); while (iterator.hasPrevious()){ System.out.println(iterator.previous()); iterator.remove(); }
// 使用并行遍历,可以将元素放在不同的迭代器进行并行遍历 Spliterator<String> spliterator = strList.spliterator(); // split,分而治之,类似算法里面的分治 Spliterator<String> otherSpliterator = spliterator.trySplit(); spliterator.forEachRemaining(System.out::println); otherSpliterator.forEachRemaining(System.out::println);
复制代码


序列化


ArrayList 的序列化没有直接序列化 elementData,而是根据 size 序列化包含的元素,忽略数组中的其它位置,提高效率并节省空间。


    private void writeObject(java.io.ObjectOutputStream s)        throws java.io.IOException{        // fail-fast,后续判断是否有并发处理        int expectedModCount = modCount;        // 序列化没有标记为static、transient的字段,包括size等。        s.defaultWriteObject();
// 没有意义,可以忽略 s.writeInt(size);
// 序列化元素 for (int i=0; i<size; i++) { s.writeObject(elementData[i]); }
if (modCount != expectedModCount) { // ArrayList被并发处理,发生结构性修改 throw new ConcurrentModificationException(); } } private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { elementData = EMPTY_ELEMENTDATA;
// 反序列化没有标记为static、transient的字段,包括size等 s.defaultReadObject();
// 可以忽略,跟writeObject里面的方法对应 s.readInt();
if (size > 0) { // 数组扩容 ensureCapacityInternal(size);
Object[] a = elementData; // 反序列化元素并填充到数组中 for (int i=0; i<size; i++) { a[i] = s.readObject(); } } }
复制代码


排序


        List<String> strList = new ArrayList<String>(4);                   strList.add("1");                   strList.add("2");                   strList.add("3");
// 可以使用以下三种排序方式 Collections.sort(strList); Collections.sort(strList, String::compareTo); strList.sort(String::compareTo);
//java8 新增的排序方法 public void sort(Comparator<? super E> c) { final int expectedModCount = modCount; // 底层使用合并排序算法进行排序 Arrays.sort((E[]) elementData, 0, size, c); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; }
复制代码


转化数组


    public Object[] toArray() {        // 直接复制ArrayList的elementData        return Arrays.copyOf(elementData, size);    }
public <T> T[] toArray(T[] a) { if (a.length < size) // 利用反射生成特定类型的数组并复制 // 备注:但是不知道为什么toArray的类型变量T跟ArrayList的不一致 return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } // 另外,除了根据ArrayList转化成数组,同样可以根据Arrays的asList将数组转换成List // 备注:Arrays是数组操作的util类,可以进行排序、查找、复制、遍历等 // 注意:asList方法返回的私有静态内部类ArrayList,静态内部类ArrayList跟java.util.ArrayList不同 // 注意:静态内部类ArrayList没有重写java.util.AbstractList的remove、add等方法,默认实现是直接抛UnsupportedOperationException,因此调用会报错 List<String> strList = Arrays.asList("1", "2", "3");
复制代码


线程安全


开头说过,ArrayList 并不是线程安全的集合,源码剖析也展示了 ArrayList 通过 modCount 以及 fali-fast 机制去避免一定程度的线程安全问题,那么我们如何保证 ArrayList 的线程安全呢?其实,我们可以通过以下方案实现:


  • 使用 Vector 代替 ArrayList。

  • 使用 Collections.synchronizedList 包装 ArrayList,然后操作包装后的 list 即可。

  • 使用 CopyOnWriteArrayList 代替 ArrayList。

  • 在使用 ArrayList 时,应用程序通过同步机制去控制 ArrayList 的读写,不建议。


前面提过,ArrayList 是一个查询为主的数据结构,本身不适合修改频繁以及并发修改的场景。如果需要并发操作,可以使用上面的方案,但是它们都会有一定的瓶颈,或许我们更换其它的集合类更合适,比如线程安全的队列。

三、总结

前面通过注释剖析了 ArrayList 的源码实现,但是能力有限,不能保证分毫不错,面面俱到。因此,希望本文能够抛砖引玉,给大家更多的启发,引导大家多到底层看看。


作者介绍:


多隆(企业代号名),目前负责贝壳基础技术中心不动产数据标准化业务,专注 java 后台技术、代码设计。


本文转载自公众号贝壳产品技术(ID:gh_9afeb423f390)。


原文链接:


https://mp.weixin.qq.com/s/dy98Y-LyQw1BbbH3_X7nBw


2019-09-27 14:372420

评论

发布
暂无评论
发现更多内容

使用 Bytebase 管理 Rainbond 上的应用数据库

北京好雨科技有限公司

7X24 高可用保障,火山引擎边缘函数为猿辅导在线教学业务保驾护航

火山引擎边缘云

Serverless 边缘计算 在线 教育 火山引擎

DHorse系列文章之镜像制作

tiandizhiguai

云原生 Serverless Kubernetes

温州有等保测评机构吗?听说没有是吗?

行云管家

等保 等保测评

Java岗位必备技能SpringBoot的9道面试题集锦

钟奕礼

Java java程序员 java面试 java编程

华为云GaussDB打造金融行业坚实数据底座,共创数字金融新未来

清欢科技

10分钟让你了解应用宝APP上架流程

YonBuilder低代码开发平台

开发者

jquery 事件绑定及取消 bind live delegate on one区别 (超详细且通俗易懂)

Ankiee

jquery 11月月更

python常用内置函数用法精要(一)

乔乔

11月月更

集世界杯+GameFi元素的MetaElfLand,为何将在世界杯期间爆发?

鳄鱼视界

华为云安全亮相世界互联网大会

科技怪授

华为云

Baklib帮助中心:自助服务指南

Baklib

客户服务 帮助中心

offset新探索:双管齐下,加速大数据量查询

IT科技苏辞

集世界杯+GameFi元素的MetaElfLand,推出世界杯专场活动

西柚子

HummerRisk V0.5.2:升级对象存储、云检测、云审计和K8s资源态势等

HummerCloud

云原生 k8s #Kubernetes# 云原生安全

kafka实战】分区重分配可能出现的问题和排查问题思路

石臻臻的杂货铺

kafka Kafka实战 11月月更

全面焕新|详解 Grafana v9.0.x 新增功能特性

阿里巴巴云原生

阿里云 云原生 Grafana 新功能

【收藏】设备的前期管理,你重视了吗?

PreMaint

设备管理

PCB做SET连片,转批量时发现利用率非常低,有遇到过吗?

华秋PCB

PCB PCB设计 拼板

Zebec开启多链布局,流支付生态持续扩张

西柚子

低代码引擎半岁啦,来跟大家唠唠嗑...

阿里巴巴终端技术

前端 低代码

从流程驱动到数据驱动 银行业数据平台架构的演进

酷克数据HashData

是时候考虑升级 JDK 17 了

世开 Coding

Java jdk JVM jdk17

刘强东给京东高管降薪:2千多位总监兄弟工资打8折,并拿出100亿保障”兄弟“基础住房

小小怪下士

程序员 京东 刘强东

NFT盲盒链游DAPP系统开发搭建技术

薇電13242772558

web3

华为再次入选2022年Gartner® SIEM魔力象限

科技怪授

华为云

极客时间架构训练营模块七作业

李晨

架构

为什么要用 Tair 来服务低延时场景 - 从购物车升级说起

阿里技术

内存数据库 低延时

双机热备与数据备份的关系说明一二

行云管家

数据备份 双机热备

Serverless 的前世今生

Serverless Devs

二面被RocketMQ虐后,狂刷这套实战到源码手册,再战阿里

钟奕礼

Java Java 面试 java程序员 java编程

java集合之ArrayList源码解读_文化 & 方法_多隆_InfoQ精选文章