本文共 8006 字，大约阅读时间需要 26 分钟。

【转载】

概述

ArrayList的基本特点

• ArrayList 底层是一个动态扩容的数组结构
• 允许存放（不止一个） null 元素
• 允许存放重复数据，存储顺序按照元素的添加顺序
• ArrayList 并不是一个线程安全的集合。如果集合的增删操作需要保证线程的安全性，可以考虑使用 CopyOnWriteArrayList 或者使用 collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类.

继承关系

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

ArrayList 继承自 AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable 接口(4接口1父类)。

构造方法

• 无参构造方法
  容量为0,调用add方法后扩为10
• 指定初始容量的构造方法
  如果事先知道数据的大小,就可以构造指定容量的list,后面不需要扩容,会节省很多开销(数组拷贝),
  避免浪费内存空间(每次扩容为原先的1.5倍，容量越大扩容越大，浪费可能越多)
• 使用另一个集合 Collection 的构造方法
  这里注意代码elementData.getClass() != Object[].class的判断,ArrayList的elementData是Object[]类型,而传入的collection对象可能不是(如Lists.asList(“a”,“b”)的toArray()结果是String[]),在赋值时,就会做判断,向上升级.

transient Object[] elementData; // non-private to simplify nested class access    ...    public ArrayList(Collection
    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;        }    }...                    public Object[] toArray() {
           return Arrays.copyOf(elementData, size);    }

添加元素,扩容机制

扩容

//add(E e)方法内，会先进行扩容检查private void ensureCapacityInternal(int minCapacity) {
       //如果是无参构造方法构造的的集合，第一次添加元素的时候会满足这个条件 minCapacity 将会被赋值为 10   if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);   }    // 将 size + 1 或 10 传入 ensureExplicitCapacity 进行扩容判断   ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {
     //操作数加 1 用于保证并发访问   modCount++;  // 如果 当前数组的长度比添加元素后所需的长度要小则进行扩容   if (minCapacity - elementData.length > 0)      grow(minCapacity);}

上面的源码主要做了扩容前的判断操作.

/** * 集合的最大长度 Integer.MAX_VALUE - 8 是为了减少出错的几率 Integer 最大值已经很大了 */private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;/** * 增加容量，以确保它至少能容纳最小容量参数指定的元素个数。 * @param 满足条件的最小容量 */private void grow(int minCapacity) {
     //获取当前 elementData 的大小，也就是 List 中当前的容量   int oldCapacity = elementData.length;   //oldCapacity >> 1 等价于 oldCapacity / 2  所以新容量为当前容量的 1.5 倍   int newCapacity = oldCapacity + (oldCapacity >> 1);   //如果扩大1.5倍后仍旧比 minCapacity 小那么直接等于 minCapacity   if (newCapacity - minCapacity < 0)       newCapacity = minCapacity;    //如果新数组大小比  MAX_ARRAY_SIZE 就需要进一步比较 minCapacity 和 MAX_ARRAY_SIZE 的大小   if (newCapacity - MAX_ARRAY_SIZE > 0)       newCapacity = hugeCapacity(minCapacity);   // minCapacity通常接近 size 大小   //使用 Arrays.copyOf 构建一个长度为 newCapacity 新数组 并将 elementData 指向新数组   elementData = Arrays.copyOf(elementData, newCapacity);}/** * 比较 minCapacity 与 Integer.MAX_VALUE - 8 的大小如果大则放弃-8的设定，设置为 Integer.MAX_VALUE  */private static int hugeCapacity(int minCapacity) {
      if (minCapacity < 0) // overflow       throw new OutOfMemoryError();   return (minCapacity > MAX_ARRAY_SIZE) ?       Integer.MAX_VALUE :       MAX_ARRAY_SIZE;}

扩容过程:

• 每次扩为原先大小的1.5倍.如果放不下,就以实际需要的空间大小为准.
• 将原来元素拷贝到一个扩容后数组大小的长度新数组中。所以 ArrayList 的扩容其实是相对来说比较消耗性能的。

末尾添加

先调用ensureCapacityInternal来判断是否需要进行数组扩容,然后将元素添加到数组末尾：elementData[size++] = e;size加一

指定位置添加

先扩容检查,然后调用System#arraycopy方法拷贝数据,再添加新元素.size加一

批量添加

…

删除元素

根据下标删除

主要是调用System#arraycopy方法进行复制（相当于前移）,然后将最后一位赋值为null(以便垃圾回收),size减一

删除指定元素

/*** 删除指定元素，如果它存在则反会 true，如果不存在返回 false。* 更准确地说是删除集合中第一出现 o 元素位置的元素 ，* 也就是说只会删除一个，并且如果有重复的话，只会删除第一个次出现的位置。*/public boolean remove(Object o) {
       // 如果元素为空则只需判断 == 也就是内存地址   if (o == null) {
          for (int index = 0; index < size; index++)           if (elementData[index] == null) {
                   //得到第一个等于 null 的元素角标并移除该元素 返回 ture               fastRemove(index);               return true;           }   } else {
           // 如果元素不为空则需要用 equals 判断。       for (int index = 0; index < size; index++)           if (o.equals(elementData[index])) {
                   //得到第一个等于 o 的元素角标并移除该元素 返回 ture               fastRemove(index);               return true;           }   }   return false;}//移除元素的逻辑和 remve(Index)一样 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}

说明:

• 根据元素删除只会删除匹配的第一次出现的元素,后面的重复的元素不删除
• 元素为null和不为null判断逻辑不一样.不为null时使用equal判断是不是同一个对象.
• 删除是使用System.arraycopy拷贝前移,然后最后一位置空,逻辑和 remve(Index)一样

批量移除/保留

…

改查

修改某下标元素,查找某下标元素,查询元素的下标或者list是否包含某元素.都是与内部数组有关的简单操作.

遍历

迭代器

public Iterator
   
     iterator() {
           return new Itr();}
   

问题: 为什么迭代器删除是安全的???

---

int cursor; // 对照 hasNext 方法 cursor 应理解为下个调用 next 返回的元素 初始为 0   int lastRet = -1; // 上一个返回的角标   int expectedModCount = modCount;//初始化的时候将其赋值为当前集合中的操作数   @SuppressWarnings("unchecked")   public E next() {
           // 验证期望的操作数与当前集合中的操作数是否相同 如果不同将会抛出异常       checkForComodification();       // 如果迭代器的索引已经大于集合中元素的个数则抛出异常，这里不抛出角标越界       int i = cursor;       if (i >= size)           throw new NoSuchElementException();                  Object[] elementData = ArrayList.this.elementData;       // 由于多线程的问题这里再次判断是否越界，如果有异步线程修改了List（增删）这里就可能产生异常       if (i >= elementData.length)           throw new ConcurrentModificationException();       // cursor 移动       cursor = i + 1;       //最终返回 集合中对应位置的元素，并将 lastRet 赋值为已经访问的元素的下标       return (E) elementData[lastRet = i];   }      final void checkForComodification() {
          if (modCount != expectedModCount)           throw new ConcurrentModificationException();   }

checkForComodification方法检验在迭代期间是否有其他线程对元素做了改动.

// 实质调用了集合的 remove 方法移除元素   public void remove() {
           // 比如操作者没有调用 next 方法就调用了 remove 操作，lastRet 等于 -1的时候抛异常       if (lastRet < 0)           throw new IllegalStateException();                   //检查操作数       checkForComodification();           try {
               //移除上次调用 next 访问的元素           ArrayList.this.remove(lastRet);           // 集合中少了一个元素，所以 cursor 向前移动一个位置（调用 next 时候 cursor = lastRet + 1）           cursor = lastRet;           //删除元素后赋值-1，确保先前 remove 时候的判断           lastRet = -1;           //修改操作数期望值， modCount 在调用集合的 remove 的时候被修改过了。           expectedModCount = modCount;       } catch (IndexOutOfBoundsException ex) {
               // 集合的 remove 会有可能抛出 rangeCheck 异常，catch 掉统一抛出 ConcurrentModificationException            throw new ConcurrentModificationException();       }   }

注意:

• 1.迭代器的remove方法,内部也是调用ArrayList#remove处理的.

• 2.删除完后,游标cursor回退一个位置

• 3.游标的remove()操作,一次循环只能调用一次

• 4.调用remove后modCod+1, expectedModCount 要设置为和modCod相等

• 5.lastRet重置为-1

  根据第2点可知,迭代器的删除方法,会在迭代器对象内维护一个游标,该游标是动态变化的.只要迭代器遍历期间没有线程改动list,在循环中进行操作都没有问题.

  而对list使用for循环,并在循环中使用ArrayList#remove方法,就会有问题.

  第3点,可以根据代码看出:

if (lastRet < 0)                throw new IllegalStateException();

next方法会将当前的游标位置赋值给lastRet:

public E next() {
               checkForComodification();            int i = cursor;            if (i >= size)                throw new NoSuchElementException();            Object[] elementData = ArrayList.this.elementData;            if (i >= elementData.length)                throw new ConcurrentModificationException();            cursor = i + 1;            return (E) elementData[lastRet = i];        }

ListIterator 迭代器

ListIterator 继承了Itr,因此不但可以向前遍,还可以向后遍历.

安全性 modCount与expectedModCount

ArrayList 并不是一个线程安全的集合。如果集合的增删操作需要保证线程的安全性，可以考虑使用 CopyOnWriteArrayList 或者使用 collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类.(CopyOnWriteArrayList使用的是可重入锁,collections.synchronizedList(List l)使用synchronized关键字)

虽然不是线程安全的集合.但是在对集合进行操作时.由于有modCount与expectedModCount对比校验,能够很快地判断是否有其他线程对数据进行了修改.

各类增加和删除元素的方法都会导致modCount加1.而在writeObject,forEach,removeIf,replaceAll,sort等方法,Iterator,SubList,ArrayListSeperator等内部类中都会进行校验.

为什么ArrayList是线程不安全的，还要使用modCount对修改进行校验呢？

我的观点是：即使是同一线程内，也可能由于API使用不当，而导致数据问题。（未完）