ArrayList的add(E e)方法与扩容

2018/12/24 14:44
阅读数 135

ArrayList是Java开发中经常用到的集合类,它是List接口的实现类,具有很高的查询性能,但不是线程安全的。本文主要讲述了ArrayList的add(E e)方法及该方法中涉及到的容量扩容技术。

  • 本文大纲

1.ArrayList底层数据结构

2.add(E e)方法流程概览

3.add(E e)方法与扩容源码分析

说明:本文对ArrayList的源码分析是基于JDK8。

  • 正文

1.ArrayList底层数据结构

ArrayList的底层数据结构为一个Object数组,对应到源码中是:

transient Object[] elementData; // non-private to simplify nested class access

2.add(E e)方法流程概览

add(E e)方法的大致流程:

                       

3.add(E e)方法与扩容源码分析

接着再看一下源码:

public boolean add(E e) {
  // 确保数组有足够的空间来存储对象e
  ensureCapacityInternal(size + 1); // Increments modCount!!
  // 将对象e存放到数组的末尾
  elementData[size++] = e;
  return true;
}
ensureCapacityInternal方法主要是确保elementData数组有足够的空间来存储待添加的元素:
// 参数minCapacity是add(E e)方法中调用ensureCapacityInternal方法时传入的size + 1的值
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

参数minCapacity是为了存放这个元素elementData数组所需要的最小的大小。比如,现在一个数组中存放了10个元素,再次向该数组存放一个元素时,那么这个minCapacity的值就是size + 1,即10 + 1 = 11。

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

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
     // 存放新元素所需的最小容量大于elementData数组的长度
        grow(minCapacity);
}

如果存放新元素所需的最小容量大于elementData数组的长度,即当前数组的容量不足,不能再存放新的元素,那么将基于elementData数组进行扩容。

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 计算新数组的容量,新数组的容量为原数组容量的1.5倍数。>>是移位运算符,oldCapacity >> 1表示oldCapacity除以2
    if (newCapacity - minCapacity < 0) // 针对当创建的ArrayList的容量大小为1时能够进行扩容(下面将详细分析)
        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); // 进行数组拷贝,并将新产生的数组赋值给elementData
}

 

 当我们在new ArrayList的时候,如果指定ArrayList的容量大小为1(比如,new ArrayList<>(1)),再进行add(E e)操作,在执行代码int newCapacity = oldCapacity + (oldCapacity >> 1)时,newCapacity的值为1,newCapacity与oldCapacity的值都为1,这样其实并没有进行扩容。if (newCapacity - minCapacity < 0)就是为避免这种情况,当newCapacity(此例中为1)的值小于minCapacity(此例中为2)时,就把minCapacity的值赋给newCapacity。

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部