Debug ArrayList 源码

 关注
发布于: 2020 年 07 月 18 日
1，ArrayList面试必问﻿
说说ArrayList和LinkedList的区别？
ArrayList默认初始容量为多少？按照几倍来扩容？
说说数组扩容的原理？
说说ArrayList常见方法的时间复杂度？
ArrayList和vector的区别
﻿
2，Debug ArrayList源码﻿
由于1.7和1.8几乎没什么变化，本文以jdk1.8为例。
﻿
2.1 用Debug分析一个元素是如何add进ArrayList﻿
编写测试用例，打上断点：
﻿
﻿
先分析构造函数如何初始化，关键步骤如下：
﻿
﻿
elementData是ArraList底层数组的实现，（ps：hashMap数组使用table命名）
﻿
﻿
DEFAULTCAPACITY_EMPTY_ELEMENTDATA表示默认的空数组，也就是说ArrayList在构造函数初始化时并不会进行底层数组的初始化。
﻿
﻿
给元素的添加打上断点，分析过程：
﻿
﻿
进入add方法内部：
﻿
public boolean add(E e) {
﻿
        //确保内部容量，在元素添加进来前可能要进行扩容操作，size初始化为0，表示集合的长度
﻿
        ensureCapacityInternal(size + 1);  // Increments modCount!!
﻿
        //添加元素，size自增
﻿
        elementData[size++] = e;
﻿
        return true;
﻿
    }
﻿
进入ensureCapacityInternal方法内部：此时elementData为空，size+1=minCapacity=1
﻿
ensureExplicitCapacity：确保明确的能力
﻿
﻿
计算容量，calculateCapacity方法：
﻿
private static int calculateCapacity(Object[] elementData, int minCapacity) {
﻿
    //判断数组是否为空，若为空，返回默认容量和最小容量的最大值，若不为空，返回最小容量
﻿
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
﻿
        return Math.max(DEFAULT_CAPACITY, minCapacity);
﻿
    }
﻿
    return minCapacity;
﻿
}
﻿
DEFAULT_CAPACITY默认容量为10：
﻿
﻿
继续分析，进入：
﻿
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));此时参数为10，也就是ArrayList的默认容量
﻿
private void ensureExplicitCapacity(int minCapacity) {
﻿
    modCount++;   //集合的修改次数
﻿
​
﻿
    //如果最小容量减去数组长度大于0，进行扩容，此时最小容量为10，数组长度为0
﻿
    if (minCapacity - elementData.length > 0)
﻿
        grow(minCapacity);
﻿
}
﻿
核心扩容函数grow：（ps：HashMap中扩容函数为resize）
﻿
private void grow(int minCapacity) {
﻿
    //oldCapacity：旧数组容量
﻿
    int oldCapacity = elementData.length;
﻿
   
﻿
   //新容量等于旧容量加上旧容量的一半,>>1相当于除以2（ArrayList扩容是1.5倍）
﻿
    int newCapacity = oldCapacity + (oldCapacity >> 1);
﻿
    
﻿
    //新容量小于最小容量，则赋值为最小容量，此时newCapacity等于0，minCapacity为10
﻿
    if (newCapacity - minCapacity < 0)
﻿
        newCapacity = minCapacity;
﻿
        
﻿
    //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
﻿
    if (newCapacity - MAX_ARRAY_SIZE > 0)
﻿
        newCapacity = hugeCapacity(minCapacity);
﻿
    //赋值给新数组
﻿
    elementData = Arrays.copyOf(elementData, newCapacity);
﻿
}
﻿
数组复制Arrays.copyOf：
﻿
﻿
﻿
2.2 用Debug分析如何通过数组下标获取ArrayList元素﻿
打上断点，debug：
﻿
﻿
首先进行范围检查，而后返回元素
﻿
﻿
﻿
2.3 用Debug分析如何通过数组下标删除一个元素﻿
打上断点：
﻿
﻿
进入remove方法内部，
﻿
 public E remove(int index) {
﻿
        //下标范围检查
﻿
        rangeCheck(index);
﻿
        //修改次数自增
﻿
        modCount++;
﻿
        //保留当前删除元素的值，稍后返回
﻿
        E oldValue = elementData(index);
﻿
        //需要移动元素的个数
﻿
        int numMoved = size - index - 1;
﻿
        if (numMoved > 0)
﻿
        //底层使用native方法，debug进不去。native方法：java调用其他语言的接口
﻿
            System.arraycopy(elementData, index+1, elementData, index,
﻿
                             numMoved);
﻿
        //最后一位置空                     
﻿
        elementData[--size] = null; // clear to let GC do its work
﻿
        //返回删除元素的值
﻿
        return oldValue;
﻿
    }
﻿
2.4 用Debug分析如何通过对象删除一个元素﻿
﻿
进入remove方法：
﻿
public boolean remove(Object o) {
﻿
//如果对象为空，则遍历ArrayList集合
﻿
        if (o == null) {
﻿
            for (int index = 0; index < size; index++)
﻿
                if (elementData[index] == null) {
﻿
                    fastRemove(index);
﻿
                    return true;
﻿
                }
﻿
        } else {
﻿
        //不为空，也遍历
﻿
            for (int index = 0; index < size; index++)
﻿
                if (o.equals(elementData[index])) {
﻿
                    fastRemove(index);
﻿
                    return true;
﻿
                }
﻿
        }
﻿
        return false;
﻿
    }
﻿
进入fastRemove方法：
﻿
 private void fastRemove(int index) {
﻿
        modCount++;
﻿
        
﻿
        //numMoved：需要移动数组的个数
﻿
        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 wrk
﻿
    }
﻿
2.5 用Debug分析向数组中间添加元素﻿
﻿
进入add方法
﻿
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++;
﻿
}
﻿
关于System.arraycopy时间复杂度问题，在添加或者删除最后一个元素的时候不会触发数组的复制机制，时间复杂度为O（1），若是添加到数组中间，由于会触发数组的复制，时间复杂度为O（n）。对于删除元素同样，根据数组下标删除的情况下，删除尾部元素是不会触发数组的扩容机制的，若删除中间的元素，同样会触发数组的复制。若根据对象删除元素，由于本身遍历到对象的时间复杂度为O（n），删除元素后再对数组进行重组，所以时间复杂度为O（n^2）。
﻿