转载

ArrayList详解-源码分析

ArrayList详解-源码分析

1. 概述

在平时的开发中，用到最多的集合应该就是ArrayList了，本篇文章将结合源代码来学习ArrayList。

  • ArrayList是基于数组实现的集合列表
  • 支持任意性的访问（可根据索引直接得到你想要的元素）
  • 线程不安全
  • 支持动态扩容
  • 查询快，增删慢
  • ...

这些大家应该都很清楚，下面根据源代码来深入分析一下ArrayList。

2. ArrayList类声明

源代码如下所示：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

初步分析：

  1. ArrayList类继承于AbstractList抽象类
  2. ArrayList类实现了List、RandomAccess、Cloneable、Serializable接口

继续分析一下：

  • AbstractList抽象类其实已经实现了Collection接口中大部分方法
  • 实现了RandomAccess接口，所以支持任意性访问（随机访问）
  • 实现了Cloneable接口，说明重写了 clone()方法，支持拷贝（Cloneable 接口只是个合法调用 clone() 的标识（marker-interface)，一个对象想调用clone()方法，则该类必须实现Cloneable 接口，否则会报错 CloneNotSupportedException）
  • 实现了Serializable接口，支持序列化操作

3. 成员变量

源代码如下所示：

private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    
    private int size;

初步思考：

  1. 一共有6个变量，各自的作用？

  2. 有两个空数组，只是命名不一样，为什么？

继续分析：

  1. 各个变量的作用：
    • serialVersionUID： 序列化版本号
    • DEFAULT_CAPACITY：默认容量大小
    • EMPTY_ELEMENTDATA：空数组时的引用
    • DEFAULTCAPACITY_EMPTY_ELEMENTDATA：初始化时默认的空数组
    • elementData：实际存储集合元素的数组
    • size：实际元素的数量（int类型默认值为0）
  2. 两个空数组：
    • 分别用于默认初始化和传入容量时的初始化

4. 构造方法

源代码如下所示：

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

   
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // 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;
        }
    }

初步思考：

  1. 提供了三个构造方法
  2. 分别对应无参构造、指定集合容量的构造以及通过Collection的子类来构造一个ArrayList对象

继续分析：

  1. 无参构造：

    • 直接将DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空数组赋值给elementData（注意：此时ArrayList的数组长度还是0）

  2. 指定容量构造：

    • 参数大于0： 创建一个该参数大小的数组，赋值给elementData
    • 参数等于0： 将成员变量EMPTY_ELEMENTDATA数组赋值给elementData
    • 参数小于0： 抛出异常

  3. 传入Collection子类对象构造：

    public ArrayList(Collection<? extends E> c) {
        /**
        *将传入的集合转换为一个Object类型的数组，并将此数组的引用赋给elementData
        */
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {// 转换后的数组不为空时
            /**
            * 判断转换后的数组是不是Object[]数组
            * 如果不是的话，就把它复制为一个Object[]数组，进行赋值
            */
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 转换后的数组为空，用成员变量EMPTY_ELEMENTDATA来辅助
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    toArray()方法源代码如下:

    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    Arrays类的copyOf()方法源代码如下：

    @SuppressWarnings("unchecked")
    public static <T> T[] copyOf(T[] original, int newLength) {
        // 此处的copyOf()调用了本类的重载方法
        return (T[]) copyOf(original, newLength, original.getClass());
    }

    重载方法源代码如下所示：

    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

    代码分析：

    • 使用三元运算符进行判断传入数组的类型

    • 如果传入的数组类型强转为Object[]数组为true，则创建一个Object[newLength]数组赋值给copy

    • 如果为false，则利用反射获取到传入数组的类型，创建一个该类型的指定长度的数组赋值给copy

  • 调用native方法进行赋值

  • 最后返回copy

    调用链最后调用到了native方法上：

    public static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos,
                                        int length);
/**
* 参数说明：
* src：源对象 
* srcPos：源数组中的起始位置 
* dest：目标数组对象 
* destPos：目标数据中的起始位置 
* length：要拷贝的数组元素的数量
*/

源代码中最后都调用到了native方法，只能看到方法名和参数，看不到具体的实现，对native方法做个简单的介绍吧。

native声明的接口方法： Java代码和本地C代码进行互操作的API，称为Java Native Interface (Java本地接口)。也就是说，带有native标记的方法，都是使用C语言来实现的，读者了解到这里即可，感兴趣的可以去查阅下相关资料，这里就不多阐述了。

5. 常用方法分析

  • add(E e)

源代码如下所示：

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

初步分析：

  1. 调用一个ensureCapacityInternal()方法，ensure Capacity Internal 直接谷歌翻译，意思是确保内部容量，此方法内应该就隐藏着ArrayList动态扩容的方法了！
  2. 将传入参数e，赋值给elementData[]数组中下标为size++的元素
  3. 返回true

继续跟踪ensureCapacityInternal()方法，该方法相关源代码如下所示：

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

分析：

  1. 先对elementData数组进行空数组判断，注意：这里是直接使用 ==运算符来进行判断的，回顾下前面讲到的ArrayList的无参构造方法 
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

发现了没？如果使用默认的构造方法，调用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组，执行add()方法之前，ArrayList数组的长度都是零，添加第一个元素后，数组的长度就变为10了。

  1. 下一个方法是ensureExplicitCapacity()，我们继续跟踪。

该方法源代码如下所示：

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

初步分析：

  • 出现了一个前面没看到的变量modCount
  • 里面还有一个grow()方法，ArrayList能够动态扩容的原因就在这个方法里面了，八九不离十了！grow这个单词我还是认识的，哈哈哈~~~

继续分析：

  1. 经过追踪，发现modCount是ArrayList 的父类AbstractList的一个成员变量，作用是记录ArrayList的size变化，添加元素时，该变量会自增一次。
  2. minCapacity变量是要添加元素在elementData数组里的索引，当该变量值超过elementData数组长度的时候，elementData数组就要进行动态扩容了！

接下来，看下grow()方法的源代码，马上就要揭开ArrayList能够动态扩容的根本原因了，想想还有些激动，哈哈~

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

分析：

  1. 将当前未添加新元素的elementData的数组长度赋值给oldCapacity变量，表示旧数组的容量

  2. 定义一个变量newCapacity，表示新数组的容量，新数组的容量大小为旧数组容量的1.5倍

    • 此处用到了移位操作，>>是移位运算符，表示带符号数右移
    • 向右移动n位，等同于除以2的n次方

  3. 此处需要注意一个地方，如果oldCapacity + (oldCapacity >> 1)执行的结果超过了int的最大值，即2的31次方减1，那么新数组的长度将变为负数

  4. 下面就是比较新数组容量和旧数组的容量，将较大的容量赋值给新数组

  5. 如果新数组的容量大小超过了定义的MAX_ARRAY_SIZE大小，那么将调用hugeCapacity()方法

代码如下：

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

  • 传入的容量是负数，考虑到了数值溢出，抛出异常

  • 传入的容量超过了MAX_ARRAY_SIZE大小，则将Integer.MAX_VALUE的值进行返回，否则返回MAX_ARRAY_SIZE

  1. 最后调用Arrays.copyOf()方法，将旧数组复制到新数组中，至此便完成了数组的动态扩容

  • add(int index, E element)

源代码如下所示：

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

基于add()方法的分析，分析如下：

  1. 判断索引是否越界
  2. 复制数组，进行移动
  3. 将传入参数赋值给指定下标的数组元素
  4. 集合长度加1

rangeCheckForAdd()方法源代码如下所示：

private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

分析如下：

  • 索引的上限是实际元素的长度，下限是0
  • 超过这两个边界值就会抛出异常

注意： 由于此处判断范围上限取的实际元素的个数，那么就会造成一个情况，我们使用指定容量的构造方法，创建了一个ArrayList对象，然后使用add（int index, E element）方法时，当添加的index不是0时，就会报错

举例如下：

public static void main(String[] args) {
		
		List<String> a = new ArrayList<>(12);// 初始化指定了数组的容量为12
		a.add(5, "element");
		
	}
//结果如下：
//  Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 5, Size: 0
//	 at java.util.ArrayList.rangeCheckForAdd(ArrayList.java:661)
//	 at java.util.ArrayList.add(ArrayList.java:473)
//	 at test.TestAddArrayList.main(TestAddArrayList.java:11)

  • get(int index)

源代码如下所示：

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

E elementData(int index) {
        return (E) elementData[index];
    }

简要分析：

  1. 首先判断索引是否在正确的范围之内，此处仅仅只是判断了上限为实际元素个数
    • 超过上限时的报错提示信息为"Index: "+index+", Size: "+size
    • 当index为负数时的报错提示信息则是：index，仅仅只是显示你访问的index值
  2. 调用elementData()方法，直接返回对应索引位置的元素

  • remove(int index)

源代码如下所示：

public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

分析：

  1. 首先对index进行判断是否在正确的范围内
  2. 移除元素使得数组长度发生了变化，所以modCount++
  3. 计算需要移动的元素个数
  4. 调用arraycopy()方法进行数组元素的复制和移动
  5. 将数组实际长度的最后一位元素赋值为null，方便GC进行回收
  6. 最后返回索引位置的元素

不难看出， 移除元素实际上也是数组的复制和移动 。

  • indexOf(Object o)

源码如下所示：

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

indexOf方法是返回某元素在ArrayList对象里的下标（索引）。

分析：

  1. 区分两种情况

  2. 查询元素为null时，使用==运算符进行判断，返回索引

  3. 非null元素时，使用equals()方法来判断（ps:由此处调用的equals()方法，可以看出为什么不支持基本类型的元素）

  4. 当查询的元素不存在列表中，返回-1

ArrayList中还有很多方法，篇幅有限，在此不再赘述。

6. 总结

ArrayList是开发中用的最多了一个集合类了，很多时候我们只是停留在使用上面，没有深入的去学习，分析，为什么是这样？为什么会这样？有时候遇到问题了，也只能两眼一抹黑，不知道具体原因是什么，多看源码，多学习，提高解决问题的能力，一点点的进步，就好。

原文  http://www.cnblogs.com/strive-for-life/p/12923608.html
正文到此结束
所属分类： 编程技术 Java

热门推荐

相关文章

阿里云首购8折
说给你听

本文目录
随机标签
书籍教程
springboot-demo Java入门教程 bootstrap3 CSS Apache基础教程 php ionic 教程 Python mysql教程 eclipse Ubuntu VPS系统配置 AngularJS 教程 MongoDB教程 Struts2教程 Redis教程 Spring教程 Git教程 Jenkins进阶系列 openfire参考指南 Java设计模式 HBase教程 Maven教程 hibernate教程 Docker 教程 memcached教程 Quartz指南 Hive教程 Ant教程 ANTLR教程 SpringCloud java实例教程 springcloud-demo XStream教程 Hazelcast教程 Elastic-Job-Lite 深入浅出MyBatis SVN教程 ibaties教程 rabittmq教程 solr教程 Hadoop教程 WebService CXF学习 JPA教程 ActiveMQ中文指南 java-demo Java内存模型 dubbo教程 python3-demo Linux入门视频教程
近期评论
  1. 1 Spring Cloud Consul实现选举机制
  2. 2 Spring Boot集成ShedLock实现分布式定时任务
  3. 3 利用oss进行数据库和网站图片备份
  4. 4 Spring Cloud Stream实现数据流处理
  5. 5 Python3访问MySQL数据库快速入门Demo
  6. 6 Github开源项目作者可以免费申请 JetBrains 全家桶
  7. 7 Spring Cloud Vault快速入门Demo
  8. 8 Spring Cloud Gateway快速入门Demo
  9. 9 Spring Cloud Contract快速入门Demo
  10. 10 Spring Cloud Consul快速入门Demo
网站信息
  • 文章总数：82,714 篇
  • 文件总数：284,287 个
  • 标签总数：2,393 个
  • 分类总数：85 个
  • 留言数量：2,560 条
  • 在线人数：609 人
  • 运行天数：4,409天
  • 最后更新：2024年11月22日01点
Loading...

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

[HBLOG]公众号 HBLOG HBLOG