ArrayList分析

写在前面的话

从这篇文章开始，将会陆续为大家介绍java基础中集合部分的相关知识，希望通过和大家一起回顾这部分内容后，在实际的工作中根据不同业务场景能够更灵活、更有效率的选择合适的集合存放数据。那么首先，让我们从ArrayList开始。

 

ArrayList是啥

ArrayList 它本质上其实是一个"可变"数组。大家都知道数组的长度一旦在初始化时定义后就不能再改变，这里的"可变"指的不是将现有的数组扩容，而是指ArrayList底层引用指向一个新的数组。

ArrayList会将原数组中的元素按索引顺序原封不动的复制到新数组中，并且新数组的容量是原数组的1.5倍。

每次存放的元素即将超出数组的最大容量后，ArrayList都会做一次这种"扩容"操作。所以如果一个ArrayList定义的不合适，那么可能会频繁的进行扩容操作从而影响效率，这一点需要注意。

 

ArrayList核心源码分析(JDK Version 1.8)

首先是相关属性：

1 private static final int DEFAULT_CAPACITY = 10;
2 
3 transient Object[] elementData;
4 
5 private int size;

 

第一行的常量指的是ArrayList在初始化时若未指定初始容量，则默认初始化容量为10。

第二行是ArrayList内部的数组，可以认为绝大多数对ArrayList的操作其实就是对该数组进行操作。

第三行是这个数组中当前元素的个数，注意和数组容量在概念上的区别噢。

 

然后是相关的方法：

1.构造方法

 1     /**
 2      * 带参构造函数，使用自定义大小来初始化一个空的ArrayList
 3      *
 4      * @param  initialCapacity  ArrayList初始容量
 5      * @throws IllegalArgumentException 若传入的自定义大小为负数，则报此异常
 6      *         
 7      */
 8     public ArrayList(int initialCapacity) {
 9         if (initialCapacity > 0) {
10             //初始化指定大小的数组
11             this.elementData = new Object[initialCapacity];
12         } else if (initialCapacity == 0) {
13             //初始化一个空的数组
14             this.elementData = EMPTY_ELEMENTDATA;
15         } else {
16             //若用户传入自定义容量大小 < 0,则抛出此异常
17             throw new IllegalArgumentException("Illegal Capacity: "+
18                                                initialCapacity);
19         }
20     }
21     
22     /**
23      * 无参构造函数，初始化一个空的数组
24      */
25     public ArrayList() {
26         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
27     }

无参和有参构造方法，没啥好啰嗦的。

 

2.ArrayList的核心方法——扩容方法 

 1     /**
 2      * 扩容的核心方法
 3      * @param minCapacity 期望最小扩容后的大小
 4      */
 5     private void grow(int minCapacity) {
 6         int oldCapacity = elementData.length;  //旧数组容量
 7         //新容量为旧容量的1.5倍.为什么是1.5倍？
 8         //如果一次扩容太大，则会造成内存浪费；如果一次扩容太小，则势必很快又需要扩容，而扩容是一项很损耗性能的操作
 9         //所以JDK开发人员进行了时间和空间的折衷，以旧容量的1.5倍为新容量（注意容量大小是int类型，即 3扩容后不是4.5,而是4!）
10         int newCapacity = oldCapacity + (oldCapacity >> 1);
11         if (newCapacity - minCapacity < 0)
12             //若期望的最小扩容后的大小比这次扩容操作后的大小要来的大，则说明这次扩容操作不足以满足期望大小，直接将list的新容量设置为期望容量
13             newCapacity = minCapacity;
14         if (newCapacity - MAX_ARRAY_SIZE > 0)
15             //如果新容量即将达到Integer最大值*(2^31-1)，则调用超大扩容方法,避免扩容后数组大小超过Integer最大值
16             newCapacity = hugeCapacity(minCapacity);
17         // 这里的操作其实分为2步：
18         // 1.先将原数组扩容，返回一个新的、扩容后的空数组
19         // 2.调用Arrays的copyOf方法，将原数组对应索引处的值拷贝到新数组对应索引处
20         elementData = Arrays.copyOf(elementData, newCapacity);
21     }

 

用图片表示扩容的过程，更加直观：

 

3.获取集合中元素的方法

 1     /**
 2      * 返回list底层数组中指定索引处的元素
 3      *
 4      * @param  index 需要返回元素的索引
 5      * @return 数组中指定索引处的元素
 6      * @throws IndexOutOfBoundsException 数组越界异常
 7      */
 8     public E get(int index) {
 9         rangeCheck(index);  //先检查用户指定索引是否超出list当前元素数量
10 
11         return elementData(index);
12     }
13     
14     @SuppressWarnings("unchecked")
15     E elementData(int index) {
16         //直接取底层数组中index处的元素值返回
17         return (E) elementData[index];
18     }

最常用的取ArrayList中元素的方法，可以看到因为底层数据结构为数组，而数组默认维护了索引，所以ArrayList取值可以直接取到数组相应索引处的元素并返回，效率非常高。

 

4.设置集合中元素的方法

 1     /**
 2      * 以用户给定的值替换list底层数组index处的元素.
 3      *
 4      * @param index 需要替换list中元素所在的数组索引
 5      * @param element 用来替换的新值
 6      * @return 数组该索引处原先的值
 7      * @throws IndexOutOfBoundsException 数组越界异常
 8      */
 9     public E set(int index, E element) {
10 
11         rangeCheck(index); //先检查用户指定索引是否超出list当前元素数量
12 
13         E oldValue = elementData(index);  //获取旧值
14         elementData[index] = element;  //替换为新值
15         return oldValue;  //返回该索引处原先的旧值
16     }

给数组中某个索引处的元素设置新值，同样因为有索引，效率很高(ArrayList做查询操作效率很高的原因)。

 

5.往集合中添加元素的方法（尾部追加和指定index处添加两种）

 1 /**
 2      * 将用户传入的元素添加到当前list末尾元素所在数组索引的下一位置
 3      *
 4      * @param e 要添加的元素
 5      * @return 成功返回true，失败返回false
 6      */
 7     public boolean add(E e) {
 8         //保证当前list的数组大小能容纳再添加一个元素进去,如果不能，则扩容
 9         ensureCapacityInternal(size + 1); 
10         //数组索引从0开始，size从1开始，所以当前size处的数组索引就是list末尾元素的后一个位置，也即这个新元素应该存放的位置
11         //新元素添加至末尾后，list的总元素个数加1
12         elementData[size++] = e;
13         return true;
14     }

将新元素添加到list内部数组末尾的方法，同样用图片来表示该过程：

 

 

 

 1    /**
 2      * 将指定元素插入当前list的数组中自定义索引位置处
 3      * 并把该索引位置处原先的元素及其后位置的元素全部往后面移动一个索引的位置
 4      *
 5      * @param index 要插入新元素的数组索引位置
 6      * @param element 插入的新元素
 7      * @throws IndexOutOfBoundsException  数组越界异常
 8      */
 9     public void add(int index, E element) {
10         rangeCheckForAdd(index);  //检查用户传入的index是否在list元素总个数范围内
11         //保证当前list的数组大小能容纳再添加一个元素进去,如果不能，则扩容
12         ensureCapacityInternal(size + 1); 
13         //先将该位置原先的元素及其后所有元素全部往右移动一个索引的位置
14         System.arraycopy(elementData, index, elementData, index + 1,
15                          size - index);
16         //然后用新元素替换该索引处原先的元素
17         elementData[index] = element;
18         //全部完成后list的总元素个数加1
19         size++;
20     }

在指定索引位置处添加新元素，相比于直接在末尾追加元素，该方法需要把插入新元素的索引处原先的元素及其后元素全部往后边移动一个索引位置(ArrayList做插入、删除操作效率较差的原因)。

同样上图：

在集合中分别插入元素 "333"和插入元素"000"。

注意：无论是哪种add操作，都需要先判断当前list中数组的容量是否能容纳放入一个新元素，如果不能，则必须先进行扩容操作。

 

6.删除集合中元素的方法

 1    /**
 2      * 删除list中第一个符合用户期望删除的元素(支持删除null)
 3      * 如果用户期望删除的元素在list中不存在，则不做任何事,返回false
 4      * 如果用户期望删除的元素在list中存在，删除成功后，返回true.
 5      *
 6      * @param o 用户期望在list中删除的元素(如果存在的话)
 7      * @return  若list中存在用户期望删除的元素，返回true
 8      */
 9     public boolean remove(Object o) {
10         if (o == null) {
11             for (int index = 0; index < size; index++)
12                 if (elementData[index] == null) { //如果用户期望删除null，则循环数组，找到第一个值为null的索引位置，删除该位置的值
13                     fastRemove(index);
14                     return true;
15                 }
16         } else {
17             for (int index = 0; index < size; index++)
18                 if (o.equals(elementData[index])) { //循环数组,找到第一个符合用户期望删除的元素所处索引位置，删除该位置的值
19                     fastRemove(index);
20                     return true;
21                 }
22         }
23         return false;
24     }
25 
26     /*
27      * 实际调用的删除方法，不做边界检查也不返回任何值
28      */
29     private void fastRemove(int index) {
30         modCount++; 
31         int numMoved = size - index - 1;  //计算需要往左移动的元素个数
32         if (numMoved > 0)
33             //如果有元素需要移动（即用户指定要删除的index并不是list末尾元素所在的index），则将需要移动的元素全部向左移动一个index位置
34             //如果numMoved为0，则表示用户指定要删除的index位置就是当前list末尾元素所在的index，则无需做移动操作
35             System.arraycopy(elementData, index+1, elementData, index,
36                              numMoved);
37         //先将原来list末尾元素所在index处的值置为null，以便让GC发现并对其进行回收
38         //再将list总元素个数-1
39         elementData[--size] = null;
40     }

同样上图：

上图为删除集合中 "333"元素的过程。

注：以上图片均来源于  博客园——五月的仓颉 ，非本人原创 !

 

结束语

到这里ArrayList就差不多介绍完了，是不是感觉很简单呢？其实集合部分的源码主要就是针对基础的数据结构的各种操作进行封装后供我们日常使用，所以还是有必要好好学习算法与数据结构滴~

本篇文章也是我在博客园发表的第一篇文章，希望大家能够从中学到东西。如有错误的地方，还望大家多多包涵并指正，谢谢！