Java知网

  • 首页
  • Spring Boot
  • 面试精选
  • 程序人生
  • 资源
  • 友链
  • 关于我
  1. 首页
  2. Java
  3. 正文

从面试角度分析ArrayList源码

2021年3月17日 228点热度 0人点赞 0条评论

注:本系列文章中用到的jdk版本均为java8

ArrayList类图如下:

image-20201212235750905

ArrayList的底层是由数组实现的,数组的特点是固定大小,而ArrayList实现了动态扩容。

ArrayList部分变量如下,在下面的分析中会用到这些变量。

/**
 * 默认容量
 */
private static final int DEFAULT_CAPACITY = 10;
/**
 * 空的对象数组
 */
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
 * 无参构造器创建的空数组
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
 * 存放数据的数组的缓存变量
 */
transient Object[] elementData;
/**
 * 元素数量
 */
private int size;

一、初始化ArrayList

初始化ArrayList一般会使用以下两个构造器

1.1 无参构造器

初始化ArrayList的时候如果不指定大小,则会创建一个空数组。

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

1.2 指定数组大小的构造器

创建一个预估大小的数组,指定大小后只是指定了数组初始值的大小,不影响后面扩容,指定的好处就是可以节省内存及时间上的开销。

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);
    }
}

二、添加元素、动态扩容

ArrayList.add(E e)源码:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

add()中elementData[size++] = e很好理解,就是将元素插入第size个位置,然后将size++,我们重点来看看ensureCapacityInternal(size + 1)方法;

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

ensureCapacityInternal()方法中判断缓存变量elementData是否为空,也就是判断是否是第一次添加元素,如果是第一次添加元素,则设置初始化大小为默认容量10,否则为传入的参数。这个方法的目的就是获取初始化数组容量。获取到初始化容量后调用ensureExplicitCapacity(minCapacity)方法;

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

ensureExplicitCapacity(minCapacity)方法用来判断是否需要扩容,假如第一次添加元素,minCapacity为10,elementData容量为0,那么就需要去扩容。调用grow(minCapacity)方法。

// 数组的最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 扩容大小为原来数组长度的1.5倍
    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);
}

grow(minCapacity)方法对数组进行扩容,扩容大小为原数组的1.5倍,如果计算出的扩容容量比需要的容量小,则扩容大小为需要的容量,如果扩容容量比数组最大容量大,则调用hugeCapacity(minCapacity)方法,将数组扩容为整数的最大长度,然后将elemetData数组指向新扩容的内存空间并将元素复制到新空间。

当需要的集合容量特别大时,扩容1.5倍就会非常消耗空间,因此建议初始化时预估一个容量大小。

三、删除元素

ArrayList提供两种删除元素的方法,可以通过索引和元素进行删除。两种删除大同小异,删除元素后,将后面的元素一次向前移动。

ArrayList.remove(int index)源码:

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;
}

删除元素时,首先会判断索引是否大于ArrayList的大小,如果索引范围正确,则将索引位置的下一个元素赋值到索引位置,将ArrayList的大小-1,最后返回移除的元素。操作图如下,假如我要移除索引为1的元素:

image-20201213134536542

四、总结

ArrayList底层是数组实现的,可以进行动态扩容,扩容大小为原来的1.5倍,虽然可以通过动态扩容,但是数组非常大时会特别浪费空间,因此建议初始化时预估数组大小。ArrayList允许插入重复值和空值。ArrayList实现了RandomAccess接口,支持快速随机访问,就是可以通过索引快速查到某个元素,因此遍历时使用for循环的方式效率更高。ArrayList是线程不安全的,可以通过Collections.synchronizedList将其转变为线程安全的集合,不过一般不会使用,Vector和CopyOnWriteArrayList是线程安全的,Vector性能一般,逐渐被CopyOnWriteArrayList取代了。

本文由 Java知网 创作
禁止未经授权转载,违者依法追究相关法律责任

相关文章:

  1. Vector与CopyOnWriteArrayList简单比较分析
  2. 从面试角度分析LinkedList源码
标签: ArrayList List
最后更新:2021年9月4日

javatip

这个人很懒,什么都没留下

点赞
< 上一篇
下一篇 >

文章评论

取消回复
搜一搜
扫一扫
    关注公众号
  • 技术干货推送
  • 免费资料领取
  • 定时福利发放
分类
  • Java / 110篇
  • Mysql / 17篇
  • Redis / 10篇
  • Spring Boot / 29篇
  • Spring Cloud / 16篇
  • 消息队列 / 14篇
  • 程序人生 / 21篇
  • 资源 / 4篇
  • 面试 / 23篇
归档
  • 2022年7月 / 1篇
  • 2022年4月 / 1篇
  • 2022年1月 / 1篇
  • 2021年12月 / 9篇
  • 2021年11月 / 2篇
  • 2021年9月 / 10篇
  • 2021年8月 / 4篇
  • 2021年7月 / 2篇
  • 2021年6月 / 10篇
  • 2021年5月 / 18篇
  • 2021年4月 / 75篇
  • 2021年3月 / 78篇

COPYRIGHT © 2021 javatip.cn. ALL RIGHTS RESERVED.

陇ICP备19004310号-2

甘公网安备 62010202003150号