GMTC深圳站本周日开幕,14大专题全部上线,完整日程>> 了解详情
写点什么

java 集合之 ArrayList 源码解读

  • 2019 年 9 月 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 年 9 月 27 日 14:371318

评论

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

架构师训练营 第3期 第5周 作业和总结

ihiming

第十周作业总结

hunk

极客大学架构师训练营

第 5 周作业提交

Binary

极客大学架构师训练营

数据库范式与反范式设计,是一门艺术

架构精进之路

数据库 范式

指尖上的警务,打造微警务管理服务平台

t13823115967

智慧警务系统开发 微警务

第 5 周学习总结

Binary

极客大学架构师训练营

架构师训练营第2期 第10周总结

月下独酌

极客大学架构师训练营

十、服务分解

Geek_28b526

6. 抹平差异,统一类型转换服务ConversionService

YourBatman

Spring Framework 类型转换 Converter ConversionService

NO.002-Java并发编程之多核硬件架构

葛一凡

操作系统 设计原则 硬件架构

第 10 周 系统架构作业

心在那片海

Week 10 模块分解

evildracula

学习 架构

架构师训练营 - 大作业一

lucian

架构师训练营 - 大作业二

lucian

程序员的bug修复宝典

程序员 经验总结 bug修复

面试官:说说操作系统微内核和Dubbo微内核?

yes

dubbo 操作系统 微内核

海纳百川无所不容,Win10环境下使用Docker容器式部署前后端分离项目Django+Vue.js

刘悦的技术博客

Python Docker 容器 镜像 部署

共享单车系统搭建

Geek_a620db

第十周作业

hunk

极客大学架构师训练营

关于Dubbo的原理

皮蛋

深入解析SpringMVC核心原理:从手写简易版MVC框架开始(SmartMvc)

Silently9527

Java mvc springmvc

全1子串算法求解、单元测试的必要性论述 John 易筋 ARTS 打卡 Week 32

John(易筋)

ARTS 打卡计划 全1子串算法求解 单元测试必要性

智能合约系统软件开发|智能合约APP开发

系统开发

掌趣电竞系统开发搭建

Geek_a620db

《Python数据科学:关于使用Python处理数据需要了解的终极指南》PDF免费下载

计算机与AI

Python 数据科学

生产环境全链路压测建设历程 21:某快递 A 股上市公司的生产压测案例之彩蛋 2 中篇

数列科技杨德华

全链路压测 七日更

架构师训练营第2期 第10周作业

月下独酌

极客大学架构师训练营

第 10 周 系统架构总结

心在那片海

Week10 作业

evildracula

使用 Serverless 创建一个简单的短网址服务

donghui

flask Serverless Lambda Store

数据可视化平台搭建,警务实战平台大数据应用

t13823115967

数据可视化 可视化数据分析搭建 警务实战平台

2021星空论坛:破局创新,论道数字化转型

2021星空论坛:破局创新,论道数字化转型

java集合之ArrayList源码解读-InfoQ