从面试角度分析 ArrayList 源码
注:本系列文章中用到的 jdk 版本均为
java8
ArrayList
类图如下:
ArrayList
的底层是由数组实现的,数组的特点是固定
大小,而ArrayList
实现了动态扩容
。
ArrayList
部分变量如下,在下面的分析中会用到这些变量。
一、初始化 ArrayList
初始化ArrayList
一般会使用以下两个构造器
1.1 无参构造器
初始化ArrayList
的时候如果不指定大小,则会创建一个空数组。
1.2 指定数组大小的构造器
创建一个预估大小的数组,指定大小后只是指定了数组初始值的大小,不影响后面扩容,指定的好处就是可以节省内存及时间上的开销。
二、添加元素、动态扩容
ArrayList.add(E e)源码:
add()
中elementData[size++] = e
很好理解,就是将元素插入第size
个位置,然后将size++
,我们重点来看看ensureCapacityInternal(size + 1)
方法;
ensureCapacityInternal()
方法中判断缓存变量elementData
是否为空,也就是判断是否是第一次添加元素,如果是第一次添加元素,则设置初始化大小为默认容量10
,否则为传入的参数。这个方法的目的就是**获取初始化数组容量**。获取到初始化容量后调用ensureExplicitCapacity(minCapacity)
方法;
ensureExplicitCapacity(minCapacity)
方法用来判断是否需要扩容,假如第一次添加元素,minCapacity
为10
,elementData
容量为0
,那么就需要去扩容。调用grow(minCapacity)
方法。
grow(minCapacity)
方法对数组进行扩容,扩容大小为原数组的1.5
倍,如果计算出的扩容容量比需要的容量小,则扩容大小为需要的容量,如果扩容容量比数组最大容量大,则调用hugeCapacity(minCapacity)
方法,将数组扩容为整数的最大长度,然后将elemetData
数组指向新扩容的内存空间并将元素复制到新空间。
当需要的集合容量特别大时,扩容1.5
倍就会非常消耗空间,因此建议初始化时预估一个容量大小。
三、删除元素
ArrayList
提供两种删除元素的方法,可以通过索引
和元素
进行删除。两种删除大同小异,删除元素后,将后面的元素一次向前移动。
ArrayList.remove(int index)源码:
删除元素时,首先会判断索引是否大于ArrayList
的大小,如果索引范围正确,则将索引位置的下一个元素赋值到索引位置,将ArrayList
的大小-1
,最后返回移除的元素。操作图如下,假如我要移除索引为1
的元素:
四、总结
ArrayList
底层是数组实现的,可以进行动态扩容,扩容大小为原来的 1.5 倍,虽然可以通过动态扩容,但是数组非常大时会特别浪费空间,因此建议初始化时预估数组大小。ArrayList
允许插入重复值和空值。ArrayList
实现了RandomAccess
接口,支持快速随机访问,就是可以通过索引快速查到某个元素,因此遍历时使用 for 循环的方式效率更高。ArrayList
是线程不安全的,可以通过Collections.synchronizedList
将其转变为线程安全的集合,不过一般不会使用,Vector
和CopyOnWriteArrayList
是线程安全的,Vector
性能一般,逐渐被CopyOnWriteArrayList
取代了。
点关注、不迷路
如果觉得文章不错,欢迎关注、*点赞*、收藏,你们的支持是我创作的动力,感谢大家。
如果文章写的有问题,请不要吝惜文笔,欢迎留言指出,我会及时核查修改。
如果你还想看到更多别的东西,可以微信搜索「Java 旅途」进行关注。「Java 旅途」目前已经整理各种中间件的使用教程及各类 Java 相关的面试题。扫描下方二维码进行关注就可以得到这些资料。
版权声明: 本文为 InfoQ 作者【Java旅途】的原创文章。
原文链接:【http://xie.infoq.cn/article/76e4c35c86a4b95d8a56235dc】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论