ArrayList 深入分析

• 导语

ArrayList是我们在编程中经常用到的类，它实现了接口List，List接口继承了Collection接口。ArrayList使用非常广泛，在集合框架中举重轻重。

分析要点

• 是否线程安全？
• 数据结构是怎样的？
• 怎么实现扩容？
• 怎么实现插入和获取元素？
• 应用与哪些场景？

深入剖析

构造函数

...
// 成员变量
transient Object[] elementData;
...
public ArrayList(int initialCapacity) {
  if (initialCapacity > 0) {
    this.elementData = new Object[initialCapacity];
  } else if (initialCapacity == 0) {
    this.elementData = EMPTY_ELEMENTDATA;
  } else {
    throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
  }
}

• 初始化一个容量为initialCapacity大小的ArrayList
• Object[] elementData ArrayList的成员变量，所有的元素都放到该数组中的，可以看出其存储的数据结构为数组

元素的插入

• 元素插入的方法，只列举其中之一

public boolean add(E e) {
  // 添加元素时，先判断数组容量是否足够，这里的容量有两个值，一个为size代表实际元素的个数，一个为length代表数组的长度
  ensureCapacityInternal(size + 1);  
  elementData[size++] = e;
  return true;
}

• calculateCapacity方法中主要计算出本次插入后实际需要的数组长度

private void ensureCapacityInternal(int minCapacity) {
  ensureExplicitCapacity(
calculateCapacity(elementData, minCapacity));
}

• 判断是否需要扩容的逻辑

private void ensureExplicitCapacity(int minCapacity) {
  modCount++;
  // 如果当前元素的实际个数+1大于了数组的长度时，则进行扩容
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}

• 扩容逻辑

private void grow(int minCapacity) {
  // 原始数组大小
  int oldCapacity = elementData.length;
  // 新数组大小，oldCapacity >> 1为具体扩容的大小
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
  // 进行元素拷贝，生成了一个长度为newCapacity的数组
  elementData = Arrays.copyOf(elementData, newCapacity);
}

元素的删除

// 该方法总的来说就是获取删除元素位置index
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; 
}

是否线程安全

ArrayList为线程不安全的，主要体现在扩容的时候。我们假设一个场景，当ArrayList容量只剩1的时候，并发来了2个请求同时进行add(e),if (minCapacity - elementData.length > 0)会都判断为true，可以进行元素插入时，就会出现数组越界异常。

应用场景

• 对于需要快速随机访问元素，应该使用ArrayList。
• 对于单线程环境或者多线程环境，但List仅仅只会被单个线程操作，此时应该使用非同步的类ArrayList。

本节只列举出了ArrayList最基本的插入和删除方法，但是我们可以从中了解到它的实现原理，对我们分析ArrayList有很大帮助。想了解更多，请阅读ArrayList源码。

扫码关注了解更多