【源码解析】扒开ArrayList的外衣

积千里跬步,汇万里江河;每天进步一点点,终有一天将成大佬。

本文内容

当然ArrayList里的方法不止这些,本文主要讲一些常用的方法

图片

方法变量

Arraylist里的方法变量主要有以下几个

图片

构造方法

有参构造

传入数组的大小

代码实现
List<String> list=new ArrayList<>(5);
源码解析

图片

传入一个list对象

其实这个就相当于把传入的list对象里的数据复制到新的ArrayList对象

代码实现
List<String> list=new ArrayList<>(Arrays.asList("z","m","h"));

这里用来Arrays工具类里的asList方法,它的源码里是直接返回一个List,有兴趣的可以去看看,这里就不介绍了

源码解析

图片

无参构造

这个比较简单,直接赋值一个空数组

代码实现

List<String> list=new ArrayList<>();

源码解析

图片

add方法

add一般常用的有两个方法,一个就是add(E e)在尾部添加数据,一个就是add(int index,E element)在指定位置插入元素

add(E e)

这个是Arrayist的主要方法,平时用的也是最多的方法之一,所以源码比较复杂,比较长

代码实现

List<String> list=new ArrayList<>();
list.add("灰灰HK");

源码解析

图片

  • ensureCapacityInternal(int minCapacity)确保数组容量充足

图片

  • calculateCapacity(Object[] elementData, int minCapacity)

图片

  • 再回到ensureExplicitCapacity(int minCapacity)这个方法,这个方法先修改次数加1,然后判断size+1是不是比当前的数组容量大,如果比当前的数组容量大,则进行扩容操作,扩大容量为原数组的1.5倍

比如第二次调用add方法,此时size+1=2, elementData.length=10,为什么等于10呢?因为第一次默认把数组容量从0扩大到了10,这时size+1elementData.length小,就不会进行扩容操作

图片

  • grow(int minCapacity)扩容

这里调用Arrays.copyOf()方法进行复制操作,当进一步深入这个方法时,发现是由System.arraycopy()这个方法实现复制功能的,这个方法由native关键字修饰,表示不是由Java语言实现的,一般是c/cpp实现

图片

小结

到这里,add的方法流程就走完了,其核心步骤:

  • 每次添加元素时判断数组容量是否充足

  • 第一次添加元素,把数组容量扩容到10

  • 扩容时,除第一次,以后的每次扩容为原大小的1.5倍

  • 扩容后调用System.arraycopy()方法把原数组的元素复制到扩容后的新数组

add(int index, E element)

该方法为在指定位置插入元素,该位置及后面所有元素后移

代码实现

List<String> list=new ArrayList<>();
list.add("hk");
list.add(0,"灰灰");

源码解析

图片

可以看到,这边又用到了System.arraycopy()这个方法

  • rangeCheckForAdd(int index)判断是否越界

这里他是和size对比,而不是和数组的length对比,我个人认为这样第一节省了空间,第二方便后面移动的操作

图片

  • System.arraycopy()拷贝数组
public static native void arraycopy(Object src,  int  srcPos,
                             		Object dest, int destPos,
                                    int length)
  • src 原数组对象
  • srcPos 原数组起始位置
  • dest 目标数组
  • destPos 目标数组起始位置
  • length 复制多少个数据

小结

插入方法其主要步骤如下:

  • 检查插入的位置是否越界
  • 检查数组容量是否充足,不充足进行扩容相关操作
  • 调用System.arraycopy()进行index及后面的元素后移

get方法

get(int index)

代码实现

List<String> list=new ArrayList<>();
list.add("hk");
list.get(0);

源码解析

图片

  • rangeCheck(int index)判断是否越界

get个add方法判断越界的方法是不一样的,这边是index>=size,多了个等于,为什么要多个等于呢?因为数组是从0开始的,而size相当于是开始的从1开始的

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
  • elementData(int index)直接返回对应下标的数组元素
E elementData(int index) {
    return (E) elementData[index];
}

小结

get方法比较简单,主要步骤为:

  • 检查是否越界
  • 返回对应元素

set方法

set(int index, E element)

代码实现

List<String> list=new ArrayList<>();
list.add("hk");
list.set(0,"灰灰");

源码解析

图片

remove方法

remove(int index)

代码实现

List<String> list=new ArrayList<>();
list.add("hk");
list.remove(0);

源码解析

当删除的元素为最后一个元素时,numMoved就小于0了,就不会进行移动元素的操作

图片

remove(Object o)

这个方法在实际中用的比较少,因为AraryList是可以保存重复的元素,所以删除是删除最早添加的元素

代码实现

List<String> list=new ArrayList<>();
list.add("hk");
list.remove("hk");

源码解析

图片

  • fastRemove(int index)删除元素

这个方法和remove(int index)内部的操作类似,不过这边不保存被删除的元素

private void fastRemove(int index) {
    modCount++;
    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
}

clear方法

clear()

代码实现

List<String> list=new ArrayList<>();
list.add("hk");
list.clear();

源码分析

图片

总结

ArrayList底层扩容或者移动数组元素时都调用了System.arraycopy()来进行相关操作,平时进行我们进行数组复制或移动的时候也可以调用这个方法了,这个性能比循环复制性能高多了,特别是在大量数据的时候。

文章好几次出现了modCount++这个操作,这个modCount主要用户内部类的迭代器