ArrayList属于Java基础知识,面试中会经常问到,所以作为一个Java从业者,它是你不得不掌握的一个知识点。:sunglasses:
可能很多人也不知道自己学过多少遍ArrayList,以及看过多少相关的文章了,但是大部分人都是当时觉得自己会了,过不了多久又忘了,真的到了面试的时候,自己回答的支支吾吾,自己都不满意:disappointed_relieved:
为什么会这样?对于ArrayList这样的知识点的学习,不要靠死记硬背,你要做的是真的理解它!:grin:
我这里建议,如果你真的想清楚的理解ArrayList的话,可以从它的构造函数开始,一步步的读源码,最起码你要搞清楚add这个操作,记住,是源码:smile:
很多人已经学习过ArrayList了,读过源码的也不少,这里给出一个问题,大家可以看看,以便测试下自己对ArrayLIst是否真的掌握:
请问在ArrayList源码中DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA是什么?它们有什么区别?
怎么样?如果你能很轻松的回答上来,那么你掌握的不错,不想再看本篇文章可以直接出门右拐(我也不知道到哪),如果你觉得不是很清楚,那就跟着我继续往下,咱们再来把ArrayList中那些重点过一遍!:sunglasses:
在我看来,ArrayList的一个相当重要的点就是 数组扩容技术 ,我们之前学习过数组,想一下数组是个什么玩意以及它有啥特点。
随机访问,连续内存分布等等,这些学过的都知道,这里说一个似乎很容易被忽略的点,那就是数组的删除,想一下,数组怎么做删除?:smirk:
关于数组的删除,我之前也是有疑惑,后来也花时间思考了一番,算是比较通透了,这里就提一点,数组并没有提供删除元素的方法,我们都是怎么做删除的?
比如我们要删除中间的一个元素,怎么操作,首先我们可以把这个元素置为null,也就把这个元素删除掉了,此时数组上就空出了一个位置,这样行吗?
当我们再次遍历这个数组的时候是不是还是会遍历到这个位置,那么就会报空指针异常,怎么办?是的我们可以先判断,但是这样的做法不好,怎么办呢?
那就是我们可以把这个元素后面的所有元素统一的向前复制,有的地方这里会说移动,我觉得不够合理,为啥?
复制是把一个元素拷贝一份放到其他位置,原来位置元素还存在,而移动呢?区别就是移动了,原本的元素就不存在了,而数组这里是复制,把元素统一的各自向前复制,最终结果就是倒数第一和第二位置上的元素是相同的。
此时的删除的本质实际上是要删除的这个元素的后一个元素把要删除的这个元素给覆盖了,后面依次都是这样的操作,可能有点绕,自己想一下。
所以就引出了数组的删除操作是要进行数组元素的复制操作,也就导致数组删除操作最坏的时间复杂度是0(n)。
为什么说这个?因为对理解数组扩容技术很有帮助!
上面我们谈到了关于数组的删除操作,我们只是分析了该如何去删除,但是数组并未提供这样的方法,如果我们要搞个数组,这个删除操作还是要我们自己写代码去实现的。
不过好在已经有实现了,谁嘞,就是我们今天的主角ArrayList,其实ArrayList就可以看作是数组的一个升级版,ArrayList底层也是使用数组来实现,然后加上了很多操作数组的方法,比如我们上面分析的删除操作,当然除此之外,还实现了一些其他的方法,然后这就形成了一个新的物种,这就是ArrayList。
本质上ArrayList就是一个普通的类,对数组进行的封装,扩展其功能
对于数组,我们还了解一点那就是数组一旦确定就不能再被改变,而这个ArrayList却可以实现自动扩容,有木有觉得很高级,其实也没啥,因为数组本身特性决定,ArrayList所谓的自动扩容其实也是新创建一个数组而已,因为ArrayList底层就是使用的数组。
我们的重点需要关注的是这个自动扩容的过程,就是怎么创建一个新的数组,创建完成之后又是怎么做的,这才是我们关注的重点。
接下来我们看两种数组扩容方式。
不知道你使用过没,我们直接看代码:
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了,接下来看另外一种
这个方法我们看看是个啥:
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
看见没,native修饰的,一般是使用c/c++写的,性能很高,我们看看这里面的这几个参数都是啥意思:
src:要拷贝的数组
srcPos:要拷贝的数组的起始位置
dest:目标数组
destPos:目标数组的起始位置
length:你要拷贝多少个数据
怎么样,知道这几个参数什么意思了,那使用就简单了,我这里就不显示了。
ps:以后复制数组别再傻傻的遍历了,用这个多香:smile:
以上两个方法都是进行数组拷贝的,这个对理解数组扩容技术很重要,而且在ArrayList中也有应用,我们等会会详细说。
下面咱们开始看看ArrayList的一些源码,加深我们对ArrayList的理解!
一般我们是怎么用ArrayList的呢?看下面这些代码:
ArrayList arrayList = new ArrayList(); arrayList.add("hello"); arrayList.add(1); ArrayList<String> stringArrayList = new ArrayList<>(); stringArrayList.add("hello");
简单,都会吧,就是new一个出来,不过上面的代码我还想说明一个问题,当你不指定具体类型的时候是可以存储任意类型的数据的,指定的话就只能存储特定类型,为啥不指定可以存储任意类型?
这个问题不做解释,等会看源码你就明白了。
一般我们看ArrayList的源码,都是从它的无参构造函数开始看起的,也就是这个:
new ArrayList();
好啦,走进去看看这个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;
咋样?明白了吧,之前不就说了嘛,ArrayList底层就是一个数组的,这里你看,new之后不就给你弄个空数组出来嘛,也就是说啊,你要使用ArrayList,一开始先new一下,然后给你搞个空数组出来。
啥?空数组?空数组怎么行呢?毕竟我们还需要用它存数据嘞,所以啊,重点来了,我们看它的add,也就是添加数据的操作。
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
就是这个啦,ArrayList不就是使用add来添加数据嘛,我们看看是怎么操作的,咋一看这段代码,让我们感到比较陌生的就是这个方法了
ensureCapacityInternal(size + 1);
这是啥玩意,翻译一下:joy:
确保内部容量?什么鬼,这里还有个size,我们看看是啥?
private int size;
就是一个变量啊,我们再看看这段代码
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
尤其是
elementData[size++] = e;
知道了嘛?我们之前不是已经创建了一个空数组,不就是elementData嘛,这好像是在往数组里面放数据啊,不过不对啊,不是空数组嘛?咋能放数据,这不是前面还有这一步嘛
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); }
也好理解吧,就是先判断下现在这个ArrayList的底层数组elementData 是不是刚创建的的空数组,这里肯定是啊,然后开始执行
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
说这个之前,你先得搞清楚这个minCapacity 是啥,它现在其实就是底层数组将要添加的第几个元素,看看上一步
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;
ok,明白了,这就是ArrayList的底层数组elementData初始化容量啊,是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); }
咋一看,判断不少啊,干啥的都是,突然看到了Arrays.copyOf,知道这是啥吧,上面可是特意讲过的,原来这是要进行数组拷贝啊,那这个elementData就是原来的数组,newCapacity就是新数组的容量
我们一步步来看代码,首先是
int oldCapacity = elementData.length;
得到原来数组的容量,接着下一步:
int newCapacity = oldCapacity + (oldCapacity >> 1);
这是得到新容量的啊,不过后面的这个oldCapacity >> 1有点看不懂啊,其实这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需要思考思考了,思考啥呢?当然是看底层数组有没有这么大容量啊,比如你要添加第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方法,因为根本不需要扩容啊,所以这一步实际啥也没做(有个计数操作):
然后就直接在相应位置赋值了。
所以这里很重要的一点就是理解这一步传入的值的意义:
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的无参构造函数,下面再来看看它的有参构造函数:
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); } }
我去,这不就是直接创建嘛,然后还有这个:
else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; }
我们看看这个EMPTY_ELEMENTDATA
private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
ok,现在你可以回答我们开篇提的那个问题了吧。
我们以上对ArrayList的源码有了一定的认识之后,我们再来看看ArrayList的读取,替换和删除操作时怎样的?
经过上面的分析,我相信你对ArrayList的其他诸如读取删除等操作也没啥问题,一起来看下。
看源码
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; }
其实就是把原来的值覆盖,没啥问题吧:smile:
这个想必大家都知道,ArrayList和vector是很像的,前者是线程不安全,后者是线程安全,我们看一下vector一段源码就明白了
public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; }
没错,区别就是这么明显!
到这里,我们基本上把ArrayList的相关重点都过了一遍,对于ArrayList来说,重点就是分析它的无参构造函数的执行,经过分析,我们知道了它有个数组拷贝的操作,这块是会影响到它的一些操作的时间复杂度的,关于这点,就留给大家取思考吧!
好了,今天就到这里,大家如果有什么问题,欢迎留言,一起交流学习!
大家好,我是ithuangqing,一路走来积累了不少的学习经验和方法,而且收集了大量的精品学习资源,现在维护了一个公众号【 编码之外 】,寓意就是在编码之外也要不停的学习,主要分享java技术相关的原创文章,现在主要在写 数据结构与算法,计算机基础,线程和并发以及虚拟机 这块的原创,另外针对小白还在连载一套《 小白的java自学课 》,力求通俗易懂,由浅入深。同时我也是个工具控,经常分享一些 高效率的黑科技工具及网站 。
对了,公众号还分享了很多我的学习心得,可以一起探讨探讨!
关注公众号,后台回复“庆哥”,2019最新java自学资源立马送上!更多原创精彩尽在【编码之外】