ArrayList常见面试点

发表于

ArrayList是Java程序员最常用的数据结构这句话说的一点都不过分，平日开发中拿来接受参数，包装数据使用非常频繁，但我们，因为它使用太简单，以至于我们好像并不是很在意ArrayList的底层实现，今天我们就来看看ArrayList的源码，以常见的面试套路来剖析它的底层原理。

面试官：你平时用ArrayList会是在那些场景，为什么用它？

我：我们一般开发时一般在接受集合类型的数据时用到，比如前端的参数，Dao层的返回值，以及业务处理集合类型的数据时用它来承载数据。因为它的特点是有序而且查询速度快，所以用它的频率很高。

  • 那你知道为什么它的查询效率为什么这么快吗？

我：因为ArrayList底层采用的是动态数组实现，我们可以通过数组索引下标定位元素所在的位置

  • 恩，那你说说JDK1.8中ArrayList的数据结构，以及它的添加元素的过程吧

我：JDK1.8中ArrayList提供了三个构造函数，无参构造默认是指向空数组，带参构造可以设置指定容量的数组，初始化时就新建一个指定容量的数组。添加元素时先检查element数组容量，如果容量不足就会扩容，如果容量充足就在数组末尾添加元素，然后集合size++。

  • 如果我创建ArrayList时，给定容量是20，那初始化以后它的容量是20吗？

我：额，是的，如果构造时指定了初始容量那么初始化时它的数组长度就是20，只不过它的size为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
复制代码    // 带参构造，自定义容量
    public ArrayList(int initialCapacity) {
        // 如果指定容量大于0，那么就初始化数组，数组长度就是指定的容量大小
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            // 如果指定容量为0，那么数组默认引用空数组对象，否则抛出异常
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    // 无参构造,默认引用空数组
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

当然还有一个带参构造：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
复制代码    //构造传入集合
    public ArrayList(Collection<? extends E> c) {
        // 将集合迭代为数组输出
        elementData = c.toArray();
        // 如果容量为空则引用空数组对象
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            // 数组类型不匹配的情况发生在toArray()中，实际元素量大于预期量时，迭代产生新的数组
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
  • 那你讲讲ArrayList是怎么扩容的吧

首先它会计算出数组需要的最小容量，然后调用grow(int minCapacity)方法进行扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
复制代码    // 计算出最小需要的容量大小
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 如果当前数组还处于空数组阶段，那么判断size+1的值也就是minCapacity和默认初始容量10的大小，取最大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
	// 添加元素的时候会调用此方法进行最小容量的计算
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        // 集合的变动次数
        modCount++;

        //如果当前数组的长度不足以容纳最小容量的元素，那么就扩容
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

我们进入grow(int minCapacity)方法看看，原来此方法就是ArrayList扩容的核心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
复制代码    // 扩容机制，传入当前需要的最小容量大小
    private void grow(int minCapacity) {
        // overflow-conscious code
        // 扩容前，数组的长度
        int oldCapacity = elementData.length;
        // 新的数组长度 = 旧的数组长度 + 旧数组长度/2 = oldCapacity*1.5 (新数组长度为旧数组长度1.5倍) 赋值为int时向下取整
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果新数组长度小于最小容量大小，则新数组长度=最小容量大小
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果新数组长度大于int范围，则返回int最大值
        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);
    }
  • 不光是ArrayList，其它集合也一样，为什么在add或者remove方法中有一个modCount，它是拿来干什么的

我：modCount是ArrayList的抽象父类AbstractList中的一个变量，用来记录集合机构被修改的次数。源码文档中的解释是它用来在迭代遍历集合的时候判断集合的修改状态，如果在遍历过程中发现modCount发生了改变，就会抛出ConcurrentModificationExceptions

  • 恩，不错。那你再讲讲ArrayList的删除元素吧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
复制代码    // 删除指定位置的元素
    public E remove(int index) {
        // 检查index是否越界
        rangeCheck(index);

        // 集合的变更次数
        modCount++;
        // 获取并返回此位置的老数据
        E oldValue = elementData(index);

        // 元素要移动的距离，如果numMoved>0标识删除的是集合内部的元素，numMoved=0标识删除的是集合末尾元素，就不用移动
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 将index后续的元素复制到数组对象上
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 将数组末尾置为null
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

其实和add(int,E)方法原理类似，根据复制一个新数组，add是将新数组追加到index后面，然后指向原数组完成添加。remove是新数组追加到index之前，然后将数组末尾置为null。

  • 好，那你知道为什么集合类实现了Serializable接口，自己却还要重新定义序列化方法？

我：完了，回去等通知吧，当场领盒饭。

不单单是ArrayList是将容纳数据的element数组用transient关键字修饰，其它很多集合都一样。transient修饰的变量语义为序列化时忽略，那么集合类为什么要这样做呢？网上有很多说法，有说虚拟机版本和平台的问题，也有说容量浪费的问题。因为集合类都有扩容机制，而且每次扩容以后容量相比以前要大很多，而一般情况下容量是撑不满的，也意味着有大量的内存空间被浪费，而序列化手段是将程序对象转换为可转移的二进制文件或数据，让然体积越小越好。

补充：ArrayList的克隆是浅克隆，是复制了原来的数组

clear()方法并不是将element数组置为null，而是将数组中的元素依次置为null

1
2
3
4
5
6
7
8
9
10
复制代码    // 清空元素，并没有将数组置为null，而是将数组内每个元素置为null
    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

RandomAccess接口是个空接口，语义为支持随机查找，推荐使用for循环遍历效率高于迭代器

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%