ArrayList史上最详细源码分析

╰半橙微兮° 2022-03-29 04:16 239阅读 0赞

今天电话面试，面试官问到ArrayList中add方法的原理，我一下蒙了，这个用的最多的一种数据结构被我忽视了，没答上来，有时候用的最多的反而最自信，最自信的东西最容易忽视其中的细节，因此今天决定扒扒源码。

### 1 ArrayList是什么？ ###

一种用来存放数据的数据结构。

它的底层是一个数组，用来存放数据。

### 2 ArrayList的特点？ ###

*  底层为数组。
 *  所存储的数据在内存中连续。
 *  查询的时候以地址偏移量来计算数据位置，因此时间复杂度为O（1）。//这里是指用索引作为参数查询，而非使用数组相应位置的内容作为参数查询。
 *  添加数据有两种方式，添加在数组的最后，或者根据输入的索引位置添加到数组的相应位置。
 *  第一种方式添加数据时，**会判断数组有没有初始化，没有初始化时，会把数组初始化为10大小的容量，并且保证数组容量足够，不足的情况会调用扩容函数。并且会调用修改次数+1的函数。**
 *  第二种方式添加数据时，先判断index参数是否数组下表越界。再执行与第一种方式一样的**操作**（上一行的蓝色文字），之后再进行插入，插入时，索引位置和之后的元素向后移一位。
 *  ArrayList有两种初始化的方式，一种空参默认的初始化，一种指定容量的初始化方式。
 *  数组采用默认初始化方式时，默认的容量为10。
 *  扩容时，以1.5倍原数组最大容量的方式扩容。

### **3.源码分析（1460行）** ###

**源码比较多的，我另开博客做了解读，源码较短较简单的，我直接说明了源码的作用。**

<table> ArrayList源码分析 
 <thead> 
 <tr> 
 <th style="width:139px;">源码类型</th> 
 <th style="width:408px;">源码概览</th> 
 <th style="width:380px;">源码分析</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td style="width:139px;">属性</td> 
 <td style="width:408px;">private static final long serialVersionUID = 8683452581122892189L;</td> 
 <td style="width:380px;">序列化时用来验证数据一致性的值</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">属性</td> 
 <td style="width:408px;">private static final int DEFAULT_CAPACITY = 10;</td> 
 <td style="width:380px;">空参构造初始化数组时，数组的默认大小为10</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">属性</td> 
 <td style="width:408px;">private static final Object[] EMPTY_ELEMENTDATA = {};</td> 
 <td style="width:380px;">一个空的数组</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">属性</td> 
 <td style="width:408px;">private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};</td> 
 <td style="width:380px;">共享空数组实例，用于默认大小的空实例。我们将其与DEFAULTCAPACITY_EMPTY_ELEMENTDATA分开来，以了解添加第一个元素时要扩容多少。</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">属性</td> 
 <td style="width:408px;">transient Object[] elementData;</td> 
 <td style="width:380px;">一个临时使用的数组</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">属性</td> 
 <td style="width:408px;">private int size;</td> 
 <td style="width:380px;">当前数组里所存放元素的个数</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public ArrayList(int initialCapacity) {}</td> 
 <td style="width:380px;">有参的构造方法，指定数组的初始容量大小</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public ArrayList() {}</td> 
 <td style="width:380px;">默认的空参构造。默认的初始化容量大小为10</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public ArrayList(Collection&lt;? extends E&gt; c) {}</td> 
 <td style="width:380px;">按照入参集合的迭代器返回的元素的顺序构造包含指定集合的元素的数组。</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public void trimToSize() {}</td> 
 <td style="width:380px;">把数组的容量变为当前数组中包含元素的大小，此方法用来最小化数组在存储空间所占用的大小。</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public void ensureCapacity(int minCapacity) {}</td> 
 <td style="width:380px;">用来在添加数据时，保证数组容量大于数组所包含的元素个数的。</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">private void ensureCapacityInternal(int minCapacity) {}</td> 
 <td style="width:380px;">当数组为空数组时，最小容量设置为传入的参数，并且最后调用函数（下一行）</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">private void ensureExplicitCapacity(int minCapacity) {}</td> 
 <td style="width:380px;"> 增加一次修改数组的次数，修改数组后，容量若小于数组元素个数，开始扩容。 </td> 
 </tr> 
 <tr> 
 <td style="width:139px;">属性</td> 
 <td style="width:408px;">private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;</td> 
 <td style="width:380px;">能分配的数组最大的大小。某些虚拟机在数组中保留一些头字。尝试分配较大的数组可能导致内存不足错误：请求的数组大小超过了VM限制，因此数组的最大容量 MAX_ARRAY_SIZE要在Integer.MAX_VALUE上要减去8个！！Integer.MAX_VALUE为<img alt="2^{31}-1" src="https://private.codecogs.com/gif.latex?2%5E%7B31%7D-1"></td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">private void grow(int minCapacity) {}</td> 
 <td style="width:380px;"><a href="https://blog.csdn.net/qq_29519041/article/details/86246881" rel="nofollow">https://blog.csdn.net/qq_29519041/article/details/86246881</a></td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">private static int hugeCapacity(int minCapacity) {}</td> 
 <td style="width:380px;"><a href="https://blog.csdn.net/qq_29519041/article/details/86246881" rel="nofollow">https://blog.csdn.net/qq_29519041/article/details/86246881</a></td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public int size() {}</td> 
 <td style="width:380px;">返回数组中存放的元素个数</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public boolean isEmpty() {}</td> 
 <td style="width:380px;">当数组中没有元素时 返回true 否者为false</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public boolean contains(Object o) {}</td> 
 <td style="width:380px;">作用：判断数组中是否包含 o 对象，原理：调用了indexOf做判断。看下一行</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public int indexOf(Object o) {}</td> 
 <td style="width:380px;"> <a href="https://blog.csdn.net/qq_29519041/article/details/86259595" rel="nofollow">https://blog.csdn.net/qq_29519041/article/details/86259595&nbsp;&nbsp;&nbsp; </a> 就是普通的遍历查找，并返回下标。 </td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public int lastIndexOf(Object o) {}</td> 
 <td style="width:380px;">与indexOf方法的唯一区别是，遍历从尾部开始。其他和indexOf完全一样。</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public Object clone() {}</td> 
 <td style="width:380px;"> 浅拷贝！，就是对一个对象只复制他们对应的引用，这些复制后的引用指向的还是之前的对象。就是说，对象的实例只有一个。但是有两个引用指向他们。我自己的理解。若有错误请留言 关于深拷贝浅拷贝相关优秀博文： <a href="https://blog.csdn.net/github_38687585/article/details/79926909" rel="nofollow">https://blog.csdn.net/github_38687585/article/details/79926909</a> <a href="https://blog.csdn.net/DeMonliuhui/article/details/54572908" rel="nofollow">https://blog.csdn.net/DeMonliuhui/article/details/54572908</a> </td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public Object[] toArray() {}</td> 
 <td style="width:380px;"> 返回包含此列表中所有元素的数组。 （从第一个元素到最后一个元素）。 &lt;p&gt;返回的数组将是“安全的”，因为此列表不维护对它的引用。（换句话说，此方法必须分配一个新数组）。 因此，调用方可以自由修改返回的数组。 &lt;p&gt;此方法充当基于数组和基于集合的API之间的桥梁。 </td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public &lt;T&gt; T[] toArray(T[] a) {}</td> 
 <td style="width:380px;"> <a href="https://rogerfederer.iteye.com/blog/788795" rel="nofollow">https://rogerfederer.iteye.com/blog/788795</a> &nbsp; 它与上面的方法的区别是，它会以传入的数组的类型来返回对应类型的数组。 </td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">E elementData(int index) {}</td> 
 <td style="width:380px;">返回数组索引位置的元素，它将会被get（int index）调用</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public E get(int index) {}</td> 
 <td style="width:380px;">返回数组索引位置的元素，首先会调用rangeCheck判断是否数组索引越界，之后调用elementData(int index)方法。</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public E set(int index, E element) {}</td> 
 <td style="width:380px;">把element替换掉index位置的元素，并返回被替换掉的元素</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public boolean add(E e) {}</td> 
 <td style="width:380px;">在尾部添加元素，之前会对元素修改次数做累加。</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public void add(int index, E element) {}</td> 
 <td style="width:380px;">在数组相应位置添加元素，对应位置及以后的元素向后移一位，这也是数组插入数据慢的原因。需要移动后面的元素。</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public E remove(int index) {}</td> 
 <td style="width:380px;"><a href="https://blog.csdn.net/qq_29519041/article/details/86316290" rel="nofollow">https://blog.csdn.net/qq_29519041/article/details/86316290</a></td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public boolean remove(Object o) {}</td> 
 <td style="width:380px;"><a href="https://blog.csdn.net/qq_29519041/article/details/86316290" rel="nofollow">https://blog.csdn.net/qq_29519041/article/details/86316290</a></td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">private void fastRemove(int index) {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public void clear() {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public boolean addAll(Collection&lt;? extends E&gt; c) {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public boolean addAll(int index, Collection&lt;? extends E&gt; c) {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">protected void removeRange(int fromIndex, int toIndex) {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">private void rangeCheck(int index) {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">private void rangeCheckForAdd(int index) {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">private String outOfBoundsMsg(int index) {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public boolean removeAll(Collection&lt;?&gt; c) {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public boolean retainAll(Collection&lt;?&gt; c) {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">private boolean batchRemove(Collection&lt;?&gt; c, boolean complement) {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">private void writeObject(java.io.ObjectOutputStream s) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; throws java.io.IOException{ </td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">private void readObject(java.io.ObjectInputStream s) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; throws java.io.IOException, ClassNotFoundException {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public ListIterator&lt;E&gt; listIterator(int index) {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public ListIterator&lt;E&gt; listIterator() {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public Iterator&lt;E&gt; iterator() {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">private class Itr implements Iterator&lt;E&gt; {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public boolean hasNext() {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public E next() {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public void remove() {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public void forEachRemaining(Consumer&lt;? super E&gt; consumer) {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">final void checkForComodification() {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">内部类ListItr</td> 
 <td style="width:408px;">private class ListItr extends Itr implements ListIterator&lt;E&gt; {}</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">ListItr的方法</td> 
 <td style="width:408px;">public boolean hasPrevious() { </td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">ListItr的方法</td> 
 <td style="width:408px;">public int nextIndex() { </td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">ListItr的方法</td> 
 <td style="width:408px;">public int previousIndex() { </td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">ListItr的方法</td> 
 <td style="width:408px;">public E previous() { </td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">ListItr的方法</td> 
 <td style="width:408px;">public void set(E e) { </td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">ListItr的方法</td> 
 <td style="width:408px;">public void add(E e) { </td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">方法</td> 
 <td style="width:408px;">public List&lt;E&gt; subList(int fromIndex, int toIndex) { </td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">静态方法</td> 
 <td style="width:408px;">&nbsp;static void subListRangeCheck(int fromIndex, int toIndex, int size) { </td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="width:139px;">&nbsp;</td> 
 <td style="width:408px;">&nbsp;</td> 
 <td style="width:380px;">&nbsp;</td> 
 </tr> 
 </tbody> 
</table>

1460行的代码太多了，慢慢更吧...

\-------------    最后结束修改于2019年1月 10日 22:45   待续...    -------------

\-------------    最后结束修改于2019年1月 11日 20:46   待续...    -------------