ArryaList源码浅析

ArryaList源码浅析

一 .继承关系

​ ArrayList是java中常用的集合框架之一，其内部数据存储为数组形式，其继承关系如上图所示。

二.属性与方法

属性

• private static final long serialVersionUID = 8683452581122892189L;
             

  序列化版本ID，用于反序列化进行版本比较，若反序列化时UID不一致将会抛出java.io.InvalidClassException异常。

• private static final Object[] EMPTY_ELEMENTDATA = {};
             

  用于空列表的共享空对象数组，避免每次实例化时重新申请。

• private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
             

  同样也是用于空列表的共享空对象数组，用于无参构造，和EMPTY_ELEMENTDATA的具体区别见注意事项。

• transient Object[] elementData;
             

  用于存放该列表的数据。

• private int size;
             

  该列表中元素的个数（指的是元素的个数，而非elementData数组的大小）。

• private static final int DEFAULT_CAPACITY = 10;
             

  默认的初始化数组大小。

• private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
             

  数组申请的最大大小，为什么会是Integer.MAX_VALUE - 8？这是因为有些虚拟机会在数组头部占用一定的空间，如果尝试申请Integer.MAX_VALUE大小的数组，可能会导致OutOfMemoryError: Requested array size exceeds VM limit。

方法

构造方法

• public ArrayList(int initialCapacity);
             

  有参构造方法，创建一个指定数组大小的空列表，如果initialCapacity为0，其elementData=EMPTY_ELEMENTDATA。

• public ArrayList();
             

  无参构造方法，elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

• public ArrayList(Collection<? extends E> c);
             

  有参构造方法，将传入的集合转换为数组存入elementData中，若集合为空，elementData=EMPTY_ELEMENTDATA。

列表核心方法

• public void ensureCapacity(int minCapacity);
             

  ArryaList的扩容方法，将对象数组的大小扩容为至少满足minCapacity大小的程度。

  扩容规则：

  1. 计算minExpand，若elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA时为0，否则为DEFAULT_CAPACITY = 10。
  2. 若minCapacity <= minExpand时，不进行扩容。否则继续进行扩容
  3. 计算minCapacity是否大于当前数组大小，大于时才进行扩容，防止数据丢失。
  4. 计算newCapacity（原数组大小的1.5倍）
  5. newCapacity取newCapacity与minCapacity的较大者
  6. 判断newCapacity是否大于MAX_ARRAY_SIZE。大于时若minCapacity < 0 抛出OutOfMemoryError异常，minCapacity > MAX_ARRAY_SIZE时newCapacity取Integer.MAX_VALUE，否则取MAX_ARRAY_SIZE。
  7. 根据newCapacity创建新数组，并将原数组数据进行拷贝。

• public int size();
             

  返回size的值，即列表中元素的个数。

• public boolean isEmpty();
             

  判断列表是否为空，即size == 0？

• public boolean contains(Object o);
             

  查询列表中是否包含对象o，若不包含对象o，返回false。

  注意：这里的o可以为null，此时比较直接使用==比较符，若o为对象，则调用该对象的equals方法。(内部实现为indexOf(Object o))。

• public int indexOf(Object o);
             

  从头开始查询列表，返回对象o的数组下表，未查询到时返回-1。

  注意：这里的o可以为null，此时比较直接使用==比较符，若o为对象，则调用该对象的equals方法。

• public int lastIndexOf(Object o);
             

  从末尾开始查询列表，返回对象o的数组下表，未查询到时返回-1。

• public E get(int index);
             

  根据索引值获取指定位置的数据。

• public E set(int index, E element);
             

  根据索引值重新设置指定位置的数据，返回旧值。

• public boolean add(E e);
             

  判断数组是否能容纳size+1个元素，不满足则先进行扩容，最后添加元素至数组末尾。

• public void add(int index, E element);
             

  判断数组是否能容纳size+1个元素，不满足则先进行扩容，最后添加元素至指定的索引位置。

• public E remove(int index);
             

  删除指定索引位置的数据，返回删除元素的值。

• public boolean remove(Object o);
             

  删除指定的元素，o可以为null，从数组头部开始配置，删除匹配到的第一个元素。

• public void clear();
             

  将数组所有元素置为null，size=0。

• public boolean addAll(Collection<? extends E> c);
             

功能方法

• public void trimToSize();
             

  调整对象数组elementData的大小与size的值一致，若size==0时将elementData的引用指向EMPTY_ELEMENTDATA。该方法主要用于减少列表的大小，释放存储空间。

• public Object clone();
             

  Object.clone()方法的实现，浅拷贝。

• public Object[] toArray();
             

  返回该列表元素的一个新数组，注意同样是浅拷贝。

• public <T> T[] toArray(T[] a);
             

  将列表中元素复制到数组a中。

  注意：当a.length<list.size时，原数组不会有任何变化，a.length=list.size时，原数组元素和列表中元素一致，a.length>list.size, a[0]~a[size-1]为列表中元素，a[size]置为null。

• public boolean addAll(Collection<? extends E> c);
             

  将指定集合添加至数组末尾。

• public boolean addAll(int index, Collection<? extends E> c);
             

  将指定集合添加至指定索引处。

• public boolean removeAll(Collection<?> c);
             

  将既存在原列表中又存在集合c中的元素移除出列表，即两集合的差集。

• public boolean retainAll(Collection<?> c);
             

  将既存在原列表中又存在集合c中的元素保留，即两集合的交集。

• public List<E> subList(int fromIndex, int toIndex);
             

  根据指定的索引返回一个新的列表。

  注意：该列表不是ArryaList，而是ArrayList的一个内部类SubList！

迭代器相关方法

• public ListIterator<E> listIterator(int index);
             

  从指定索引处返回迭代器ListItr

• public ListIterator<E> listIterator();
             

  从数组起始处返回迭代器ListItr

• public Iterator<E> iterator();
             

  返回迭代器Itr

三.注意事项

1. EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA

   ArryaList的无参构造函数会默认elementData为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，在扩容时若需求大小小于DEFAULT_CAPACITY（10）时，扩容为10，防止在列表小的时候频繁扩容。

2. ArrayList支持序列化为什么elementData被transient修饰？

   在writeObject和readObject方法中进行了处理，只序列化实际存储的元素和size，而不是整个elementData数组。因为elementData数组的大小比size大，不需要序列化大于size的这部分数组。

3. 迭代器ListItr和Itr的区别