【专题推荐】AI大模型落地的前景和痛点,技术人面临哪些机会和挑战? 了解详情
写点什么

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:371926

评论

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

【DevOps实践】企业应用场景众多,怎样选择合适的代码分支模型?

嘉为蓝鲸

git DevOps 软件开发 持续交付 代码管理

11.11 程序员的 1111 种死法

京东科技开发者

程序员 程序人生

架构训练营-week8-数据结构与算法,网络,IO

于成龙

极客大学架构师训练营 架构训练营

技术干货:Apache Pulsar 在移动云上的应用

Apache Pulsar

大数据 开源 云原生 Apache Pulsar

阿里突遭断网断电!双11最惊险一幕刚刚曝光

Java架构师迁哥

Pulsar Summit Asia 2020 | 场景案例论坛(下):多行业,多场景

Apache Pulsar

大数据 开源 Apache Pulsar

甲方日常 50

句子

工作 随笔杂谈 日常

一次完整的JVM堆外内存泄漏故障排查记录

Zhendong

双“11”搞促销?用贪心算法来盘他!

王磊

算法

搞微服务用阿里开源的 Nacos 真香啊!

阿里巴巴 开源 编程

当Tomcat遇上Netty,我这一系列神操作,同事看了拍手叫绝

小Q

Java 学习 程序员 架构 面试

LeetCode题解:剑指 Offer 22. 链表中倒数第k个节点,使用栈,JavaScript,详细注释

Lee Chen

算法 大前端 LeetCode

面试蚂蚁金服,首战被MySQL惨虐,熬夜啃透这份阿里面经复盘一个月再战拿下P7offer

比伯

Java 程序员 架构 面试 阿里

MySQL 的 join 功能弱爆了?

程序员历小冰

MySQL postgres 多表join

Reactor详解之:异常处理

程序那些事

响应式 reactor 程序那些事 响应式系统 响应式架构

Java动态修改LOGGER日志级别

Zhendong

Java Arthas

目标检测-框架之darknet-数据读取

Dreamer

要求自愿降薪,员工内心普遍满意:“服从”是如何发生的?

脑极体

【Mycat】Mycat核心开发者带你看尽Mycat三大核心配置文件!!

冰河

分布式数据库 中间件 mycat

腾讯WeMap,一颗“孢子”的数智化之旅

脑极体

【概念篇】你真正了解越来越火的“数据驱动” 吗?

Java架构师迁哥

spring-注入配置

Isuodut

浅谈程序员的“内卷化”

数据社

iptables 端口转发

田振宇

SpringBoot启动原理

编程门槛 框架设计 spring Boot Starter】

「架构师训练营」第 4 周作业

小黄鱼

极客大学架构师训练营

第七周作业

Geek_4c1353

极客大学架构师训练营

阿里首发MySQL“完美日记”,基础+优化+事务+集群+锁+主从复制+安全备份

Java架构追梦

Java MySQL 数据库 架构 面试

面试官问我redis数据类型,我回答了8种

数据库 学习 面试

Java批量导入去除重复数据并返回结果,我差点就被放倒了

小Q

Java 学习 程序员 架构

双“11”搞促销?本文教你用贪心算法来盘他!

Java架构师迁哥

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