集合框架----源码解读ArrayList篇

1.ArrayList

List接口的可改变尺寸的- array实现。实现所有可选列表操作，并允许所有元素，包括null。除了实现List接口外，该类还提供了操纵内部用于存储列表的数组大小的方法。(该类与Vector大致等价,只是不同步。)
其中size、isEmpty、get、set、迭代程序和list迭代程序操作在恒定时间内运行。add操作在摊销常量时间内运行，即添加n个元素需要O ( n )时间。其他所有操作都在线性时间内运行(大致说来)。与线性链表实现相比，常数因子较低。
每个ArrayList实例都有一个容量。容量是用来存储列表中元素的数组的大小。它总是至少与列表大小一样大。随着元素被添加到ArrayList中，其容量会自动增长。除了增加一个元素具有恒定的摊余时间成本这一事实之外，没有具体说明增长政策的细节。
一个应用程序可以在增加大量元素之前，通过保证容量操作来增加ArrayList实例的容量。这可能会减少增量再分配的数量。
一个应用程序可以在增加大量元素之前，通过保证容量操作来增加ArrayList实例的容量。这可能会减少增量再分配的数量。
注意，这种实现并不同步。如果多个线程并发访问一个ArrayList实例，且其中至少一个线程对列表进行了结构性修改，则必须进行外部同步。(结构修改是增加或删除一个或多个元素,或显式地调整后台阵的任何操作;仅仅设定一个要素的数值,并不是一种结构性的修改。)这通常是通过对一些自然封装列表的对象进行同步来完成的。如果不存在这样的对象，则应该使用Collections . synchronousedList方法对列表进行"包装"。这最好在创建时完成，以防止意外的不同步访问列表：List list = Collections.synchronizedList(new ArrayList(...));
该类的迭代程序和list迭代程序方法返回的迭代程序是快速失败的：如果在迭代程序创建后的任何时候都对列表进行了结构修改，除了通过迭代程序自己的删除或添加方法之外，迭代程序都会抛出ConcurrentModificationException异常。因此，在面对并发修改时，迭代程序能够快速、干净地失效，而不是冒着在未来某个未确定时间发生任意、非确定性行为的风险。
需要注意的是，迭代程序的快速失效行为是无法保证的，因为一般来说，在存在非同步并发修改的情况下，不可能做出任何硬性保证。Fail-fast迭代程序在尽力而为的基础上抛出Concurrent ModificationException。因此，编写依赖于该异常的程序来判断其正确性是错误的：迭代程序的快速失效行为应该仅用于检测bug。
该类是Java集合框架的成员。

 当我们new一个 ArrayList，我们去看一下他的无参构造器

 再点击DEFAULTCAPACITY_EMPTY_ELEMENTDATA

我们发现这就是一个数组，由此可以得出  ArrayList就是一个数组。

2.ArrayList的add方法

进入add方法，下面就是尺寸加1，不知道他为什么扩容，我们也不知道为什么扩容，我们再进入ensureCapacityInternal方法看一下 

 进入这个方法我们就是把这个集合的最小容量传进去了，我们进入calculateCapacity方法

当ArrayList是空的时候，就去判断如果最小容量，比默认容量10小，就返回10

我们拿到10去 ensureExplicitCapacity 方法 进入grow方法，这个方法也就是扩容方法

 老的容量是0，因为我们之前没有扩过容，就是0，

  新增的容量 等于 0+0>>1=0，0右移一位加0，新的容量就是0，右移一位，可以理解为除以2但是不能当做除以2

 如果新容量-最小容量<0 ,就把最小容量给新的容量大小。现在新的容量应该是10

如果 10-数组的最大尺寸>0  ，执行newCapacity = hugeCapacity(minCapacity); 

 利用Arrays.copyOf(elementData, newCapacity); 数组复制方法把新的容量复制给空数组

 把第一个元素放到0的位置

 总结：

ArrayList的add方法底层实现原理：

1.判断是否需要扩容

默认给我们数组初始化容量==10；

2.直接通过index赋值

3.ArrayList的扩容如果1.5倍（理论的）

4.扩容其实就是生成一个新的对象

15.>>1 不是等于7.5而是等于7 。在机器里面是没有0.5这个概念的

3.ArrayList的get方法

 检查边缘，也就是是否越界

如果下标大于尺寸就会报数组下标越界异常

 没有越界就把对应的坐标的数据返回回去

 总结：get方法

1.判断数组下标是否越界

2.根据下标获取数组内容

 4.ArrayList的remove方法

检查下标是有问题，

 记录ArrayList结构修改次数，默认是0

 获取该坐标的元素

 我们进入这个缩容方法

打开api文档搜索这个方法 ，如果你没有api文档 我的开源仓库有

note/java/jdk api 1.8_google.CHM · Royalreairman/learn-computer - Gitee.com

 

 缩容原理：从删除下标后一位开始复制给要删除哪一位，最后一位变成null

总结：

删除实际上就是删除对应的下标index，删除后，后面的自动补齐。

remove方法我们发现ArrayList一个缺点，只要扩容过，无论我们这么缩容，他能装的数据还是最大的扩容数据，也是官方简绍的结构修改是添加或删除一个或多个元素，或显式调整支持数组的大小的任何操作;仅仅设置元素的值并不是结构修改。

5.数组的时间复杂度(查询）

O(1): 基于数组下标index查询只要一次

O(n): 从头查询到尾部的次数 根据元素来查询 效率低

6.ArrAyList总结

1.ArrayList底层基于数组实现，根据index下标查询效率非常高

2.增、删底层基于数组实现的扩容，缩容 效率也很低

3.修改是方法是如果是根据index下标来修改所以效率高

4.无法对结构进行修改

5.每次缩容扩容会生成新的对象

6.不是同步的。如果多个线程并发访问一个ArrayList实例，并且至少有一个线程在结构上修改了该列表，那么它必须在外部同步。