Skip to content

Latest commit

 

History

History
622 lines (453 loc) · 24.8 KB

arraylist.md

File metadata and controls

622 lines (453 loc) · 24.8 KB
title shortTitle category tag description head
京东实习一面:聊聊Java ArrayList,扩容机制了解吗?
ArrayList详解(附源码)
Java核心
集合框架(容器)
本文详细解析了 Java ArrayList 的实现原理、功能特点以及源码,为您提供了 ArrayList 的实际应用示例和性能优化建议。阅读本文,将帮助您更深入地理解 ArrayList,从而在实际编程中充分发挥其优势。
meta
name content
keywords
Java,ArrayList,ArrayList源码,源码分析, java arraylist

6.3 ArrayList详解(附源码)

“二哥,听说今天我们开讲 ArrayList 了?好期待哦!”三妹明知故问,这个托配合得依然天衣无缝。

“是的呀,三妹。”我肯定地点了点头,继续说道,“ArrayList 可以称得上是集合框架方面最常用的类了,可以和 HashMap 一较高下。”

从名字就可以看得出来,ArrayList 实现了 List 接口,并且是基于数组实现的。

数组的大小是固定的,一旦创建的时候指定了大小,就不能再调整了。也就是说,如果数组满了,就不能再添加任何元素了。ArrayList 在数组的基础上实现了自动扩容,并且提供了比数组更丰富的预定义方法(各种增删改查),非常灵活。

Java 这门编程语言和别的编程语言,比如说 C语言的不同之处就在这里,如果是 C语言的话,你就必须得动手实现自己的 ArrayList,原生的库函数里面是没有的。

01、创建 ArrayList

“二哥,如何创建一个 ArrayList 啊?”三妹问。

ArrayList<String> alist = new ArrayList<String>();

可以通过上面的语句来创建一个字符串类型的 ArrayList(通过尖括号来限定 ArrayList 中元素的类型,如果尝试添加其他类型的元素,将会产生编译错误),更简化的写法如下:

List<String> alist = new ArrayList<>();

由于 ArrayList 实现了 List 接口,所以 alist 变量的类型可以是 List 类型;new 关键字声明后的尖括号中可以不再指定元素的类型,因为编译器可以通过前面尖括号中的类型进行智能推断。

此时会调用无参构造方法(见下面的代码)创建一个空的数组,常量DEFAULTCAPACITY_EMPTY_ELEMENTDATA的值为 {}

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

如果非常确定 ArrayList 中元素的个数,在创建的时候还可以指定初始大小。

List<String> alist = new ArrayList<>(20);

这样做的好处是,可以有效地避免在添加新的元素时进行不必要的扩容。

02、向 ArrayList 中添加元素

“二哥,那怎么向 ArrayList 中添加一个元素呢?”三妹继续问。

可以通过 add() 方法向 ArrayList 中添加一个元素。

alist.add("沉默王二");

我们来跟一下源码,看看 add 方法到底执行了哪些操作。跟的过程中,我们也可以偷师到 Java 源码的作者(大师级程序员)是如何优雅地写代码的。

我先给个结论,全当抛砖引玉。

堆栈过程图示:
add(element)
└── if (size == elementData.length) // 判断是否需要扩容
    ├── grow(minCapacity) // 扩容
    │   └── newCapacity = oldCapacity + (oldCapacity >> 1) // 计算新的数组容量
    │   └── Arrays.copyOf(elementData, newCapacity) // 创建新的数组
    ├── elementData[size++] = element; // 添加新元素
    └── return true; // 添加成功

来具体看一下,先是 add() 方法的源码(已添加好详细地注释)

/**
 * 将指定元素添加到 ArrayList 的末尾
 * @param e 要添加的元素
 * @return 添加成功返回 true
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 确保 ArrayList 能够容纳新的元素
    elementData[size++] = e; // 在 ArrayList 的末尾添加指定元素
    return true;
}

参数 e 为要添加的元素,此时的值为“沉默王二”,size 为 ArrayList 的长度,此时为 0。

继续跟下去,来看看 ensureCapacityInternal()方法:

/**
 * 确保 ArrayList 能够容纳指定容量的元素
 * @param minCapacity 指定容量的最小值
 */
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 如果 elementData 还是默认的空数组
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 使用 DEFAULT_CAPACITY 和指定容量的最小值中的较大值
    }

    ensureExplicitCapacity(minCapacity); // 确保容量能够容纳指定容量的元素
}

此时:

  • 参数 minCapacity 为 1(size+1 传过来的)
  • elementData 为存放 ArrayList 元素的底层数组,前面声明 ArrayList 的时候讲过了,此时为空 {}
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA 前面也讲过了,为 {}

所以,if 条件此时为 true,if 语句minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity)要执行。

DEFAULT_CAPACITY 为 10(见下面的代码),所以执行完这行代码后,minCapacity 为 10,Math.max() 方法的作用是取两个当中最大的那个。

private static final int DEFAULT_CAPACITY = 10;

接下来执行 ensureExplicitCapacity() 方法,来看一下源码:

/**
 * 检查并确保集合容量足够,如果需要则增加集合容量。
 *
 * @param minCapacity 所需最小容量
 */
private void ensureExplicitCapacity(int minCapacity) {
    // 检查是否超出了数组范围,确保不会溢出
    if (minCapacity - elementData.length > 0)
        // 如果需要增加容量,则调用 grow 方法
        grow(minCapacity);
}

此时:

  • 参数 minCapacity 为 10
  • elementData.length 为 0(数组为空)

所以 10-0>0,if 条件为 true,进入 if 语句执行 grow() 方法,来看源码:

/**
 * 扩容 ArrayList 的方法,确保能够容纳指定容量的元素
 * @param minCapacity 指定容量的最小值
 */
private void grow(int minCapacity) {
    // 检查是否会导致溢出,oldCapacity 为当前数组长度
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容至原来的1.5倍
    if (newCapacity - minCapacity < 0) // 如果还是小于指定容量的最小值
        newCapacity = minCapacity; // 直接扩容至指定容量的最小值
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 如果超出了数组的最大长度
        newCapacity = hugeCapacity(minCapacity); // 扩容至数组的最大长度
    // 将当前数组复制到一个新数组中,长度为 newCapacity
    elementData = Arrays.copyOf(elementData, newCapacity);
}

此时:

  • 参数 minCapacity 为 10
  • 变量 oldCapacity 为 0

所以 newCapacity 也为 0,于是 newCapacity - minCapacity 等于 -10 小于 0,于是第一个 if 条件为 true,执行第一个 if 语句 newCapacity = minCapacity,然后 newCapacity 为 10。

紧接着执行 elementData = Arrays.copyOf(elementData, newCapacity);,也就是进行数组的第一次扩容,长度为 10。

回到 add() 方法:

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

执行 elementData[size++] = e

此时:

  • size 为 0
  • e 为 “沉默王二”

所以数组的第一个元素(下标为 0) 被赋值为“沉默王二”,接着返回 true,第一次 add 方法执行完毕。

PS:add 过程中会遇到一个令新手感到困惑的右移操作符 >>,借这个机会来解释一下。

ArrayList 在第一次执行 add 后会扩容为 10,那 ArrayList 第二次扩容发生在什么时候呢?

答案是添加第 11 个元素时,大家可以尝试分析一下这个过程。

03、右移操作符

“oldCapacity 等于 10,oldCapacity >> 1 这个表达式等于多少呢?三妹你知道吗?”我问三妹。

“不知道啊,>> 是什么意思呢?”三妹很疑惑。

>> 是右移运算符,oldCapacity >> 1 相当于 oldCapacity 除以 2。”我给三妹解释道,“在计算机内部,都是按照二进制存储的,10 的二进制就是 1010,也就是 0*2^0 + 1*2^1 + 0*2^2 + 1*2^3=0+2+0+8=10 。。。。。。”

还没等我解释完,三妹就打断了我,“二哥,能再详细解释一下到底为什么吗?”

“当然可以啊。”我拍着胸脯对三妹说。

先从位权的含义说起吧。

平常我们使用的是十进制数,比如说 39,并不是简单的 3 和 9,3 表示的是 3*10 = 30,9 表示的是 9*1 = 9,和 3 相乘的 10,和 9 相乘的 1,就是位权。位数不同,位权就不同,第 1 位是 10 的 0 次方(也就是 10^0=1),第 2 位是 10 的 1 次方(10^1=10),第 3 位是 10 的 2 次方(10^2=100),最右边的是第一位,依次类推。

位权这个概念同样适用于二进制,第 1 位是 2 的 0 次方(也就是 2^0=1),第 2 位是 2 的 1 次方(2^1=2),第 3 位是 2 的 2 次方(2^2=4),第 4 位是 2 的 3 次方(2^3=8)。

十进制的情况下,10 是基数,二进制的情况下,2 是基数。

10 在十进制的表示法是 0*10^0+1*10^1=0+10=10。

10 的二进制数是 1010,也就是 0*2^0 + 1*2^1 + 0*2^2 + 1*2^3=0+2+0+8=10。

然后是移位运算,移位分为左移和右移,在 Java 中,左移的运算符是 <<,右移的运算符 >>

oldCapacity >> 1 来说吧,>> 左边的是被移位的值,此时是 10,也就是二进制 1010>> 右边的是要移位的位数,此时是 1。

1010 向右移一位就是 101,空出来的最高位此时要补 0,也就是 0101。

“那为什么不补 1 呢?”三妹这个问题很尖锐。

“因为是算术右移,并且是正数,所以最高位补 0;如果表示的是负数,就需要补 1。”我慢吞吞地回答道,“0101 的十进制就刚好是 1*2^0 + 0*2^1 + 1*2^2 + 0*2^3=1+0+4+0=5,如果多移几个数来找规律的话,就会发现,右移 1 位是原来的 1/2,右移 2 位是原来的 1/4,诸如此类。”

也就是说,ArrayList 的大小会扩容为原来的大小+原来大小/2,也就是 1.5 倍。

这下明白了吧?

你可以通过在 ArrayList 中添加第 11 个元素来 debug 验证一下。

04、向 ArrayList 的指定位置添加元素

除了 add(E e) 方法,还可以通过 add(int index, E element) 方法把元素添加到 ArrayList 的指定位置:

alist.add(0, "沉默王三");

add(int index, E element) 方法的源码如下:

/**
 * 在指定位置插入一个元素。
 *
 * @param index   要插入元素的位置
 * @param element 要插入的元素
 * @throws IndexOutOfBoundsException 如果索引超出范围,则抛出此异常
 */
public void add(int index, E element) {
    rangeCheckForAdd(index); // 检查索引是否越界

    ensureCapacityInternal(size + 1);  // 确保容量足够,如果需要扩容就扩容
    System.arraycopy(elementData, index, elementData, index + 1,
            size - index); // 将 index 及其后面的元素向后移动一位
    elementData[index] = element; // 将元素插入到指定位置
    size++; // 元素个数加一
}

add(int index, E element)方法会调用到一个非常重要的本地方法 System.arraycopy(),它会对数组进行复制(要插入位置上的元素往后复制)。

来细品一下。

这是 arraycopy() 的语法:

System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

ArrayList.add(int index, E element) 方法中,具体用法如下:

System.arraycopy(elementData, index, elementData, index + 1, size - index);
  • elementData:表示要复制的源数组,即 ArrayList 中的元素数组。
  • index:表示源数组中要复制的起始位置,即需要将 index 及其后面的元素向后移动一位。
  • elementData:表示要复制到的目标数组,即 ArrayList 中的元素数组。
  • index + 1:表示目标数组中复制的起始位置,即将 index 及其后面的元素向后移动一位后,应该插入到的位置。
  • size - index:表示要复制的元素个数,即需要将 index 及其后面的元素向后移动一位,需要移动的元素个数为 size - index。

“三妹,注意看,我画幅图来表示下。”我认真地做起了图。

05、更新 ArrayList 中的元素

“二哥,那怎么更新 ArrayList 中的元素呢?”三妹继续问。

可以使用 set() 方法来更改 ArrayList 中的元素,需要提供下标和新元素。

alist.set(0, "沉默王四");

假设原来 0 位置上的元素为“沉默王三”,现在可以将其更新为“沉默王四”。

来看一下 set() 方法的源码:

/**
 * 用指定元素替换指定位置的元素。
 *
 * @param index   要替换的元素的索引
 * @param element 要存储在指定位置的元素
 * @return 先前在指定位置的元素
 * @throws IndexOutOfBoundsException 如果索引超出范围,则抛出此异常
 */
public E set(int index, E element) {
    rangeCheck(index); // 检查索引是否越界

    E oldValue = elementData(index); // 获取原来在指定位置上的元素
    elementData[index] = element; // 将新元素替换到指定位置上
    return oldValue; // 返回原来在指定位置上的元素
}

该方法会先对指定的下标进行检查,看是否越界,然后替换新值并返回旧值。

06、删除 ArrayList 中的元素

“二哥,那怎么删除 ArrayList 中的元素呢?”三妹继续问。

remove(int index) 方法用于删除指定下标位置上的元素,remove(Object o) 方法用于删除指定值的元素。

alist.remove(1);
alist.remove("沉默王四");

先来看 remove(int index) 方法的源码:

/**
 * 删除指定位置的元素。
 *
 * @param index 要删除的元素的索引
 * @return 先前在指定位置的元素
 * @throws IndexOutOfBoundsException 如果索引超出范围,则抛出此异常
 */
public E remove(int index) {
    rangeCheck(index); // 检查索引是否越界

    E oldValue = elementData(index); // 获取要删除的元素

    int numMoved = size - index - 1; // 计算需要移动的元素个数
    if (numMoved > 0) // 如果需要移动元素,就用 System.arraycopy 方法实现
        System.arraycopy(elementData, index+1, elementData, index,
                numMoved);
    elementData[--size] = null; // 将数组末尾的元素置为 null,让 GC 回收该元素占用的空间

    return oldValue; // 返回被删除的元素
}

需要注意的是,在 ArrayList 中,删除元素时,需要将删除位置后面的元素向前移动一位,以填补删除位置留下的空缺。如果需要移动元素,则需要使用 System.arraycopy 方法将删除位置后面的元素向前移动一位。最后,将数组末尾的元素置为 null,以便让垃圾回收机制回收该元素占用的空间。

再来看 remove(Object o) 方法的源码:

/**
 * 删除列表中第一次出现的指定元素(如果存在)。
 *
 * @param o 要删除的元素
 * @return 如果列表包含指定元素,则返回 true;否则返回 false
 */
public boolean remove(Object o) {
    if (o == null) { // 如果要删除的元素是 null
        for (int index = 0; index < size; index++) // 遍历列表
            if (elementData[index] == null) { // 如果找到了 null 元素
                fastRemove(index); // 调用 fastRemove 方法快速删除元素
                return true; // 返回 true,表示成功删除元素
            }
    } else { // 如果要删除的元素不是 null
        for (int index = 0; index < size; index++) // 遍历列表
            if (o.equals(elementData[index])) { // 如果找到了要删除的元素
                fastRemove(index); // 调用 fastRemove 方法快速删除元素
                return true; // 返回 true,表示成功删除元素
            }
    }
    return false; // 如果找不到要删除的元素,则返回 false
}

该方法通过遍历的方式找到要删除的元素,null 的时候使用 == 操作符判断,非 null 的时候使用 equals() 方法,然后调用 fastRemove() 方法。

注意:

继续往后面跟,来看一下 fastRemove() 方法:

/**
 * 快速删除指定位置的元素。
 *
 * @param index 要删除的元素的索引
 */
private void fastRemove(int index) {
    int numMoved = size - index - 1; // 计算需要移动的元素个数
    if (numMoved > 0) // 如果需要移动元素,就用 System.arraycopy 方法实现
        System.arraycopy(elementData, index+1, elementData, index,
                numMoved);
    elementData[--size] = null; // 将数组末尾的元素置为 null,让 GC 回收该元素占用的空间
}

同样是调用 System.arraycopy() 方法对数组进行复制和移动。

“三妹,注意看,我画幅图来表示下。”我认真地做起了图。

07、查找 ArrayList 中的元素

“二哥,那怎么查找 ArrayList 中的元素呢?”三妹继续问。

如果要正序查找一个元素,可以使用 indexOf() 方法;如果要倒序查找一个元素,可以使用 lastIndexOf() 方法。

alist.indexOf("沉默王二");
alist.lastIndexOf("沉默王二");

来看一下 indexOf() 方法的源码:

/**
 * 返回指定元素在列表中第一次出现的位置。
 * 如果列表不包含该元素,则返回 -1。
 *
 * @param o 要查找的元素
 * @return 指定元素在列表中第一次出现的位置;如果列表不包含该元素,则返回 -1
 */
public int indexOf(Object o) {
    if (o == null) { // 如果要查找的元素是 null
        for (int i = 0; i < size; i++) // 遍历列表
            if (elementData[i]==null) // 如果找到了 null 元素
                return i; // 返回元素的索引
    } else { // 如果要查找的元素不是 null
        for (int i = 0; i < size; i++) // 遍历列表
            if (o.equals(elementData[i])) // 如果找到了要查找的元素
                return i; // 返回元素的索引
    }
    return -1; // 如果找不到要查找的元素,则返回 -1
}

如果元素为 null 的时候使用“==”操作符,否则使用 equals() 方法。

lastIndexOf() 方法和 indexOf() 方法类似,不过遍历的时候从最后开始。

/**
 * 返回指定元素在列表中最后一次出现的位置。
 * 如果列表不包含该元素,则返回 -1。
 *
 * @param o 要查找的元素
 * @return 指定元素在列表中最后一次出现的位置;如果列表不包含该元素,则返回 -1
 */
public int lastIndexOf(Object o) {
    if (o == null) { // 如果要查找的元素是 null
        for (int i = size-1; i >= 0; i--) // 从后往前遍历列表
            if (elementData[i]==null) // 如果找到了 null 元素
                return i; // 返回元素的索引
    } else { // 如果要查找的元素不是 null
        for (int i = size-1; i >= 0; i--) // 从后往前遍历列表
            if (o.equals(elementData[i])) // 如果找到了要查找的元素
                return i; // 返回元素的索引
    }
    return -1; // 如果找不到要查找的元素,则返回 -1
}

contains() 方法可以判断 ArrayList 中是否包含某个元素,其内部就是通过 indexOf() 方法实现的:

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

08、二分查找法

如果 ArrayList 中的元素是经过排序的,就可以使用二分查找法,效率更快。

Collections 类的 sort() 方法可以对 ArrayList 进行排序,该方法会按照字母顺序对 String 类型的列表进行排序。如果是自定义类型的列表,还可以指定 Comparator 进行排序。

这里先简单地了解一下,后面会详细地讲。

List<String> copy = new ArrayList<>(alist);
copy.add("a");
copy.add("c");
copy.add("b");
copy.add("d");

Collections.sort(copy);
System.out.println(copy);

输出结果如下所示:

[a, b, c, d]

排序后就可以使用二分查找法了:

int index = Collections.binarySearch(copy, "b");

09、ArrayList增删改查时的时间复杂度

“最后,三妹,我们来简单总结一下 ArrayList 的时间复杂度吧,方便后面学习 LinkedList 时对比。”我喝了一口水后补充道。

1)查询

时间复杂度为 O(1),因为 ArrayList 内部使用数组来存储元素,所以可以直接根据索引来访问元素。

/**
 * 返回列表中指定位置的元素。
 *
 * @param index 要返回的元素的索引
 * @return 列表中指定位置的元素
 * @throws IndexOutOfBoundsException 如果索引超出范围(index < 0 || index >= size())
 */
public E get(int index) {
    rangeCheck(index); // 检查索引是否合法
    return elementData(index); // 调用 elementData 方法获取元素
}

/**
 * 返回列表中指定位置的元素。
 * 此方法不进行边界检查,因此只应由内部方法和迭代器调用。
 *
 * @param index 要返回的元素的索引
 * @return 列表中指定位置的元素
 */
E elementData(int index) {
    return (E) elementData[index]; // 返回指定索引位置上的元素
}

2)插入

添加一个元素(调用 add() 方法时)的时间复杂度最好情况为 O(1),最坏情况为 O(n)。

  • 如果在列表末尾添加元素,时间复杂度为 O(1)。
  • 如果要在列表的中间或开头插入元素,则需要将插入位置之后的元素全部向后移动一位,时间复杂度为 O(n)。

3)删除

删除一个元素(调用 remove(Object) 方法时)的时间复杂度最好情况 O(1),最坏情况 O(n)。

  • 如果要删除列表末尾的元素,时间复杂度为 O(1)。
  • 如果要删除列表中间或开头的元素,则需要将删除位置之后的元素全部向前移动一位,时间复杂度为 O(n)。

4)修改

修改一个元素(调用 set()方法时)与查询操作类似,可以直接根据索引来访问元素,时间复杂度为 O(1)。

/**
 * 用指定元素替换列表中指定位置的元素。
 *
 * @param index 要替换元素的索引
 * @param element 要放入列表中的元素
 * @return 原来在指定位置上的元素
 * @throws IndexOutOfBoundsException 如果索引超出范围(index < 0 || index >= size())
 */
public E set(int index, E element) {
    rangeCheck(index); // 检查索引是否合法

    E oldValue = elementData(index); // 获取原来在指定位置上的元素
    elementData[index] = element; // 将指定位置上的元素替换为新元素
    return oldValue; // 返回原来在指定位置上的元素
}

10、总结

ArrayList,如果有个中文名的话,应该叫动态数组,也就是可增长的数组,可调整大小的数组。动态数组克服了静态数组的限制,静态数组的容量是固定的,只能在首次创建的时候指定。而动态数组会随着元素的增加自动调整大小,更符合实际的开发需求。

学习集合框架,ArrayList 是第一课,也是新手进阶的重要一课。要想完全掌握 ArrayList,扩容这个机制是必须得掌握,也是面试中经常考察的一个点。

要想掌握扩容机制,就必须得读源码,也就肯定会遇到 oldCapacity >> 1,有些初学者会选择跳过,虽然不影响整体上的学习,但也错过了一个精进的机会。

计算机内部是如何表示十进制数的,右移时又发生了什么,静下心来去研究一下,你就会发现,哦,原来这么有趣呢?

“好了,三妹,这一节我们就学到这里,收工!”


GitHub 上标星 10000+ 的开源知识库《二哥的 Java 进阶之路》第一版 PDF 终于来了!包括Java基础语法、数组&字符串、OOP、集合框架、Java IO、异常处理、Java 新特性、网络编程、NIO、并发编程、JVM等等,共计 32 万余字,500+张手绘图,可以说是通俗易懂、风趣幽默……详情戳:太赞了,GitHub 上标星 10000+ 的 Java 教程

微信搜 沉默王二 或扫描下方二维码关注二哥的原创公众号沉默王二,回复 222 即可免费领取。