ArrayList详解

ArrayList介绍

list的特点：是有顺序的，先进先出原则；元素是可以重复的；包含带索引的方法

ArrayList详解

ArrayList集合是Collection和List接口的实现类，底层的数据结构可变的Object数组，对ArrayList的所有操作都是通过数据来实现的，数据结构特点是增删慢、查询快。

数据结构详解

//空对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量空对象数据，通过空的构造函数生成ArrayList对象实例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//实际对象数组，ArrayList可以存储任意引用数据类型
transient Object[] elementData; // non-private to simplify nested class access
复制代码

查询快，增删慢

由于底层是数据，数据是一种查询快，增删慢的数据结构，查询是通过索引下标进行定位的，所以查询效率很高，删除和新增的时候，则需把原始的数据进行移动，所以效率就比较低eg：

默认容量

//默认容量
private static final int DEFAULT_CAPACITY = 10;
//最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
复制代码

ArrayList 无参数构造的时候容量是多少呢? 通过下面来看 刚创建的时候容量是0，在执行add方法的时候判断数组的容量是否有存储空间，如果没有则初始化一个10的容量

public ArrayList() {
  //DEFAULTCAPACITY_EMPTY_ELEMENTDATA 上面已经定义了 {}
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
复制代码

//向数组中添加元素
public boolean add(E e) {
  //确保有容量，如果第一次添加，会初始化一个容量为10的list
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  //添加元素
  elementData[size++] = e;
  return true;
}
private void ensureCapacityInternal(int minCapacity) {
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) 
  //第一次的时候elementData是空数据，如果是空数组的时候 则比较 默认容量和minCapacity 返回其中大的，
  //所以第一次添加的时候返回是10
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}
//确保不会超过数组的真实容量
private void ensureExplicitCapacity(int minCapacity) {
  //当前数据的计数器
  modCount++;
  // overflow-conscious code
  //最小容量是minCapacity是10，减去当前容量
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}
复制代码

有参构造方法

//窗机爱你Arrayist集合，并且设置固定的集合容量
public ArrayList(int initialCapacity) {
  //initialCapacity 手动传入的容量
  if (initialCapacity > 0) {
    //如果容量大于0 ，创建一个对象数组为指定容量大小
    this.elementData = new Object[initialCapacity];
  } else if (initialCapacity == 0) {
    //如果为0 则为空数组{}
    this.elementData = EMPTY_ELEMENTDATA;
  } else {
    //如果不是0 也不大于0 则抛出异常
    throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
  }
}
复制代码

注意： 使用 ArrayList的集合，建议设置集合容量的大小，提高集合的使用效率

ArrayList扩容原理

add方法先要确保数组的容量足够，防止数组已经填满了还往里面添加数据。

• 如果数据空间足够，直接将数据添加到数组中
• 如果数据空间不足，则进行扩容，扩容原来1.5倍容量
• 扩容：原始数组copy到新数组中，同时向新数组后面添加数据
• ArrayList的数组最大值是Integer.MAX_VALUE,
• 新增元素时，没有严格的数据值检查，所以可以设置为null

//minCapacity 当前数组的最小容量，实际上就是存储了多少个元素
private void grow(int minCapacity) {
  // 获取当前数组的长度
  int oldCapacity = elementData.length;
  //新容量 = 旧容量 + 0.5 * 旧容量，所以也就是1.5倍扩容
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  //极端情况过滤，如果新容量 减去minCapacity 小于0 【考虑的是int值溢出的问题】
  if (newCapacity - minCapacity < 0)
    //新容量等于minCapacity 则不尽兴扩容
    newCapacity = minCapacity;
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    //如果新容量超过了默认最大容量，则以ArrayList最大值为当前容量
    newCapacity = hugeCapacity(minCapacity);
  // minCapacity is usually close to size, so this is a win:
  elementData = Arrays.copyOf(elementData, newCapacity);
}
复制代码