Java之ArrayList解剖学

• 2019 年 10 月 8 日
• 筆記

“ 一起来了解集合中ArrayList的源码实现 。” —— 23号老板

0

1

引入

先送一张图。好好珍藏~ （来自网络）

回归基础，回归原理，你会有更深的领悟。今天来聊一聊在Java当中常用的一个集合类：ArrayList。

在大学学习数据结构的时候，我们知道常见的一种数据结构，就是集合。而在Java中的集合，是用于存储对象的工具类容器，它实现了常用的数据结构，提供了一系列公开的方法用于增加、删除、修改、查找和遍历数据，降低了日常开发的成本，提高了开发效率。

从上面的框架图中可以看出，Java的集合主要分为两类。

1、按照单个元素存储的Collection，在其继承树中，Set、List都实现了Collection接口；

2、按照Key – Value存储的Map，也是当下最流行的一种数据结构，业内出现了以此为基础的各式Nosql数据存储层产品。

02

了解ArrayList

List集合是线性数据结构的主要实现，集合元素通常存在一个明确的元素关系，Pre、Next。因此，List集合的遍历结果是稳定的。ArrayList就是List集合中的一个实现类，在开发中也是最常使用的一个集合类。这里以最常使用的JDK8为例，如果有版本上的不一致，请参看对比。

public class ArrayList<E> extends AbstractList<E>          implements List<E>, RandomAccess, Cloneable, java.io.Serializable  

也许你会在面试当中，常说到这样的话，和LinkedList作一次对比。ArrayList在使用上查询效率较高，新增元素的效率较低，balabala……然后就没什么可说的。再一问，这是为什么？不知道。

简单来说，ArrayList在内存上的存储，是利用了一个连续的存储空间，是一个顺序容器。即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。

ArrayList的几个实现。

1、实现RandomAccess类

其原理的本质就在于indexedBinarySerach(list,key)或iteratorBinarySerach(list,key)方法。你会发现实现RandomAccess接口的List集合采用一般的for循环遍历，而未实现这接口则采用迭代器。通过大量的测试可以知道，使用迭代器遍历集合的速度会比for循环遍历差。

2、实现Cloneable类

Cloneable是一个标记接口，只有实现这个接口后，然后在类中重写Object中的clone方法，然后通过类调用clone方法才能克隆成功，如果不实现这个接口，则会抛出CloneNotSupportedException(克隆不被支持)异常。

3、实现Serializable类

实现Serializable接口的作用是就是可以把对象存到字节流，然后可以恢复（反序列化），能够进行关于对象的网络传输方式。

0

3

深入理解

/**   * 默认初始容量   */  private static final int DEFAULT_CAPACITY = 10;    private static final Object[] EMPTY_ELEMENTDATA = {};    /**   * 空表的表示方法   */  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};    /**   * 底层的数组为elementData   */  transient Object[] elementData; // non-private to simplify nested class access    /**   * ArrayList的大小   */  private int size;    /**   * 带有初始容量的构造器   */  public ArrayList(int initialCapacity) {      if (initialCapacity > 0) {//大于0时创建一个initialCapacity大小的数组          this.elementData = new Object[initialCapacity];      } else if (initialCapacity == 0) {          this.elementData = EMPTY_ELEMENTDATA;      } else {          throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);      }  }    /**   * 无参构造，默认空表数组 {}   */  public ArrayList() {      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  }    /**   * 当size大于0，采用Arrays.copyOf的复制方法赋值数组   */  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;      }  }

03

add、remove等

ArrayList的底层是基于动态数组实现的原因，动态数组的意思就是指底层的数组大小并不是固定的，而是根据添加的元素大小进行一个判断，不够的话就动态扩容，扩容的代码就在ensureCapacity里。

/**   * 确保在扩容时的容量   */  public void ensureCapacity(int minCapacity) {      int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)          // any size if not default element table          ? 0          // larger than default for default empty table. It's already          // supposed to be at default size.          : DEFAULT_CAPACITY;        if (minCapacity > minExpand) {          ensureExplicitCapacity(minCapacity);      }  }    /**   * 数组的最大长度值，超过则OutOfMemoryError   * OutOfMemoryError: Requested array size exceeds VM limit   */  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;    /**   * 扩容，原数组长度的2倍+1，采用的Arrays.copyOf复制方法   */  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);      elementData = Arrays.copyOf(elementData, newCapacity);  }      public int size() { return size;}    public boolean isEmpty() { return size == 0;}    public boolean contains(Object o) { return indexOf(o) >= 0;}  

空间的问题解决后，插入过程就显得非常简单。

/**   * 获取index位置的元素   */  public E get(int index) {      rangeCheck(index);        return elementData(index);  }    /**   * 替换index位置上的元素   */  public E set(int index, E element) {      rangeCheck(index);      E oldValue = elementData(index);      elementData[index] = element;      return oldValue;  }    /**   * 新增元素   */  public boolean add(E e) {      ensureCapacityInternal(size + 1);  // Increments modCount!!      elementData[size++] = e;      return true;  }    /**   * 删除元素   */  public E remove(int index) {      rangeCheck(index);      modCount++;      E oldValue = elementData(index);        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 work      return oldValue;  }    public boolean remove(Object o) {      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;  }    private void fastRemove(int index) {      modCount++;      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 work  }  

删除是每次进行数组复制，然后让旧的elementData置为null进行垃圾回收。

以remove()方法为例。

可以看到这个 remove() 方法被重载了，一种是根据下标删除，一种是根据元素删除，这也都很好理解。

根据下标删除的 remove() 方法，大致的步骤如下：

1、检查有没有下标越界，就是检查一下当前的下标有没有大于等于数组的长度

2、列表被修改（add和remove操作）的次数加1

3、保存要删除的值

4、计算移动的元素数量

5、删除位置后面的元素向左移动，这里是用数组拷贝实现的

6、将最后一个位置引用设为 null，使垃圾回收器回收这块内存

7、返回删除元素的值

根据元素删除的 remove() 方法，大致的步骤如下：

1、元素值分为null和非null值

2、循环遍历判等

3、调用 fastRemove(i) 函数

a、修改次数加1

b、计算移动的元素数量

c、数组拷贝实现元素向左移动

d、将最后一个位置引用设为 null

e、返回 fase

4、返回 true

04

小结

现在，你对ArrayList是不是有了一个更深入的理解。深入源码，有时候能够让你更加理解代码的逻辑和数据结构。

文章部分内容来自网络博客，综合整理，在此鸣谢。