【ArrayList】JDK1.8源码详细注释 以及如何实现线程安全的链表

ArrayList(JDK8)

• ArrayList有四个内部类，成员内部类Itr，成员内部类ListItr，静态内部类SubList，ArrayListSpliterator（暂时用不到）
• Itr是Iterator的实现类，支持正向遍历，ArrayList的iterator方法返回一个Itr对象
• ListItr是ListIterator的实现类，支持双向遍历，ArrayList的listIterator方法返回一个ListIterator类对象

Itr

1. 增强 for 遍历数组时, 被编译成普通 for 循环, 增强 for 遍历集合时, 被编译成使用 Iterator; 无论是数组还是集合, 只用增强 for 都无法修改原本引用的指向;

2. 单步迭代中, 不允许多次调用迭代器的 remove 方法; 逻辑上来说, 你迭代一次, 当然只能判断当前的对象是不是需要被删除, 干嘛要多次删除? 其次, 这样也能让迭代器的代码逻辑更简洁, 避免很多边界条件的判断, 也能避免很多潜在的错误;

3. 如果要通过循环删除 List 中的所有元素, 可以这样做

   for(int i = 0; i < list.size(); i++){list.remove(i);i--;
   }// 或者
   // removeIf 的本质就是迭代器实现的;
   list.removeIf(i->true);// 或者通过迭代器;
   

// ArrayList的
public Iterator<E> iterator() {return new Itr();
}
// 作为ArrayList的成员内部类
private class Itr implements Iterator<E> {int cursor;       // index of next element to returnint lastRet = -1; // index of last element returned; -1 if no such// 显式赋值，让自己的expectedModCount = ArrayList.this.modCount// 在内部类的成员方法和构造函数中，隐含了ArrayList.this和this传参int expectedModCount = modCount;// prevent creating a synthetic constructorItr() {}public boolean hasNext() {// ArrayList.this.sizereturn cursor != size;}@SuppressWarnings("unchecked")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];}public void remove() {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {// 局部内部类对象依附于外围类对象而存在，持有外围类对象指针ArrayList.this// 这里修改了所依附的外围类对象arrayList的modCountArrayList.this.remove(lastRet);// 删除时cursor要往前移动一位cursor = lastRet;// 防止连续删除lastRet = -1;// 更新自己的modCountexpectedModCount = modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}
}

sublist

public List<E> subList(int fromIndex, int toIndex) {subListRangeCheck(fromIndex, toIndex, size);return new SubList<>(this, fromIndex, toIndex);
}// 本身也实现了AbstracList，有add，remove等等常见方法，不再列出
// 但是要记住它的add，remove等等方法修改的都是源ArrayList！
// 重点看iterator()方法返回的匿名内部类对象
private static class SubList<E> extends AbstractList<E> implements RandomAccess {// 如果是从ArrayList投影来的，让root指向源集合private final ArrayList<E> root;// 如果是Sublist又subList来的，让parent = 源Sublist, root = parent.root// 从SubList再截取时，行为比较特殊，会继续向上去找源ArrayList，迭代器依旧在ArrayList上进行，像        双亲委派模型private final SubList<E> parent;// 在源中的偏移量，例如从ArrayList第二个元素截取，offset = 1private final int offset;// sublist的长度private int size;// 从ArrayList截取Sublistpublic SubList(ArrayList<E> root, int fromIndex, int toIndex) {this.root = root;this.parent = null;this.offset = fromIndex;this.size = toIndex - fromIndex;// this.modCount是从AbstractList继承来的this.modCount = root.modCount;}// Sublist自己可以继续sublistpublic List<E> subList(int fromIndex, int toIndex) {subListRangeCheck(fromIndex, toIndex, size);return new SubList<>(this, fromIndex, toIndex);}// 从Sublist截取private SubList(SubList<E> parent, int fromIndex, int toIndex) {// 无论subList几次，root始终指向源ArrayListthis.root = parent.root;this.parent = parent;// 记录的是相对于源ArrayList的偏移量this.offset = parent.offset + fromIndex;this.size = toIndex - fromIndex;// this.modCount = 上级modCount = 。。。最终 = 源ArrayList的modCount this.modCount = parent.modCount;}// SubList的removepublic E remove(int index) {Objects.checkIndex(index, size);checkForComodification();E result = root.remove(offset + index);// 更新自己的modCount和root的一样， 自己的size-1updateSizeAndModCount(-1);return result;}// Sublist无论是iterator还是listIterator，返回的都是listIterator子类对象public Iterator<E> iterator() {// 调用从AbstractList继承的listItoreator// 其实现是调用listIterator(0)return listIterator();}// index = 0public ListIterator<E> listIterator(int index) {checkForComodification();rangeCheckForAdd(index);// 是Sublist的局部内部类// 只列出了next方法，其余的方法大同小异，最终也都是在原ArrayList上操作return new ListIterator<E>() {	int cursor = index;int lastRet = -1;// 也就是源ArrayList的modCountint expectedModCount = SubList.this.modCount;public boolean hasNext() {return cursor != SubList.this.size;}@SuppressWarnings("unchecked")public E next() {// 检查并发修改异常时也是和ArrayList对比checkForComodification();int i = cursor;if (i >= SubList.this.size)throw new NoSuchElementException();Object[] elementData = root.elementData;if (offset + i >= elementData.length)throw new ConcurrentModificationException();cursor = i + 1;// 真正遍历时实际上是用 offset + cursor 去遍历源集合return (E) elementData[offset + (lastRet = i)];}public void remove() {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {// 调用外围类Sublist的remove方法，最终还是修改了原ArrayListSubList.this.remove(lastRet);cursor = lastRet;lastRet = -1;expectedModCount = SubList.this.modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}final void checkForComodification() {if (root.modCount != expectedModCount)throw new ConcurrentModificationException();}}; // return匿名内部类对象} // public ListIterator<E> listIterator(int index)
} // Sublist

容量

• add 和 addAll 会检查容量是否够用，即 size 是否已经 ==capacity 或者能否放得下加入的集合，不够的时候才扩容;

• 无论add还是 addAll, 扩容机制都是在需要增长到的容量和原容量1.5倍之间选择大的进行扩容；除了无参构造首次扩容有些特殊, 直接扩容到10 ;

• 如果是无参构造创建的ArrayList，首次添加第一个元素时，扩容到10，如果首次直接使用 addAll 添加集合c，会有特殊判断, 扩容到 max { c.length , 10 }

• 如果是有参构造，指定多少就立即分配多少, 指定 size == 0 时除外

/**
* 首先区分容量capacity(底层数组能放多少)
* 和大小size(集合的逻辑大小，底层数组实际使用了多少)
*/// 默认容量10
private static final int DEFAULT_CAPACITY = 10;// 
private static final Object[] EMPTY_ELEMENTDATA = {};// 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};transient Object[] elementData;private int size;// 1. 无参构造时，使用空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA作为底层数组，初次扩容时作为标记
//		初始容量实际上为0
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}// 2. 有参构造时，如果传入的容量为0，底层使用空数组EMPTY_ELEMENTDATA，初次扩容时和	
//			DEFAULTCAPACITY_EMPTY_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);}
}// 1. 无参构造首次添加元素时elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; size = 0；	
public boolean add(E e) {modCount++;add(e, elementData, size);return true;
}// 1. if 条件满足，调用grow扩容
private void add(E e, Object[] elementData, int s) {if (s == elementData.length)elementData = grow();elementData[s] = e;
}public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();modCount++;int numNew = a.length;if (numNew == 0)return false;Object[] elementData;final int s;// 如果elementData不足以放下所有元素，扩容if (numNew > (elementData = this.elementData).length - (s = size))elementData = grow(s + numNew);System.arraycopy(a, 0, elementData, s, numNew);size = s + numNew;return true;
}// 1. 调用grow(1) 
private Object[] grow() {return grow(size + 1);
}// 1.1 如果是add方法添加单个元素，minCapacity = 1
// 1.2 如果是addAll方法添加集合c，minCapacity = size + c.length
private Object[] grow(int minCapacity) {// 1. oldCapacity = 0int oldCapacity = elementData.length;// 2. 首次添加单个元素，minCapacity = 1，oldCapacity = 0； minCapacity是指总容量最少为多少//		minGrowth = 1； old/2 = 0； 最终增长1//		再加一个元素， minGrowth=1；old/2 = 0， 增长1，size=2// 		再加，只要是add(E e)，minGrowth就是1， old/2 = 1； 增长1， size = 3//		再加，加1； 再加，加2， 直到第五次添加元素， 开始加 > 1//	而如果添加多个元素，要对比添加元素个数和原本容量的0.5倍哪个更大if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity = ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* minimum growth */oldCapacity >> 1           /* preferred growth */);return elementData = Arrays.copyOf(elementData, newCapacity);} else {// 1. 在minCapacity 和 DEFAULT_CAPACITY(10) 之间选大的那个// 		这里只会在无参构造的ArrayList首次扩容的时候执行到return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}
}// ArraysSupport类
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {// 在最小需要增量和0.5倍原容量中选择大的那个，加上原容量，作为新容量的大小// 例如原容量为10，addAll添加了一个长度为6的集合，那么传入的oldLength = 10；// minGrowth = 6，此方法返回 10 + 6int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflowif (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {return prefLength;} else {// put code cold in a separate methodreturn hugeLength(oldLength, minGrowth);}
}// 可以手动调用ensureCapacity来无条件扩容，参数是总容量，不是要扩展的容量
// 手动调用时，如果给出的总容量小于现有容量，do nothing
// 如果当前是刚用无参构造构造出的ArrayList还没有扩容过，而且给出的总容量小于等于10的话，不会扩容
// 因为多此一举，反正等到添加第一个元素的时候就会扩容到10
public void ensureCapacity(int minCapacity) {if (minCapacity > elementData.length&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA&& minCapacity <= DEFAULT_CAPACITY)) {modCount++;grow(minCapacity);}
}

线程安全的 List

一 自己加 Synchronized 进行控制

二 CopyOnWriteArrayList

写时复制的 List; 非常适合读多写少又要求线程安全的场景;

其基本工作原理是，当对列表进行写操作（如添加、删除、更新元素）时，它会 new 数组 + System.ArrayCopy , 创建一个底层数组的副本，然后在新数组上执行写操作。修改完成后，用副本替换掉原有的数组。

其底层数组由 volatile 修饰, 保证可见性;

CopyOnWriteArrayList 的迭代器在迭代的时候，如果数组内容被修改了，CopyOnWriteArrayList 不会报 ConcurrentModificationException 的异常，因为迭代器使用的依然是旧数组，只不过迭代的内容可能已经过时了。迭代器并不支持 remove 方法;

原理是: 创建 COWIterator 的时候, 会将底层数组的引用传进入, 这样, 即使有其他线程更换了底层数组, 也不会影响到当前的迭代器;

remove 方法还是会加锁, 使用的是 ReentrantLock, 整个 list 对象就一个;

三 Collections.synchronizedList()

对 get set add 等等这些方法都加了 synchronized, 和我们自己控制, 没啥区别; synchronized 作用的对象是链表本身;

public E get(int index) {synchronized (mutex) {return list.get(index);}
}

需要注意, 拿到 Iterator 进行遍历的时候, 必须手动保证线程安全, 比如可以用 synchronized(list);

不然还是会并发修改异常;

synchronized (list) {Iterator i = list.iterator(); // Must be in synchronized blockwhile (i.hasNext())foo(i.next());
}