专栏首页Java进阶之路ArrayList 源码剖析

ArrayList 源码剖析

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

Arraylist

size(), isEmpty(), get(), set()方法均能在常数时间内完成,add()方法的时间开销跟插入位置有关,addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。 为追求效率,ArrayList没有实现同步(synchronized),如果需要多个线程并发访问,用户可以手动同步,也可使用Vector替代。

  • 方法剖析
  1. set() 既然底层是一个数组ArrayList的set()方法也就变得非常简单,直接对数组的指定位置赋值即可。
public E set(int index, E element) {
    rangeCheck(index);//下标越界检查
    E oldValue = elementData(index);
    elementData[index] = element;//赋值到指定位置
    return oldValue;
}
  1. get() get()方法同样很简单,唯一要注意的是由于底层数组是Object[],得到元素后需要进行类型转换。
public E get(int index) {
    rangeCheck(index);
    return (E) elementData[index];//注意类型转换
}
  1. add() 在添加元素之前,需要进行剩余空间检查,如果需要则自动扩容。扩容操作最终是通过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自动管理了内存,这里也就不需要考虑源数组释放的问题。

Arraylist容量

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

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 纪念第一次手写源码

    神秘的寇先森
  • Java分布式缓存框架Ehcache 使用(二)

    神秘的寇先森
  • JVM参数配置

    参考:https://docs.oracle.com/cd/E19900-01/819-4742/abeik/index.html

    神秘的寇先森
  • Java 集合框架 ArrayList 源码剖析

    总体介绍 ArrayList实现了List接口,是顺序容器,即元素存放的数据与放进去的顺序相同,允许放入null元素,底层通过数组实现。除该类未实现同步外,其余...

    用户1667431
  • 精解四大集合框架:List核心知识总结

    Java集合框架早也是个老话题了,今天主要是总结一下关于Java中的集合框架List的核心知识点。肯定有人会问,这篇写的是List那接下来就还有三篇?是的,ja...

    田维常
  • 堆排序&&动态中位数

    heapify():  这里是指最大heapify。 我们只需要从  k = N / 2开始,  在k >= 1的条件下对 k 进行shiftDown(), 然...

    大学里的混子
  • 【AlexeyAB DarkNet框架解析】七,YOLOV1损失函数代码详解(detection_layer.c)

    灵魂拷问,你真的懂YOLOV1的损失函数吗?进一步,懂了损失函数,你清楚它的反向求导过程吗?为了解决这俩问题,本文就结合DarkNet中的YOLOV1的损失函数...

    BBuf
  • ArrayList源码分析

    Krains
  • 原 GIT忽略本地已存在文件的修改

    霡霂
  • 在phpstudy集成环境下的nginx服务器下配置url重写

    直接在对应的vhosts.conf配置文件的location / {}中添加以下内容:

    砸漏

扫码关注云+社区

领取腾讯云代金券