JAVA基础集合框架【一】ArrayList之源码分析

文章首发于：clawhub.club

---

继承与实现

ArrayList 继承(extends) AbstractList抽象类,实现（implements) List, RandomAccess, Cloneable, java.io.Serializable接口。

AbstractList

是List接口的一个框架实现，以尽量减少实现此接口所需的工作。

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

List

继承Collection集合接口，是一个有序的集合，提供插入、查找等操作。

public interface List<E> extends Collection<E>

RandomAccess

这是一个标记接口，用于随机访问列表时提供更好的性能，如果集合类实现了RandomAccess接口，则表示这个集合类持支快速随机访问，且量用for(int i = 0; i < size; i++) 来遍历，效率高。

Cloneable

实现Cloneable接口的目的是重写java.lang.Object的clone()的方法，实现浅拷贝。
浅拷贝只复制一层对象的属性，而深拷贝则递归复制了所有层级。

java.io.Serializable

实现该接口的类支持序列化。
序列化：可以将一个对象的状态写入一个Byte流里。

构造函数

ArrayList 提供了三个构造函数：

ArrayList()：默认构造函数，提供初始容量为 10 的空列表。

ArrayList(int initialCapacity)：构造一个具有指定初始容量的空列表。

ArrayList(Collection<? extends E> c)：构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。

这里面涉及到的EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA的区别，后期专门分析。

// 默认空数组，final 关键字修饰
private static final Object[] EMPTY_ELEMENTDATA = {};
// 空数据的共享空数组实例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 存储ArrayList元素的数组缓冲区，即ArrayList 存放数据的地方
 * ArrayList的容量是这个数组缓冲区的长度
 * transient 关键字修饰，elementData 不支持序列化
 */
transient Object[] elementData;

/**
 * 默认无参构造方法
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * 带整型参数的构造方法
 * @param initialCapacity 初始化容量大小
 */
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);
    }
}

/**
 * 泛型集合参数构造方法
 * @param c 集合类型参数
 */
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;
    }
}

新增

主要介绍add(E e)，add(int index, E element)，set(int index, E element)方法。
add(E e)：将指定的元素添加到此列表的尾部。

   public boolean add(E e) {
       ensureCapacityInternal(size + 1);  // Increments modCount!!
	//元素添加到列表的尾部
       elementData[size++] = e;
       return true;
   }

   //计算容量
   private static int calculateCapacity(Object[] elementData, int minCapacity) {
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           return Math.max(DEFAULT_CAPACITY, minCapacity);
       }
       return minCapacity;
   }
   //确认集合内部容量大小
   private void ensureCapacityInternal(int minCapacity) {
       ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
   }

//确保可以容纳新增元素
   private void ensureExplicitCapacity(int minCapacity) {
       modCount++;

       // overflow-conscious code
       if (minCapacity - elementData.length > 0)
	    //扩容，后面专门介绍
           grow(minCapacity);
   }

add(int index, E element)：将指定的元素插入此列表中的指定位置。
核心方法是System.arraycopy()，此方法耗时，所以有大量插入操作时，选择LinkedList

  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++;
  }
/**
   * A version of rangeCheck used by add and addAll.
* 判断索引位置是否正确
   */
  private void rangeCheckForAdd(int index) {
      if (index > size || index < 0)
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  }

set(int index, E element)：用指定的元素替代此列表中指定位置上的元素。

   public E set(int index, E element) {
    //索引判断
       rangeCheck(index);

	//获取原有的值
       E oldValue = elementData(index);
       // 将新增值替换到原有值
	elementData[index] = element;
	// 返回原有的值
       return oldValue;
   }
private void rangeCheck(int index) {
       if (index >= size)
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }

@SuppressWarnings("unchecked")
   E elementData(int index) {
       return (E) elementData[index];
   }

查找

get(int index) ，速度非常快，随机访问。

   public E get(int index) {
       rangeCheck(index);

       return elementData(index);
   }
private void rangeCheck(int index) {
       if (index >= size)
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }

@SuppressWarnings("unchecked")
   E elementData(int index) {
       return (E) elementData[index];
   }

删除

remove(int index)：移除此列表中指定位置上的元素。从源码中可以看到发生了数据拷贝，消耗性能，
所以遇到大量删除元素的情况，使用LinkedList。

  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);
      // 数据最后一位置空，等待GC							 
      elementData[--size] = null; // clear to let GC do its work

//返回删除的值
      return oldValue;
  }

remove(Object o)：移除此列表中首次出现的指定元素（如果存在）。

  public boolean remove(Object o) {
   //ArrayList支持null元素
      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 remove method that skips bounds checking and does not
   * return the value removed.
   */
  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
  }

retainAll(Collection<?> c)：只保留此列表中包含在指定集合中的元素。换句话说，从这个列表中删除指定集合中不包含的所有元素。

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

参考资料：

http://wiki.jikexueyuan.com/project/java-enhancement/java-twentyone.html
https://snailclimb.gitee.io/javaguide/#/./java/ArrayList
https://juejin.im/post/5c0a7130e51d4529ee233d3b
https://www.cnblogs.com/mingmingcome/p/9350667.html
https://juejin.im/post/5b76357df265da27fd70c3ce