集合类图.png
上图为Collection的类图，可以看到，实现类都是从Iterable、Collection、Set、List、Queue等接口派生而来，也就是具有以上接口提供的功能与特性。

Iterable

该接口提供了一个for-each循环的能力。

forEach

  1. default void forEach(Consumer<? super T> action) {
  2.     Objects.requireNonNull(action);
  3.     for (T t : this) {
  4.         action.accept(t);
  5.     }
  6. }

对于迭代的每个元素都执行一次action提供的操作，知道所有的元素迭代完成或者抛出异常。

spliterator

  1. default Spliterator<T> spliterator() {
  2.     return Spliterators.spliteratorUnknownSize(iterator(), 0);
  3. }

实现必备
默认实现从迭代器创建一个预绑定拆分器（Spliterator）。拆分器继承iterable迭代器的fail-fast属性。

注意事项
子类需要重新该方法。默认实现返回的spliterator具有较差的拆分功能，不可扩展，并且不会反馈任何spliterator特性。实现类可以提供更好的实现。

iterator

  1. Iterator<T> iterator();

对于类型为T的元素集返回一个迭代器。

ListIterator

  1. public interface ListIterator<E> extends Iterator<E> {
  3. }

专用于List的迭代器，有以下特点：

  1. 可以从任意方向遍历集合；
  2. 在遍历期间可以修改集合；
  3. 获取迭代器当前的位置；

**ListIterator**没有当前元素，其**cursor**始终位于调用**previous()**返回的元素和调用**next()**返回的元素之间。长度为**n**的**List**迭代器有**n+1**个可能的**cursor**位置，例如：

  1.                            Element(0)   Element(1)   Element(2)   ... Element(n-1)
  2.  cursor positions:    ^            ^            ^            ^                  ^

注意：remove() 和 set(Object) 方法并不是根据游标位置定义的；它们被定义为对调用 next() 或 previous() 返回的最后一个元素进行操作。

hasNext

  1. boolean hasNext();

是否还有更多元素

next

  1. E next();

获取下一个元素并移动游标位置

hasPrevious

  1. boolean hasPrevious();

当反向遍历集合时，如果还存在更多元素，则返回true

previous

  1.     /**
  2.      * Returns the previous element in the list and moves the cursor
  3.      * position backwards.  This method may be called repeatedly to
  4.      * iterate through the list backwards, or intermixed with calls to
  5.      * {@link #next} to go back and forth.  (Note that alternating calls
  6.      * to {@code next} and {@code previous} will return the same
  7.      * element repeatedly.)
  8.      *
  9.      * @return the previous element in the list
  10.      * @throws NoSuchElementException if the iteration has no previous
  11.      *         element
  12.      */
  13.     E previous();

nextIndex

  2.     /**
  3.      * Returns the index of the element that would be returned by a
  4.      * subsequent call to {@link #next}. (Returns list size if the list
  5.      * iterator is at the end of the list.)
  6.      *
  7.      * @return the index of the element that would be returned by a
  8.      *         subsequent call to {@code next}, or list size if the list
  9.      *         iterator is at the end of the list
  10.      */
  11.     int nextIndex();

previousIndex

  1.     /**
  2.      * Returns the index of the element that would be returned by a
  3.      * subsequent call to {@link #previous}. (Returns -1 if the list
  4.      * iterator is at the beginning of the list.)
  5.      *
  6.      * @return the index of the element that would be returned by a
  7.      *         subsequent call to {@code previous}, or -1 if the list
  8.      *         iterator is at the beginning of the list
  9.      */
  10.     int previousIndex();

remove

  1.     /**
  2.      * Removes from the list the last element that was returned by {@link
  3.      * #next} or {@link #previous} (optional operation).  This call can
  4.      * only be made once per call to {@code next} or {@code previous}.
  5.      * It can be made only if {@link #add} has not been
  6.      * called after the last call to {@code next} or {@code previous}.
  7.      *
  8.      * @throws UnsupportedOperationException if the {@code remove}
  9.      *         operation is not supported by this list iterator
  10.      * @throws IllegalStateException if neither {@code next} nor
  11.      *         {@code previous} have been called, or {@code remove} or
  12.      *         {@code add} have been called after the last call to
  13.      *         {@code next} or {@code previous}
  14.      */
  15.     void remove();

set

  1.     /**
  2.      * Replaces the last element returned by {@link #next} or
  3.      * {@link #previous} with the specified element (optional operation).
  4.      * This call can be made only if neither {@link #remove} nor {@link
  5.      * #add} have been called after the last call to {@code next} or
  6.      * {@code previous}.
  7.      *
  8.      * @param e the element with which to replace the last element returned by
  9.      *          {@code next} or {@code previous}
  10.      * @throws UnsupportedOperationException if the {@code set} operation
  11.      *         is not supported by this list iterator
  12.      * @throws ClassCastException if the class of the specified element
  13.      *         prevents it from being added to this list
  14.      * @throws IllegalArgumentException if some aspect of the specified
  15.      *         element prevents it from being added to this list
  16.      * @throws IllegalStateException if neither {@code next} nor
  17.      *         {@code previous} have been called, or {@code remove} or
  18.      *         {@code add} have been called after the last call to
  19.      *         {@code next} or {@code previous}
  20.      */
  21.     void set(E e);

add

  1.     /**
  2.      * Inserts the specified element into the list (optional operation).
  3.      * The element is inserted immediately before the element that
  4.      * would be returned by {@link #next}, if any, and after the element
  5.      * that would be returned by {@link #previous}, if any.  (If the
  6.      * list contains no elements, the new element becomes the sole element
  7.      * on the list.)  The new element is inserted before the implicit
  8.      * cursor: a subsequent call to {@code next} would be unaffected, and a
  9.      * subsequent call to {@code previous} would return the new element.
  10.      * (This call increases by one the value that would be returned by a
  11.      * call to {@code nextIndex} or {@code previousIndex}.)
  12.      *
  13.      * @param e the element to insert
  14.      * @throws UnsupportedOperationException if the {@code add} method is
  15.      *         not supported by this list iterator
  16.      * @throws ClassCastException if the class of the specified element
  17.      *         prevents it from being added to this list
  18.      * @throws IllegalArgumentException if some aspect of this element
  19.      *         prevents it from being added to this list
  20.      */
  21.     void add(E e);

Collection

  1. public interface Collection<E> extends Iterable<E> {
  3. }

集合层次结构中的根接口。集合表示一组对象，每个对象称之为元素。有些集合允许元素重复，有些则不允许。有些是有序的，有些是无序的。JDK不提供此接口的任何直接实现，只提供更具体的子接口（如Set和List）的实现。此接口通常用于传递集合，并在需要最大通用性的地方对其进行操作。

所有通用的Collection实现类（通常通过实现Collection的一个子接口）都应提供两个“标准”构造函数：一个void（无参数）构造函数，用于创建空集合；另一个构造函数具有一个Collection类型的参数，它将创建一个新集合，其元素与其参数相同。实际上，后一个构造函数允许用户复制任何集合，从而生成所需实现类型的等效集合。无法强制执行此约定（因为接口不能包含构造函数），但Java平台库中的所有通用集合实现都符合此约定。

此接口中包含的“破坏性”方法（即修改其操作的集合的方法），在该集合不支持该操作时引发UnsupportedOperationException异常。在这种情况，如果该方法调用对集合没有影响，可以（但不是必需）抛出UnsupportedOperationException。例如，对不可修改的集合（unmodifiable）调用addAll方法可能（但不是必需）引发异常。

有些集合对其包含的元素有限制。例如，有些实现禁止空元素，有些实现对其元素的类型有限制。尝试添加不符合条件的元素会引发未检查的异常，通常是NullPointerException或ClassCastException。尝试查询不合格元素的存在可能会引发异常，或者只返回false等。

每个集合决定自己的同步策略。在实现没有更强有力的保证的情况下，未定义的行为可能是由于调用另一个线程正在变异的集合上的任何方法而导致的；这包括直接调用、将集合传递给可能执行调用的方法以及使用现有迭代器检查集合。

集合框架接口中的许多方法都是用**equals**方法定义的。例如，contains(Object o)方法的规范说：“当且仅当此集合至少包含一个元素e，使得（o==null？e==null:o.equals（e））”，该方法返回true。

对于集合直接或间接包含自身的自引用实例，执行集合递归遍历的操作可能会引发异常而失败。但clone()、equals()、hashCode()和toString()方法则不会。

size

  1. int size();

返回集合中的元素数量。如果集合中的元素数量超过Integer.MAX_VALUE，则返回Integer.MAX_VALUE。

Empty

  1. boolean isEmpty();

集合中不包含任何元素则返回true。

contains

  1. boolean contains(Object o);

如果集合中包含了这个特定的元素，则返回true。

集合中至少存在一个元素满足：(o==null ? e==null : o.equals(e))

  • ClassCastException: 该元素的类型与集合内部元素类型不同
  • NullPointException: 该元素为null且集合不能存储null元素

    toArray

    1. Object[] toArray();
    返回一个包含该集合中所有元素的数组。如果此集合保证其迭代器返回元素的顺序，则此方法必须以相同的顺序返回元素。

返回的数组将是“安全的”，因为此集合不维护对它的引用。（换句话说，即使此集合由数组支持，此方法也必须分配新数组）。因此，调用者可以自由地修改返回的数组。

  1. <T> T[] toArray(T[] a);

返回包含此集合中所有元素的数组；返回数组的运行时类型与指定数组的运行时类型相同。如果集合所有元素可以放入指定的数组，则返回该数组。否则，将使用指定数组的运行时类型和此集合的大小分配一个新数组。

如果此集合可以填充到指定的数组，并且有空闲空间（即，数组中的元素多于此集合），则紧跟在集合结束之后的数组中的元素将设置为null。（仅当调用方知道此集合不包含任何null元素时，这个方法才能真正确定此集合的长度）

如果此集合保证其迭代器返回元素的顺序，则此方法必须以相同的顺序返回元素。

与toArray()方法一样，此方法充当基于数组和基于集合的API之间的桥梁。此外，该方法允许对输出数组的运行时类型进行精确控制，并且在某些情况下可以用于节省分配成本。

假设x是只包含字符串的集合。以下代码可用于将集合转储到新分配的字符串数组中：
/

  1. String[] y = x.toArray(new String[0]);

注意，toArray(new Object[0])在功能上与toArray()相同。

ArrayStoreException：指定数组的元素类型不是集合中任意一个元素类型的超类，抛出该异常
NullPointException：指定数组为空，抛出该异常

add

  1. boolean add(E e);

添加元素。如果此集合不允许添加重复的元素，且该元素已经包含在此集合中，返回false。
**
支持此操作的集合可能会对可添加到此集合的元素施加限制。特别是，一些集合将拒绝添加null元素，而其他集合将对可能添加的元素类型施加限制。集合类应在其文档中明确指定对可以添加哪些元素的任何限制。

如果集合拒绝添加特定元素的原因不是因为它已经包含该元素，那么它必须抛出异常（而不是返回false）。这保留了在该调用返回后集合始终包含指定元素的不变量。

UnsupportedOperationException：该集合不支持添加操作
ClassCastException：指定元素的类型不能添加到该集合（元素类型不一致）
NullPointException：指定元素为null且该集合不支持添加null元素
IllegalArgumentException：因为指定元素的一些属性导致其不能添加到该集合
IllegalStateException：因为插入操作限制导致该元素不能添加到集合

remove

  1. boolean remove(Object o);

移除元素

ClassCastException：指定元素的类型不能添加到该集合（元素类型不一致）
NullPointException：指定元素为null且该集合不支持null元素
UnsupportedOperationException：该集合不支持添加操作

containsAll

  1. boolean containsAll(Collection<?> c);

集合中包含了指定集合c中的所有元素。

ClassCastException：两个集合中的元素至少有一个类型不兼容
NullPointException：指定集合不支持添加null元素且该集合中至少包含一个null元素，或者指定集合为null。

addAll

  1. boolean addAll(Collection<? extends E> c);

将指定集合中的所有元素添加到此集合。如果在操作进行过程中修改了指定的集合，则此操作的行为未定义。（这意味着指定的集合就是当前集合，并且此集合不为空，则此调用的行为未定义。）

UnsupportedOperationException： 该集合不支持该操作
ClassCastException： 指定集合中某个元素的类型不能添加到该集合（元素类型不一致）
NullPointException： 指定集合不支持添加null元素且该集合中至少包含一个null元素，或者指定集合为 null。
IllegalArgumentException： 指定集合中某个元素的一些属性导致其不能添加到该集合
IllegalStateException： 因为插入操作限制导致该集合中不是所有元素都能添加到集合

removeAll

  1. boolean removeAll(Collection<?> c);

移除该集合中所有同样存在于指定集合c中的元素。该操作结束之后，两个集合中不会再存在相同元素。

removeIf

  1.     default boolean removeIf(Predicate<? super E> filter) {
  2.         Objects.requireNonNull(filter);
  3.         boolean removed = false;
  4.         final Iterator<E> each = iterator();
  5.         while (each.hasNext()) {
  6.             if (filter.test(each.next())) {
  7.                 each.remove();
  8.                 removed = true;
  9.             }
  10.         }
  11.         return removed;
  12.     }

删除此集合中满足给定条件的所有元素。迭代过程中或指定条件引发的错误或运行时异常将转发给调用方。

NullPointException： filter为null<br />UnsupportedOperationException: 默认是现实调用集合的Iterator#remove()方法，如果该Iterator不支持此方法，抛出该异常

retainAll

  1. boolean retainAll(Collection<?> c);

保留既存在于该集合，也存在于指定集合的元素。

clear

  1. void clear();

移除集合中所有元素

equals

  1. boolean equals(Object o);

比较指定对象与此集合的相等性。

hashcode

  1. int hashCode();

返回此集合的哈希代码值。

stream

  1. default Stream<E> stream() {
  2.     return StreamSupport.stream(spliterator(), false);
  3. }

返回以此集合为源的流。

当spliterator()方法无法返回不可变、并发或后期绑定的spliterator时，应重写此方法。（有关详细信息，请参见spliterator()

parallelStream

  1. default Stream<E> parallelStream() {
  2.     return StreamSupport.stream(spliterator(), true);
  3. }

返回一个可能的并行流，并将此集合作为其源 。允许此方法返回顺序流。

当spliterator()方法不能返回一个不可变、并发或后期绑定的spliterator时，应重写此方法。

List

  1. public interface List<E> extends Collection<E> {
  2. }

:::info 有序集合，用户可以精确控制集合中的每个元素。通过索引访问元素。 :::

:::info 不同于Set，List允许元素重复，即允许存在两个或多个元素，他们的equals方法相等。 :::

replaceAll

  1.     default void replaceAll(UnaryOperator<E> operator) {
  2.         Objects.requireNonNull(operator);
  3.         final ListIterator<E> li = this.listIterator();
  4.         while (li.hasNext()) {
  5.             li.set(operator.apply(li.next()));
  6.         }
  7.     }

将集合中的每一个元素执行一次apply()方法在设置回原集合。
注意，UnaryOperator继承至Function接口，内部还有compose和andThen等方法，分别表示在执行apply()前后执行某些操作：

  1.     default <V> Function<V, R> compose(Function<? super V, ? extends T> before) {
  2.         Objects.requireNonNull(before);
  3.         return (V v) -> apply(before.apply(v));
  4.     }
  6.     default <V> Function<T, V> andThen(Function<? super R, ? extends V> after) {
  7.         Objects.requireNonNull(after);
  8.         return (T t) -> after.apply(apply(t));
  9.     }

sort

  1.     default void sort(Comparator<? super E> c) {
  2.         Object[] a = this.toArray();
  3.         Arrays.sort(a, (Comparator) c);
  4.         ListIterator<E> i = this.listIterator();
  5.         for (Object e : a) {
  6.             i.next();
  7.             i.set((E) e);
  8.         }
  9.     }
  1. comparator可以为null，但是集合的某个元素都必须实现Comparable接口，是现在自然排序；
  2. 在Android 25之后，可以使用Collections#sort(List)方法代理该方法；
  3. 转化为Array排序可以避免LinkedList的n````log(n)的性能损耗
  4. 采用归并排序，当输入数组部分排序时，它需要的比较远远少于nlg(n)，如果输入数组几乎已排序，则实现需要大约n个比较；
  5. 该实现在其输入数组中利用升序和降序的同等优势，并且可以在同一输入数组的不同部分利用升序和降序。它非常适合合并两个或多个已排序的数组：只需将数组串联起来并对结果数组进行排序；

get

  1. E get(int index);

set

  1. E set(int index, E element);

替换index索引处的元素为element。

  • UnsupportedOperationException
  • ClassCastException
  • NullPointException
  • IllegalArgumentException’

  • IndexOutOfException

    add

    1. void add(int index, E element);

    在index索引处插入element元素。

  • UnsupportedOperationException

  • ClassCastException
  • NullPointException
  • IllegalArgumentException’

  • IndexOutOfException

    remove

    1. void add(int index, E element);

  • UnsupportedOperationException

  • IndexOutOfException

    indexOf

    1. int indexOf(Object o);

    在集合中找到指定元素第一次出现的位置，返回-1表示集合中不存在该元素。

  • ClassCastException

  • NullPointException

    lastIndexOf

    在集合中找到指定元素最后一次出现的位置，返回-1表示集合中不存在该元素。

    subList

    1. List<E> subList(int fromIndex, int toIndex);
    返回此列表中指定的fromIndex（包含）和toIndex（不包含）之间部分的元素集合。（如果fromIndex和toIndex相等，则返回的列表为空。）返回的列表由此列表派生，因此返回列表中的非结构更改将反映在此列表中，反之亦然。

例如，从列表中删除一系列元素：

  1. list.subList(from, to).clear();

of

  1.     static <E> List<E> of() {
  2.         return ImmutableCollections.List0.instance();
  3.     }
  5.     static <E> List<E> of(E e1) {
  6.         return new ImmutableCollections.List1<>(e1);
  7.     }
  9.     static <E> List<E> of(E e1, E e2) {
  10.         return new ImmutableCollections.List2<>(e1, e2);
  11.     }
  13.     ....
  15.     static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) {
  16.         return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
  17.                                                 e6, e7, e8, e9, e10);
  18.     }

创建不可改变数组。

AbstractList

  1. public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
  2. }

subList

  1.     public List<E> subList(int fromIndex, int toIndex) {
  2.         subListRangeCheck(fromIndex, toIndex, size());
  3.         return (this instanceof RandomAccess ?
  4.                 new RandomAccessSubList<>(this, fromIndex, toIndex) :
  5.                 new SubList<>(this, fromIndex, toIndex));
  6.     }

可以看到，subList返回的是RandomAccessSubList或者SubList类型，不一定是原集合类型。例如，ArrayList#subList(int , int)返回的就是RandomAccessSubList类型的集合。

  1. private static class SubList<E> extends AbstractList<E> {
  2. }
  4. private static class RandomAccessSubList<E>
  5.             extends SubList<E> implements RandomAccess {
  6. }

注意：SubList内部使用的就是源集合，直接在原集合的基础上进行操作的。也就是说，对SubList的任何操作都会反映到原List中。

  1.         public SubList(AbstractList<E> root, int fromIndex, int toIndex) {
  2.             this.root = root;
  3.             this.parent = null;
  4.             this.offset = fromIndex;
  5.             this.size = toIndex - fromIndex;
  6.             this.modCount = root.modCount;
  7.         }
  9.        public E set(int index, E element) {
  10.             Objects.checkIndex(index, size);
  11.             checkForComodification();
  12.             // 直接在原集合操作
  13.             return root.set(offset + index, element);
  14.         }
  16.         public E get(int index) {
  17.             Objects.checkIndex(index, size);
  18.             checkForComodification();
  19.              // 直接在原集合操作
  20.             return root.get(offset + index);
  21.         }
  23.         public int size() {
  24.             checkForComodification();
  25.             return size;
  26.         }
  28.         public void add(int index, E element) {
  29.             rangeCheckForAdd(index);
  30.             checkForComodification();
  31.             // 直接在原集合操作，root就是原集合，见构造方法
  32.             root.add(offset + index, element);
  33.             updateSizeAndModCount(1);
  34.         }
  36.         public E remove(int index) {
  37.             Objects.checkIndex(index, size);
  38.             checkForComodification();
  39.              // 直接在原集合操作，root就是原集合，见构造方法
  40.             E result = root.remove(offset + index);
  41.             updateSizeAndModCount(-1);
  42.             return result;
  43.         }
  45.         // 重要：并发修改异常
  46.         private void checkForComodification() {
  47.             if (root.modCount != this.modCount)
  48.                 throw new ConcurrentModificationException();
  49.         }

ConcurrentModificationException

我们都知道，不同线程对非并发List操作可能会产生ConcurrentModificationException。这是因为List内部存在一个modCount变量，专门用来计算对集合修改的次数，只要两次修改操作中该值不一致，就会触发该异常。

modCount在以下场景中会修改其值：
image.png

ArrayList

  1. 内部实现由可变长数组实现；
  2. 可以存储任何元素，包括null;

  3. 内部数组会在合适的时候自动扩容；

    1. public class ArrayList<E> extends AbstractList<E>
    2.      implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    4.      private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    6.     // 存储ArrayList元素的数组缓冲区。
    7.     // ArrayList的容量是此数组缓冲区的长度。当添加第一个元素时，任何
    8.     // 的空ArrayList（elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA）都将扩展为DEFAULT_CAPACITY（10）
    9.     transient Object[] elementData;
    11.     // ArrayList的长度，不是elementData的容量，而是ArrayList中的真正元素数量
    12.     private int size;
    14. }

    add源码分析

    1. public boolean add(E e) {
    2.      ensureCapacityInternal(size + 1);  // Increments modCount!!
    3.      // 很明显，在数组长度大于等于Integer.MAX_VALUE的情况下，会触发数组越界异常
    4.      elementData[size++] = e;
    5.      return true;
    6.  }

    ensureCapacityInternal方法用来保证数组的容量可以添加该元素，否则进行扩容。

注意：modCount在这里会被修改

  1.     private void ensureCapacityInternal(int minCapacity) {
  2.         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  3.             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  4.         }
  6.         ensureExplicitCapacity(minCapacity);
  7.     }
  9.     private void ensureExplicitCapacity(int minCapacity) {
  10.         // 修改modCount
  11.         modCount++;
  13.         // overflow-conscious code
  14.         // minCapacity表示当前元素个数。该条件成立表示数组已满，不足以再放入任何元素，需要扩容
  15.         if (minCapacity - elementData.length > 0)
  16.             grow(minCapacity);
  17.     }
  19.     private void grow(int minCapacity) {
  20.         // overflow-conscious code
  21.         int oldCapacity = elementData.length;
  22.         // 预先增加一半的容量
  23.         int newCapacity = oldCapacity + (oldCapacity >> 1);
  24.         // 增加1.5倍之后还是不能存放下元素，修改newCapacity的值，保证元素可以放入
  25.         if (newCapacity - minCapacity < 0)
  26.             newCapacity = minCapacity;
  27.         // 新容量大于最大容量，去int最大值作为新数组的长度
  28.         if (newCapacity - MAX_ARRAY_SIZE > 0)
  29.             // 保证newCapacity最大为Integer.MAX_VALUE
  30.             newCapacity = hugeCapacity(minCapacity);
  31.         // minCapacity is usually close to size, so this is a win:
  32.         // copyOf方法内部创建一个长度为newCapacity的数组，再将elementData的元素全部复制到新数组中，完成扩容
  33.         elementData = Arrays.copyOf(elementData, newCapacity);
  34.     }
  36.     private static int hugeCapacity(int minCapacity) {
  37.         if (minCapacity < 0) // overflow
  38.             throw new OutOfMemoryError();
  39.         return (minCapacity > MAX_ARRAY_SIZE) ?
  40.             Integer.MAX_VALUE :
  41.             MAX_ARRAY_SIZE;
  42.     }
  1. 数组elementData不足以添加新元素时，则进行扩容；每次扩容之后的新容量为原elementData数组长度的1.5倍；
  2. 扩容最大长度为Integer.MAX_VALUE；
  3. 新数组容量确定之后调用Arrays.copyOf方法将原数组内容拷贝到新数组中，并返回新数组赋值给elementData。

remove源码分析

  1.     public E remove(int index) {
  2.         if (index >= size)
  3.             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  5.         modCount++;
  6.         E oldValue = (E) elementData[index];
  8.         // 删除元素，需要将删除位置之后的所有元素往前移动。比较耗费性能。这点LinkedList就会好很多
  9.         int numMoved = size - index - 1;
  10.         if (numMoved > 0)
  11.             System.arraycopy(elementData, index+1, elementData, index,
  12.                              numMoved);
  13.         // 最后一个元素置空，因为该元素已经往前移动一位了
  14.         elementData[--size] = null; // clear to let GC do its work
  16.         return oldValue;
  17.     }

AbstractSequentialList

  1. public abstract class AbstractSequentialList<E> extends AbstractList<E> {
  3. }

该类提供了List接口的一个基本实现框架，目的是为了最小化顺序访问 （链表）数据所需的工作量。对于随机访问的数据集，更应该是使用这个类，因为性能更高。

理解，插入一个数据到List，如果使用ArrayList，则需要进行数组复制和移动；但如果使用LinkedList，就只需要断链，再更改指针的指向就行了，效率更高。

该类的子类需要实现listIterator和size方法，因为子类的增删改查都是通过这两个方法来完成的。

  • 提供无参构造方法和参数为Collection类型的构造方法
  • 对于一个不可更改的集合来说，只需要实现迭代器的hasNext/next/hasprepoint/previous/index方法即可。
  • 对于一个可更改的集合来说，还需要实现迭代器的set方法
  • 对于可扩展集合，好需要实现迭代器的remove和add方法

    get

    1.   public E get(int index) {
    2.       try {
    3.           return listIterator(index).next();
    4.       } catch (NoSuchElementException exc) {
    5.           throw new IndexOutOfBoundsException("Index: "+index);
    6.       }
    7.   }
    从指定位置获取一个list迭代器，然后，使用ListIterator.next获取对应元素并返回。

set

  1.     public E set(int index, E element) {
  2.         try {
  3.             ListIterator<E> e = listIterator(index);
  4.             E oldVal = e.next();
  5.             e.set(element);
  6.             return oldVal;
  7.         } catch (NoSuchElementException exc) {
  8.             throw new IndexOutOfBoundsException("Index: "+index);
  9.         }
  10.     }

指定位置插入新元素，并将旧元素返回。

add

  1.     public void add(int index, E element) {
  2.         try {
  3.             listIterator(index).add(element);
  4.         } catch (NoSuchElementException exc) {
  5.             throw new IndexOutOfBoundsException("Index: "+index);
  6.         }
  7.     }

remove

  1.     public E remove(int index) {
  2.         try {
  3.             ListIterator<E> e = listIterator(index);
  4.             E outCast = e.next();
  5.             e.remove();
  6.             return outCast;
  7.         } catch (NoSuchElementException exc) {
  8.             throw new IndexOutOfBoundsException("Index: "+index);
  9.         }
  10.     }

LinkedList

List和Deque接口的双链接列表实现。
**

Node

  1.     private static class Node<E> {
  2.         E item;
  3.         Node<E> next;
  4.         Node<E> prev;
  6.         Node(Node<E> prev, E element, Node<E> next) {
  7.             this.item = element;
  8.             this.next = next;
  9.             this.prev = prev;
  10.         }
  11.     }

双向链表的节点表示。next和prev分别表示下一个节点或上一个节点。可以存储null元素。

add源码分析

  1.     public boolean add(E e) {
  2.         linkLast(e);
  3.         return true;
  4.     }
  6.     void linkLast(E e) {
  7.         final Node<E> l = last;
  8.         // 为该元素创建一个Node，然后作为last的next节点
  9.         final Node<E> newNode = new Node<>(l, e, null);
  10.         last = newNode;
  11.         if (l == null)
  12.             first = newNode;
  13.         else
  14.             l.next = newNode;
  15.         size++;
  16.         modCount++;
  17.     }

remove源码分析

  1.     public boolean remove(Object o) {
  2.         if (o == null) {
  3.             for (Node<E> x = first; x != null; x = x.next) {
  4.                 if (x.item == null) {
  5.                     unlink(x);
  6.                     return true;
  7.                 }
  8.             }
  9.         } else {
  10.             for (Node<E> x = first; x != null; x = x.next) {
  11.                 // 通过equals比较
  12.                 if (o.equals(x.item)) {
  13.                     unlink(x);
  14.                     return true;
  15.                 }
  16.             }
  17.         }
  18.         return false;
  19.     }
  21.     E unlink(Node<E> x) {
  22.         // assert x != null;
  23.         final E element = x.item;
  24.         final Node<E> next = x.next;
  25.         final Node<E> prev = x.prev;
  27.         if (prev == null) {
  28.             // 说明x就是first节点，直接将next节点作为first节点，因为x被移除了
  29.             first = next;
  30.         } else {
  31.             // 移除x，将x.next作为x.prev的next节点
  32.             prev.next = next;
  33.             x.prev = null;
  34.         }
  36.         if (next == null) {
  37.             last = prev;
  38.         } else {
  39.             next.prev = prev;
  40.             x.next = null;
  41.         }
  43.         x.item = null;
  44.         size--;
  45.         modCount++;
  46.         return element;
  47.     }

get源码分析

  1.     public E get(int index) {
  2.         checkElementIndex(index);
  3.         return node(index).item;
  4.     }
  6.     Node<E> node(int index) {
  7.         // assert isElementIndex(index);
  8.         // 二分法，减少遍历次数
  9.         if (index < (size >> 1)) {
  10.             Node<E> x = first;
  11.             for (int i = 0; i < index; i++)
  12.                 x = x.next;
  13.             return x;
  14.         } else {
  15.             Node<E> x = last;
  16.             for (int i = size - 1; i > index; i--)
  17.                 x = x.prev;
  18.             return x;
  19.         }
  20.     }

Set

  1. public interface Set<E> extends Collection<E> {
  3. }

不包含重复的元素，可以存储**null**元素。

ArraySet

  1. public final class ArraySet<E> implements Collection<E>, Set<E> {
  2.     private int[] mHashes; // 每个元素对应的Hash值
  3.     Object[] mArray; // 元素数组
  4.     int mSize; // Set的长度，元素个数
  5.     private static final int BASE_SIZE = 4; // 元素数组的扩容之后的最小容量
  6.     private static final int CACHE_SIZE = 10; // 数组中entry的最大数量
  8.     // 缓存小数组对象以避免大量的垃圾回收。cache object[]变量是指向数组对象的链表的指针。
  9.     // 数组中的第一个条目是指向列表中下一个数组的指针；
  10.     // 数组中的第二个条目是指向该数组的int[]哈希码数组的指针。
  11.     private static @Nullable Object[] sBaseCache;
  12.     private static int sBaseCacheSize;
  13.     private static @Nullable Object[] sTwiceBaseCache;
  14.     private static int sTwiceBaseCacheSize;
  15. }

ArraySet是一种通用的set数据结构，是一个比java.util.HashSet内存更高效的设计.。

注意，ArraySet并不适用于可能包含大量数据的场景。通常比HashSet慢，因为在数组中插入和删除条目需要二进制搜索，添加和删除。对于以百计量的数据，性能差异不显著，小于50%。

ArraySet旨在更好地平衡内存使用，与大多数其他标准Java实现不同，它将在从中移除项时收缩其数组。

indexOf源码分析

在mArray数组中查找指定元素，如果存在该元素，则返回元素索引，否则返回负数。注意：不一定返回-1。

  2.     /**
  3.       * @param key 指定元素
  4.       * @param hash key的hashcode()返回的hash值，如果key等于null，则hash为0
  5.       */
  6.     private int indexOf(Object key, int hash) {
  7.         final int N = mSize;
  9.         // Important fast case: if nothing is in here, nothing to look for.
  10.         // 不存在任何元素（即首次添加，返回-1）
  11.         if (N == 0) {
  12.             return ~0;
  13.         }
  15.         // 二分法查找hash值，找到即表示mArray中存在该元素，找不到返回-1
  16.         // 注意：mArray和mHashes是一一对应的关系，即一个元素对应一个hash值，之所以存在这个结构，
  17.         //       是为了方便比较
  18.         int index = ContainerHelpers.binarySearch(mHashes, N, hash);
  20.         // If the hash code wasn't found, then we have no entry for this key.
  21.         // 没有找到，直接返回负数
  22.         if (index < 0) {
  23.             return index;
  24.         }
  26.         // If the key at the returned index matches, that's what we want.
  27.         // 找到对应的hash值，且两个元素相等（equals返回一致），则直接返回index
  28.         // 注意，这里之所以还要再做一次equals，是因为不同元素的hashcode值有可能是一样的，不能因为hash值一致就得出两个元素一样的结论
  29.         if (key.equals(mArray[index])) {
  30.             return index;
  31.         }
  33.         // 从index处往后遍历，查找元素
  34.         int end;
  35.         for (end = index + 1; end < N && mHashes[end] == hash; end++) {
  36.             if (key.equals(mArray[end])) return end;
  37.         }
  39.          // 从index处往前遍历，查找元素
  40.         for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
  41.             if (key.equals(mArray[i])) return i;
  42.         }
  44.         // 返回一个负数
  45.         return ~end;
  46.     }

结论：indexOf是在mArray数组中查找该元素，查找规则为**hashcode**值一致且**equals**方法一致，找到指定元素则返回元素索引，否则返回赋值。

freeArrays源码解析

  1.    private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
  2.         if (hashes.length == (BASE_SIZE * 2)) {
  3.             synchronized (ArraySet.class) {
  4.                 // 缓存次数小于10
  5.                 if (sTwiceBaseCacheSize < CACHE_SIZE) {
  6.                     array[0] = sTwiceBaseCache;
  7.                     array[1] = hashes;
  8.                     for (int i = size - 1; i >= 2; i--) {
  9.                         array[i] = null;
  10.                     }
  11.                     sTwiceBaseCache = array;
  12.                     sTwiceBaseCacheSize++;
  13.                 }
  14.             }
  15.         } else if (hashes.length == BASE_SIZE) {
  16.             synchronized (ArraySet.class) {
  17.                 if (sBaseCacheSize < CACHE_SIZE) {
  18.                     array[0] = sBaseCache;
  19.                     array[1] = hashes;
  20.                     for (int i = size - 1; i >= 2; i--) {
  21.                         array[i] = null;
  22.                     }
  23.                     sBaseCache = array;
  24.                     sBaseCacheSize++;
  25.                     if (DEBUG) {
  26.                         System.out.println(TAG + " Storing 1x cache " + array + " now have "
  27.                                 + sBaseCacheSize + " entries");
  28.                     }
  29.                 }
  30.             }
  31.         }
  32.     }

该方法会在移除元素时在合适的时机释放内存，当hash数组长度为4或8的时候，会将原数组保存下来，注意，仅保存数据空间，不保存元素，因为保存元素有可能导致内存泄漏。也就是说，sBaseCache和sTwiceBaseCache数组保存两个元素，第一个元素保存长度为4或8的空数组Object[]，第二个元素保存长度为4或8的hash值数组，当内存收缩到只有4或8个元素的时候，不用重新new数组，而是取出这两个数组来使用。至于为什么是4或8作为临界点，应该是工程设计得出的结论。换句话说，sBaseCache和sTwiceBaseCache相当于一个数组池，避免频繁创建数组而设计。

allocArrays源码解析

  1.     // size参数表示数组即将扩容的大小
  2.     private void allocArrays(final int size) {
  3.         if (size == (BASE_SIZE * 2)) {
  4.             // 当数组长度定位8时，如果存在缓存，直接将
  5.             synchronized (ArraySet.class) {
  6.                 if (sTwiceBaseCache != null) {
  7.                     final Object[] array = sTwiceBaseCache;
  8.                     mArray = array;
  9.                     sTwiceBaseCache = (Object[]) array[0];
  10.                     mHashes = (int[]) array[1];
  11.                     array[0] = array[1] = null;
  12.                     sTwiceBaseCacheSize--;
  13.                     if (DEBUG) {
  14.                         System.out.println(TAG + " Retrieving 2x cache " + mHashes + " now have "
  15.                                 + sTwiceBaseCacheSize + " entries");
  16.                     }
  17.                     return;
  18.                 }
  19.             }
  20.         } else if (size == BASE_SIZE) {
  21.             synchronized (ArraySet.class) {
  22.                 if (sBaseCache != null) {
  23.                     final Object[] array = sBaseCache;
  24.                     mArray = array;
  25.                     sBaseCache = (Object[]) array[0];
  26.                     mHashes = (int[]) array[1];
  27.                     array[0] = array[1] = null;
  28.                     sBaseCacheSize--;
  29.                     if (DEBUG) {
  30.                         System.out.println(TAG + " Retrieving 1x cache " + mHashes + " now have "
  31.                                 + sBaseCacheSize + " entries");
  32.                     }
  33.                     return;
  34.                 }
  35.             }
  36.         }
  38.         mHashes = new int[size];
  39.         mArray = new Object[size];
  40.     }

该方法给数组分配合适的内存空间。注意，如果sBaseCache和sTwiceBaseCache存在，在创建长度为4或8的时候，直接使用缓存的数组对象，不再直接创建。

add源码分析

  1.     @Override
  2.     public boolean add(@Nullable E value) {
  3.         final int hash;
  4.         int index;
  5.         if (value == null) {
  6.             hash = 0;
  7.             index = indexOfNull();
  8.         } else {
  9.             hash = value.hashCode();
  10.             index = indexOf(value, hash);
  11.         }
  12.         // 找到相等的元素，直接返回false ，不用再次插入
  13.         if (index >= 0) {
  14.             return false;
  15.         }
  17.         // 返回该元素插入的对应位置
  18.         index = ~index;
  19.         // mHashes.length和mArray.length在调用带有初始容量的构造器时已经初始化为初始容量大小 
  20.         if (mSize >= mHashes.length) {
  21.             // 扩容机制:
  22.             // 1. 元素数量超过8，每次扩容0.5倍；
  23.             // 2. 元素数量超过BASE_SIZE(也就是4)，直接扩容到8；
  24.             // 3. 元素数量小于4，直接扩容到4
  25.             final int n = mSize >= (BASE_SIZE * 2) ? (mSize + (mSize >> 1))
  26.                     : (mSize >= BASE_SIZE ? (BASE_SIZE * 2) : BASE_SIZE);
  28.             final int[] ohashes = mHashes;
  29.             final Object[] oarray = mArray;
  30.             allocArrays(n);
  32.             if (mHashes.length > 0) {
  33.                 System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
  34.                 System.arraycopy(oarray, 0, mArray, 0, oarray.length);
  35.             }
  37.             freeArrays(ohashes, oarray, mSize);
  38.         }
  40.         if (index < mSize) {
  41.             System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
  42.             System.arraycopy(mArray, index, mArray, index + 1, mSize - index);
  43.         }
  45.         mHashes[index] = hash;
  46.         mArray[index] = value;
  47.         mSize++;
  48.         return true;
  49.     }
  1. 在mArray数组不再能够装得下指定元素的时候进行扩容；
  2. 在扩容为4、8或者更大的值的时候会在freeArrays方法中将长度为4或8的mArray数组和mHashes数组保存下类备用，方便下次不再重新创建数组。

注意：只有当mSize = 4或者mSize = 8的时候，才会将mHashes进行缓存，且分别缓存在mBaseCache和mTwiceBaseCache数组中。

remove源码分析

  1.     @Override
  2.     public boolean remove(@Nullable Object object) {
  3.         final int index = indexOf(object);
  4.         if (index >= 0) {
  5.             removeAt(index);
  6.             return true;
  7.         }
  8.         return false;
  9.     }
  11.     public E removeAt(int index) {
  12.         // 获取需要移除的元素
  13.         final Object old = mArray[index];
  14.         if (mSize <= 1) {
  15.             // 上面的示例，只剩下最后一个元素时，此时mHashes的长度为12,只不过后8个元素为无效值
  16.             freeArrays(mHashes, mArray, mSize);
  17.             mHashes = INT;
  18.             mArray = OBJECT;
  19.             mSize = 0;
  20.         } else {
  21.             // hash数组长度大于8且元素个数小于hash数组的三分之一
  22.             // 上面的实例来看，该分支不满足，一直走else分支，直到只剩下最后一个元素
  23.             if (mHashes.length > (BASE_SIZE * 2) && mSize < mHashes.length / 3) {
  24.                 // 保证数组缩小之后其大小大于8，避免在4和8之间暴动
  25.                 // 得到一个合适的缩小数组的范围
  26.                 final int n = mSize > (BASE_SIZE * 2) ? (mSize + (mSize >> 1)) : (BASE_SIZE * 2);
  28.                 final int[] ohashes = mHashes;
  29.                 final Object[] oarray = mArray;
  30.                 allocArrays(n);
  32.                 mSize--;
  33.                 // 两次赋值，直接将原数组除开指定元素的所有数据复制到新数组
  34.                 if (index > 0) {
  35.                     System.arraycopy(ohashes, 0, mHashes, 0, index);
  36.                     System.arraycopy(oarray, 0, mArray, 0, index);
  37.                 }
  38.                 if (index < mSize) {
  39.                     System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);
  40.                     System.arraycopy(oarray, index + 1, mArray, index, mSize - index);
  41.                 }
  42.             } else {
  43.                 mSize--;
  44.                 if (index < mSize) {
  45.                     System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);
  46.                     System.arraycopy(mArray, index + 1, mArray, index, mSize - index);
  47.                 }
  48.                 mArray[mSize] = null;
  49.             }
  50.         }
  51.         return (E) old;
  52.     }
  1. 移除元素，元素不存在则返回false;
  2. 在合适的时机进行内存回收，该时机就是hash数组长度大于8且元素个数小于hash数组长度的三分之一。

HashSet

  1. public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable {
  3.     private transient HashMap<E,Object> map;
  5.     public HashSet() {
  6.         map = new HashMap<>();
  7.     }
  8.     public HashSet(Collection<? extends E> c) {
  9.         map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
  10.         addAll(c);
  11.     }
  12.     public HashSet(int initialCapacity, float loadFactor) {
  13.         map = new HashMap<>(initialCapacity, loadFactor);
  14.     }
  15.     public HashSet(int initialCapacity) {
  16.         map = new HashMap<>(initialCapacity);
  17.     }
  18.     HashSet(int initialCapacity, float loadFactor, boolean dummy) {
  19.         map = new LinkedHashMap<>(initialCapacity, loadFactor);
  20.     }
  21. }
  1. HashSet的底层是使用HashMap实现的。那么，只要保证同一个key只对应一个元素，就能实现Set的不存在重复元素的特性。
  2. 由于底层采用的是HashMap实现，那么HashMap的优化方案同样也适用于HashSet。

add

  1.     public boolean add(E e) {
  2.         return map.put(e, PRESENT)==null;
  3.     }

remove

  1.     public boolean remove(Object o) {
  2.         return map.remove(o)==PRESENT;
  3.     }

add和remove操作都是直接调用HashMap的方法完成。

Queue

  1. public interface Queue<E> extends Collection<E> {
  3. }

一种被设计来优先处理保存元素的集合。除了基本操作外，队列还提供附加的插入、提取和检查操作。这些方法都有两种形式：一种是在操作失败时抛出异常，另一种是返回特殊值（null或false）。插入操作的后一种形式是专门为容量受限的队列实现而设计的；在大多数实现中，插入操作不能失败。

Queue方法预览：

抛出异常 返回特殊值
insert add(e) offer
remove remove() poll()
examine element() peed()

队列实现通常不允许插入null元素，尽管有些实现（如LinkedList）不禁止插入null元素。即使在允许它的实现中，也不应该将null插入到队列中，因为null也被poll方法用作特殊的返回值，以指示队列不包含任何元素。

BlockingQueue

  1. public interface BlockingQueue<E> extends Queue<E> {
  2. }

BlockingQueue额外支持了阻塞属性，也就是在拉取元素的时候，如果队列为空，则阻塞等待，直到队列有元素插入；在插入元素的时候，如果队列为已满，则阻塞等待，直到队列有空位可以让元素进行插入；

BlockingQueue方法预览：

抛出异常 返回特殊值 阻塞 超时等待
insert add(e) offer(e) put(e) offer(e, time, Unit)
remove remove() poll() take() poll(time, Unit)
examine element() peed()
  1. BlockingQueue不接受空元素。实现在尝试add、put或offer一个null时会抛出NullPointerException。null用作默认值，表示查询操作失败。
  2. 阻塞队列可能有容量限制。在任何给定的时间，它都可能有一个剩余的容量，超过这个容量，就不能不阻塞地放置额外的元元素。没有任何内在容量约束的BlockingQueue总是默认剩余容量为Integer.MAX值.
  3. BlockingQueue实现主要用于生产者-消费者队列，但也支持Collection接口。因此，例如，可以使用remove（x）从队列中删除任意元素。
  4. BlockingQueue实现是线程安全的。所有排队方法都是通过使用内部锁或其他形式的并发控制来实现其原子效果的。但是，除非在实现中另有规定，否则批量收集操作addAll、containsAll、retainal和removeAll不一定是原子式执行的。例如，addAll(c)在只添加c中的一些元素之后就有可能失败（抛出异常）。
  5. BlockingQueue本质上不支持任何类型的“关闭”或“关闭”操作，以指示不再添加任何项。这些特性的需求和使用往往依赖于实现。例如，一种常见的策略是生产商插入特殊的流末或毒物对象，当消费者使用这些对象时，会对其进行相应的解释。

使用示例，基于典型的生产者-消费者场景。请注意，BlockingQueue可以安全地与多个生产者和多个消费者一起使用。

  1.  class Producer implements Runnable {
  2.    private final BlockingQueue queue;
  3.    Producer(BlockingQueue q) { queue = q; }
  4.    public void run() {
  5.      try {
  6.        while (true) { queue.put(produce()); }
  7.      } catch (InterruptedException ex) { ... handle ...}
  8.    }
  9.    Object produce() { ... }
  10.  }
  12.  class Consumer implements Runnable {
  13.    private final BlockingQueue queue;
  14.    Consumer(BlockingQueue q) { queue = q; }
  15.    public void run() {
  16.      try {
  17.        while (true) { consume(queue.take()); }
  18.      } catch (InterruptedException ex) { ... handle ...}
  19.    }
  20.    void consume(Object x) { ... }
  21.  }
  23.  class Setup {
  24.    void main() {
  25.      BlockingQueue q = new SomeQueueImplementation();
  26.      Producer p = new Producer(q);
  27.      Consumer c1 = new Consumer(q);
  28.      Consumer c2 = new Consumer(q);
  29.      new Thread(p).start();
  30.      new Thread(c1).start();
  31.      new Thread(c2).start();
  32.    }
  33.  }

Deque(双向队列)

  1. public interface Deque<E> extends Queue<E> {
  2. }

支持在两端插入和删除元素的线性集合。deque是“double ended queue”的缩写，通常发音为“deck”。

这个接口定义了访问deque两端元素的方法。提供了插入、移除和检查元素的方法。这些方法都有两种形式：一种是在操作失败时抛出异常，另一种是返回特殊值（null或false，具体取决于操作）。后一种形式的insert操作专门设计用于容量受限的Deque实现；在大多数实现中，insert操作不能失败。

下表总结了上述12种方法：

First Element（Head） Last Element（Tail）
Throws Exception Special Value Throws Exception Special Value
Insert addFirst(e) offerFirst(e) addLast(e) offerLast(e)
Remove removeFirst() pollFirst() removeLast() pollLast()
Examine getFirst() peekFirst() getLast() peekLast()

该接口继承至Queue接口，当作为一个Queue来使用的时候，遵循FIFO原则。

removeFirstOccurrence

  1. boolean removeFirstOccurrence(Object o);

从队列中删除第一个与指定元素相等的匹配项。

removeLastOccurrence

  1. boolean removeLastOccurrence(Object o);

从队列中删除最后一个与指定元素相等的匹配项。