深入java底层源码, 揭开ArrayList神秘面纱

我就是我 2022-11-29 03:10 99阅读 0赞

一般情况下，当我们想用一个List集合时，首先想到的是ArrayList，其次就是LinkedList，但是我相信大部分小伙伴在项目中用到的ArrayList远比LinkedList，为什么呢？什么样的情况下优先选择ArrayList，什么样的情况下优先选择LinkedList? 哪种数据结构在什么样的条件下的性能更好？以及为什么在阿里开发规范中对集合要强调必须要初始化大小呢？还有为什么在并发情况下去remove数据的时候会出现ConcurrentModificationException呢？等等，我们将先来一步步揭开ArrayList的神秘面纱

public class ArrayListDemo {
        public static void main(String[] args) throws Exception {
            List<String> list = new ArrayList<>(20);
            list.add("aa");
            list.add("bb");
            list.add("cc");
            list.set(1, "dd");  //替换
            list.add(1, "ee");
            list.get(1);
            list.remove(1);
        }
    }

看源码前我们先整一个demo例子，主要是增删改查，平时我们用的最多也就是上面的方法

## ArrayList初始化 ##

我们先看一下ArrayList内部定义了哪些全局变量

// 初始化大小
    private static final int DEFAULT_CAPACITY = 10;
    // 空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 默认大小空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 存放元素的数组
    transient Object[] elementData;
    // 数组中元素的个数
    private int size;

补充: transient的意思是当对ArrayList对象进行序列化时，这个属性不进行序列化，想更深入理解的小伙伴可以自行百度

### 初始化构造函数一无参构造函数 ###

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

这也是我们平时最喜欢用的构造函数之一，初始化一个ArrayList对象之后，实际上就是初始化了一个空数组，里面什么都没有，也没有分配内存空间

### 初始化构造函数二有参构造函数 ###

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);
            }
        }

此构造函数需要我们传递进去一个初始化ArrayList大小的值，然后根据传递进来的值来初始化一个数组(分配好空间，但是没有数据)，如果传递的是0，则还是初始化为空数组。这个构造函数也是我们比较推荐的初始化方式，也是比较容易忽略的问题，我们后面看代码时再来说明为什么要进行数组大小的初始化

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;
            }
        }

这个构造函数就是把你传入进来的集合Collection转为一个ArrayList

## 添加方法-add ##

public boolean add(E e) {
            //确保数组有足够的容量
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

直接往集合中添加一个元素，第一步就是先保证底层数组的大小足够你去存放这个值，我们先重点分析一下这个ensureCapacityInternal()这个方法

private void ensureCapacityInternal(int minCapacity) {
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }

先看里面的方法calculateCapacity()计算大小

private static int calculateCapacity(Object[] elementData, int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                //初始化大小
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }

首先判断当前数组是否是一个空数组，如果我们初始化时调用的是无参构造方法，此时elementData肯定是一个空数组，则返回的是DEFAULT\_CAPACITY = 10，和minCapacity中最大值，肯定就是默认值10了，而如果初始化时设置了数组的大小，此时直接返回minCapacity, 即为 初始化大小 + 1

我们再看一下ensureExplicitCapacity()方法

private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // overflow-conscious code
            //判断是否需要扩容过
            if (minCapacity - elementData.length > 0)
                //扩容
                grow(minCapacity);
        }

modCount++这个属性值我们后面分析，minCapacity就是上面的方法返回的值，要么是minCapacity，要么就是DEFAULT\_CAPACITY和minCapacity中的最大值，如果我们第一次进来，没有初始化大小，则minCapacity = 10, elementData.length因为还没有放数据，所以为0，minCapacity - elementData.length > 0, 然后第一次调用grow方法进行扩容

private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            //新数组的容量为旧数组的 1.5倍
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            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);
        }

第一次的时候

int oldCapacity = elementData.length = 0;
            int newCapacity = oldCapacity + (oldCapacity >> 1) = 0;
            minCapacity = 10
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity = 10;

下面再调用

elementData = Arrays.copyOf(elementData, newCapacity);

底层是一个数组的拷贝，也可以简单理解为初始化一个数组，长度为10

此时相当于我们对数组进行了一个初始化，数组长度为10，接着调用

elementData[size++] = e;

接着把数据放入到size的位置，然后size ++ 往后移动一位

如实例代码，当我们调用完list.add("add")时, 此时数组长度为10，size = 1, elementData = \["aa", null, null, null,null,null, null, null,null, null\];

当第二次进行add时

此时elementData != \{\}，直接返回minCapacity = size + 1 = 2

if (minCapacity - elementData.length > 0)
                //扩容
                grow(minCapacity);

minCapacity - elementData.length = 2 - 10 < 0，所以此时不会再进行扩容调用grow方法

现在我们假设数组中已经有了十个数据，即此时数组长度为10，size = 10, elementData = \["aa", “bb”, "cc", "dd","ee","ff", "gg", "hh","ii", "jj"\];

我们接下来第十一次进行add，此时会发生什么

minCapacity = size + 1 = 11, 此时返回11

if (minCapacity - elementData.length > 0)
                //扩容
                grow(minCapacity);

然后判断minCapacity - elementData.length = 11 - 10 = 1 > 0，此时会再次触发调用grow方法进行扩容

private void grow(int minCapacity) {
            
            int oldCapacity = elementData.length = 10;
            int newCapacity = oldCapacity + (oldCapacity >> 1) = 10 + 5 = 15;
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            // 肯定 newCapacity < MAX_ARRAY_SIZE
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
    
            //声明新的数组，并把旧数组中的数据拷贝到新数组中
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

如代码注释，此时会进行扩容，扩容后的大小即为原来容量大小的1.5倍，扩容完毕之后，会先声明一个新的数组，然后把旧数组中的数据拷贝到新数组中去

ArrayList缺点一：当我们对ArrayList集合进行大量的add时, 就会导致底层的数据频繁进行扩容，再扩容时底层会先创建一个数组，然后把旧数组拷贝到新数组中，第一: 当数据量很大时，会导致内存空间的浪费，也有可能导致堆内存空间不够导致出现gc，再一个大数组拷贝时，对性能来说是一个比较大的考验

为什么阿里java代码规范中强调在集合初始化时，要指定集合初始值大小？

因为在指定了集合初始值大小时，会初始化数组大小，elementData.length = 初始化大小，此时，当我们执行如下判断进行扩容时

if (minCapacity - elementData.length > 0)
                //扩容
                grow(minCapacity);

就会根据我们初始化大小来判断什么时候进行扩容。打个比方，如果我们要往集合中添加11个元素，如果我们不设置初始化大小的值，则会调用grow两次，第一次数组拷贝其实就是拷贝空数组到一个新初始化DEFAULT\_CAPACITY大小的数组中，相当于初始化，第二次就是数组拷贝扩容。而如果我们指定了大小为11，此时压根就不会调用grow来进行扩容，此时性能是比较高，所以我们在使用ArrayList集合时，尽量指定大小，当数据量很大时，会提升很大的性能

测试代码，1000W数据

//默认大小
        private static void test1() {
            List<Integer> list = new ArrayList<>();
            long start = System.currentTimeMillis();
            for (int i = 0; i < 10000000; i++) {
                list.add(i);
            }
            System.out.println(System.currentTimeMillis() - start);
        }
        //设置初始化大小
        private static void test2() {
            List<Integer> list = new ArrayList<>(10000000);
            long start = System.currentTimeMillis();
            for (int i = 0; i < 10000000; i++) {
                list.add(i);
            }
            System.out.println(System.currentTimeMillis() - start);
        }

以上代码的输出为

2183 和320，性能相差7倍

### 在指定位置添加元素 ###

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++;
        }

当前数组数据为：数组长度为10，size = 4, elementData = \["aa", “bb”, "cc", “dd”,null,null, null, null,null, null\];

此时要在index = 1的位置添加"ee"元素进去

第一步校验index是否越界

private void rangeCheckForAdd(int index) {
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

第二步就是扩容，确保数组的长度足够，看上面的代码分析

接下来就是先进行一个数组的拷贝

System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);

我们可以把我们预设的值填写进去，最终结果就是

System.arraycopy(elementData, 1, elementData, 2, 3);

就是把数组elementData中的元素，从1位置的元素，拷贝3个数据， 拷贝的位置是从2的位置开始，最后的到的数组中的元素就是

elementData = \["aa", “bb”, "bb", “cc”,"dd",null, null, null,null, null\];这样的数组

然后执行elementData\[index\] = element; 即把index = 1的位置设置为element = "ee",即最终的数组就是

elementData = \["aa", “ee”, "bb", “cc”,"dd",null, null, null,null, null\];

缺点二：当我们往指定的位置添加数据的时，也是需要对数组进行拷贝的，所以往指定位置添加元素时，性能也不是很好

### 修改指定位置的元素-set ###

public E set(int index, E element) {
            rangeCheck(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }

这个方法就很简单了，先检查index是否越界，然后取出来index位置的元素旧值，然后替换index位置的元素，最后返回旧值，因为是通过索引位置进行直接修改的，所以性能很高

### 获取指定位置的元素-get ###

public E get(int index) {
            rangeCheck(index);
    
            return elementData(index);
        }

这个方法也很简单，就是通过index直接定位到数组中的元素

ArrayList优点: 可以通过下标索引快速定位到指定位置的元素然后返回，性能很高

### 移除指定位置的元素-remove ###

public E remove(int index) {
            //校验index
            rangeCheck(index);
    
            modCount++;
            E oldValue = elementData(index);
    
            int numMoved = size - index - 1;
            //拷贝index后的numMoved的数据往前移动一位
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            //释放最后一个元素
            elementData[--size] = null; // clear to let GC do its work
    
            return oldValue;
        }

我们以之前set修改之后的数组为例，来剖析一下remove指定的逻辑，即elementData = \["aa", “ee”, "bb", “cc”,"dd",null, null, null,null, null\]; size = 5;

我们现在要删除index = 1位置的元素即 ee

第一步校验index是否越界

第二步modCount++，下面分析

第三步获取index = 1位置的元素

第四步 numMoved = size - index - 1 = 5 - 1 - 1 = 3 即为要移动的元素个数

接着就是执行 System.arraycopy(elementData, 2, elementData, 1, 3);

从2个位置开始，拷贝3个元素，拷贝到 从第一个位置开始，即elementData = \["aa", “bb”, "cc", “dd”,"dd",null, null, null,null, null\];

拷贝之后即为上面的样子，最后一步

elementData\[--size\] = null; 即把最后的一个元素这只为null，elementData\[4\] = null，最终的出

elementData = \["aa", “bb”, "cc", “dd”,null,null, null, null,null, null\];

所以remove操作也有元素的拷贝，但是不知道大家有没有注意到一个问题，比如，当我们数组现在有1000W个元素，然后我把这么多元素一个个remove掉了之后，数组的长度是没有任何变化的，依然是1000W，依然占据着内存中的一篇区域，如果不对其进行回收，就导致空间的大量浪费，所以最好的做法是，再删除remove操作的时候，需要对数据进行缩容，比如当数组中的元素为原来的一半时，进行一次缩容

以上代码分析了增删改查操作，即增删改都会涉及到数组元素的移动，是比较消耗性能的，而我们get一个数据时，可以通过下标索引快速查询到我们需要的数据，即: ArrayList更适用于读多写少的场景，另外，因为数组是有序的，所以ArrayList同时兼具有序性的特点，即，我们放入集合中的顺序是什么样的，我们得到的数据就是什么样的

### 迭代输出-iterator ###

public Iterator<E> iterator() {
            return new Itr();
        }

返回的是一个内部类Itr对象，此对象实现了Iterator接口

在此对象内部，首先声明了一个变量，即int expectedModCount = modCount; 我们在调用iterator方法时，此时直接把modCount的值赋值给了expectedModCount, 相当于保存了当时的一个快照

在上面我们分析添加元素扩容前、remove数据的时候都会对modCount进行操作

public boolean hasNext() {
                return cursor != size;
            }

hasNext()方法来判断是否还有下一个元素可以获取, cursor一步步向前走

我们看一下next()方法获取元素

public E next() {
                checkForComodification();
                int i = cursor;
                if (i >= size)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                if (i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i + 1;
                return (E) elementData[lastRet = i];
            }

首先会调用checkForComodification()方法

final void checkForComodification() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }

所以，我们可以得出结论，当有一个线程调用了iterator()方法对ArrayList集合进行遍历时，此时又有其他线程对ArrayList进行了添加或者remove操作，此时会导致modCount的修改，那么此时modCount != expectedModCount成立，就会导致ConcurrnetModificationException的异常，这也是为什么ArrayList不能保证线程的安全的一个原因

最后我们再看一下ArrayList的时间复杂度

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>操作</td> 
   <td>时间复杂度</td> 
  </tr> 
  <tr> 
   <td>add(E element)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>add(int index)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>remove</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>set</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>get</td> 
   <td>O(1)</td> 
  </tr> 
 </tbody> 
</table>