Java集合-ArrayList

mgs2002 2020年01月19日 272次浏览

ArrayListJava里面经常使用的一种集合,这篇文章简单的对ArrayList里面的知识点做一个总结。

简单介绍

最常用的一种集合类型,用于存储列表型数据,底层数据结构是数组(Object[] elementData),线程不安全,支持随机访问数据('RandomAccess'),适合读多写少的场景。

存取原理

这部分结合源码总结一下ArrayList的操作原理。

初始化

两种方式初始化List:

  • 无参构造方法(ArrayList()
  • 带容量参数的构造方法(ArrayList(int initialCapacity)
    两者相同的地方都是生成一个object数组,区别是无参构造方法指向一个空的object数组,而带参数的构造方法传入容量参数(initialCapacity)生成object[initialCapacity]的数组。
//带参数的构造方法
public ArrayList(int initialCapacity) {
        //如果initialCapacity > 0 新生成容量为initialCapacity的数组
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
	 //如果initialCapacity = 0 直接指向空的object[]数组
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        //否则抛出异常
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
 //无参构造方法
 public ArrayList() {
        //elementData直接指向空的object[]数组
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

问题

构造方法初始化List后可以直接set数据吗?
这个问题我遇到过,稍微不注意就会答错,正确答案是在set的是会抛出数组下标越界的异常IndexOutOfBoundsException),下面我们通过代码来复现。

public void initListExceptionTest(){
        //调用初始化方法,设置初始容量为1
        List<String> list = Lists.newArrayListWithCapacity(1);
        //调用size方法发现list长度位0,通过源码发现只是初始化了底层object数组的容量
        System.out.println(list.size());
        //调用set方法会抛出数组下标越界异常java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
        //因为设置值前会进行长度范围检查rangeCheck,比较set下标和size大小
        //只有index大于size才会通过,否则抛出异常
        //可以先add数据再set,因为add后会真正分配空间给List
        list.set(0,"a");
    }

执行一下这段代码会发生如下异常
QQ截图20200119195254.png
原因在代码注释里面已经讲得很清楚了,由于初始化数组的时候只是初始化了object数组的容量并没有真正初始化List的大小(size = 0),set的时候会去检查数组下标是否越界(index >= size)。
QQ截图20200119200353.png
那什么时候List会真正初始化呢,接下来就会讲到这块。

添加数据

添加数据分为尾部添加和按下标添加数据两种方式。

尾部添加

流程:

  1. 根据size判断是否需要扩容,如果element为空数组赋默认值10
    如果(size+1)>数组长度(elementData.length)则进行扩容
  2. 将元素添加到List尾部(elementData[size++] = e)。

按下标添加

流程:

  1. 判断index是否下标越界,越界抛出异常IndexOutOfBoundsException否则同直接添加的第一步.
  2. 复制一个新的数组,从index+1位置起,腾出index的位置。
  3. 将元素添加到index位置。
public void add(int index, E element) {
   //判断下标是否越界
   rangeCheckForAdd(index);
  //判断是否需要扩容
  ensureCapacityInternal(size + 1);  
  //复制新的数组  
  System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
   //放置新元素并且size+1
   elementData[index] = element;
   size++;
 }

问题

List扩容时机?
从添加数据的流程里可以看出List不是在初始化的时候扩容,而是在添加的数据的时候根据size+1和数组长度(elementData.length)比较来触发扩容,下图展示了List的具体扩容流程。
List扩容流程图.png
可以看到长度为5的List扩容后变成了7(数组长度),这是因为扩容的算法采用了位运算的方式(int newCapacity = oldCapacity + (oldCapacity >> 1))定价于oldCapacity + (oldCapacity / 2) ,所以newCapacity = 5+2 = 7

删除数据

分为按下标删除和按元素删除,本质就是复制一个新的数组,从index+1位置起,到list结束位置止,并将其放在index的位置上面(其实就是覆盖掉index的数据,感觉像是删除了一样)。
ArrayList删除演示.png

简单总结

  • ArrayList底层是object数组,支持随机访问数据,遍历效率高,适合读多写少的场景
  • ArrayList的扩容和操作(添加、删除)原理都是复制新的数组,列表数据量小没关系,如果数据量大了(几千几万甚至更多)效率比较低