本帖最后由 小蜀哥哥 于 2019-2-13 09:39 编辑
Java中ArrayList源码解析
前言
集合是Java开发人员必不可少的一个工具，而ArrayList是Java集合中的最为常用的一种，了解其底层原理能让
我们更好的去使用它。本文将通过对于ArrayList类中源代码的分析来逐步揭开其底层原理的神秘面纱 。
1. ArrayList的本质
我们从ArrayList类源码中找到一个非常重要的成员变量：
[Java] 纯文本查看 复制代码 transient Object[] elementData;
elementData翻译过来可以理解为：元素数据，其实这个Object类型的数组就是最终ArrayList存放数据的容
器，由此可知，其实ArrayList的底层就是一个Object数组，而我们对集合元素的操作，本质上就是操作的这
个数组。
众所周知，集合其实本质上就是一个容器，而ArrayList其实就是众多容器的一种，其实数组也是一种容器，
为什么程序员会更偏爱集合呢，最重要的原因就是：集合的长度是可以随着元素的增删而产生变化的，而数
组的长度一旦数组初始化完毕就已经固定了。我们来看一段代码：
[Java] 纯文本查看 复制代码 public class Test {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
// 当集合添加四个元素后，集合的长度就是4
System.out.println("集合的长度为：" + list.size()); // 集合的长度为：4
// 当集合再次添加一个元素，集合的长度就已经变成了5
list.add("e");
System.out.println("集合的长度为：" + list.size()); // 集合的长度为：5
System.out.println("=================");
// 对于数组来说，一旦初始化完毕，数组的长度就已经固定了，不会随着元素的赋值而改变
String[] strs = new String[5];
strs[0] = "a";
strs[1] = "b";
strs[2] = "c";
strs[3] = "d";
System.out.println("数组的长度为："+strs.length); // 数组的长度为：5
strs[4] = "e";
System.out.println("数组的长度为："+strs.length); // 数组的长度为：5
}
}
以上代码已经说明了使用集合的优点，长度可以动态的变化，免去了我们很多的烦恼。那么现在问题来了，我们已经说过了，数组的长度是固定的，而ArrayList集合的底层是数组，长度却是可以变化的，那么这不是自相矛盾吗？接下来我们通过集合"增删改查"四个功能的源码分析来揭晓答案。
2. ArrayList源码解析之添加功能
2.1 添加功能源码
我们都知道，元素添加的功能是add方法，话不多说，直接上源码（我已经添加了中文注释帮助阅读）：
[Java] 纯文本查看 复制代码 public boolean add(E e) {
// modCount是用于统计元素修改次数的变量，最终会用于检测并发修改异常，可参见我的另一篇文章：Java并发修改异常的源码解析
modCount++;
// 添加元素的方法
add(e, elementData, size);
// 由于ArrayList允许添加重复元素，所以元素必定添加成功，返回值恒为true
return true;
}
private void add(E e, Object[] elementData, int s) {
// s为集合元素的个数，elementData.length为数组的长度，如果元素的个数已经等于集合的长度，那么数组就需要扩容了
if (s == elementData.length)
// grow为扩容的方法，返回一个扩容后的新数组
elementData = grow();
// 将新添加进来的元素赋值给数组的对应位置。（size-1为最后一个元素的位置，那么size就是第一个空的位置）
elementData = e;
// 添加完一个元素后，长度+1
size = s + 1;
}
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity)); // copyOf是一个数组复制的方法，会将已有的元素都复制到一个更大的数组中，并返回新数组。
}
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // newCapacity是新数组的容量，等于旧数组容量的1.5倍
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
2.2 添加功能源码分析
1. 第一个add方法中的第二行调用了第二个add方法，传递了三个参数，e表示要添加到集合中的元
素，elementData则是存储元素的数组，size是集合元素的个数
2. 第二个add方法中，进行了一个集合容量的判断：如果元素的个数已经等于集合的长度，那么数组
就需要扩容了，扩容调用的是grow方法。
3. grow方法中返回了一个新的数组，由newCapacity方法中的代码——int newCapacity =
oldCapacity + (oldCapacity >> 1)——可知，新数组的容量，等于旧数组容量的1.5倍。并将旧数组
的长度复制到的新数组中。
4. 扩容完毕后，回到第二个add方法中完成新元素的添加，并让记录元素个数的变量size值+1
以下是添加功能流程图：
2.3 添加功能总结
到目前为止我们已经分析完了ArrayList添加元素的源代码，我们可以发现，原来ArrayList集合底层存储元素
的数组和我们使用的数组相比并没有长度可变的"特异功能"，实际是通过创建新数组扩容来达到使得集合长度
动态变化的目的，并且通过size值的变化来记录元素个数。
接下来要分析的删除方法相信你心中也有底了。
3. ArrayList源码解析之删除功能
3.1 删除功能源码
删除功能我们分析remove功能，上源码：
[Java] 纯文本查看 复制代码 public boolean remove(Object o) {
// 如果要删除的元素值为null，则遍历数组查找null第一次出现的位置
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
// 调用方法删除这个数据
fastRemove(index);
return true;
}
} else {
// 如果要删除的元素不为null，则遍历数组查找元素第一次出现的位置，并将元素删除
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
// 如果没有找到需要被删除的元素，则返回false，表示删除失败。
return false;
}
// 快速删除对应索引位置的元素
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
3.2 删除功能源码分析
1. remove方法中先对元素进行了为null的判断，这样做的好处是避免传递进来null造成元素内容比较时的空指针异常。
2. 无论是否为null，进行的操作都比较类似：先遍历所有元素，查找要删除的元素第一次出现的索引位置，如果找到了，则调用方法快速删除，并返回true表示删除成功
3. fastRemove方法中，对元素的删除，本质上就是把要删除元素位置后的所有元素往前移动一位，将要被删除的元素覆盖掉
4. 如果遍历结束后还没找到要删除的元素，则表示要删除的元素在集合中不存在，所以在remove方法的最后返回false，表示删除失败。
以下是删除功能流程图：
3.3 删除功能总结
删除功能源码已经分析完了，ArrayList的删除分为两步：1. 找到被删除的元素。2. 把要删除元素用后续的元素覆盖掉。当然，如果要删除的元素是最后一个元素，则会把最后一个元素值设置为null，达到删除元素的效果。
接下来要分析的修改和获取功能就非常简单了。
4. ArrayList源码解析之修改功能和获取功能
4.1 修改功能源码
修改功能方法名为set，接收一个被修改元素的索引和新的元素，上源码：
[Java] 纯文本查看 复制代码 public E set(int index, E element) {
// 检查是否索引越界，如果越界，则抛出异常
Objects.checkIndex(index, size);
// 先把被修改的元素用一个变量存储起来
E oldValue = elementData(index);
// 将新的值赋值给被修改元素的位置
elementData[index] = element;
// 返回被修改的元素
return oldValue;
}
4.2 修改功能源码分析
1. 由于修改元素需要指定被修改元素的索引位置，所以第一步先用checkIndex方法检查索引是否超出正常索引范围。
2. 把要被修改的元素先用一个变量存储起来，以便于最后返回。
3. 修改元素就是把对应位置元素赋值为新的值
4. 最后返回被修改的值。
4.3 获取功能源码
获取集合元素的功能为get，需要传递一个索引值，返回对应索引位置的元素，源码如下：
[Java] 纯文本查看 复制代码 public E get(int index) {
// 检查index是否索引越界
Objects.checkIndex(index, size);
// 返回index所在的元素值
return elementData(index);
}
4.5 获取功能源码分析
1. 先检查要获取元素的索引是否越界，如果越界则会抛出索引越界异常
2. 将数组中对应索引位置的元素返回
4.6 获取和修改功能总结
由于ArrayList是用一个数组来存储元素的，所以获取功能和修改功能都非常简单。而在源码中，这两个功能第一步都对索引值进行了正确性判断，这提醒我们以后的开发中需要更全面的考虑各种情况，保证代码的健壮性。
5. 总结
那么到目前为止，我们已经通过对ArrayList最主要的"增删查改"四个功能源码的分析，完成了本文对于ArrayList的介绍。我们可以做出以下总结：
数组本身是不可变的，ArrayList通过新数组的创建等操作，巧妙的完成了容器长度的变化。一些常见的异常，比如空指针异常和索引越界异常，ArrayList的功能都进行了比较全面的健壮性判断，值得我们学习。
以上就是本文的全部内容，谢谢观看。
| 
收藏
淘帖
踩
