List之Arraylist源码

ArrayList的特点

ArrayList是一个动态数组,与Java中的数组相比,他的容量可以动态增加(1.5倍)

  • 快速随机访问
  • 允许存放多个null元素
  • 底层存储是个Object数组
  • 增加元素个数可能很慢(可能需要扩容),删除元素可能很慢(可能需要移动很多元素),对于元素随机访问get和set比较快。
  • 线程不安全

ArrayList的继承关系

  • ArrayList继承于AbstractList,AbstractList继承AbstractCollection实现了List接口。
  • 实现了List接口,那么ArrayList元素是有序的,可以重复的,可以有null元素的集合。
  • 实现了RandomAccess接口,标识着其支持随机快速访问,实际上,查看RandomAccess源码可以看到,是空的啥都没有.ArrayList底层是数组,那么随机快速访问是理所当然的,访问速度O(1)。
  • 实现了Cloneable接口,ArrayList里面的clone()复制其实是浅复制。
  • 实现java.io.Serializable接口,即ArrayList支持序列化,能通过序列化去传输和存储。

ArrayList为什么可以序列化

transient Object[] elementData; 前面有个修饰符 transienttransient标识之后是不被序列化 。
然而elementData 就是ArrayList的存储容器,为什么能被序列化?

ArrayList在序列化的时候会调用writeObject(),直接将size和element写入ObjectOutputStream;反序列化时调用readObject(),从ObjectInputStream获取size和element,再恢复到elementData。

为什么不用系统的系列化,反而自己去重写?

主要是从效率考虑,elementData是一个缓存数组,一般都是会比实际存储大一些,它通常会预留一些容量,等容量不足时再扩充容量(当前容量的1.5倍),那么有些空间可能就没有实际存储元素,采用上面的方式来实现序列化时,就可以保证只序列化实际存储的那些元素,而不是整个数组,从而节省空间和时间。

ArrayList初始化

不考虑性能问题或者不知道参数个数,可以直接new一个ArrayList,此时会调用ArrayList的无参构造方法。
此时的element的长度为1 size为0 但是当我们进行add()时;element会变成默认的长度 10;
(这里需要注意,如果知道参数个数的话 还是推荐指定容量。这样可以避免使用扩容机制带来的额外开销)

为什么无参会创造一个10长度空列表呢?

如果是以ArrayList()无参构造方法初始化,那么数组指向的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA.
第一次add()元素会进入if内部,且minCapacity1,那么最后minCapacity肯定是10

也就是说当我们第一次add()的时候,就会触发扩容机制,空列表的长度会扩容到默认长度也就是10


Grow扩容机制

  • 1)如果原数组是空的,那么第一次添加元素时会给数组一个默认大小10。
  • 确保数组已使用长度size加1之后是否还有容量存储下一个数据。
  • 2)修改次数modCount 标识自增1,如果当前数组已使用长度(size)加1后的大于当前的数组长度,则调用grow方法,增长数组,grow方法会将当前数组的长度变为原来容量的1.5倍。
  • 3)确保新增的数据有地方存储之后,则将新元素添加到位于size的位置上。
  • 4)返回添加成功布尔值。

注意扩容有两个方法分别是ensureCapacity方法和ensureCapacityInternal方法
从源码的角度来说ensureCapacity方法是一次性扩容到指定容量的:性能较好
ensureCapacityInternal方法则是一点点的扩容:性能较差

add机制

  • 1)确保数插入的位置小于等于当前数组长度,并且不小于0,否则抛出异常
  • 2)确保数组已使用长度(size)加1之后足够存下 下一个数据
  • 3)修改次数(modCount)标识自增1,如果当前数组已使用长度(size)加1后的大于当前的数组长度,则调用grow方法,增长数组
  • 4)grow方法会将当前数组的长度变为原来容量的1.5倍。
  • 5)确保有足够的容量之后,使用System.arraycopy 将需要插入的位置(index)后面的元素统统往后移动一位。
  • 6)将新的数据内容存放到数组的指定位置(index)上