ArrayList

掌握扩容机制,首次扩容为 10,再次扩容为原 1.5 倍

ArrayList 的构造函数,在 jdk1.8 中,ArrayList 有三种方式来初始化

  • 无参构造,创建空数组
  • 带初始容量的有参构造
  • collection 集合的有参构造
/**
  * 默认初始容量大小
  */
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
  *默认构造函数,使用初始容量10构造一个空列表(无参数构造)
  */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
  *带初始容量参数的构造函数。
  */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {//初始容量大于0
        //创建initialCapacity大小的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {//初始容量等于0
        //创建空数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else {//初始容量小于0,抛出异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
/**
  *构造包含指定collection元素的列表,这些元素利用该集合的迭代器按顺序返回
  *如果指定的集合为null,throws NullPointerException。
  *Arrays.copyOf()后面说
  */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

以无参数构造创建 ArrayList 时,实际上初始化赋值的是一个空数组。当真正添加元素(add)操作时,才真正分配容量。即向数组中添加第一个元素时,数组容量扩为 10。

jdk1.7 无参构造创建 ArrayList 对象时,直接创建了长度是10的 Object[] 数组 elementData 。jdk7中的 ArrayList 的对象的创建类似于单例的饿汉式,而 jdk8 中的 ArrayList 的对象的创建类似于单例的懒汉式

/**
  * 将指定的元素追加到此列表的末尾。
  */
public boolean add(E e) {
    //添加元素之前,先调用ensureCapacityInternal
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //这里看到ArrayList添加元素的实质就相当于为数组赋值
    elementData[size++] = e;
    return true;
}
//jdk7 得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 获取默认的容量和传入参数的较大值
        // 当要add第1个元素时,minCapacity为1,在Math.max()方法比较后,minCapacity为10。
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    // 10-0>0 扩容
    if (minCapacity - elementData.length > 0)
        //调用grow方法进行扩容,调用此方法代表已经开始扩容了
        grow(minCapacity);
}

JDK11 移除了 ensureCapacityInternal()ensureExplicitCapacity() 方法

grow() 扩容

/**
  * Integer.MAX_VALUE - 8 可以避免一些内存溢出
  */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
  * ArrayList扩容的核心方法。
  */
private void grow(int minCapacity) {
    // oldCapacity 为旧容量,newCapacity 为新容量
    int oldCapacity = elementData.length;
    //将oldCapacity 右移一位,其效果相当于oldCapacity /2,
    //我们知道位运算的速度远远快于整除运算,整句运算式的结果就是将新容量更新为旧容量的1.5倍,
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么就把最小需要容量当作数组的新容量,
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量大于 MAX_ARRAY_SIZE,执行 hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE
    // 如果 minCapacity 大于 MAX_ARRAY_SIZE,则新容量则为 Integer.MAX_VALUE,否则:新容量大小则为 MAX_ARRAY_SIZE,即 Integer.MAX_VALUE - 8
    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);
}
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //对minCapacity和MAX_ARRAY_SIZE进行比较
    //若minCapacity大,将Integer.MAX_VALUE作为新数组的大小
    //若MAX_ARRAY_SIZE大,将MAX_ARRAY_SIZE作为新数组的大小
    //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

扩容 1.5 倍后的容量不够用时,就直接使用需要的最小容量。如果新容量(扩容1.5倍)后的结果超过 MAX_ARRAY_SIZE,那就不去扩容1.5倍了,而是去拿目前需要的容量来跟 MAX_ARRAY_SIZE 比较,没超过就用 MAX_ARRAY_SIZE,超过就用 Integer.MAX_VALUE因此 ArrayList 最大容量其实是 Integer.MAX_VALUE

Arrays.copyOf() 方法

public static int[] copyOf(int[] original, int newLength) {
    // 申请一个新的数组
    int[] copy = new int[newLength];
    // 调用System.arraycopy,将源数组中的数据进行拷贝,并返回新的数组
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

System.arraycopy() 方法

// arraycopy 是一个 native 方法
/**
  * 复制数组
  * @param src 源数组
  * @param srcPos 源数组中的起始位置
  * @param dest 目标数组
  * @param destPos 目标数组中的起始位置
  * @param length 要复制的数组元素的数量
  */
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

题外话:ArrayList 源码中有一个 ensureCapacity() 方法,能让你提前扩容容量,在增加大量数据前调用它,可以减少一定的时间消耗。

/**
  *
  * @param minCapacity 所需的最小容量
  */
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;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

LinkedList

掌握 LinkedList 和 ArrayList 比较

LinkedList

  1. 基于双向链表,无需连续内存
  2. 随机访问慢(要沿着链表遍历)
  3. 头尾插入删除性能高
  4. 占用内存多

ArrayList

  1. 基于数组,需要连续内存
  2. 随机访问快(指根据下标访问)
  3. 尾部插入、删除性能可以,其它部分插入、删除都会移动数据,因此性能会低
  4. 可以利用 cpu 缓存,局部性原理

补充:

同样在中间位置插入元素,LinkedList 的速度简直不敢恭维,因为它去查询到该位置就已经消耗了很多时间。

下面的言论是不准确的,必须纠正的是,查询的意思是查询某个元素,而不是随机访问,对于随机访问确实是 ArrayList 快,但对于查询来说事实上他们两者都不太适合用来查询,选择一种更高效的数据结构例如 HashMap、TreeMap 更好。



腾讯云社区邀请各位技术博主加入,福利多多噢!
Last modification:November 4th, 2021 at 11:21 pm
如果觉得我的文章对你有用,请随意赞赏