Java集合框架源码剖析:ArrayList

总体介绍

ArrayList实现了List接口,是顺序容器,即元素存放的数据与放进去的顺序相同,允许放入null元素,底层通过数组实现。除该类未实现同步外,其余跟Vector大致相同。每个ArrayList都有一个容量(capacity),表示底层数组的实际大小,容器内存储元素的个数不能多于当前容量。当向容器中添加元素时,如果容量不足,容器会自动增大底层数组的大小。前面已经提过,Java泛型只是编译器提供的语法糖,所以这里的数组是一个Object数组,以便能够容纳任何类型的对象。

ArrayList_base

size(), isEmpty(), get(), set()方法均能在常数时间内完成,add()方法的时间开销跟插入位置有关,addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。

为追求效率,ArrayList没有实现同步(synchronized),如果需要多个线程并发访问,用户可以手动同步,也可使用Vector替代。

方法剖析

set()

既然底层是一个数组ArrayListset()方法也就变得非常简单,直接对数组的指定位置赋值即可。

get()

get()方法同样很简单,唯一要注意的是由于底层数组是Object[],得到元素后需要进行类型转换。

add()

跟C++ 的vector不同,ArrayList没有bush_back()方法,对应的方法是add(E e)ArrayList也没有insert()方法,对应的方法是add(int index, E e)。这两个方法都是向容器中添加新元素,这可能会导致capacity不足,因此在添加元素之前,都需要进行剩余空间检查,如果需要则自动扩容。扩容操作最终是通过grow()方法完成的。

由于Java GC自动管理了内存,这里也就不需要考虑源数组释放的问题。

ArrayList_grow

空间的问题解决后,插入过程就显得非常简单。

ArrayList_add

add(int index, E e)需要先对元素进行移动,然后完成插入操作,也就意味着该方法有着线性的时间复杂度。

addAll()

addAll()方法能够一次添加多个元素,根据位置不同也有两个把本,一个是在末尾添加的addAll(Collection extends E> c)方法,一个是从指定位置开始插入的addAll(int index, Collection extends E> c)方法。跟add()方法类似,在插入之前也需要进行空间检查,如果需要则自动扩容;如果从指定位置插入,也会存在移动元素的情况。
addAll()的时间复杂度不仅跟插入元素的多少有关,也跟插入的位置相关。

remove()

remove()方法也有两个版本,一个是remove(int index)删除指定位置的元素,另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()操作的逆过程,需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用,必须显式的为最后一个位置赋null值。

关于Java GC这里需要特别说明一下,有了垃圾收集器并不意味着一定不会有内存泄漏。对象能否被GC的依据是是否还有引用指向它,上面代码中如果不手动赋null值,除非对应的位置被其他元素覆盖,否则原来的对象就一直不会被回收。

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

2 4 收藏 4 评论

关于作者:CarpenterLee

中国科学院计算技术研究所在读硕士,从事高性能计算、大数据等领域。 个人主页 · 我的文章 · 7 ·    

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部