【Java集合】之 ArrayList 详解

曾经终败给现在 2023-02-23 03:37 10阅读 0赞

***小王，听说你对 ArrayList 很熟呀！今天我们就来聊一下它吧！***

（小 case 了，这种问题早就滚瓜烂熟了呀！放马过来吧！）

好的，没问题，想了解什么都可以问！

***你先说一下 ArrayList 是一个什么东西？可以用来干嘛？***

ArrayList就是数组列表，主要用来装载数据，当我们装载的是基本类型的数据int，long，boolean，short，byte…的时候我们只能存储他们对应的包装类，它的主要底层实现是数组Object\[\] elementData。

ArrayList底层是用数组实现的存储，特点是查询效率高，增删效率低，线程不安全。使用频率很高，

***我们知道 ArrayList 是线程不安全的，为什么还使用它呢？***

因为我们正常使用的场景中，都是用来查询，不会涉及太频繁的增删，如果涉及频繁的增删，可以使用LinkedList，如果你需要线程安全就使用Vector，这就是三者的区别了，实际开发过程中还是ArrayList使用最多的。

不存在一个集合工具是查询效率又高，增删效率也高的，还线程安全的，至于为啥大家看代码就知道了，因为数据结构的特性就是优劣共存的，想找个平衡点很难，牺牲了性能，那就安全，牺牲了安全那就快速。

***说一下 ArrayList 的初始化过程***

ArrayList 的无参构造方法的方式ArrayList()初始化，则赋值底层数Object\[\] elementData为一个默认空数组Object\[\] DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA = \{\} 所以数组容量为0，只有真正对数据进行添加add时，才分配默认DEFAULT\_CAPACITY = 10的初始容量，源码如下：

// 指定初始化大小构造器
    public ArrayList(int initialCapacity) { 
        if (initialCapacity > 0) { 
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) { 
            this.elementData = EMPTY_ELEMENTDATA;
        } else { 
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    // 默认构造器
    public ArrayList() { 
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    // 默认元素大小
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };

***ArrayList 的扩容机制是怎样的？***

ArrayList 不同于数组，数组是固定长度的，而 ArrayList 是会动态调整数组元素的大小，也就是我们所说的扩容。我们知道，ArrayList 的初始化的是不会为元素分配空间的，只有当第一次 add() 的时候才会分配默认 10 个元素的空间大小：

/** * Default initial capacity. */
    private static final int DEFAULT_CAPACITY = 10;

后续不断添加元素的时候，首先会先判断元素空间是否已满，如果满了则会扩容 1.5 倍，然后把原数组的数据，原封不动的复制到新数组中，这个时候再把指向原数的地址换到新数组。

***ArrayList 的默认数组大小为什么是10？***

其实我也没找到具体原因，据说是因为sun的程序员对一系列广泛使用的程序代码进行了调研，结果就是10这个长度的数组是最常用的最有效率的，也有说就是随便起的一个数字，8个12个都没什么区别，只是因为10这个数组比较的圆满而已。

***你说到 ArrayList 的增删很慢，那 ArrayList 在增删的时候是怎么做的么？***

好的，我分别说一下他的新增的逻辑吧，它有指定index新增，也有直接新增的，在这之前他会有一步校验长度的判断**ensureCapacityInternal**，就是说如果长度不够，是需要扩容的。

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

在扩容的时候，老版本的jdk和8以后的版本是有区别的，8之后的效率更高了，采用了位运算，**右移**一位，其实就是除以2这个操作：

private void grow(int minCapacity) { 
        // overflow-conscious code
        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);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

指定位置新增的时候，在校验之后的操作很简单，就是数组的copy：

public void add(int index, E element) { 
        rangeCheckForAdd(index);
    
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

**arraycopy** 的原理是这样子的：假如有10个元素，需要在 index 5 的位置去新增一个元素A，它会把从index 5的位置开始的后面所有元素赋值到 index 5+1 的位置，然后在 index 5 的位置放入元素A就完成了新增的操作了。

至于为啥说他效率低，我想我不说你也应该知道了，我这只是在一个这么小的List里面操作，要是我去一个几百几千几万大小的List新增一个元素，那就需要后面所有的元素都复制，然后如果再涉及到扩容啥的就更慢了不是嘛。

***我问你个真实的场景问题，ArrayList（int initialCapacity）会不会初始化数组大小？***

答案是：**不会初始化数组大小！**

从源码可以看出，ArrayList（int initialCapacity) 只是给 elementData 分配了初始空间而已，数组元素大小 size 并没有初始化或者说赋值，所以说初始化之后调用 size() 返回的是0。只有调用 add() 方法才会改变 size 的值。

***ArrayList插入删除一定慢么？***

不一定，这取决于你删除的元素离数组末端有多远，ArrayList拿来作为堆栈来用还是挺合适的，push和pop操作完全不涉及数据移动操作。

***那 ArrayList 的删除怎么实现的呢？***

删除其实跟新增是一样的，不过叫是叫删除，但是在源码中我们发现，他还是在copy一个数组：

public E remove(int index) { 
        rangeCheck(index);
    
        modCount++;
        E oldValue = elementData(index);
    
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    
        return oldValue;
    }

比如我们现在要删除数组中的 index5 的这个位置上的元素 ，那代码他就复制一个index5+1开始到最后的数组，然后把它放到index开始的位置，index5的位置就成功被”删除“了其实就是被覆盖了，给了你被删除的感觉，同理他的效率也低，因为数组如果很大的话，一样需要复制和移动的位置就大了。

***ArrayList 用来做队列合适么？***

队列一般是FIFO（先入先出）的，如果用ArrayList做队列，就需要在数组尾部追加数据，数组头部删除数组，反过来也可以。但是无论如何总会有一个操作会涉及到数组的数据搬迁，这个是比较耗费性能的，所以 ArrayList 不适合做队列。

***那数组适合用来做队列么？***

数组是非常合适的，比如ArrayBlockingQueue内部实现就是一个环形队列，它是一个定长队列，内部是用一个定长数组来实现的，另外著名的Disruptor开源Library也是用环形数组来实现的超高性能队列，具体原理不做解释，比较复杂，简单点说就是使用两个偏移量来标记数组的读位置和写位置，如果超过长度就折回到数组开头，前提是它们是定长数组。

***ArrayList的遍历和LinkedList遍历性能比较如何？***

论遍历ArrayList要比LinkedList快得多，ArrayList遍历最大的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。