黑马程序员技术交流社区

标题: 【成都校区】深入理解ArrayList [打印本页]

作者: 小蜀哥哥 时间: 2019-12-6 12:12
标题: 【成都校区】深入理解ArrayList
什么是ArrayList？
ArrayList的实现原理其实就是数组（动态数组），ArrayList的介绍及简单使用方法
动态数组与一般数组有什么区别？
与Java中的数组相比，ArrayList的容量能动态地增长
ArrayList效率怎么样？
ArrayList不是线程安全的，所以效率比较高，但是只能用于单线程的环境中，那多线程呢？别急，文末会讲到
ArrayList主要继承哪些类实现了哪些接口？
ArrayList主要继承了AbstractList类，实现了List、RandomAccess、Cloneable、Serializable接口
public class ArrayList<E> extends AbstractList<E>
      implements List<E>, RandomAccess, Cloneable, java.io.Serializable
RandomAccess的意思是其拥有快速访问的能力，ArrayList可以以 O(1)[^1]的时间复杂度去根据下标访问元素。由于ArrayList底层结构是数组，所以它占据了一块连续的内存空间，其长度就是数组的大小，因此它也有数组的缺点，在空间效率不高，但是也有它的优点，就是查询速度快，时间效率较快
ArrayList的常量与变量有哪些？
// 序列ID
private static final long serialVersionUID = 8683452581122892189L;
// ArrayList默认的初始容量大小
private static final int DEFAULT_CAPACITY = 10;
// 空对象数组，用于空实例的共享空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
// 空对象数组，如果使用默认的构造函数创建，则默认对象内容是该值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存放当前数据，不参与序列化
transient Object[] elementData; // non-private to simplify nested class access
// list大小
private int size;
当集合中的元素超出数组规定的长度时，数组就会进行扩容操作，扩容操作就是ArrayList存储操作缓慢的原因，尤其是当数据量较大的时候，每次扩容消耗的时间会越来越多
ArrayList的构造方法有哪些？
一、ArrayList(int initialCapacity)
所以当我们要使用ArrayList时，可以 new ArrayList(大小)构造方法来指定集合的大小，以减少扩容的次数，提高写入效率，该构造函数的源码如下：
// 自定义初始容量的构造方法
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
      this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
      this.elementData = EMPTY_ELEMENTDATA;
} else {
      // 如果初始容量小于0，则会出现 IllegalArgumentException 异常
      throw new IllegalArgumentException("Illegal Capacity: "+
                                       initialCapacity);
}
}
这个构造函数还是比较好理解的，因为涉及到的代码也不多，而且都是一些基础的代码，相信聪明的你肯定看得懂的
二、ArrayList()
这个就更简单了，只有两行代码
// 默认的构造方法，构造一个初始容量为10的空列表
public ArrayList() {
// elementData 初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
三、ArrayList(Collection<? extends E> c)
// 构造一个包含指定元素的列表集合，按集合的返回顺序迭代器
// 传入参数为Collection对象
// c要将其元素放入此列表的集合
public ArrayList(Collection<? extends E> c) {
// 调用toArray()方法将Collection对象转换为Object[]
elementData = c.toArray();
// 判断size的大小，如果size值为0，则会抛出NullPointerException异常
// 如果size > 0 ，则执行以下代码
if ((size = elementData.length) != 0) {
      // c.toArray might (incorrectly) not return Object[] (see 6260652)
      if (elementData.getClass() != Object[].class)
         // 执行Arrays.copyOf，把Collection对象的内容copy到elementData中
         elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
      // replace with empty array.
      this.elementData = EMPTY_ELEMENTDATA;
}
}
ArrayList的方法有哪些？
add()
单个add()
// 添加单个元素,添加元素之前会先检查容量，如果容量不足则调用grow方法
public boolean add(E e) {
// 判断添加后的长度是否需要扩容
ensureCapacityInternal(size + 1);  // Increments modCount!!
// 然后在数组末尾添加当前元素，并且修改size的大小
elementData[size++] = e;
// 返回布尔值true
return true;
}
add()方法中主要用到了一个新的方法——ensureCapacityInternal，来看下ensureCapacityInternal的源码：
// 判断是否需要扩容
private void ensureCapacityInternal(int minCapacity) {
// 执行 calculateCapacity
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
而 ensureCapacityInternal 主要调用的是 ensureExplicitCapacity 方法和 calculateCapacity 方法，我们先看下calculateCapacity 方法
// 判断是否是第一次初始化数组
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 判断当前数组是否等于空的数组
// 注意：这里的 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 并不是 EMPTY_ELEMENTDATA，不过并无太大差别，只是为了          区分何时需要扩容而已
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      // 取其中最大的值作为判断本次是否需要扩容的依据，由于第一次数组是空的，所以默认要使数组扩容到10的长度
      return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
点击ensureCapacityInternal中的ensureExplicitCapacity，可以看到来到了 ensureExplicitCapacity 方法，而 ensureExplicitCapacity 主要调用的就是上面所说的 grow 方法，源码如下：
// 判断扩容的方法
private void ensureExplicitCapacity(int minCapacity) {
// 如果需要扩容modCount自增，这个参数是指当前列表的结构被修改的次数
modCount++;
// overflow-conscious code
// 判断当前数据量是否大于数组的长度，如果是，进行扩容
if (minCapacity - elementData.length > 0)
      // 执行扩容操作
      grow(minCapacity);
}
grow方法源码如下：
// grow扩容方法
private void grow(int minCapacity) {
// overflow-conscious code
// 记录扩容前的数组长度
int oldCapacity = elementData.length;
// 将原数组的长度扩大1.5倍作为扩容后数组的长度（如果扩容钱数组长度为10，那么经过扩容后的数组长度应该为15）
// 这里涉及到异或运算，不懂的朋友可以看下这篇文章 https://blog.csdn.net/Woo_home/article/details/103146845
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);
}
grow方法调用的hugeCapacity源码如下：
//如果新数组长度超过当前数组定义的最大长度时
private static int hugeCapacity(int minCapacity) {
// 抛出OOM异常
if (minCapacity < 0) // overflow
      throw new OutOfMemoryError();
// 将扩容长度设置为Interger.MAX_VALUE,也就是int的最大长度
return (minCapacity > MAX_ARRAY_SIZE) ?
      Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
public void add(int index, E element) {
//判断下标是否越界，如果是则抛出IndexOutOfBoundsException异常
rangeCheckForAdd(index);
// 判断是否需要扩容，上面讲到过，这里不再解释
ensureCapacityInternal(size + 1);  // Increments modCount!!
// 拷贝数组，将下标后面的元素全部向后移动一位
System.arraycopy(elementData, index, elementData, index + 1,
                  size - index);
// 将元素插入到当前下标的位置
elementData[index] = element;
size++;
}
rangeCheckForAdd方法
// 判断下标是否越界，如果是则抛出IndexOutOfBoundsException异常
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
      throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
添加多个元素addAll()
// 添加多个元素
public boolean addAll(Collection<? extends E> c) {
return addAll(this.size, c);
}
// 添加多个元素到指定下标
public boolean addAll(int index, Collection<? extends E> c) {
// 判断下标是否越界，上面提到过
rangeCheckForAdd(index);
// 判断c的大小是否大于0
int cSize = c.size();
// 如果等于0 返回 false
if (cSize==0)
      return false;
checkForComodification();
// 将元素插入到数组中
parent.addAll(parentOffset + index, c);
// 将修改次数赋值给 modCount
this.modCount = parent.modCount;
// size大小加一
this.size += cSize;
return true;
}
private void checkForComodification() {
// 如果修改的次数不相等
if (ArrayList.this.modCount != this.modCount)
      // 则抛出ConcurrentModificationException（并发修改）异常
      throw new ConcurrentModificationException();
}
总结：
在进行 add 操作时先判断下标是否越界，是否需要扩容，如果需要扩容，就复制数组，然后设置对应的下标元素值
扩容：默认扩容一半，如果扩容一半不够的话，就用目标的size作为扩容后的容量
// 先判断下标索引
public E get(int index) {
// 调用rangeCheck判断是否超出了Object数组长度
rangeCheck(index);
// 调用 elementData 方法
return elementData(index);
}
private void rangeCheck(int index) {
// 如果超出了Object数组的长度
if (index >= size)
      // 则抛出 IndexOutOfBoundsException（数组下标越界）异常
      throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 通过下标索引找到对应的元素值，返回指定元素
E elementData(int index) {
return (E) elementData[index];
}
public E set(int index, E element) {
// 调用rangeCheck判断是否超出范围，上面讲到过，不懂的同学往上翻翻
rangeCheck(index);
// 返回指定元素，上面也讲到过
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
// 删除元素
public E remove(int index) {
// 调用rangeCheck方法判断是否超出范围，上面讲到过
rangeCheck(index);
modCount++;
// 位置访问操作
E oldValue = elementData(index);

// 计算移除元素后需要移动的元素个数
int numMoved = size - index - 1;
if (numMoved > 0)
      // 通过 System.arraycopy 方法将后面的元素往前移动一位
      System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);

// 最后一位赋值为null
elementData[--size] = null; // clear to let GC do its work

// 返回移除后元素的值
return oldValue;
}
// 删除对象
public boolean remove(Object o) {
// 如果对象为null
if (o == null) {
      // 遍历整个list去匹配移除的值
      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++;
// 位置访问操作
int numMoved = size - index - 1;
if (numMoved > 0)
      // 通过 System.arraycopy 方法将后面的元素往前移动一位
      System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);
elementData[--size] = null; // clear to let GC do its work
}

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2