上篇我们分析了Java集合的总体类图，下面我们接着来具体探究一下相关的源码。
Collection 简介
Collection 的定义
public interface Collection<E> extends Iterable<E>{}
Collection是一个接口，是高度抽象的集合，其包含了集合的基本操作，如添加，删除，遍历，是否为空，集合转为数组，集合大小，集合之间的合并。
其API如下：
// Collection的API abstract boolean add(E object) //添加元素 abstract boolean addAll(Collection<? extends E> collection) //添加集合 abstract void clear() //删除元素 abstract boolean contains(Object object) //是否包含特定元素 abstract boolean containsAll(Collection<?> collection) //是否包含某个集合 abstract boolean equals(Object object) // abstract int hashCode() //获取集合的hashCode值 abstract boolean isEmpty() //判断集合是否为空 abstract Iterator<E> iterator() //获取集合的迭代器 abstract boolean remove(Object object) //移除元素 abstract boolean removeAll(Collection<?> collection) abstract boolean retainAll(Collection<?> collection) abstract int size() //获取集合的大小 abstract <T> T[] toArray(T[] array) //集合转化成数组 abstract Object[] toArray() //集合转化成数组
List 简介
List的定义
public interface List<E> extends Collection<E>{}
List 是一个继承于Collection的接口，即List是集合中的一种接口。所以，Collection 接口有的方法List中也有。
List 是一个有序队列，集合的初始索引是0，以后每增加一个元素索引+1。List中允许有重复元素。
其增加的API如下：(与Collection相同的API不重复列出)
abstract void add(int location, E object) //在指定位置添加元素 abstract boolean addAll(int location, Collection<? extends E> collection) //在指定位置添加集合 abstract E get(int location) //获取指定位置的元素 abstract int indexOf(Object object)//获取元素的索引值 abstract int lastIndexOf(Object object) abstract ListIterator<E> listIterator(int location) abstract ListIterator<E> listIterator() abstract E remove(int location) //移除指定位置的元素 abstract E set(int location, E object) abstract List<E> subList(int start, int end) //获取子集合
Set 简介
Set的定义
public interface Set<E> extends Collection<E>{}
Set是一个继承于Collection的接口，即List是集合中的一种接口。 不允许有重复元素。其API与Collection的API完全一样。再次不再赘述。
Queue 简介
AbstractCollection
AbstractCollection的定义是
public abstract class AbstractCollection<E> implements Collection<E>{}
AbstractCollection是一个实现了Collection的抽象类，其实现了Collection中除了iterator和size方法之外的方法。所以，继承与AbstractCollection的其他实现类，只需要实现AbstractCollection类没有实现的方法以及按照需求重写相关方法。
public abstract Iterator<E> iterator(); public abstract int size();
具体分析下AbstractCollection类下的相关方法的实现。
public boolean isEmpty() { return size() == 0; } //检查集合是否包含特定元素 public boolean contains(Object o) { Iterator<E> it = iterator(); if (o==null) { //任何非空集合都包含null while (it.hasNext()) if (it.next()==null) return true; } else { while (it.hasNext()) if (o.equals(it.next())) return true; } return false; } //将集合转化成数组 public Object[] toArray() { // Estimate size of array; be prepared to see more or fewer elements Object[] r = new Object[size()]; //定义一个与集合等大的数组 Iterator<E> it = iterator(); //循环将集合中的元素copy到数组r中 for (int i = 0; i < r.length; i++) { if (! it.hasNext()) // fewer elements than expected return Arrays.copyOf(r, i); r[i] = it.next(); } return it.hasNext() ? finishToArray(r, it) : r; } private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; private static <T> T[] finishToArray(T[] r, Iterator<?> it) { int i = r.length; while (it.hasNext()) { int cap = r.length; if (i == cap) { int newCap = cap + (cap >> 1) + 1; // overflow-conscious code if (newCap - MAX_ARRAY_SIZE > 0) newCap = hugeCapacity(cap + 1); r = Arrays.copyOf(r, newCap); } r[i++] = (T)it.next(); } // trim if overallocated return (i == r.length) ? r : Arrays.copyOf(r, i); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError ("Required array size too large"); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } public <T> T[] toArray(T[] a) { // Estimate size of array; be prepared to see more or fewer elements int size = size(); T[] r = a.length >= size ? a : (T[])java.lang.reflect.Array .newInstance(a.getClass().getComponentType(), size); Iterator<E> it = iterator(); for (int i = 0; i < r.length; i++) { if (! it.hasNext()) { // fewer elements than expected if (a == r) { r[i] = null; // null-terminate } else if (a.length < i) { return Arrays.copyOf(r, i); } else { System.arraycopy(r, 0, a, 0, i); if (a.length > i) { a[i] = null; } } return a; } r[i] = (T)it.next(); } // more elements than expected return it.hasNext() ? finishToArray(r, it) : r; } // Modification Operations public boolean add(E e) { throw new UnsupportedOperationException(); } //删除元素o public boolean remove(Object o) { Iterator<E> it = iterator(); if (o==null) { while (it.hasNext()) { if (it.next()==null) { it.remove(); return true; } } } else { while (it.hasNext()) { if (o.equals(it.next())) { it.remove(); return true; } } } return false; } // Bulk Operations public boolean containsAll(Collection<?> c) { for (Object e : c) if (!contains(e)) return false; return true; } public boolean addAll(Collection<? extends E> c) { boolean modified = false; for (E e : c) if (add(e)) modified = true; return modified; } //删除集合c中所有元素（如果存在的话） public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); boolean modified = false; Iterator<?> it = iterator(); while (it.hasNext()) { if (c.contains(it.next())) { it.remove(); modified = true; } } return modified; } //删除不在集合c中的所有元素（如果存在的话） public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); boolean modified = false; Iterator<E> it = iterator(); while (it.hasNext()) { if (!c.contains(it.next())) { it.remove(); modified = true; } } return modified; } // 清空 public void clear() { Iterator<E> it = iterator(); while (it.hasNext()) { it.next(); it.remove(); } } // String conversion // 将List 转成[String] biao'shi public String toString() { Iterator<E> it = iterator(); if (! it.hasNext()) return "[]"; StringBuilder sb = new StringBuilder(); sb.append('['); for (;;) { E e = it.next(); sb.append(e == this ? "(this Collection)" : e); if (! it.hasNext()) return sb.append(']').toString(); sb.append(',').append(' '); } }
AbstractList
AbstractList的定义
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>{}
从定义看出AbstractList继承了AbstractCollection类。实现了List接口。与AbstractCollection类相比其实现了iterator方法。
AbstractList部分源码分析
// Search Operations //如果找到则返回该元素的前一个索引值，没有就返回-1 public int indexOf(Object o) { ListIterator<E> it = listIterator(); if (o==null) { while (it.hasNext()) if (it.next()==null) return it.previousIndex(); } else { while (it.hasNext()) if (o.equals(it.next())) return it.previousIndex(); } return -1; } //如果找到则返回该元素的后一个索引值，没有就返回-1 public int lastIndexOf(Object o) { ListIterator<E> it = listIterator(size()); if (o==null) { while (it.hasPrevious()) if (it.previous()==null) return it.nextIndex(); } else { while (it.hasPrevious()) if (o.equals(it.previous())) return it.nextIndex(); } return -1; } // Bulk Operations //清除集合中的元素 public void clear() { removeRange(0, size()); } public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); //检查索引值是否合法 boolean modified = false; for (E e : c) { add(index++, e); modified = true; } return modified; } private void rangeCheckForAdd(int index) { if (index < 0 || index > size()) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } protected void removeRange(int fromIndex, int toIndex) { ListIterator<E> it = listIterator(fromIndex); for (int i=0, n=toIndex-fromIndex; i<n; i++) { it.next(); it.remove(); } } -------------------------------------------------------------------------------- public Iterator<E> iterator() { return new Itr(); } public ListIterator<E> listIterator() { return listIterator(0); } public ListIterator<E> listIterator(final int index) { rangeCheckForAdd(index); return new ListItr(index); } private class Itr implements Iterator<E> { /** * Index of element to be returned by subsequent call to next. */ int cursor = 0; /** * Index of element returned by most recent call to next or * previous. Reset to -1 if this element is deleted by a call * to remove. */ int lastRet = -1; /** * The modCount value that the iterator believes that the backing * List should have. If this expectation is violated, the iterator * has detected concurrent modification.（源代码的注释） * 译：iterator 每次遍历都会检测modCount的值是否与List应有的长度相等，如果不相等的话，则会抛出一个ConcurrentModificationException的异常 这种场景常见于多线程的情况下。当一个线程正在遍历集合list时，如果在其中另外一个线程删除了list中的某个元素，则会出现该异常 */ int expectedModCount = modCount; public boolean hasNext() { return cursor != size(); } public E next() { checkForComodification(); try { int i = cursor; E next = get(i); lastRet = i; cursor = i + 1; return next; } catch (IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); } } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { AbstractList.this.remove(lastRet); if (lastRet < cursor) cursor--; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException e) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } private class ListItr extends Itr implements ListIterator<E> { ListItr(int index) { cursor = index; } public boolean hasPrevious() { return cursor != 0; } public E previous() { checkForComodification(); try { int i = cursor - 1; E previous = get(i); lastRet = cursor = i; return previous; } catch (IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); } } public int nextIndex() { return cursor; } public int previousIndex() { return cursor-1; } public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { AbstractList.this.set(lastRet, e); expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void add(E e) { checkForComodification(); try { int i = cursor; AbstractList.this.add(i, e); lastRet = -1; cursor = i + 1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } } -------------------------------------------------------------------------------- // 获取List的子集subList，指定开始索引和结束索引 public List<E> subList(int fromIndex, int toIndex) { return (this instanceof RandomAccess ? new RandomAccessSubList<>(this, fromIndex, toIndex) : new SubList<>(this, fromIndex, toIndex)); } class SubList<E> extends AbstractList<E> { private final AbstractList<E> l; private final int offset; private int size; /** 从`SubList`的构造器我们可以看出，其并不是返回一个真正的子集，还是原有的集合List，只是偏移量改成了fromIndex，大小改成了toIndex - fromIndex，所以对子集增加，删除元素会直接作用域原有的List*/ SubList(AbstractList<E> list, int fromIndex, int toIndex) { if (fromIndex < 0) throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); if (toIndex > list.size()) throw new IndexOutOfBoundsException("toIndex = " + toIndex); if (fromIndex > toIndex) throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); l = list; offset = fromIndex; size = toIndex - fromIndex; this.modCount = l.modCount; } public E set(int index, E element) { rangeCheck(index); checkForComodification(); return l.set(index+offset, element); } public E get(int index) { rangeCheck(index); checkForComodification(); return l.get(index+offset); } public int size() { checkForComodification(); return size; } public void add(int index, E element) { rangeCheckForAdd(index); checkForComodification(); l.add(index+offset, element); this.modCount = l.modCount; size++; } public E remove(int index) { rangeCheck(index); checkForComodification(); E result = l.remove(index+offset); this.modCount = l.modCount; size--; return result; } protected void removeRange(int fromIndex, int toIndex) { checkForComodification(); l.removeRange(fromIndex+offset, toIndex+offset); this.modCount = l.modCount; size -= (toIndex-fromIndex); } public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); int cSize = c.size(); if (cSize==0) return false; checkForComodification(); l.addAll(offset+index, c); this.modCount = l.modCount; size += cSize; return true; } public Iterator<E> iterator() { return listIterator(); } public ListIterator<E> listIterator(final int index) { checkForComodification(); rangeCheckForAdd(index); return new ListIterator<E>() { private final ListIterator<E> i = l.listIterator(index+offset); public boolean hasNext() { return nextIndex() < size; } public E next() { if (hasNext()) return i.next(); else throw new NoSuchElementException(); } public boolean hasPrevious() { return previousIndex() >= 0; } public E previous() { if (hasPrevious()) return i.previous(); else throw new NoSuchElementException(); } public int nextIndex() { return i.nextIndex() - offset; } public int previousIndex() { return i.previousIndex() - offset; } public void remove() { i.remove(); SubList.this.modCount = l.modCount; size--; } public void set(E e) { i.set(e); } public void add(E e) { i.add(e); SubList.this.modCount = l.modCount; size++; } }; } public List<E> subList(int fromIndex, int toIndex) { return new SubList<>(this, fromIndex, toIndex); } private void rangeCheck(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private void rangeCheckForAdd(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } private void checkForComodification() { if (this.modCount != l.modCount) throw new ConcurrentModificationException(); } }
从上述源码中，我理解的两条重要信息是：
1. AbstractList是非线程安全的，当一个线程在遍历List时，另外一个线程对该List进行修改则会直接抛出ConcurrentModificationException的异常
2. 从SubList的构造器我们可以看出，其并不是返回一个真正的子集，还是原有的集合List，只是偏移量改成了fromIndex，大小改成了toIndex - fromIndex，所以对子集增加，删除元素会直接作用域原有的List
AbstractSet
AbstractSet的定义是
public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E>{}
AbstractSet的部分源码分析
protected AbstractSet() { } // Comparison and hashing public boolean equals(Object o) { if (o == this) return true; if (!(o instanceof Set)) return false; Collection<?> c = (Collection<?>) o; if (c.size() != size()) return false; try { return containsAll(c); } catch (ClassCastException unused) { return false; } catch (NullPointerException unused) { return false; } } public int hashCode() { int h = 0; Iterator<E> i = iterator(); while (i.hasNext()) { E obj = i.next(); if (obj != null) h += obj.hashCode(); } return h; } public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); boolean modified = false; if (size() > c.size()) { for (Iterator<?> i = c.iterator(); i.hasNext(); ) modified |= remove(i.next()); } else { for (Iterator<?> i = iterator(); i.hasNext(); ) { if (c.contains(i.next())) { i.remove(); modified = true; } } } return modified; }
从上述源码中可以看出AbstractSet 只是重写了AbstractCollection中的removeAll方法。
Iterator 简介
Iterator的定义
public interface Iterator<E>{}
Iterator是一个接口，Iterator 是Collection分支下的集合的最重要的遍历工具，所有的List和Set都需要依赖它。
从API中看出，其包含的方法有，是否有下一个元素，获取下一个元素，删除当前元素。
Iterator遍历集合时采取的是 fast-fail 机制，即，当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了，那么线程A访问集合时，就会抛出CurrentModificationException异常，产生fail-fast事件。
Iterator的API是
abstract boolean hasNext() abstract E next() abstract void remove()
ListIterator 简介
ListIterator的定义
public interface ListIterator<E> extends Iterator<E> {}
ListIterator是一个继承Iterator的接口，它是队列迭代器。专门用于遍历List，能提供向前和向后遍历。相比于Iterator，它新增了添加、是否存在上一个元素、获取上一个元素等API接口：
// 继承于Iterator的接口 abstract boolean hasNext() abstract E next() abstract void remove() // 新增API接口 abstract void add(E object) abstract boolean hasPrevious() abstract int nextIndex() abstract E previous() abstract int previousIndex() abstract void set(E object)
