ArrayList源码分析(JDK1.8)

Stella981
• 阅读 620

概述

ArrayList底层是基于 数组 实现的,并且支持 动态扩容 的动态数组(变长的集合类)。ArrayList允许空值和重复的元素,当向ArrayList中添加元素数量大于其底层数组容量时,会通过 扩容机制 重新生成一个容量更大的数组。另外,由于ArrayList底层数据结构是数组,所以保证了在O(1)复杂度下完成随机查找操作。ArrayList是非线程安全的,在并发环境下,多个线程同时操作ArrayList会引发不可预知的错误。

ArrayList源码分析(JDK1.8)

从上面的类图可以看出,ArrayList实现了4个接口和继承了1个抽象类,分别是:

  • List接口:主要提供了数组的添加、删除、修改、迭代遍历等操作;

  • Cloneable接口:标识克隆操作;

  • Serializable接口:标识可序列列化操作;

  • RandomAccess接口:标识可随机访问操作;

  • 继承AbstractList抽象类,主要提供迭代遍历相关操作。

属性

ArrayList的属性比较少,只有两个属性:elementData和size。

1 private static final int DEFAULT_CAPACITY = 10;2 3 private static final Object[] EMPTY_ELEMENTDATA = {};4 5 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};6 // 底层存放元素的数组7 transient Object[] elementData;8 // elementData数组中元素的数量 9 private int size;

构造方法

ArrayList有3个构造方法,分别如下:

  • ArrayList(int initialCapcity):根据传入的initialCapacity初始化容量来创建elementData数组;

  • ArrayList():无参构造方法;

  • ArrayList(Collection<? extends E> c):使用传入的集合C作为ArrayList的elementData;

    // 1. ArrayList(int initialCapacity)构造方法// 需要注意:当初始化容量initialCapacity为0时,使用EMPTY_ELEMENTDATA对象创建一个空数组,在添加元素的时候,会进行扩容创建需要的数组public ArrayList(int initialCapacity) { if (initialCapacity > 0) {       // 初始化容量大于0,创建Object数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) {       // 初始化容量为0时,使用EMPTY_ELEMENTDATA对象 this.elementData = EMPTY_ELEMENTDATA; } else {       // 参数异常 throw new IllegalArgumentException("Illegal Capacity:" + initialCapacity); }}// 2. ArrayList()无参构造方法public ArrayList() {     // 实际创建的时候是空数组,在首次添加元素的时候,才会初始化容量为10的数组 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}// 3. ArrayList(Collection<? extends E> c)构造方法public ArrayList(Collection<? extends E> c) {     // elementData指向c.toArray() elementData = c.toArray(); if ((size = elementData.length) != 0) {       // 如果集合元素的类型不是Object.class类型,则拷贝成Object.class类型 // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; }}

插入元素

对于数组(线性表)结构,插入操作分为两种情况:① 在元素序列尾部插入;② 指定位置插入;对于ArrayList插入方法有4个:

  • public boolean add(E e):在数组尾部插入元素;

  • public void add(int index, E element):在数组指定index位置插入元素;

  • public boolean addAll(Collection<? extends E> c):在数组尾部插入多个元素;

  • public boolean addAll(int index, Collection<? extends E> c):在数组指定index位置插入多个元素;

    public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true;}

主要关注ensureCapacityInternal方法具体做了什么事情: 现有的数组容量是否支持新增元素的需求,如果不满足,则考虑扩容操作 。

通过底层源码,我们看看JDK的设计者是如何考虑的:

STEP-1 :首先是ensureCapacityInternal(int minCapacity)方法,该方法的主要功能是 确保数组内部容量足以满足本次插入操作 。

该方法实际是首先调用calculateCapacity(Object[] elementData, int minCapacity)方法, 计算满足本次插入操作所需要的容量 ,然后调用ensureExplicitCapacity(int minCapacity)方法, 保证容量足够 ;

/*** 确保数组容量足够添加元素** @param minCapacity 最小容量*/private void ensureCapacityInternal(int minCapacity) {    // 计算容量    int capacity = calculateCapacity(elementData, minCapacity);    // 确保容量足够 -- 如不足够则触发扩容    ensureExplicitCapacity(capacity);}

STEP-2 :考量calculateCapacity(Object[] elementData, int minCapacity)方法是如何计算本次插入操作所需容量的。

如果elementData数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA:没有指定初始化容量时;则会判断是最小容量minCapacity和DEFAULT_CAPACITY的大小,取两者中较大者。

/*** 计算容量* @param elementData 元素数组* @param minCapacity 最小容量* @return int 计算后的数组容量大小*/private static int calculateCapacity(Object[] elementData, int minCapacity) {    // 如果是DEFAULT_CAPACITY ,那么就会从10开    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        // DEFAULT_CAPACITY 定义:private static final int DEFAULT_CAPACITY = 10;        return Math.max(DEFAULT_CAPACITY, minCapacity);    }    // 如果不是则直接返回需要的最小容量    return minCapacity;}

STEP-3 :考量 ensureExplicitCapacity 如何确保数组容量足够本次新增操作的: 当所需的最小容量minCapacity大于elementData.length数组长度时 ,则触发 grow() 执行扩容。

/**  * 确保数组剩余容量足够  * @param minCapacity 最小容量  */private void ensureExplicitCapacity(int minCapacity) {    // 在父类 AbstractList中定义了 用以记录数组修改的次数(注意是次数)    modCount++;    // minCapacity代表的是本次(新增)操作所需要的最小容量, elementData.length代表的是当前元素数组的长度    // 可能写成 minCapacity > elementData.length 更好理解    if (minCapacity - elementData.length > 0) {        // 扩容可指定最小的容量(满足当前需求)        grow(minCapacity);    }}

/**  * 扩容机制  * 旧容量经过运算扩展为1.5倍后与最小容量minCapacity进行比较  * 如果大于则采用旧容量扩展1.5倍后的大小,否则采用最小容量minCapacity  * @param minCapacity 新增操作所需最小容量  */private void grow(int minCapacity) {    // 旧容量大小 elementData数组的长度    int oldCapacity = elementData.length;    // 新容量大小 == 旧 + 旧的位运算 (向右移动1位)   大致上是原大小的1.5倍    // ArrayList扩容机制int newCapacity = oldCapacity + (oldCapacity >> 1);    // 如果计算出来的新容量小于 指定的最小容量,则创建指定的最小容量大小的新数组    // 可理解为 newCapacity < minCapacity 不知道为啥会喜欢写成减法的形式。。。    if (newCapacity - minCapacity < 0) {        newCapacity = minCapacity;    }    // 如果新容量大于最大值(会出现内存不足的情况)    // private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8    if (newCapacity - MAX_ARRAY_SIZE > 0) {        // hugeCapicaty方法用以当 newCapacity超过指定范围的时候,确保创建的数组不会溢出        newCapacity = hugeCapacity(minCapacity);    }    // 数组拷贝,将原有的数据搬到新的数组上    elementData = Arrays.copyOf(elementData, newCapacity);}

综述:经过上述过程的研讨,我们知道ArrayList插入操作的整个过程:首先计算插入元素所需的最小容量;然后判断当前elementData数组是否支持本次插入操作,当容量不足时则触发扩容机制,将原有数组的元素拷贝到新数组上,然后往后追加新的元素。【备注,其他3个插入操作过程基本类似,可自行分析源码】

查找元素

public int indexOf(Object o):查找首个为指定元素o的位置,源码如下:

/**  * 查找首个为指定元素 o 的位置  * @param o 被查找元素  * @return int 如果存在则返回对应index 不存在返回-1  */@Overridepublic int indexOf(Object o) {    // 从这里我们其实也可以看出,ArrayList是支持存储null值的    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;            }        }    }    // 不存在则返回 -1    return -1;}

删除元素

删除元素的方法主要有4个,分别如下:

  • public E remove(int index):移除指定位置的元素,并返回该位置的原元素;

  • public boolean remove(Object o):移除首个为o的元素,并返回是否移除成功;

  • protected void removeRange(int fromIndex, int toIndex):批量移除[fromIndex, toIndex)内的多个元素,注意 包左不含右 ;

  • public boolean removeAll(Collection<?> c):批量移除指定的多个元素;

public E remove(int index) 继承于  AbstractList 抽象类,删除指定位置的元素,并返回该位置上的原元素。

/**  * 删除指定位置index的元素,并返回该元素  * @param index  * @return E  */public E remove(int index) {    // index 合法性校验,不合法则抛出相关异常    rangeCheck(index);    // 修改数组的次数 + 1    modCount++;    // 获取index下标对应的value,elementData方法其实就是 return (E) elementData[index]    E oldValue = elementData(index);    // 每删除一个元素,都需要对原有的数组进行移动,所以从这里也可以看出ArrayList并不是特别适合于删除操作比较多的场景~    // 需要移动的元素的数量    int numMoved = size - index - 1;    if (numMoved > 0)        System.arraycopy(elementData, index + 1, elementData, index, numMoved);    // 数组的最后一个位置设置为null  帮助GC    elementData[--size] = null;    return oldValue;}private void rangeCheck(int index) {    // index 合法性校验    if (index >= size) {        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));    }}

【注意】:删除源码是比较简单易读的,注意一点:凡是涉及到index的操作首先需要参数合法性检查,然后再获取index对应下标的元素,再对index位置后的元素向前移动,最终返回被删除的元素值。

转换成数组

  • public Object[] toArray():将ArrayList转换为Object[]数组;

  • public T[] toArray(T[] a):将ArrayList转换为指定T泛型的数组;

    /** * 将ArrayList转换成Object类型数组 * @return Object[] */@Overridepublic Object[] toArray() { // 返回的是Object[] 类型,需要注意;转换成数组就相当于是将 ArrayList的底层elementData暴露出去而已 return Arrays.copyOf(elementData, size);}public static T[] copyOf(T[] original, int newLength) { return (T[]) copyOf(original, newLength, original.getClass());}

    /** * 将ArrayList转换成指定泛型的数组 * @param a * @return T[] */@Override@SuppressWarnings("unchecked")public T[] toArray(T[] a) { // 《1》如果传入的数组小于 size 的大小,直接拷贝一个新的数组返回 if (a.length < size) { return (T[]) Arrays.copyOf(elementData, size, a.getClass()); } // 《2》否则直接拷贝数组即可 System.arraycopy(elementData, 0, a, 0, size); // 额 这个的目的是?有点没看懂 if (a.length > size) { a[size] = null; } // 返回传入的a,但是考虑到《1》的时候会返回新的数组,所以即时《2》返回a数组,最好还是按照 a = list.toArray(a); 来使用 return a;}

【注意】:我们在调用toArray()方法时,可能会遇到异常java.lang.ClassCastException:这是因为toArray()方法返回的类型是Object[],如果我们将其转换为其他类型,可能排除异常。这是 因为Java并不支持向下转型 ,所以当我们需要将ArrayList转换成数组并且指定类型的时候,应该使用指定泛型的方法。

其他方法

/**  * 判断集合中是否含有元素 o  * 可以看出,contains方法其实就是依赖的 indexOf方法  * @param o  * @return boolean  */@Overridepublic boolean contains(Object o) {    return indexOf(o) >= 0;}/**  * 获取指定index位的元素  * @param index  * @return E  */@Overridepublic E get(int index) {    // 参数检查    rangeCheck(index);    // 相当于直接返回 elementData[index]    return elementData(index);}/**  * 设置指定index位置的元素,并且返回该index位置旧元素值  * 并返回旧元素的值(相当于替换)  * @param index  * @param element  * @return E  */@Overridepublic E set(int index, E element) {    // 参数检查    rangeCheck(index);        E oldValue = elementData(index);    elementData[index] = element;    return oldValue;}/**  * 清空集合  */@Overridepublic void clear() {    // 数组操作次数 + 1,虽然不知道记录这个东东有啥子用    modCount++;    // 遍历数组,全部设置为null,同时更新size值    for (int i = 0; i < size; i++) {        elementData[i] = null;    }    size = 0;} /**   * 创建子数组   * 注意:subList并不是只读数组,而是和父数组共享相同的 elementData 的数组,换句话说,对subList的操作会影响到 父数组   * 只不过是fromIndex 和 toIndex限制了查看的范围   * @param fromIndex 开始下标   * @param toIndex 结束下标   *                是一个 [fromIndex, toIndex)的效果   */public List<E> subList(int fromIndex, int toIndex) {    subListRangeCheck(fromIndex, toIndex, size);    return new SubList(this, 0, fromIndex, toIndex);}

总结

本文从源码的角度,主要总结了ArrayList的属性、构造方法、核心方法。有不准确之处,望指正!!!

作者:轩辕慕雨
原文地址:http://www.cnblogs.com/wfei-hlw-flying/p/14366043.html

END

版权申明:内容来源网络,版权归原创者所有。除非无法确认,我们都会标明作者及出处,如有侵权烦请告知,我们会立即删除并表示歉意。谢谢。

ArrayList源码分析(JDK1.8)

如果你觉得文章不错,文末的赞 👍 又回来啦, 记得给我「点赞」和「在看」哦~

本文分享自微信公众号 - JAVA高级架构(gaojijiagou)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
2年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
灯灯灯灯 灯灯灯灯
2年前
「JDK——ArrayList源码」超强解析,图文详解
ArrayList源码解析简介ArrayList是Java集合框架中非常常用的一种数据结构。继承自AbstractList,实现了List接口。底层基于数组来实现动态容量大小的控制,允许null值的存在。同时还实现了RandomAccess、Cloneable、Serializable接口,支持快速访问、复制、序列化操作。了解数组数组简单来说就是将所有的
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Chase620 Chase620
3年前
ArrayList底层
一、ArrayList集合底层数据结构1.ArrayList集合介绍List集合的可调整大小数组实现。2.数组结构介绍增删快:每次增加删除元素,都需要更改数组长度、拷贝以及移除元素位置。查询快:由于数组在内存中是一块连续空间,因此可以根据地址索引的方式快速获
Stella981 Stella981
2年前
List接口(动态数组)
List接口(动态数组)List集合类中元素_有序且可重复_ArrayList(重要)作为List接口的主要实现类线程不安全的,效率高底层使用Object\\elementData数组存储ArrayList的源码分析jdk7
Wesley13 Wesley13
2年前
Java集合ArrayList源代码详细解析
一、ArrayList简介  ArrayList是可以动态增长和缩减的索引序列,它是基于数组实现的List类。  该类封装了一个动态再分配的Object\\数组,每一个类对象都有一个capacity属性,表示它们所封装的Object\\数组的长度,当向ArrayList中添加元素时,该属性值会自动增加。如果想ArrayList中添加大
Wesley13 Wesley13
2年前
Java中ArrayList的使用
ArrayList类是一个特殊的数组动态数组。来自于System.Collections命名空间;通过添加和删除元素,就可以动态改变数组的长度。优点:1、支持自动改变大小2、可以灵活的插入元素3、可以灵活的删除元素局限:比一般的数组的速度慢一些;用法一、初始化:1、不初始化容量ArrayList
京东云开发者 京东云开发者
7个月前
分布式系统的主键生成方案对比 | 京东云技术团队
UUID​UUID(通用唯一识别码)是由32个十六进制数组成的无序字符串,通过一定的算法计算出来。为了保证其唯一性,UUID规范定义了包括网卡MAC地址、时间戳、名字空间(Namespace)、随机或伪随机数、时序等元素,以及从这些元素生成UUID的算法。
Python进阶者 Python进阶者
4个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这