文档章节

【JDK1.8】ArrayList源码分析

XuePeng77
 XuePeng77
发布于 07/07 20:33
字数 3482
阅读 191
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

ArrayList的特性

ArrayList内部使用数据作为存储结构,ArrayList可以理解为数组的扩展对象,封装了常用的和非常用的操作数组的方法。以及当数组长度不足以保存数组时,自动扩容数组,通常ArrayList有如下特点:

数据按顺序存储;

  • 根据索引查询数据的时间复杂度是O(1);
  • 在数组中间部分根据索引写入或删除元素效率低;
  • 写入数组时若数组长度不足则会触发扩容;
  • ArrayList允许保存NULL;
  • ArrayList是非线程安全的设计;

下面来阅读源码,证明这几个特性。

ArrayList源码分析

重要成员变量

    /**
     * ArrayList默认的容量长度
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 定义一个空数组对象
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 当ArrayList中没有任何对象时,使用该变量赋值,是一个默认的缺省空数组对象
     * 用于无参构造函数为elementData赋值,或判断数组是否是缺省值
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * ArrayList中真正保存数据的数组
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * 数组中保存的对象的个数
     */
    private int size;

这段代码中,核心参数有2个:

  • elementData:它是ArrayList中真正存储数据的对象,也证明ArrayList内部是由数组实现的,elementData用transient修饰;
  • DEFAULT_CAPACITY:它表示数组在一般情况下,初次扩容的长度;

ArrayList默认初始化的长度并不是10,也就是说不是DEFAULT_CAPACITY的长度,下面通过阅读源码来确认。

构造函数

ArrayList提供了三种构造函数:

第一种,无参构造函数

    public ArrayList() {
        // 用缺省的DEFAULTCAPACITY_EMPTY_ELEMENTDATA来赋值给elementData数组
        // 变量定义:static final DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

这说明通过ArrayList list = new ArrayList()创建一个ArrayList时,初始化长度是0,而不是10。

第二种,根据指定容量创建

    // initialCapacity是new ArrayList(5)时传递的指定容量
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            // 根据initialCapacity实例化elementData对象
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            // 如果传进来的是0,那么则用EMPTY_ELEMENTDATA初始化,这里要跟DEFAULTCAPACITY_EMPTY_ELEMENTDATA做好区分
            // 变量定义:static final EMPTY_ELEMENTDATA = {}
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

带初始化容量参数的构造函数也很好理解,在内部做了一个initialCapacity等于0的判断处理。

第三种,根据其他类型集合来初始化

    // Collection是多种集合(List,Set,Queue)的的顶级接口
    // 也就是说,实现Collection接口的对象都可以用来初始化ArrayList
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            // 调用Arrays.copyOf为elementData赋值
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 如果参数长度为0,则用EMPTY_ELEMENTDATA赋值elementData
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

三种构造函数都很简单,都是为了初始化内部的elementData。

下面来看一下数组elementData的扩容源码。之所以在分析常用方法前先分析扩容方法,是因为常用方法中经常会设计到数组的扩容,而且ArrayList的源码中最核心的功能之一就是扩容。

数组扩容

ArrayList会在内部数组长度不足时自动扩容,同时它也提供了主动扩容的方法,下面来看看两种扩容的源码。

主动扩容

    public void ensureCapacity(int minCapacity) {
        // 获取最小的扩容长度,0或者10
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
        // 当主动扩容传入的参数大于最小扩容长度时进行扩容,否则不进行扩容
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

上面的代码就是主动扩容的源码,可以通过list.ensureCapacity(100)由使用者调用进行主动扩容。

因为扩容涉及到数组的拷贝,所以源码中加入了判断,当要扩容的长度小于最小扩容长度,则不进行扩容。

自动扩容

    private void ensureCapacityInternal(int minCapacity) {
        // 先调用calculateCapacity方法,获取要扩容的长度
        // 后调用ensureExplicitCapacity方法,进行扩容
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 如果数组是初始化数组,则取DEFAULT_CAPACITY和minCapacity中较大的数作为扩容长度
        // 也就是说,初始化数组的长度是0,如果第一次添加对象,那么minCapacity将是1,数组会扩容到10
        // 所以可以认为,数组初始化是0,当添加第一个对象时,扩容到10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    private void ensureExplicitCapacity(int minCapacity) {
        // 记录数组的修改次数,这个变量在AbstractList类中,是ArrayList的父类
        modCount++;

        // 确认是否进行扩容,也就是说数组elementData的长度不足以存放对象了
        // 调用grow进行真正的扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    // elementData的最大长度
    // 是一个Integer的最大值-8的长度
    // 之所以减8是因为一些虚拟机对数组的实现,需要用减掉的这个8来保存一些头信息
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    private void grow(int minCapacity) {
        // 获取旧的容量
        int oldCapacity = elementData.length;
        // 将容量扩大1.5倍, >>1效率更高
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 做一些逻辑判断,若要扩容的长度小于最小扩容长度,也就是比传入的参数小,则扩容长度取传入的参数
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 若要扩容的长度大于Integer.MAX -8,这种极端形况下调用hugeCapacity进行处理
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 扩容!调用Arrays.copyOf方法
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        // 如果minCapacity等于负数,有可能是内存溢出了,则抛出OOM异常
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        // 否则如果确实是大于了Integer.MAX - 8,但在Integer.MAX内,则返回Integer.MAX
        // 但能否扩容成功,要根据JVM虚拟机的实现来看了
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

上面的代码就是ArrayList扩容部分的代码,核心点如下:

  • 自动扩容为原数组长度的1.5倍,用>>1效率更高;
  • 扩容的最大长度,理想状态下应该是Integer.MAX - 8的长度,因为一些JVM实现数组需要保存头信息,会占用数组的长度;
  • 当极端情况下超过了Integer.MAX - 8,则扩容到Integer.MAX;

常用方法

下面来分析一下ArrayList的常用方法,例如get、set、add、remove等函数。

get方法

    public E get(int index) {
        // 检测索引是否越界
        rangeCheck(index);
        // 从数组中找到数据并返回,时间复杂度的O(1)
        return elementData(index);
    }

    private void rangeCheck(int index) {
        // 检测索引是否越界,如果越界则抛出异常
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
    
    E elementData(int index) {
        // 返回数组中制定索引的数据
        return (E) elementData[index];
    }

get方法的时间复杂度是O(1)

set方法

    public E set(int index, E element) {
        // 检测索引越界
        rangeCheck(index);
        // 获取索引对应的值,将索引位置的值设置成element,然后返回旧值,时间复杂度是O(1)
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

set方法的时间复杂度是O(1)

add方法

add(E e)

    public boolean add(E e) {
        // 将ArrayList长度+1,然后调用内部扩容函数
        // 若数组还有空间则不会进行扩容
        ensureCapacityInternal(size + 1);
        // 保存到数组最后面
        elementData[size++] = e;
        return true;
    }

add方法由几率会出发扩容,在上面分析扩容代码时已经注意到了:

if (minCapacity - elementData.length > 0)
    grow(minCapacity);

如果elementData.length的长度小于minCapacity(结合上下文就是size +1),那么将会将数组扩容1.5倍。

不触发扩容的情况下add(E e)的时间复杂度是O(1)

add(int index, E element)

    public void add(int index, E element) {
        // 判断索引是否越界
        rangeCheckForAdd(index);
        // 触发扩容
        ensureCapacityInternal(size + 1);
        // 将index位置后的元素统一向后移动
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 将数组保存到索引位置,并将长度+1
        elementData[index] = element;
        size++;
    }

    private void rangeCheckForAdd(int index) {
        // 索引不能大于ArrayList的size,并且不能小于0
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

调用add(int index, E element)效率不高的原因就在于此,每次add一个元素,都要移动该元素后面的所有元素。最坏的情况下时间复杂度是O(n)

还有一些add方法,比如addAll(Collection<? extends E> c)或者addAll(int index, Collection<? extends E> c)的实现方式都差不多,篇幅原因不在贴代码了。

remove方法

remove(int index)

    public E remove(int index) {
        // 检查索引越界
        rangeCheck(index);
        // 记录修改次数
        modCount++;
        // 获取要被删除的元素,准备在方法结束时返回给调用者
        E oldValue = elementData(index);
        // 这里做了一个判断,如果删除的不是最后一个元素,则需要将index后的元素向前移动
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 将最后一个元素位置置为null,便于GC回收
        elementData[--size] = null; // clear to let GC do its work
        return oldValue;
    }

与add(int index, E element)类似,如果从中间删除时,数组会将index后的元素统一向前移动。

从数组中间位置删除元素效率低的原因就在于此,最坏的情况下时间复杂度是O(n)

remove(Object o)

    public boolean remove(Object o) {
        if (o == null) {
            // 如果对象是null,则找到第一个null元素的索引,并从数组中删除,查找方式是从前到后
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            // 如果对象不是null,则找到对象的索引,从数组中删除,查找方式也是从前到后
            for (int index = 0; index < size; index++)
                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)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 最后以为元素设置为null,便于GC回收
        elementData[--size] = null; // clear to let GC do its work
    }

remove(Object o)的做法是先循环找到o对应的index,然后跟remove(int index)执行差不多逻辑,将index后面的数据向前移动。

remove(Object o),从前向后查找元素,并将后面的元素向前移动,所以它的时间复杂度是是O(n)

removeAll和retainAll

removeAll方法的入参是一个Collection接口的实现类,这个方法的作用是,删除你的ArrayList与参数c中重复的数据,下面来看一下代码:

    public boolean removeAll(Collection<?> c) {
        // c不能为null
        Objects.requireNonNull(c);
        // 核心方法在这里,传入false代表删除elementData和c中重复的元素
        return batchRemove(c, false);
    }

    public boolean retainAll(Collection<?> c) {
        // c不能为null
        Objects.requireNonNull(c);
        // 核心方法在这里,传入true代表保留elementData和c中重复的元素,删除不通的元素,可以理解为取交集
        return batchRemove(c, true);
    }

    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        // 使用try-finally结构,支持快速失败
        try {
            // 将两个数组中重复的元素,被后一个元素前移,替换掉
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // 删除数组尾部无用的元素
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }
  • removeAll方法是用来删除两个数组中都存在的数据;
  • retainAll方法是用来删除两个数组中不一致的数据;

核心方法是batchRemove方法中,确保时间复杂度的一个不确定因素是c.contains方法,如果该方法的时间复杂度是O(1),那么整个batchRemove的时间复杂度将会是O(n)。

其他方法

还有一些其他的常用方法,在这里统一阅读分析一遍。

size与isEmpty方法

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

indexOf与lastIndexOf方法

    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;
    }

indexOf和lastIndexOf的时间复杂度都是O(n)

contains方法

    public boolean contains(Object o) {
        // 调用indexOf来判断是否存在
        return indexOf(o) >= 0;
    }

这里就验证了batchRemove方法中c.contains会确定该方法的时间复杂度的说法。如果removeAll传入的参数也是一个ArrayList,那么removeAll方法是时间复杂度将会是O(n^2)

trimToSize方法

    public void trimToSize() {
        modCount++;
        // 如果elementData的长度大于ArrayList的size,则说明有剩余空间,可以进行裁剪
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

虽然ArrayList没有自动缩容功能,但提供了一个trimToSize方法,可以让使用者主动调用,进行剩余空间的释放。

总结

从源码分析可以得出结论:

  • ArrayList内部是由数组实现的;
  • ArrayList在创建时候可以指定数组容量;
  • ArrayList的get和set方法的时间复杂度是O(1),添加元素到尾部的时间复杂度是O(1);
  • ArrayList内部数组容量不足时会自动扩容,扩容比例是1.5倍;
  • ArrayList从数组中间删除或添加元素性能不高;

所以,ArrayList的适用与顺序添加元素到数组中,并可以通过索引检索数据的场景,如果可以确定元素个数还可以减少扩容次数。

以上就是对ArrayList的源码分析,有不足之处欢迎大家随时指出。

XuePeng77
粉丝 55
博文 195
码字总数 275416
作品 0
丰台
私信 提问
加载中
请先登录后再评论。
Flappy Bird(安卓版)逆向分析(一)

更改每过一关的增长分数 反编译的步骤就不介绍了,我们直接来看反编译得到的文件夹 方法1:在smali目录下,我们看到org/andengine/,可以知晓游戏是由andengine引擎开发的。打开/res/raw/at...

enimey
2014/03/04
5.9K
18
beego API开发以及自动化文档

beego API开发以及自动化文档 beego1.3版本已经在上个星期发布了,但是还是有很多人不了解如何来进行开发,也是在一步一步的测试中开发,期间QQ群里面很多人都问我如何开发,我的业余时间实在...

astaxie
2014/06/25
2.7W
22
程序猿媛一:Android滑动翻页+区域点击事件

滑动翻页+区域点击事件 ViewPager+GrideView 声明:博文为原创,文章内容为,效果展示,思路阐述,及代码片段。文尾附注源码获取途径。 转载请保留原文出处“http://my.oschina.net/gluoyer...

花佟林雨月
2013/11/09
4.1K
1
实时分析系统--istatd

istatd是IMVU公司工程师开发的一款优秀的实时分析系统,能够有效地收集,存储和搜索各种分析指标,类似cacti,Graphite,Zabbix等系统。实际上,istatd修改了Graphite的存储后端,重新实现了...

匿名
2013/02/07
2.8K
1
日志分析平台 - Kibana

Kibana 是一个为 Logstash 和 ElasticSearch 提供的日志分析的 Web 接口。可使用它对日志进行高效的搜索、可视化、分析等各种操作。 环境要求: ruby >= 1.8.7 (probably?) bundler logstash...

匿名
2013/02/13
11.5W
1

没有更多内容

加载失败,请刷新页面

加载更多

MySql大表分页(附独门秘技)

问题背景 MySql(InnoDB)中的订单表需要按时间顺序分页查询,且主键不是时间维度递增,订单表在百万以上规模,此时如何高效地实现该需求? 注:本文并非主要讲解如何建立索引,以下的分析均建...

osc_8kei32r9
14分钟前
0
0
css中使用变量

2017年3月,微软宣布 Edge 浏览器将支持 CSS 变量。 这个重要的 CSS 新功能,所有主要浏览器已经都支持了。 声明css变量的时候,变量名前面要加两根连词线(--)。 变量名大小写敏感,--hea...

osc_mpdswsal
15分钟前
0
0
WAS 忘记密码

一、重置密码 1.首先关闭was,ps –ef|grep java 查看java进程号,然后kill -9 XXXX杀掉进程即可。或者使用命令./stopServer.sh server1 2.取消控制台安全验证 方法一:/opt/IBM/WebSphere/...

osc_1i3ltp99
16分钟前
0
0
npm install的--save选项是什么? - What is the --save option for npm install?

问题: I saw some tutorial where the command was: 我看到了一些命令所在的教程: npm install --save What does the --save option mean? --save选项是什么意思? Not able to find the......

fyin1314
16分钟前
0
0
C#使用读写锁三行代码简单解决多线程并发写入文件时线程同步的问题

在开发程序的过程中,难免少不了写入错误日志这个关键功能。实现这个功能,可以选择使用第三方日志插件,也可以选择使用数据库,还可以自己写个简单的方法把错误信息记录到日志文件。 选择最...

osc_7cws6vmd
17分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部