Java 集合框架 ArrayList 源码剖析
ArrayList实现了List接口,是顺序容器,即元素存放的数据与放进去的顺序相同,允许放入null元素,底层通过数组实现。除该类未实现同步外,其余跟Vector大致相同。每个ArrayList都有一个容量(capacity),表示底层数组的实际大小,容器内存储元素的个数不能多于当前容量。当向容器中添加元素时,如果容量不足,容器会自动增大底层数组的大小。前面已经提过,Java泛型只是编译器提供的语法糖,所以这里的数组是一个Object数组,以便能够容纳任何类型的对象。
size(), isEmpty(), get(), set()方法均能在常数时间内完成,add()方法的时间开销跟插入位置有关,addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。
为追求效率,ArrayList没有实现同步(synchronized),如果需要多个线程并发访问,用户可以手动同步,也可使用Vector替代。
方法剖析
set()
既然底层是一个数组ArrayList的set()方法也就变得非常简单,直接对数组的指定位置赋值即可。
public E set(int index, E element) { rangeCheck(index);//下标越界检查 E oldValue = elementData(index); elementData[index] = element;//赋值到指定位置,复制的仅仅是引用 return oldValue; }
get()
get()方法同样很简单,唯一要注意的是由于底层数组是Object[],得到元素后需要进行类型转换。
public E get(int index) { rangeCheck(index); return (E) elementData[index];//注意类型转换 }
add()
跟C++ 的vector不同,ArrayList没有bush_back()方法,对应的方法是add(E e),ArrayList也没有insert()方法,对应的方法是add(int index, E e)。这两个方法都是向容器中添加新元素,这可能会导致capacity不足,因此在添加元素之前,都需要进行剩余空间检查,如果需要则自动扩容。扩容操作最终是通过grow()方法完成的。
private void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1);//原来的3倍 if (newCapacity – minCapacity < 0) newCapacity = minCapacity; if (newCapacity – MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity);//扩展空间并复制 }
由于Java GC自动管理了内存,这里也就不需要考虑源数组释放的问题。
空间的问题解决后,插入过程就显得非常简单。
add(int index, E e)需要先对元素进行移动,然后完成插入操作,也就意味着该方法有着线性的时间复杂度。
addAll()
addAll()方法能够一次添加多个元素,根据位置不同也有两个把本,一个是在末尾添加的addAll(Collection c)方法,一个是从指定位置开始插入的addAll(int index, Collection c)方法。跟add()方法类似,在插入之前也需要进行空间检查,如果需要则自动扩容;如果从指定位置插入,也会存在移动元素的情况。
addAll()的时间复杂度不仅跟插入元素的多少有关,也跟插入的位置相关。
remove()
remove()方法也有两个版本,一个是remove(int index)删除指定位置的元素,另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()操作的逆过程,需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用,必须显式的为最后一个位置赋null值。
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; //清除该位置的引用,让GC起作用 return oldValue; }
关于Java GC这里需要特别说明一下,有了垃圾收集器并不意味着一定不会有内存泄漏。对象能否被GC的依据是是否还有引用指向它,上面代码中如果不手动赋null值,除非对应的位置被其他元素覆盖,否则原来的对象就一直不会被回收。
原文发布时间为:2018-08-06
本文作者:Java杂记
本文来自云栖社区合作伙伴“Java杂记”,了解相关信息可以关注“Java杂记”
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
你真的了解博客园的目录么。。
前言 事情是这样的,最近忙着软件测试没注意博客园的消息,今天无意间点开看到这个: 非常感谢这位盆友能发现这个问题,奖励鸡腿,这是那篇博文:要嫁就嫁程序员,因为。。。 恩?,博客园的目录设置在手机端居然有问题,一直都用电脑没注意,我赶紧用手机点开一看 好端端的文章全部被目录给遮住了,影响阅读,很影响心情啊;我赶快找找解决办法; 目前我学会了目录的四种形式: 1.目录在侧边栏: 示例:https://www.cnblogs.com/clwydjgs/p/9290075.html 也就是我现在用的这个目录,我让目录在侧边栏显示,这样手机端不受任何影响,只是网页端的美化效果没有之前的好; 方法: 在页首HTML中加入: 1 <link href="http://files.cnblogs.com/files/clwydjgs/cnblog-scroller.css" type="text/css" rel="stylesheet"> 2 <script src="http://files.cnblogs.com/files/clwydjgs/scrollspy.js" typ...
- 下一篇
你真的懂JavaScript计时器吗?
在今天之前我一直以为setTimeout这个函数是异步的,无意中看到了一篇关于setTimeout的文章,发现自己以前的认识全是错误的,赶紧总结下。 先看一段代码: var start = new Date(); setTimeout(function(){ var end = new Date(); console.log("Time elapsed: ", end - start, "ms"); }, 500); while (new Date - start <= 1000) { } 运行这段脚本可以看到:Time elapsed的值大概在1001ms左右,肯定会超过1000ms。也就是说:setTimeout失效了,指定的函数并没有在500ms后执行,而是延迟到1000ms后才执行。 再看一段代码: function a() { setTimeout(function(){console.log(1);},0); console.log(2); } a(); 运行这段脚本可以看到:先打印2后打印1,我们在setTimeout里面指定了0ms,希望能立即执行,但是实际上没有...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS6,CentOS7官方镜像安装Oracle11G
- Red5直播服务器,属于Java语言的直播服务器
- Hadoop3单机部署,实现最简伪集群
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- SpringBoot2整合Redis,开启缓存,提高访问速度
- CentOS6,7,8上安装Nginx,支持https2.0的开启