集合List ArrayList源码分析
type
status
date
slug
summary
tags
category
icon
password
前言
基于
JDK1.8源码List是个接口，里面定义了一些对于List的相关的一些操作，ArrayList底层基于一个Object类型的数组，数组操作的时间复杂度如下Op | Time complexity |
prepend | O(1) |
append | O(1) |
lookup | O(1) |
insert | O(n) |
delete | O(n) |
可以明显看到数组在插入和删除操作时的时间复杂度很高，因为在插入和删除过程中需要进行数组元素的群移操作。而头追加、尾追加和指定下标的查找为
O(1)比较省时，头追加为什么不是O(n)呢！头追加的均摊时间复杂度为O(1)摊销分析会以增、删、改、查四个操作去分析源码。变量
构造函数
先来看一下构造函数
注意
- elementData = c.toArray()
因为不同的类通过
toArray方法返回的不一定是Object类型其类型取决于其返回的实际类型.（如下），这样会导致在调用ArrayList增加Object元素的方法的时候出现错误。要避免这种情况，编写者便判断了下：elementData.getClass() != Object[].class，不通过的话调用Arrays.copyOf方法来实现把类型变为Object。输出：
- 为什么
为什么返回的不一定就是 Object[] 呢？原因很简单，因为由于继承的原因，我们父类实例的具体类型，实际上是取决于在 new 时，我们所使用的子类类型。
增
注意ArrayList添加的两大核心
- System.arraycopy()
- Arrays.copyOf()
删
删除中比较难理解的方法
- batchRemove()
改
查
总结
概括的说，ArrayList 是一个动态数组，其底层数据结构依然是数组，它实现了List<E>, RandomAccess, Cloneable, java.io.Serializable接口，其中RandomAccess代表了其拥有随机快速访问的能力，`ArrayList'可以以O(1)的时间复杂度去根据下标访问元素。
因其底层数据结构是数组，所以可想而知，它是有一个容量的（数组的length），当集合中的元素超出这个容量，便会进行扩容操作。扩容操作也是ArrayList 的一个性能消耗比较大的地方，所以若我们可以提前预知数据的规模，应该通过public ArrayList(int initialCapacity) {}构造方法，指定集合的大小，去构建ArrayList实例，以减少扩容次数，提高效率。
或者在需要扩容的时候，手动调用public void ensureCapacity(int minCapacity) {}方法扩容。
不过该方法是ArrayList的API，不是List接口里的，所以使用时需要强转:
((ArrayList)list).ensureCapacity(30);
- 增删改查中， 增导致扩容，则会修改modCount，删一定会修改。 改和查一定不会修改modCount。
- 扩容操作会导致数组复制，批量删除会导致 找出两个集合的交集，以及数组复制操作，因此，增、删都相对低效。 而 改、查都是很高效的操作。
- 因此，结合特点，查 操作是最高频的。相对来说，增操作 只有在列表加载更多时才会用到 ，而且是在列表尾部插入，所以也不需要移动数据的操作。而删操作则更低频。 故选用ArrayList作为保存数据的结构。
Loading...