ArrayList深度解析

全栈开发日记

发布于 2022-05-13 14:26:31

2160

发布于 2022-05-13 14:26:31

文章被收录于专栏：全栈开发日记

目录：

ArrayList集合底层数组创建和扩容机制 ArrayList的构造方法优化ArrayList

以下测试源码均使用JDK1.8

1 ArrayList集合底层数组创建和扩容机制

① 通过源码中查看到elementData属性是ArrayList的底层数组。

② 所以只要我们获取到当前ArrayList类中该字段的值就可以知道该集合当前底层数组的长度。

这里我使用了反射的机制，来强行获取elementData属性的值。

public static void main(String[] args) {
    ArrayList arrayList=new ArrayList();

        //获取类对象
    Class clazz=arrayList.getClass();

    try {
      //获取类中elementData字段
      Field field=clazz.getDeclaredField("elementData");
            
      //进行爆破，获取权限
      field.setAccessible(true);
            
      //将对象传入，获取该字段当前的值
      Object[] obj=(Object[])field.get(arrayList);
            
      //打印底层数组的长度
      System.out.println(obj.length);
            
    } catch (Exception e) {
      e.printStackTrace();
    }
}

③ 测试后的结果：

1、当只是对集合进行初始化，而不添加任何元素的时候，集合的底层数组长度为0

2、当给集合添加 1 个元素，集合底层数组长度扩容10

3、当给集合添加 10 个元素，集合底层数组长度还是10

4、当给集合添加 11 个元素后，集合扩容为15，呈1.5倍增长

5、当给集合添加 16 个元素后，集合扩容为22，还是原数组的长度的1.5倍

2 ArrayList构造方法

① 空参

空参构造方法初始化了一个空的数组。

② int类型参数

public ArrayList(int initialCapacity) {
    //如果参数大于 0 则创建参数大小的底层数组 等待扩容
    if (initialCapacity > 0) { 
      this.elementData = new Object[initialCapacity];

    //如果参数等于 0 则创建一个空的底层数组 等待扩容
    } else if (initialCapacity == 0) { 
      this.elementData = EMPTY_ELEMENTDATA;

    //否则抛出异常
    } else { 
      throw new IllegalArgumentException("Illegal Capacity: "+
        initialCapacity);
    }
}

③Collection类型参数

将传入的Collection构建为一个集合。

Collection是List、Set、Queue的父接口，是单列集合的老大。也就是说，传入的可以是List集合，也可以是Set、Queue集合的子类。它通过迭代器返回的顺序构建一个ArrayList集合。

3 优化ArrayList

了解了ArrayList的创建机制，就要想办法优化它。

如果我们要在集合中添加一百万个数据，它只能是通过每次扩容1.5倍，每次将原数组数据放入新的数组，很明显非常消耗资源。

解决方式：

① 构造方法

在构造ArrayList时传入一个整型，就会直接构造一个该长度的集合，避免一直扩容造成的资源浪费。

② 使用普通方法

还可以使用ensureCapacity(int minCapacity)方法。参数为扩容为目标大小。

如果要加入大量的数据，这种方式可以比传统方式快10倍以上，加入数据越多，越明显。

这是该方法的源码，我加入了一些自己的注释：

public void ensureCapacity(int minCapacity) {
    //判断当前集合中是否已经有数据
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
    // any size if not default element table
    ? 0
    // larger than default for default empty table. It's already
    // supposed to be at default size.
    : DEFAULT_CAPACITY;
    //这里判断扩容必须大于10，否则不进行扩容，具体扩容多少，再调用下一个方法继续判断
    if (minCapacity > minExpand ) {
      ensureExplicitCapacity(minCapacity);
    }
}

ensureExplicitCapacity方法：

private void ensureExplicitCapacity(int minCapacity) {
    //对集合的操作次数+1，该属性在父类中
    modCount++;

    // 再次判断，扩容大小-当前容量 >0
    if (minCapacity - elementData.length > 0)
    //调用扩容方法
    grow(minCapacity);
}

grow方法：

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

使用该ensureCapacity(int minCapacity)方法需要注意：

if( 扩容大小 > 10){
    if( 集合中是否已经有元素 ){
        if( 扩容大小 > 当前容量*1.5 ){
          扩容为目标大小
        }else{
          扩容为当前容量的1.5倍
        }
      }else{
          扩容为目标大小
      }
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-11-29，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法