ArrayList源码解析

目录

序言:ArrayList是Java集合中的基础中的基础,也是面试中常问常考的点,今天我们来点简单的,盘盘ArrayList

下面我凭自己的经验大概说一下如何看源码。

  • 先看继承结构,方便了解整体的逻辑和关系
  • 再看核心调用方法,看它做了什么,方便了解核心的功能
  • 得有看英文注释的习惯,毕竟它相当于说明书

ArrayList 简介

注:本篇文章所有分析,针对 jdk1.8版本

  1. ArrayList 的本质是可以动态扩容的数组集合,是基于数组去实现的List类
  2. ArrayList 的底层的数据结构是 Object[] 类型的数组,默认创建为空数组,采用懒加载的方式节省空间,每次采取1.5倍扩容的方式
  3. ArrayList 是线程不安全的,线程安全的 List 参考 Collections.synchronizedList() 或者 CopyOnWriteArrayList
    ArrayList源码解析插图

 

ArrayList源码分析

继承结构

ArrayList源码解析插图(1)
ArrayList源码解析插图(2)

大致结构如上图,先考虑三个问题:

1.为什么要继承 AbstractList,而让 AbstractList 去实现 List , 并不是直接实现呢 ?

这里主要运用了模板方法设计模式,设想一下,jdk 开发作者 还有一个类要实现叫 LinkedList ,它也有何 ArrayList 相同功能的基础方法,但是由于是直接实现接口的方式,这个 类 LinkedList 就没法复用之前的方法了

 

2.ArrayList 实现了哪些其他接口,有什么用 ?

RandomAccess 接口: 是一个标志接口, 表明实现这个这个接口的 List 集合是支持快速随机访问的。也就是说,实现了这个接口的集合是支持 快速随机访问 策略的,实现了此接口 for循环的迭代效率,会高于 Iterator

Cloneable 接口: 实现了该接口,就可以使用 Object.Clone()方法

Serializable 接口:实现序列号接口,表明该类可以被序列化

 

3. 为什么AbstractList 已经实现了 List接口了,作为父类ArrayList 再去实现一遍呢 ?
ArrayList源码解析插图(3)

作者说这是一个错误,一开始拍脑袋觉得可能有用,后来没用到,但没什么影响就留到了现在

 

类中的属性

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

 private static final long serialVersionUID = 8683452581122892189L;

 //默认初始容量为10
 private static final int DEFAULT_CAPACITY = 10;
 //空的对象数组
 private static final Object[] EMPTY_ELEMENTDATA = {};
 //缺省空对象数组
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 //集合容器,transient标识不被序列化
 transient Object[] elementData;
 //容器实际元素长度
 private int size;

}

  

核心方法

创建集合

1. 使用无参构造器

	/**
	* 默认无参构造器创建的时候其实只是个空数组,使用懒加载节省内存开销
    * Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
	*/
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

 

2. 创建时,指定集合大小,如何一开始就能预估存储元素的size,推荐用此种方式

public ArrayList(int initialCapacity) {
     /**
     * 如果initialCapacity > 0,就申明一个这么大的数组
     * 如果initialCapacity = 0,就用属性 EMPTY_ELEMENTDATA
     * Object[] EMPTY_ELEMENTDATA = {}
     * 如果initialCapacity < 0,不合法,抛异常 
     */
     if (initialCapacity > 0) { 
         this.elementData = new Object[initialCapacity];
     } else if (initialCapacity == 0) {
         this.elementData = EMPTY_ELEMENTDATA; 
     } else {
         throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
     }
}

  

添加集合元素

可以看出有四个添加的方式,我们挑选前两个常用方法讲解源码,其他基本差不多
ArrayList源码解析插图(4)

 

1. boolean add(E) 默认在末尾插入元素

/**
* 添加一个元素到list的末端
*/
public boolean add(E e) {
    	//确保内置的容量是否足够
        ensureCapacityInternal(size + 1);
    	//如果足够添加加元素放进数组中,size + 1
        elementData[size++] = e;
    	//返回成功
        return true;
}

//minCapacity = size + 1 
private void ensureCapacityInternal(int minCapacity) { 
        //确认容器容量是否足够
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//先计算容量大小,elementData是初始创建的集合容器,minCapacity= size + 1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //判断初始容器是否等于空
    	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //为空,就拿size + 1和默认容量10比,谁大返回谁
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    	//否则返回size + 1 
        return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
        //列表结构被修改的次数,用户迭代时修改列表抛异常(ConcurrentModifyException)
    	modCount++;
        /**
        * minCapacity 如果超过容器的长度,则进行扩容,两种场景
        * 1.第一次添加元素,minCapacity = size + 1,size = 0,在上个方法中会
        * 与默认的容器容量10进行大小比较最后为10,那么10 > 0,初始化容器
        * 2.添加到第10个元素,上个方法则返回 size + 1 = 11,11 > 10,需要扩容
        * 不然数组装不下了
        */
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}

//容器的扩容方法
private void grow(int minCapacity) {
        //将扩充前的容器长度赋值给oldCapacity
        int oldCapacity = elementData.length;
        //扩容后的newCapacity = 1 + 1/2 = 1.5,所以为1.5倍扩容
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        /**
        * 适用于初始创建,elementData为空数组,length = 0
        * oldCapacity = 0,但minCapacity = 10,此处则进行了初始化
        */
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
    	//如果新容量超过容量上限Integer.MAX_VALUE - 8,则会再尝试扩容
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //新的容量确定后,只需要将旧元素全部拷贝进新数组就可以了
        elementData = Arrays.copyOf(elementData, newCapacity);
}

//此方法主要是给集合赋最大容量用的 
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
    	/**
    	* 这一步无非再判断一次 
    	* size + 1 > Integ er.MAX_VALUE - 8 ?
    	* 如果大的话赋值 Integer.MAX_VALUE
    	* 说明集合最大也就 Integer.MAX_VALUE的长度了
    	*/
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}

 

2. void add(int,E);在指定位置添加元素

public void add(int index, E element) {
    	//边界校验 插入的位置必须在0-size之间
        rangeCheckForAdd(index);
		//不分析了上面有
        ensureCapacityInternal(size + 1); 
        //就是将你插入位置的后面的数组往后移一位
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
    	//放入该位置
        elementData[index] = element;
    	//元素个数+1
        size++;
}

private void rangeCheckForAdd(int index) {
    	//插入位置过于离谱,反手给你一个越界异常
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
* src:源对象
* srcPos:源对象对象的起始位置
* dest:目标对象
* destPost:目标对象的起始位置
* length:从起始位置往后复制的长度
*/
public static native void arraycopy(Object src,  int  srcPos, Object dest,
                                    int destPos, int length)

 

总结:

初始容量为10,1.5倍扩容,扩容最大值为 Integer.MAX_VALUE,

当我们调用add方法时,实际方法的调用如下:
ArrayList源码解析插图(5)

删除集合元素

因为这几个都基本类似,我们就选两个进行剖析
ArrayList源码解析插图(6)

1. remove(int):通过删除指定位置上的元素

public E remove(int index) {
    	//检测index,是否在索引范围内
        rangeCheck(index);
		//列表结构被修改的次数,用户迭代时修改列表抛异常
        modCount++;
    	//取出要被删除的元素
        E oldValue = elementData(index);
		//和添加的逻辑相似,算数组移动的位置
        int numMoved = size - index - 1;
    	//大于0说明不是尾部
        if (numMoved > 0)
            //将删除位置后面的数组往删除位前移一格
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
    	/*
    	* 由于只是将数组前移盖住了一位,但是长度没变
    	* 如果删除位置不是末尾,此时末尾会有两个相同元素
    	* 需要删除末尾最后一个元素,size - 1
    	*/
        elementData[--size] = null; // clear to let GC do its work
		//返回要删除的元素值
        return oldValue;
    }

	/*
    * 这个方法不过多解释了,但是笔者认为这小小的检查边界的方法细节写的不是很完美
    * 这个地方没有主动考虑,index < 0的情况,异常是后续直接抛的,并不是在这
    * 后续版本似乎对这个细节做了纠正
	*/
    private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

 

2. removeAll(collection 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;
    	//r代表elementData循环次数,w代表不需要删除的元素个数
        int r = 0, w = 0;
    	//修改变动默认为false
        boolean modified = false;
        try {
            //遍历集合,遍历几次r就是几,直至r=size
            for (; r < size; r++)
                //查看当前集合元素是否不被包含,complement = false
                if (c.contains(elementData[r]) == complement)
                    //不被包含,那我在当前容器从头开始放,w是下标
                    elementData[w++] = elementData[r];
        } finally {
            /**
            * 如果r没有成功遍历完,抛异常了(这是个finally)
            * 理所当然将后面没有遍历完的元素归为不被包含
            */
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            //存在不需要被删除的元素
            if (w != size) {
                //遍历删除
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                //有做过修改变动
                modified = true;
            }
        }
        return modified;
}

  

修改集合元素

public E set(int index, E element) {
        //边界范围校验
    	rangeCheck(index);
		//取出旧值
        E oldValue = elementData(index);
    	//赋上新值
        elementData[index] = element;
    	//返回旧值
        return oldValue;
}

 

查找集合元素

  public E get(int index) {
      	//边界范围校验
        rangeCheck(index);
      	//通过下标获取查找的元素
        return elementData(index);
    }

 

总结

  • 线程不安全
  • 本质是数组,默认长度10,扩容核心方法为grow() ,每次扩容1.5倍,最大容量为 Integer.MAX_VALUE
  • 实现了RandomAccess接口,所以for循环比迭代器循环效率更高
  • 因为底层是数组,所以查询快,修改快,增删慢

原创文章,作者:迷途资源,如若转载,请注明出处:https://www.mipng.com/1315.html

这些信息可能会帮助到你: 下载帮助 | 报毒说明 | 进站必看

修改版本安卓软件,加群提示为修改者自留,非本站信息,注意鉴别

发表评论

邮箱地址不会被公开。 必填项已用*标注