如果ArrayList是个人……
共 19031字，需浏览 39分钟
·
2021-04-28 21:21
庆哥： 今天给大家请到的是我们的ArrayList，相信今天的对话结束之后，大家对ArrayList就不会那么陌生了，好了，先请我们的ArrayList给大家做下自我介绍吧！
ArrayList介绍
ArrayList：大家好，我是ArrayList，想必在做的各位只要学习过Java，那一定都知道我吧，怎么说呢？其实我是属于Java中的基础知识，不过你可别小看我，在面试中，我可是重点对象，很多人应该都花时间去熟悉过我，可是我发现，很多人过不了多久就又把我忘的一干二净了，唉，真的好像你们去深入的了解我，记住我啊。
庆哥： 那你觉得大家应该如何更好的记住你呢？
ArrayList：其实大家不要去死记硬背，你们需要真正的深入我的内心，我希望的是大家能够真正的懂我……比如，你们可以先从我的构造函数去了解我。
庆哥： 为什么你会觉得大家都不懂你呢？
ArrayList：怎么说呢？先考考大家一个问题吧，大家是否能回答以下这个关于我的问题呢？
“我的源码中DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA是什么？它们有什么区别？
不知道有多少人能够回答出这个问题呢？如果你能回答出这个问题，我真的好开心，原来你的心里真有我。
庆哥： 想必懂你的人应该也不少吧，你觉得大家要想懂你应该先了解什么呢？
ArrayList重点前置知识
ArrayList：你们知道吗？想要了解我，你们需要熟悉数组扩容技术，数组大家都学过，什么随机访问，什么连续内存分布等等这些，但是你们还应该注重学习下数组的删除，那么，数组是做到如何删除的呢？
关于数组删除的问题
你们知道吗？数组其实并没有提供删除元素的方法，那么你想过它是如何做到删除元素的吗？
比如我们要删除中间的一个元素，怎么操作，首先我们可以把这个元素置为null，也就把这个元素删除掉了，此时数组上就空出了一个位置，这样行吗？
当我们再次遍历这个数组的时候是不是还是会遍历到这个位置，那么就会报空指针异常，怎么办？是的我们可以先判断，但是这样的做法不好，怎么办呢？
那就是我们可以把这个元素后面的所有元素统一的向前复制，有的地方这里会说移动，我觉得不够合理，为啥？
复制是把一个元素拷贝一份放到其他位置，原来位置元素还存在，而移动呢？区别就是移动了，原本的元素就不存在了，而数组这里是复制，把元素统一的各自向前复制，最终结果就是倒数第一和第二位置上的元素是相同的。
此时的删除的本质实际上是要删除的这个元素的后一个元素把要删除的这个元素给覆盖了，后面依次都是这样的操作，可能有点绕，自己想一下。
所以就引出了数组的删除操作是要进行数组元素的复制操作，也就导致数组删除操作最坏的时间复杂度是0(n)。
为什么说这个？因为对理解数组扩容技术很有帮助！
庆哥： 我觉得这个知识点，应该有不少人没有思考过吧。
数组扩容技术
ArrayList：是的，上面我们谈到了关于数组的删除操作，我们只是分析了该如何去删除，但是数组并未提供这样的方法，如果我们要搞个数组，这个删除操作还是要我们自己写代码去实现的。
不过好在已经有实现了，谁嘞，就是我 -- ArrayList，其实你们可以把我看作是数组的一个升级版，我的底层也是使用数组来实现，然后加上了很多操作数组的方法，比如上面分析的删除操作，当然除此之外，我肯定还实现了一些其他的方法，然后这就形成了一个独一无二的我了。
庆哥： 哈哈，经你这么一说，我就觉得吧：
“其实吧，你就是一个普通的类，然后对数组进行的封装，扩展其功能
ArrayList：言语过于直白，但是说的很对，对于数组，我们还了解一点那就是数组一旦确定就不能再被改变，但是我却可以实现自动扩容，有木有觉得很高级，其实也没啥，因为数组本身特性决定，我提供的自动扩容其实也是新创建一个数组而已，因为我的底层其实就是使用的数组。
你们的重点就是需要关注我的自动扩容的过程，就是怎么创建一个新的数组，创建完成之后又是怎么做的。
接下来我们看两种数组扩容方式。
Arrays.copyof
不知道你使用过没，我们直接看代码：
public static void main(String[] args) {
int[] a1 = new int[]{1, 2};
for (int a : a1) {
System.out.println(a);
}
System.out.println("-------------拷贝------------");
int[] b1 = Arrays.copyOf(a1, 10);
for (int b : b1) {
System.out.println(b);
}
}
代码不多，很简单，看看输出结果你就明白了
ok，是不是很简单，知道这个简单用法就ok了，接下来看另外一种
System.arraycopy()
这个方法我们看看是个啥：
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
看见没，native修饰的，一般是使用c/c++写的，性能很高，我们看看这里面的这几个参数都是啥意思：
“src：要拷贝的数组 srcPos：要拷贝的数组的起始位置 dest：目标数组 destPos：目标数组的起始位置 length：你要拷贝多少个数据
怎么样，知道这几个参数什么意思了，那使用就简单了，我这里就不显示了。
“ps：以后复制数组别再傻傻的遍历了，用这个多香
以上两个方法都是进行数组拷贝的，这个对理解数组扩容技术很重要，而且我也有也有应用，我们等会会详细说。
下面我就给大家看看我的一些源码，希望加深大家对我的了解！
庆哥： 接下来就是大家真正去读懂你的时候啦！
源码中的我
ArrayList：我会好好介绍的，毕竟我需要更多的人去懂我，首先，大家一般都是怎么使用我的呢？
ArrayList arrayList = new ArrayList();
arrayList.add("hello");
arrayList.add(1);
ArrayList<String> stringArrayList = new ArrayList<>();
stringArrayList.add("hello");
简单，都会吧，就是把我给new出来，不过上面的代码我还想说明一个问题，当你不指定具体类型的时候我是可以存储任意类型的数据的，指定的话就只能存储特定类型，为啥不指定可以存储任意类型？
这个问题不做解释，等会看源码你就明白了。
看看我的无参构造函数
一般大家看我的源码，都应该从我的无参构造函数开始，也就是这个：
new ArrayList();
好啦，走进去看看这里我到底做了什么了吧。
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
是不是很简单，我这里其实就有个赋值操作，你们需要了解两个新东西，就是elementData和DEFAULTCAPACITY_EMPTY_ELEMENTDATA，这是啥？
这是什么呢？
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
这不就是Object数组嘛，好像还真是的，那transient啥意思？它啊，你就记住被它修饰序列化的时候会被忽略掉。
好了，除此之外，就是个数组，对Object类型的。
不好像有点区别啊，DEFAULTCAPACITY_EMPTY_ELEMENTDATA已经指定是个空数组了，而elementData只是声明，在new一个ArrayList的时候进行了赋值，也就是这样：
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
咋样？明白了吧，之前不就说了嘛，我的底层就是一个数组，这里你看，你们把我new出来其实就是给你弄个空数组出来，也就是说啊，你要使用我，一开始先new一下，然后我给你搞个空数组出来。
啥？空数组？空数组怎么行呢？毕竟你们还需要用我存数据嘞，所以啊，重点来了，来看看我的add，也就是添加数据的操作。
看看我的添加操作
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
**庆哥：**看到这段代码，让我比较疑惑的就是这个了：
ensureCapacityInternal(size + 1);
这单词啥意思啊，唉，我这英语啊，我翻一下得知，这个是确保内部容量的意思，啥意思啊？这里还有个size又是啥啊？
ArrayList：别着急，给你看看这个size：
private int size;
这就是一个变量，你再看看这段代码：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
尤其是：
elementData[size++] = e;
庆哥： 实话说，有点小懵……之前把你new出来的时候，你创建了一个空数组就是elementData，这好像是在往你创建的这个空数组里面放数据啊，不过不对啊，不是空数组嘛？咋能放数据？
ArrayList：你看，这不是前面还有这一步嘛：
ensureCapacityInternal(size + 1);
是不是有想法了，这一步就是把数组的容量给确定下来的，赶紧进去看看：
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
就是这个了，这一步很重要:
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
也好理解吧，就是这里我先判断下我的底层数组elementData 是不是刚创建的的空数组，这里肯定是啊，然后开始执行：
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
minCapacity是个啥（重要）
庆哥： 这个minCapacity是个啥？
ArrayList：它现在其实就是底层数组将要添加的第几个元素，看看上一步
ensureCapacityInternal(size + 1);
这里size+1了，所以现在minCapacity 相当于是1，也就是我的底层数组将要被添加第一个元素了，这一点的理解很重要，所以从minCapacity 的字面意思理解也就是“最小容量”，你现在将要添加第一个元素，那我至少给你保证我的底层数组有一个空位置，不然你怎么放数据嘞。
重点来了，因为你是第一次添加，我的底层数组刚开始是没有一个位置的，所以需要先确定下来一共有多少个位置，就是先给数组一个默认的长度。
于是这里给重新赋值了（只有第一次添加数据才会执行这步，这一步就是为了指定默认数组长度的，指定一次就ok了）
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
这怎么赋值的应该知道嘛，哪个大取哪个，那我们要看看DEFAULT_CAPACITY是多少了
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
庆哥： 哇哇哇，我似乎懂了，这里的10不就是你的的底层数组的初始化容量嘛？
ArrayList：完全正确，但是我现在的底层数组长度可还不是10，也就是这里，我做的事情很简单，你要添加数据给我，但是我刚开始创建的是一个空数组啊，没办法，没位置了，可是你要添加数据了，怎么办，我先搞一个默认的长度吧，就是先弄出来一些位置，那弄多少位置呢先弄10个吧，也就是这里的minCapacity就是10了，我们再接着看下面的代码，也即是：
ensureExplicitCapacity(minCapacity);
进去看看吧：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
也比较简单，我现在底层数组长度肯定还不到10啊，所以我们继续看grow方法：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
庆哥： 怎么突然觉得代码多了起来，哈哈
ArrayList：咋一看，判断确实不少啊，干啥的都是，不过，你看，是不是有个Arrays.copyOf，知道这是啥吧，上面我可是特意讲过的，原来这是要进行数组拷贝啊，那这个elementData就是原来的数组，newCapacity就是新数组的容量
我们一步步来看代码，首先是：
int oldCapacity = elementData.length;
得到原来数组的容量，接着下一步：
int newCapacity = oldCapacity + (oldCapacity >> 1);
庆哥： 这是得到新容量的吧，不过后面的这个oldCapacity >> 1有点看不懂啊
ArrayList：其实这oldCapacity >> 1就相当于oldCapacity /2，这是移位运算，感兴趣的自行搜索学习。
说白了，也就是扩容为原来的1.5倍，接下来这一步：
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
因为目前数组长度为0，所以这个新的容量也是0，而minCapacity 则是10，所以会执行方法体内的赋值操作，也就是现在的新容量成了10。
接着这句代码就知道怎么回事了：
elementData = Arrays.copyOf(elementData, newCapacity);
不知道你发现没，这里绕了一大圈，我其实就是为了创建一个默认长度为10的底层数组。
底层数组长度要看ensureCapacityInternal
ensureCapacityInternal这个方法就像我的一个守卫，时刻监视着我的底层数组容量，然后过来一个数值，也就是说要向数组添加第几个数据，那ensureCapacityInternal需要思考思考了，思考啥呢？当然是看底层数组有没有这么大容量啊，比如你要添加第11个元素了，那我的底层数组长度最少也得是11啊，不然添加不了啊，看它是怎么帮我把关的：
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
记住了这段代码
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
它的存在就是为了一开始创建默认长度为10的数组的，当添加了一个数据之后就不会再执行这个方法，所以重难点是这个方法：
ensureExplicitCapacity(minCapacity);
也就是真正的把关在这里，看它的实现：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
怎么样，看明白了吧，比如你要添加第11个元素，可是我的底层数组长度只有10，不够啊，然后执行grow方法，干嘛执行这个方法，它其实就是用来扩容的，不信你再看看它的实现，上面已经分析过了，这里就不说了。
假如你要添加第二个元素，这里底层数组长度为10，就不需要执行grow方法，因为根本不需要扩容啊，所以这一步实际啥也没做（有个计数操作）：
然后就直接在相应位置赋值了。
庆哥： 感觉信息量好大啊……
ArrayList：所以这里很重要的一点就是理解这一步传入的值的意义：
ensureCapacityInternal(size + 1);
“简单点就是要向底层数组中添加第几个元素了，然后开始进行一系列的判断，容量够的话直接返回，直接赋值，不够的话就执行grow方法开始扩容。
主要判断就在这里：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
具体的扩容是这里:
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
这里需要注意这段代码:
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
这段代码只有在第一次添加数据的时候才会执行，也是为创建默认长度为10的数组做准备的，因为这个时候原本数组长度为0，扩容后也是0，而minCapacity 为默认值10，所以会执行这段代码。
但是一旦添加数据之后，底层数组默认就是10了，再加上之前的判断，这里的newCapacity 一定会比minCapacity 大，这个点需要了解。
看看我的有参构造函数
我们上面着重分析了下我的无参构造函数，下面再来看看我的有参构造函数：
ArrayList arrayList1 = new ArrayList(100);
先来看看我的这个构造函数张啥样？
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
庆哥： 觉得这里就是直接创建啊
ArrayList：没错，再来看看这个：
else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
}
我们看看这个EMPTY_ELEMENTDATA:
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
ok，现在大家可以回答我开篇提的那个问题了吧。
以上大家应该对我的源码有了一定的认识，接下来我们再来看看关于我的读取，替换和删除操作是怎样的？
我的其他操作
经过上面的分析，我相信你对我的其他诸如读取删除等操作也没啥问题，一起来看下。
读取操作
先来看看我这块的源码：
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
代码很简单，rangeCheck就是用来判断数组是否越界的，然后直接返回下标对应的值。
删除操作
看源码
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
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
return oldValue;
}
代码相对来说多一些，要理解这个，可以仔细看看我上面对“关于数组删除的一些思考”的分析，这里是一样的道理。
替换操作
看源码
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
其实就是把原来的值覆盖，没啥问题吧
和vector很像
这个想必大家都知道，我和vector是很像的，只不过我是线程不安全，而vector这个家伙是线程安全，我们看一下vector一段源码就明白了
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
没错，区别就是这么明显！
总结
庆哥： 感觉今天又重新认识了一遍你（ArrayList）
ArrayList：到这里，我基本上把自己的相关重点都过了一遍，其实吧，对于我来说，重点就是分析我的无参构造函数的执行，经过分析，我们知道了其实我是有个数组拷贝的操作，这块是会影响到我的一些操作的时间复杂度的，关于这点，就留给大家取思考吧！
另外啊，我在开篇也说过了，很多人其实也都有花时间去了解过我，只不过对我的熟悉也只是一阵子，过不了多久基本上就忘了，知识的学习其实就是这样，温故而知新，是需要大家经常回顾的，所以，我也希望大家时不时的去回顾一下我，希望不要把我给忘掉，希望大家能真正懂我！
本文完！
往期推荐：