ArrayList源码分析

x33g5p2x  于2021-08-23 转载在 Java  
字(7.2k)|赞(0)|评价(0)|浏览(393)

一 前言

知识追寻者目前的系列都是基于jdk1.8进行学习分析;本篇源码分析会进行每步分析,当所有方法分析完最后还会做个大总结;如果不爱看源码分析步骤,只要面试最终结论的读者可以看看文末的总结就行了;

二 ArrayList源码分析

2.2 空参构造方法源码分析

调试代码

  public static void main(String[] args) {
        // 初始化长度为0
        ArrayList list = new ArrayList();//断点
  }      

首先刚刚开始调到断点时,会默认显示ArrayList初始化长度为0;

其次进入构造方法

   public ArrayList() {
        // elementData 是 Object[] ---> 故 Arraylist底层由对象数组实现
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

可以看出就是一个DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值给 elementData ;

先看看什么是DEFAULTCAPACITY_EMPTY_ELEMENTDATA,源码如下,可以看出是final修饰的Object[]数组;

   // 共享的空数组实例,当第一个元素添加时从EMPTY_ELEMENTDATA辨别出扩张大小
   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

再看看elementData是什么,源码如下

    // 动态数组缓冲区,ArrayList存储元素的地方,elementData长度就是ArrayList长度
    // 当第一个元素添加时 DEFAULT_CAPACITY 被被扩张        
    transient Object[] elementData; // non-private to simplify nested class access

后面再进入调试会进入父类,给张类图看看ArrayList的都继承了哪些父类

image.png

真正的步入顺序如下

AbstractList --> AbstractCollection--> Object

有趣的是知识追寻者在分析过程中还发行执行了如下一行代码,也就是记录list大小改变的次数,如果发生了无法预料的改变就会抛出ConcurrentModificationException异常;这就解释了为什么在迭代器中不能进行使用List的remove等操作(这边就不对迭代器Iterator进行扩展,后面会出相关源码分析);这是由fail-fast机制提供的方案;

科普fail-fast 机制

fail-fast 机制 就是快速失败机制,也就是在集合发送结构改变的时候会抛出ConcurrentModificationException异常,用于快速的对bug进行检测做出失败判定;

// 记录list被修改的次数,也就是大小改变的次数
// 如果在迭代器中使用迭代,做出了不是期待的改变就会抛出ConcurrentModificationException
protected transient int modCount = 0;

Tip1 : 以后面试答List集合在迭代过程中调用了remove方法后会发生什么情况?答:我看过知识追寻者ArrayList源码系列文章,是由于 fail-fast机制检测到List发生结构变化抛出了 ConcurrentModificationException 异常;瞬间高大尚有木有,难道我答是由于集合在迭代过程中发生了remove,add, set , next, previous操作?太细节了吧,太low了吧,有实力的面试官就知道你水平了,小伙子背的不错额!

Tip: ArrayList底层基于动态Object数组实现

2.2 初始化容量源码分析

ArrayList的初始化容量大体就给定初始化值,则创建对应大小的Object数组;没有给定初值值,则使用成员共享遍历空Object数组;否则其它情况抛出非法参数异常;

测试代码

public static void main(String[] args) {
        // 初始化为0
        ArrayList list = new ArrayList(5);
    }

源码

    public ArrayList(int initialCapacity) {
        // 初始化容量大于0,创建指定大小的object数组
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        // 初始化容量等于0,空 object数组
        } else if (initialCapacity == 0) {
            // 其中 private static final Object[] EMPTY_ELEMENTDATA = {};
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            // 否则抛出非法参数异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

Tip 给定指定大小的容量进行初始化ArrayList会返回指定大小的ArrayList

2.3 add方法源码分析

测试代码

   public static void main(String[] args) {
        // 初始化为0
        ArrayList list = new ArrayList();
        list.add("a");
        System.out.println(list);
    }

首先:先看看add源码

  public boolean add(E e) {
        // 确保容量
        // size就是list的大小,也就是集包含合的元素个数
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

可以看见有个ensureCapacityInternal(size + 1) 方法进行了确保容量,直接从这个表达式上可以得出结论在原来的数组长度上加1;进入看看

    private void ensureCapacityInternal(int minCapacity) { 
    		// 期望大小 添加1个a 所以是1
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
        	// 判定是否是空数组
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); 
            // 在1 和 10(DEFAULT_CAPACITY)中取最大值
        }

        ensureExplicitCapacity(minCapacity);//此时就是10
    }

调试源码上可以直接得出结论如果,由于加入的的元素是1,所以期望容量为1,当经过与默认的初始容量比较后取最大值,此时就是10;所以添加一个元素后ArrayList的期望扩容大小扩大到了10

我们看下确保具体的扩容,集合修改次数 加1 ,如果期望扩容大于大于了ArrayList长度,会进行再次扩容;

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//list改变次数加1

        // overflow-conscious code
        //如果期望扩容小于元素ArrayList长度,会进行再次扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);//扩容
    }

看下扩容grow(minCapacity); 其内部实现思路也很简单,每次扩容都是在原来List长度上加 50%;如果期望容量超过了数组最大长度 (int整数最大值 - 8) 就使用int整数最大值 作为数组长度;最后会进行数组拷贝和重新指定数组大小;这边值的一说是 数会保留8个位置作为数组头的预留位置,如果分配长度超过数组最大长度MAX_ARRAY_SIZE就会抛出OutOfMemoryError异常,;VM 通常都会限制这个大小,实际中可能没到 MAX_ARRAY_SIZE 就抛出最大异常了,更不用说 int 的最大值;

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;//oldCapacity=0 当前元素a未插入时的长度
        int newCapacity = oldCapacity + (oldCapacity >> 1);//newCapacity=0 原始长度 + 原始长度左移一位,也就是 除以2; 如果长度10,经过扩容后就是15
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;//(0-10)< 0 故 新的容量为10;即 newCapacity=10
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);///如果期望容量大于数组容量最大值就使用Int最大值;否则使用数组最大值
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);//数组拷贝,容量为10
    }

hugeCapacity(minCapacity); 源码如下

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

Tip : ArrayList 初始化容量为0,添加一个元素后扩容到10;超过10后每次在原有的数组长度上 加50%长度进行扩容;ArrayList 的 最大长度为 Integer.MAX_VALUE - 8; 最后会调用 Arrays.copyOf 方法重新赋值 Object数组

2.4 set 源码分析

测试代码

    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add("a");
        list.set(0,"b");
        System.out.println(list);
    }

首先进入set方法

   public E set(int index, E element) {
        rangeCheck(index);// index =0 ; element = b ;检测ArrayList是否越界

        E oldValue = elementData(index);//获取原来数组索引对象
        elementData[index] = element;//根据对应重新赋值
        return oldValue;//返回对象
    }

第一行就是检测ArrayList是否越界

  private void rangeCheck(int index) {
        if (index >= size) // 给定索引大于等于数组长度抛出异常
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

第二行是获取原来Object数组位置上的对象;

  @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];// index =0 ; elementData 是个 object[]
    }

第三行根据索引重新赋值,最后返回;那么 这边 oldValue 就是 elementData[index];

Tip : set方法就是重新赋值数组位置上的值;相当于更新操作;如果给定位置上没有元素,会抛异常;

2.5 get 源码分析

测试代码

    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add("a");
        list.get(0);
        System.out.println(list);
    }

进入get方法

  public E get(int index) {
        rangeCheck(index);//检测数组是否越界

        return elementData(index);//获取数组对应位置上的对象
    }

与set方法后面一致,还是调用elementData获取数组对应位置上的对象;get 方法没什么奇特点;

2.6 remove源码分析

测试代码

    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add("a");
        list.add("b");
        list.remove(0);
        System.out.println(list);
    }

源码如下,整体

    public E remove(int index) {
        rangeCheck(index);// 检测数组是否越界

        modCount++;//修改次数 +1
        E oldValue = elementData(index);//获取数组index位置上的值 oldValue=a

        int numMoved = size - index - 1;// numMoved = 2-0-1 = 1;表示移动的数量
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);//数组拷贝
        elementData[--size] = null; // clear to let GC do its work.数组长度 -1 位置置为null.

        return oldValue;//返回移除的值
    }

这边可以对arraycopy方法进行一个简要说明

public static native void arraycopy(Object src,int  srcPos,Object dest, int destPos,int length);

参数

  • src 要被复制的数组
  • srcPos 开始复制的下标
  • dest 目标数组
  • destPos 开始存放数据的位置
  • length 放置个数

说完不懂的人肯定还是一头雾水,我们举个栗子看看

    public static void main(String[] args) {
        int[] src = new int[]{1,2,3,4,5};
        int[] desc = new int[]{6,7,8,9,10};
        System.arraycopy(src,2,desc,1,2);
        Arrays.stream(desc).boxed().forEach(des ->{
            System.out.println(des); // 6 ,3, 4, 9, 10
        });
    }

src 从 位置index = 2 开始取值,取几个呢取length = 2 个 (也就是3和4);将其放入 desc 的index = 1 的位置开始,此时就会完成覆盖也就是(3,4会覆盖7,8)

原理懂咧,那么刚刚那个源码里面是 src 和 desc 都是一同一个数组,假定要删除index =0 (即元素1);该复制几位?movNum = size - index -1 = 5 - 0- 1 = 4 ; 需要复制4位;src 的 2,3,4,5 就会覆盖 1,2,3,4;最终得到 2 ,3,4,5,5; 最后将 最后一个元素置为 null 就完成了删除操作!! 哦哦哦 你学会了么,知识追寻者学会了,瞬间高大尚,以后写数据结构又有的完了;

    public static void main(String[] args) {
        int[] src = new int[]{1,2,3,4,5};
        int[] desc = new int[]{1,2,3,4,5};
        System.arraycopy(src,1,desc,0,4);
        Arrays.stream(desc).boxed().forEach(des ->{
            System.out.println(des); // 2,3,4,5,5
        });

    }

Tip remove 操作 底层调用的是System.arraycopy 方法,将 要删除元素后面所有元素进行拷贝至删除元素索引位置,再将数组尾节点置为null

三 总结

  1. 集合在迭代过程中发生了remove,add, set , next, previous操作,会触发fast-fail机制,做出了不是期待的改变就会抛出ConcurrentModificationException;
  2. ArrayList底层基于动态Object数组实现, 所有数组的优缺点和ArrayList差不多,查找快把,增删慢;
  3. ArrayList 初始化容量为0,添加一个元素后扩容到10;超过10后每次在原有的数组长度上 加50%长度进行扩容;ArrayList 的 最大长度为 Integer.MAX_VALUE - 8;给定指定大小的容量进行初始化ArrayList会返回指定大小的ArrayList;
  4. set方法就是重新赋值数组位置上的值;相当于更新操作;如果给定位置上没有元素,会抛异常;
  5. remove 操作 底层调用的是System.arraycopy 方法,将 要删除元素后面所有元素进行拷贝至删除元素索引位置,再将数组尾节点置为null;

半天就过去了;知识追寻者有空再补ArrayList其它方法的源码吧;

相关文章