Java集合框架解析（2） - 深入ArrayList源码

ArrayList 是我们常用的集合之一。从名称可以看出，ArrayList 必然和Array有着不可或缺的联系。

我们看看ArrayList 比较核心的操作

1. 以什么样的数据结构来存储数据的？
2. 怎么初始化的？做了哪些事情？
3. add中做了哪些操作呢？
4. add中的扩容怎么扩容的？
5. 怎么get数据呢？

我们先看看在ArrayList中的一些操作性的东西

默认参数

private static final int DEFAULT_CAPACITY = 10; // 默认数组容量
private static final Object[] EMPTY_ELEMENTDATA = {}; //空Object数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //空Object数组 初始化使用
transient Object[] elementData;  //存储数据的数组
private int size; // 实际有值的容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 建议的数组容量值

初始化

初始化分为三种情况

1. 无参数初始化；
   将存储对象的数组设置为空的Object数组
2. 根据容量初始化；
   根据传递的容量大小初始化容量，并初始化为Object数组
3. 根据集合数据初始化；
   将集合转为数组后，设置给存储数组，然后将数组转换为Object数组

无参数就好比我们做老式大巴车一样，生意不好的时候只有一个空车，连座位都没有这种，等有人上车再给一个个安排座位；司机如果懒就先放了些空位,等后面有人上车不用安排座位了，直接坐就好了,等空位满了再一个个安排，这就是容量初始化；过年过节人多了，就直接所有人上车，然后安排各自座位；

// 默认无参初始化
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//设置为空数组
}

// 初始化容量的实现
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
          this.elementData = new Object[initialCapacity]; // 初始化 Object数组
    } else if (initialCapacity == 0) {
         this.elementData = EMPTY_ELEMENTDATA; //设置为空Object数组
    } else {
         throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
}

// 参数为集合的初始化
public ArrayList(Collection<? extends E> c) {
     elementData = c.toArray(); //将传递的集合转数组
     if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class) // 非Object 数组
              elementData = Arrays.copyOf(elementData, size, Object[].class);//将数组转为Object数组
    } else {
       this.elementData = EMPTY_ELEMENTDATA; //设置为空Object数组
   }
}

add ?

当有人上车，会出现两种情况；
（1） 有人上车呢，随便做，司机就给安排到最后做去了；
（2） 有人非要根据座位号去坐车，怎么办呢？司机直接把座位后面的人一个个往后排了，然后给他让出空位置给他坐；
无论这上面那种情况，都会涉及到一个问题，预先安排的空座位不够了，需要加座位了，司机只有来一个人加一个，来一双加两个了。

看看代码中是怎么实现的呢

/**
 *  根据下标添加数据
 * @param  e 添加的对象
 */
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++;
}

/**
 *  直接添加数据
 * @param  e 添加的对象
 */
public boolean add(E e) {
      // 验证车（数组）时候还有位置，没了则给车加位置（扩容），保证容量足够，所有人都能坐着
     ensureCapacityInternal(size + 1); 
     elementData[size++] = e; // 将入参对象追加到末尾，并对size + 1
     return true;
}

/**
 * 处理容量
 * @param minCapacity 最小容量
 */
private void ensureCapacityInternal(int minCapacity) {
     // 先调用计算容量函数
     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

/**
 *  计算需要的座位数（容量）
 * @param minCapacity 需要的最小容量
 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
      // 判断数组是否为初始化的Object 数组 ，是则根据 需要的最小容量 和默认容量取大值，不是则返回最小容量
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
         return Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      return minCapacity;
}

/**
 *  判断有没有位置，没位置则加位置（扩容）
 * @param minCapacity 最小容量
 */
private void ensureExplicitCapacity(int minCapacity) {
      modCount++;  // modCount 计数
    
     // 当最小容量大于数组的容量时，进行扩容操作
     if (minCapacity - elementData.length > 0)
          grow(minCapacity); //扩容函数
}

扩容？

司机在安排新座位的时候，都会重新给在车上的人再安排一下，来达到加座位的目的；智障啊！没办法，程序就是这么智障

/**
 *  扩容
 * @param minCapacity 需要的最小容量
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; 
    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);// 对已经存在的数组进行扩容copy
}

/**
 *  获取车最大的载客数
 * @param minCapacity 所有的人（需要的容量）
 */
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 当需要的容量大于数组的容量时，返回最大的容量为 Integer.MAX_VALUE 否则 MAX_ARRAY_SIZE
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; 
}

get 呢 ?

车到达目的地后，看看有哪些人该下车了，直接根据座位号就可以找到人，然后通知下车咯！

public E get(int index) {
    rangeCheck(index); //验证长度
    return elementData(index);//返回 index 的值
}

/**
 *  验证index的值是否大于当前数据的总容量值
 * @param index 下标
 */
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 *  根据下标获取数据
 * @param index 下标
 */
E elementData(int index) {
    return (E) elementData[index]; //获取index 的值
}

我们来分析下结论

1. ArrayList 的底层数据结构为Array；
2. ArrayList 和Array 一样，下标都是从0开始；
3. 数组默认的初始化容量大小为 10；
4. 当Array的没有空位置的时候，每次新增，都会进行扩容操作，效率是及其低下的;
5. 如果在数据已知的情况下可以初始化数组的大小，可以节约性能，不过也不可以盲目的设置初始化大小值，以免占用空间；

可以关注我的公众号哦！ 进阶全栈.jpg