JAVA 集合类概览

Java 集合（也称为容器），是将多个元素组合成一个单元的对象。分为两大类： Collection 和 Map，常用集合为 List 、Set、Map；本文源码分析基于 JDK 1.8 。

基础

概念

集合框架是用于表示和操作集合的统一体系结构，所有集合框架包含以下内容：

接口 Interfaces
表示集合的抽象数据类型，接口允许独立于其表示的细节来操纵集合。
实现 Implementations
集合接口的具体实现，本质上它们是可重用的数据结构。
算法 Algorithms
这些是对实现集合接口的对象，执行有用计算（如搜索和排序）的方法，算法被认为是多态的：相同的方法可以用在集合接口的不同实现上，算法是可重用的功能。

除了 Java Collections Framework 之外，最着名的集合框架示例是 C ++ 标准模板库 STL 。

for-each

for-each 循环是加强型 for 循环，用来循环遍历集合和数组，JDK 5.0 引入的特性。其语法如下：

1
2
3

for(type element: array) {
    System.out.println(element);
}

Iterator

即迭代器，也是一种设计模式，允许访问一个聚合对象而无需暴露内部实现。是一种”轻量级”对象，只能单向遍历。

// java.util.Iterator.java
public interface Iterator<E> {
    // 是否结束
    boolean hasNext();
    // 取下一个元素
    E next();
    // 删除
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer<? super E> action) {...}
}

Iterable

可迭代的，实现了这个接口的类表示可迭代的，并且支持 for-each 循环遍历。

// java.lang.Iterable.java
public interface Iterable<T> {
    // 包含一个迭代器
    Iterator<T> iterator();
    default void forEach(Consumer<? super T> action) {...}
    default Spliterator<T> spliterator() {...}
}

接口

Java 集合框架的基础是：核心集合接口，它封装了不同类型的集合，这些接口可以独立的操作集合。类图结构如下：

集合框架都是使用的是泛型，也就是说实例化时必须要指定具体类型。集合框架包含两个大的类型：

Collection ：我们常说的集合
Map ：保存具有映射关系的数据，包含键和值。键不能重复，每个键只有一个对应的值

Collection 接口表示一组称为其元素的对象，Java 平台不提供此接口的任何实现，只有子接口的实现。它有四个常用的子接口：

Set ：表示不能包含重复元素的集合
List ：表示元素是有序的集合，有时也称为序列
Queue ：队列，通常指先进先出 FIFO 集合，集合的操作都集中在队列某一端
Deque ：双端队列，它实际是 Queue 的子类（感觉并不能和 Queue 并列讨论），可以在队列两端操作集合；它实现了栈 LIFO 和队列 FIFO 两种数据结构

SoretedSet, SoretedMap 表示按升序排好序的集合或键值对。

`Collection` 接口

public interface Collection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    default boolean removeIf(Predicate<? super E> filter) {...}
    boolean retainAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, 0);
    }
    default Stream<E> stream() {
        return StreamSupport.stream(spliterator(), false);
    }
    default Stream<E> parallelStream() {
        return StreamSupport.stream(spliterator(), true);
    }
}

Collection 接口是可迭代的，它提供了集合的一些基本操作：

集合大小，是否为空，是否包含，增加，删除，是否相等，全部清除
迭代访问
集合转换为数组
集合间操作：集合是否包含指定集合，集合添加到目标集合，从集合中移除指定集合
集合取交集：retainAll ，如果和指定集合有交集，则当前集合只保留交集部分；否则当前集合变为空
移除符合特定条件的元素 removeIf
支持并行处理 Spliterator
支持转换为流 Stream

`List` 接口

在介绍 List 接口前，先看看 ListIterator 迭代器的定义：

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
}

ListIterator 继承了 Iterator ，即是一个加强版的迭代器。 ListIterator 是 List 的专有接口，它在迭代时可以向前或者向后迭代，并且支持返回索引值。接下来看 List 接口定义：

public interface List<E> extends Collection<E> {
    ...
    boolean addAll(int index, Collection<? extends E> c);
    default void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final ListIterator<E> li = this.listIterator();
        while (li.hasNext()) {
            li.set(operator.apply(li.next()));
        }
    }
    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }
    E get(int index);
    E set(int index, E element);
    void add(int index, E element);
    E remove(int index);
    int indexOf(Object o);
    int lastIndexOf(Object o);
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);
    List<E> subList(int fromIndex, int toIndex);
}

List 接口中除了 Collection 定义的方法以及重复定义的方法外，新增了一些以索引 index 相关的操作：

集合插入操作：在指定位置插入集合 addAll(int index, Collection<? extends E> c)
集合替换操作：按照指定一元运算符计算并替换当前集合所有的元素 replaceAll(UnaryOperator<E> operator)
集合排序操作：按照指定排序方式，将当前集合内部排序 sort(Comparator<? super E> c)
集合截取操作：给定两个指定位置，截取这部分元素集合 List<E> subList(int fromIndex, int toIndex)
索引 Index 操作：获取指定位置元素、设置指定位置元素、在指定位置添加元素、移除指定位置元素、指定元素的第一个位置 indexOf 、指定元素的最后一个位置 lastIndexOf
支持 ListIterator 迭代器：既可以向前遍历，也可以向后遍历

`Queue` 接口

public interface Queue<E> extends Collection<E> {
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
}

Queue 接口继承了 Collection ，并重新定义了如下几个方法：

add/offer ：向队列中添加一个元素
remove/poll ：删除并取出队首元素
element/peek ：获取队首元素，但在队列中不删除该元素

这些功能相似，却有两个独立方法的区别是：抛出异常！

add 方法在容量有有限制的队列中，添加元素超出容量限制时会抛出异常；而 offer 只会返回 false
remove 方法在队列为空时，删除会抛出异常；而 poll 只会返回 null
element 方法在队列为空时，取出队首元素抛出异常；而 peek 只会返回 null

所以它们在选择并使用时，主要是考虑当前程序是否需要处理异常；当然也和集合的具体实现类有关，取决于集合实现类是否严格按照方法的定义去实现了。

`Deque` 接口

public interface Deque<E> extends Queue<E> {
    void addFirst(E e);
    void addLast(E e);
    boolean offerFirst(E e);
    boolean offerLast(E e);
    E removeFirst();
    E removeLast();
    E pollFirst();
    E pollLast();
    E getFirst();
    E getLast();
    E peekFirst();
    E peekLast();
    boolean removeFirstOccurrence(Object o);
    boolean removeLastOccurrence(Object o);
    boolean add(E e);
    boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
    void push(E e);
    E pop();
    boolean remove(Object o);
    boolean contains(Object o);
    public int size();
    Iterator<E> iterator();
    Iterator<E> descendingIterator();
}

Deque 继承了 Queue ，属于双端队列，接口中的方法明显增多，主要是多出了双端操作：

不管是增加还是删除，都提供队首或队尾操作
实现数据结构队列的操作时：从队尾插入，从队首取出，模拟 FIFO 过程
实现数据结构栈的操作时：从队首插入，从队首取出，模拟 LIFO 过程
支持指定元素操作：从队首开始删除第一个匹配的指定元素 removeFirstOccurrence/remove ，从队尾开始删除第一个匹配的指定元素 removeLastOccurrence ，判断是否包含指定元素 contains
支持双端遍历：从队首开始遍历 iterator ；从队尾开始遍历 descendingIterator

`Set` 接口

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

Set 继承了 Collection ，并没有增加任何新的方法，特点是集合中没有重复元素，最多只允许一个 null 元素。
Set 的实现类都是基于 Map 来实现的：HashSet 是通过 HashMap 实现的；TreeSet 是通过 TreeMap 实现的。

`Map` 接口

public interface Map<K,V> {
    int size();
    boolean isEmpty();
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    V get(Object key);
    V put(K key, V value);
    V remove(Object key);
    void putAll(Map<? extends K, ? extends V> m);
    void clear();
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
    boolean equals(Object o);
    int hashCode();
    default V getOrDefault(Object key, V defaultValue) {...}
    // 遍历图中所有元素，每个元素按照指定方法操作
    default void forEach(BiConsumer<? super K, ? super V> action) {...}
    // 遍历图中所有元素，每个元素按照指定方法操作后的结果，替换键对应的值
    default void replaceAll(BiFunction<? super K, ? super V, 
            ? extends V> function) {...}
    // 键对应的值为空时，存储该键值对
    default V putIfAbsent(K key, V value) {...}
    // 移除指定键值对
    default boolean remove(Object key, Object value) {...}
    // 使用新值替换存在的键值对
    default boolean replace(K key, V oldValue, V newValue) {...}
    // 替换指定键对应的值
    default V replace(K key, V value) {...}
    // 键值不存在时，使用指定方法计算后，再存储键值对
    default V computeIfAbsent(K key,
            Function<? super K, ? extends V> mappingFunction) {...}
    // 键值对存在时，使用指定方法计算后，更新键值对
    default V computeIfPresent(K key,
            BiFunction<? super K, ? super V, ? extends V> 
            remappingFunction) {...}
    // 如果键值存在则移除；如果不存在，使用指定方法计算后存储键值对
    default V compute(K key,
            BiFunction<? super K, ? super V, ? extends V> 
            remappingFunction) {...}
    // 使用给定键值对，或者指定方法，更新当前键值对
    default V merge(K key, V value,
            BiFunction<? super V, ? super V, ? extends V> 
            remappingFunction) {...}

    interface Entry<K,V> {
        K getKey();
        V getValue();
        V setValue(V value);
        boolean equals(Object o);
        int hashCode();
        public static <K extends Comparable<? super K>, V> 
                Comparator<Map.Entry<K,V>> comparingByKey() {
            return (Comparator<Map.Entry<K, V>> & Serializable)
                (c1, c2) -> c1.getKey().compareTo(c2.getKey());
        }
        public static <K, V extends Comparable<? super V>> 
                Comparator<Map.Entry<K,V>> comparingByValue() {
            return (Comparator<Map.Entry<K, V>> & Serializable)
                (c1, c2) -> c1.getValue().compareTo(c2.getValue());
        }
        public static <K, V> Comparator<Map.Entry<K, V>> 
                comparingByKey(Comparator<? super K> cmp) {
            Objects.requireNonNull(cmp);
            return (Comparator<Map.Entry<K, V>> & Serializable)
                (c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
        }
        public static <K, V> Comparator<Map.Entry<K, V>> 
                comparingByValue(Comparator<? super V> cmp) {
            Objects.requireNonNull(cmp);
            return (Comparator<Map.Entry<K, V>> & Serializable)
                (c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
        }
    }
}

Map.Entry 接口表示 Map 的每个基本元素，它提供如下功能：

getKey 获取当前元素的键
getValue/setValue 获取和设置当前元素的值
判断当前元素是否相等 hashCode, equals
按键比较元素 comparingByKey ，支持指定比较器
按值比较元素 comparingByValue ，支持指定比较器

Map 接口提供的功能包含：

基本操作：大小，判断是否为空，是否包含键，是否包含值，清除图中所有元素，是否相等
键值对相关操作
集合操作：获取图中所有键 keySet，获取图中所有值 values，获取图中所有元素 entrySet
整个图操作：forEach 遍历图中所有元素，每个元素按照指定方法操作；replaceAll 遍历图中所有元素，每个元素按照指定方法操作后的结果，替换键对应的值

`SoretedSet` 接口

public interface SortedSet<E> extends Set<E> {
    Comparator<? super E> comparator();
    SortedSet<E> subSet(E fromElement, E toElement);
    SortedSet<E> headSet(E toElement);
    SortedSet<E> tailSet(E fromElement);
    E first();
    E last();
    default Spliterator<E> spliterator() {...}
}

SoretedSet 接口根据对象的比较顺序排序的集合。

`NavigableSet` 接口

public interface NavigableSet<E> extends SortedSet<E> {
    E lower(E e);
    E floor(E e);
    E ceiling(E e);
    E higher(E e);
    E pollFirst();
    E pollLast();
    Iterator<E> iterator();
    NavigableSet<E> descendingSet();
    Iterator<E> descendingIterator();
    NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                           E toElement,   boolean toInclusive);
    NavigableSet<E> headSet(E toElement, boolean inclusive);
    NavigableSet<E> tailSet(E fromElement, boolean inclusive);
    SortedSet<E> subSet(E fromElement, E toElement);
    SortedSet<E> headSet(E toElement);
    SortedSet<E> tailSet(E fromElement);
}

NavigableSet 接口继承了 SoretedSet，所以它是有序的；具有导航方法返回小于、小于等于、大于等于、大于给定元素的元素。

`SoretedMap` 接口

public interface SortedMap<K,V> extends Map<K,V> {
    Comparator<? super K> comparator();
    SortedMap<K,V> subMap(K fromKey, K toKey);
    SortedMap<K,V> headMap(K toKey);
    SortedMap<K,V> tailMap(K fromKey);
    K firstKey();
    K lastKey();
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
}

SoretedMap 接口表示按照键值升序排序的 Map，也可以按照指定比较器排序。

`NavigableMap` 接口

public interface NavigableMap<K,V> extends SortedMap<K,V> {
    Map.Entry<K,V> lowerEntry(K key);
    K lowerKey(K key);
    Map.Entry<K,V> floorEntry(K key);
    K floorKey(K key);
    Map.Entry<K,V> ceilingEntry(K key);
    K ceilingKey(K key);
    Map.Entry<K,V> higherEntry(K key);
    K higherKey(K key);
    Map.Entry<K,V> firstEntry();
    Map.Entry<K,V> lastEntry();
    Map.Entry<K,V> pollFirstEntry();
    Map.Entry<K,V> pollLastEntry();
    NavigableMap<K,V> descendingMap();
    NavigableSet<K> navigableKeySet();
    NavigableSet<K> descendingKeySet();
    NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                             K toKey,   boolean toInclusive);
    NavigableMap<K,V> headMap(K toKey, boolean inclusive);
    NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
    SortedMap<K,V> subMap(K fromKey, K toKey);
    SortedMap<K,V> headMap(K toKey);
    SortedMap<K,V> tailMap(K fromKey);
}

NavigableMap 接口继承了 SortedMap，所以它是有序的；具有针对给定搜索目标返回最接近匹配项的导航方法，比如小于、小于等于、大于、大于等于某个键的元素等。

抽象实现类

`AbstractCollection` 抽象类

public abstract class AbstractCollection<E> implements Collection<E> {

    protected AbstractCollection() {}
    public abstract Iterator<E> iterator();
    public abstract int size();
    public boolean isEmpty() {
        return size() == 0;
    }
    public boolean contains(Object o) {...}
    public Object[] toArray() {...}
    public <T> T[] toArray(T[] a) {...}
    public boolean add(E e) {
        throw new UnsupportedOperationException();
    }
    public boolean remove(Object o) {...}
    public boolean containsAll(Collection<?> c) {...}
    public boolean addAll(Collection<? extends E> c) {...}
    public boolean removeAll(Collection<?> c) {...}
    public boolean retainAll(Collection<?> c) {...}
    public void clear() {...}
    public String toString() {...}
}

抽象集合类 AbstractCollection 中，已经实现的方法，基本都是使用最原始的迭代器 Iterator 来遍历实现的；但 iterator 方法是抽象的，也就是说迭代器由具体类来实现。

抽象类包含两个抽象方法：iterator, size
add 方法必须由子类重写，否则抛出异常

`AbstractList` 抽象类

public abstract class AbstractList<E> extends AbstractCollection<E> 
    implements List<E> {

    protected AbstractList() {}
    public boolean add(E e) {
        add(size(), e);
        return true;
    }
    abstract public E get(int index);
    public E set(int index, E element) {
        throw new UnsupportedOperationException();
    }
    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }
    public E remove(int index) {
        throw new UnsupportedOperationException();
    }
    public int indexOf(Object o) {...}
    public int lastIndexOf(Object o) {...}
    public void clear() {
        removeRange(0, size());
    }
    public boolean addAll(int index, Collection<? extends E> c) {...}
    public Iterator<E> iterator() {
        return new Itr();
    }
    public ListIterator<E> listIterator() {
        return listIterator(0);
    }
    public ListIterator<E> listIterator(final int index) {...}
    public List<E> subList(int fromIndex, int toIndex) {
        return (this instanceof RandomAccess ?
                new RandomAccessSubList<>(this, fromIndex, toIndex) :
                new SubList<>(this, fromIndex, toIndex));
    }
    public boolean equals(Object o) {...}
    public int hashCode() {...}
    private class Itr implements Iterator<E> {...}
    private class ListItr extends Itr implements ListIterator<E> {...}
    class SubList<E> extends AbstractList<E> {...}
    class RandomAccessSubList<E> extends SubList<E> 
        implements RandomAccess {...}
}

几个内部类及对应功能：

Itr ：迭代器的普通实现，顺序迭代
ListItr ：迭代器实现了 ListIterator ，即支持向前，也支持向后迭代
SubList ：AbstractList 列表的一部分，从开始到结束索引这部分的列表
RandomAccessSubList ：支持随机访问

`AbstractSequentialList` 抽象类

public abstract class AbstractSequentialList<E> extends AbstractList<E> {
    protected AbstractSequentialList() {}
    public E get(int index) {
        try {
            return listIterator(index).next();
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }
    public E set(int index, E element) {
        try {
            ListIterator<E> e = listIterator(index);
            E oldVal = e.next();
            e.set(element);
            return oldVal;
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }
    public void add(int index, E element) {...}
    public E remove(int index) {...}
    public boolean addAll(int index, Collection<? extends E> c) {...}
    public Iterator<E> iterator() {
        return listIterator();
    }
    public abstract ListIterator<E> listIterator(int index);
}

AbstractSequentialList 抽象类继承了 AbstractList，重写了添加、删除、获取、设置等方法，从具体实现可以看出它只支持按次序访问；而 AbstractList 还支持随机访问的。唯一的抽象方法是 listIterator ，按照索引返回 ListIterator 迭代器。

`AbstractQueue` 抽象类

public abstract class AbstractQueue<E>
    extends AbstractCollection<E>
    implements Queue<E> {
    
    protected AbstractQueue() {}
    public boolean add(E e) {
        if (offer(e))
            return true;
        else
            throw new IllegalStateException("Queue full");
    }
    public E remove() {
        E x = poll();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }
    public E element() {
        E x = peek();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }
    public void clear() {
        while (poll() != null)
            ;
    }
    public boolean addAll(Collection<? extends E> c) {...}
}

AbstractQueue 抽象类实现了 Queue 接口的 add, remove, element 三个方法；Queue 接口定义的其他方法由子类去实现。

`AbstractSet` 抽象类

public abstract class AbstractSet<E> extends AbstractCollection<E> 
    implements Set<E> {

    protected AbstractSet() {}
    public boolean equals(Object o) {...}
    public int hashCode() {...}
    public boolean removeAll(Collection<?> c) {...}
}

AbstractSet 抽象类仅实现了 equals, hashCode, removeAll 三个方法。

`AbstractMap` 抽象类

public abstract class AbstractMap<K,V> implements Map<K,V> {

    protected AbstractMap() {}
    public int size() {
        return entrySet().size();
    }
    public boolean isEmpty() {
        return size() == 0;
    }
    public boolean containsValue(Object value) {...}
    public boolean containsKey(Object key) {...}
    public V get(Object key) {...}
    public V put(K key, V value) {
        throw new UnsupportedOperationException();
    }
    public V remove(Object key) {...}
    public void putAll(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
            put(e.getKey(), e.getValue());
    }
    public void clear() {
        entrySet().clear();
    }
    transient volatile Set<K>        keySet;
    transient volatile Collection<V> values;
    public Set<K> keySet() {...}
    public Collection<V> values() {...}
    public abstract Set<Entry<K,V>> entrySet();
    public boolean equals(Object o) {...}
    public int hashCode() {...}
    public String toString() {...}
    protected Object clone() throws CloneNotSupportedException {...}
    private static boolean eq(Object o1, Object o2) {
        return o1 == null ? o2 == null : o1.equals(o2);
    }
    public static class SimpleEntry<K,V>
        implements Entry<K,V>, java.io.Serializable {...}
    public static class SimpleImmutableEntry<K,V>
        implements Entry<K,V>, java.io.Serializable {...}
}

两个内部类，实现了 Entry 元素接口：

SimpleEntry ：可以通过 set 修改值
SimpleImmutableEntry ：线程安全，不能通过 set 修改元素的值

AbstractMap 抽象类中，定义了数据存储方式：

Set<K> keySet ：存储键，键是不可重复的，所以使用了 Set
Collection<V> values ：存储值，普通集合满足

实现类分类

常用集合实现类

存储方式分类

任何数据结构的数据存储都只有两种：数组和链表；并基于这两种衍生出其他结构：树，hash 表，图等。本文介绍的集合，就按照其存储方式有：

Hash table 哈希表实现：HashMap, HashSet
Array 数组实现：ArrayList, ArrayDeque
Tree 树实现：TreeMap, TreeSet
Linked list 链表实现：LinkedList
Hash table + Linked list 哈希表加链表混合实现：LinkedHashMap, LinkedHashSet

按照接口分类

List 接口：ArrayList, LinkedList, Vector, Stack
Set 接口：HashSet, TreeSet, LinkedHashSet, EnumSet
Map 接口：HashMap, TreeMap, LinkedHashMap, EnumMap
Queue/Deque 接口：ArrayDeque, LinkedList

`ArrayList` 及集合操作

定义

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
    ...
    private static final int DEFAULT_CAPACITY = 10;
    transient Object[] elementData;
    // 动态数组的实际大小  
    private int size;
    ...
}

ArrayList 的特点：

它是一个列表，支持随机访问，也支持顺序访问
是一个数组队列，支持容量动态扩展，每次扩展 1.5 倍
Object[] elementData 数组存储所有的元素，默认容量大小为 10
size 是动态数组的实际大小
不是线程安全的

遍历方式

Iterator iterator = lists.iterator();
while (iterator.hasNext()) {
    value = (Integer) iterator.next();
    System.out.print(value + " ");
}

// Random
for (int i = 0; i < lists.size(); i++){
    value = lists.get(i);
    System.out.print(value + " ");
}

// for-each
for (Integer element : lists){
    System.out.print(element + " ");
}

不管是哪种遍历方式，访问顺序都是一样的，都是按照存入顺序访问的。集合中 for-each 访问效率是最高的，实际测试 ArrayList 也是如此。

数组转换

1 2	Object[] toArray(); <T> T[] toArray(T[] contents);

其中 toArray() 可能会抛出现类型转换异常，通常使用泛型 toArray 实现：

1	Integer[] values = lists.toArray(new Integer[0]);

`fail-fast` 机制

fail-fast 机制是集合 Collection 中的一种错误机制，当多个线程对同一个集合的内容进行操作时，就可能会产生 fail-fast 事件：即抛出 ConcurrentModificationException 异常。

private void testFailFast(){
    new Thread(new Runnable() {
        @Override
        public void run() {
            for (Integer element : lists){
                System.out.print(element + " ");
            }
            System.out.println();
        }
    }).start();
    new Thread(new Runnable() {
        @Override
        public void run() {
            lists.remove(300);
        }
    }).start();
}

示例中，在线程遍历集合数据时，另一个线程删除了集合中的一个数据，因为 ArrayList 并不是线程安全的，所以会产生 fail-fast 事件。可以使用 concurrent 包中的 CopyOnWriterArrayList 来代替。

常用集合实现类

`LinkedList`

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
    
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    ...
}

LinkedList 的特点：

数据存储结构是链表实现，链表中每个元素使用 Node 表示，它记录了链表前后的元素，以及元素当前值
first 表示链表头结点；last 表示链表尾节点；size 表示链表中元素个数
链表顺序访问效率会非常高，随机访问需要遍历链表效率低
实现了 List 接口，并继承了 AbstractSequentialList，也就是可以当做列表使用；支持随机访问和顺序访问
实现了 Deque 接口，也就是可以当做双端队列使用，*实现了栈 LIFO 和队列 FIFO *两种数据结构
不是线程安全的

`Vector`

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    
    protected Object[] elementData;
    protected int elementCount;
    ...
    public synchronized int size() {...}
    public synchronized boolean isEmpty() {...}
    ...
}

Vector 的特点：

继承了 AbstractList 并实现了 List 接口，所以它是一个列表
Object[] elementData 数组存储所有的元素，该列表使用方法同 ArrayList 类似
所有的方法都是用了 synchronized 关键字，也就是说 Vector 是线程安全的

`Stack`

public class Stack<E> extends Vector<E> {
    public Stack() {}
    public E push(E item) {...}
    public synchronized E pop() {...}
    public synchronized E peek() {...}
    public boolean empty() {...}
    public synchronized int search(Object o) {...}
    ...
}

Stack 的特点：

继承了 Vector ，也就是说实质上只是一个同步的 ArrayList
实现了 push, pop, peek 方法，即可以当做栈来使用，可以认为是一个同步栈

`HashMap`

1 2	public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {...}

HashMap 核心是使用了”数组+链表”的存储方式，使用拉链法解决冲突（将冲突的 key 的对象放入链表中），Java 1.8 中链表长度大于 8 时，链表转换为红黑树结构；参考：Java HashMap 简介。
HashMap 的 key, value 都可以为 null ；但只允许出现一个为 null 的键。

`LinkedHashMap`

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V> {
    
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

    transient LinkedHashMap.Entry<K,V> head;
    transient LinkedHashMap.Entry<K,V> tail;

    final boolean accessOrder;
    
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }
    
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }
    
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }
    
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
    
    ...
    
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }
    
    // 新建节点，新节点会插入链表尾部
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }
    
    // 如果按照访问顺序，每次读取一个元素时都会重新排序
    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }
    
    // 访问后将该元素移动到链表尾部
    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {...}
        ...
    }
    
    abstract class LinkedHashIterator {
        LinkedHashMap.Entry<K,V> next;
        LinkedHashMap.Entry<K,V> current;
        ...

        LinkedHashIterator() {
            next = head;
            ...
        }

        public final boolean hasNext() {
            return next != null;
        }

        // 迭代器默认使用
        final LinkedHashMap.Entry<K,V> nextNode() {
            LinkedHashMap.Entry<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            current = e;
            next = e.after;
            return e;
        }
        ...
    }
    final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }
    
    final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
        ...
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new LinkedEntryIterator();
        }
        ...
    }
    // 遍历时返回 LinkedEntrySet
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? 
            (entrySet = new LinkedEntrySet()) : es;
    }
    ...
}

LinkedHashMap 类是哈希表+链表实现的集合，有如下几个特点：

继承 HashMap ，所以数据存储和 HashMap 一致
LinkedHashMap.Entry 中增加了 after, before 来记录当前元素的前后元素，形成链表
head, tail 表示元素链表的头和尾
accessOrder 表示 LinkedHashMap 的遍历顺序：true 表示按照访问顺序输出（也就是每次访问一个元素后，这个元素都会移动到链表尾部）， false 表示按照插入顺序输出（有序性）；该变量是 final 的，只在构造方法中赋值，默认为 false
newNode 新建节点时，除了存储数据，同时会将该节点插入链表尾部
LinkedEntrySet 遍历时返回的数据集，数据迭代器是按照链表顺序输出的

accessOrder 特性：

访问顺序：利用这个特性可以实现 LRU: Least Recently Used 缓存，即最近最少使用原则；链表尾总是保存最近使用的元素，当数据过多时，总是删除链表头部元素
插入顺序：解决了 HashMap 元素随机遍历的问题，可以按照插入顺序输出元素

遍历时返回的是 LinkedEntrySet，而它使用的迭代器为 LinkedEntryIterator ，迭代器中重写了访问下一个元素的方式， nexNode 会从链表头部开始逐个访问。也就是说，遍历始终是从链表头部到尾部的：

插入顺序输出：当新建节点 newNode 时，该节点同时会插入链表尾部，即链表维持了插入顺序
访问顺序输出：当访问了一个节点后 get，会同时将被访问节点移动到尾部 afterNodeAccess，即链表维护了访问顺序（没有被访问过的还是插入顺序）

`HashTable`

1
2
3

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {...}

HashTable 是一个线程安全的散列表，所有的方法都有 synchronized 关键字，但是通常推荐使用并发包中的 ConcurrentHashMap 。

`TreeMap`

1
2
3

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable {...}

TreeMap 类是红黑树的 Java 实现，存储有序的键值对；参考算法 - 红黑树。

`HashSet`

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    ...
    private transient HashMap<E,Object> map;
    
    public HashSet() {
        map = new HashMap<>();
    }
    
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
    
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }
    
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }
    
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
    
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }
    ...
}

HashSet 表示没有重复元素的集合，它是由 HashMap 来实现数据存储的，所以不保证元素的顺序。有如下几个特点：

HashSet 公开构造方法，默认使用的是 HashMap 存储数据；数据是无序的
HashSet 还有一个包内可见的构造方法，主要是供子类 LinkedHashSet 调用的，使用的是 LinkedHashMap 来存储数据；数据是有序的
HashSet 的每个元素对应 HashMap 中一个 key ，遍历时即是遍历所有的 key

`LinkedHashSet`

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    ...
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }
    public LinkedHashSet() {
        super(16, .75f, true);
    }
    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }
    ...
}

LinkedHashSet 继承 HashSet，并没有提供额外的功能，仅仅是构造方法调用父类设置容量、装载因子等，而最大的特点是只调用父类包内可见构造方法，即使用 LinkedHashMap 来存储数据，所以数据是有序的。

`TreeSet`

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {
    
    private transient NavigableMap<E,Object> m;
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }
    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }
    ...
}

TreeSet 表示有序集合，从构造方法可以看出，它是由 TreeMap 实现的有序性。

`ArrayDeque`

public class ArrayDeque<E> extends AbstractCollection<E>
            implements Deque<E>, Cloneable, Serializable {

    transient Object[] elements;
    transient int head;
    transient int tail;
    ...
}

ArrayDeque 类是双端队列的数组实现：

Object[] elements 数组存储双端队列元素
head, tail 表示队头和队尾索引

`PriorityQueue`

1 2	public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {...}

PriorityQueue 类是优先队列的 Java 实现，默认为小根堆；参考算法 - 优先队列 - 二叉堆。

工具类

`Arrays`

public class Arrays {
    
    // 普通排序
    public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }
    public static void sort(...) {...}
    
    // 并行排序
    public static void parallelSort(int[] a) {
        int n = a.length, p, g;
        if (n <= MIN_ARRAY_SORT_GRAN ||
            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
            DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
        else
            new ArraysParallelSortHelpers.FJInt.Sorter
                (null, a, new int[n], 0, n, 0,
                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
                 MIN_ARRAY_SORT_GRAN : g).invoke();
    }
    public static void parallelSort(...) {...}
    
    // 并行计算
    public static <T> void parallelPrefix(T[] array, 
            BinaryOperator<T> op) {
        Objects.requireNonNull(op);
        if (array.length > 0)
            new ArrayPrefixHelpers.CumulateTask<>
                    (null, op, array, 0, array.length).invoke();
    }
    public static <T> void parallelPrefix(...) {...}

    // 二分查找
    public static int binarySearch(int[] a, int key) {
        return binarySearch0(a, 0, a.length, key);
    }
    public static int binarySearch(...) {...}
    
    // 比较数组是否相同
    public static boolean equals(int[] a, int[] a2) {
        if (a==a2)
            return true;
        if (a==null || a2==null)
            return false;

        int length = a.length;
        if (a2.length != length)
            return false;

        for (int i=0; i<length; i++)
            if (a[i] != a2[i])
                return false;

        return true;
    }
    public static boolean equals(...) {...}
    
    // 数据填充
    public static void fill(int[] a, int val) {
        for (int i = 0, len = a.length; i < len; i++)
            a[i] = val;
    }
    public static void fill(...) {...}
    
    // 数组拷贝
    public static int[] copyOf(int[] original, int newLength) {
        int[] copy = new int[newLength];
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }
    public static int[] copyOf(...) {...}
    public static int[] copyOfRange(int[] original, int from, int to) {...}
    
    // 数组转换为列表  
    public static <T> List<T> asList(T... a) {...}
    
    // 数组计算 hashCode
    public static int hashCode(int a[]) {
        if (a == null)
            return 0;

        int result = 1;
        for (int element : a)
            result = 31 * result + element;

        return result;
    }
    public static int hashCode(...) {...}
    
    public static void setAll(int[] array, IntUnaryOperator generator) {
        Objects.requireNonNull(generator);
        for (int i = 0; i < array.length; i++)
            array[i] = generator.applyAsInt(i);
    }
    public static void parallelSetAll(int[] array, 
        IntUnaryOperator generator) {
        Objects.requireNonNull(generator);
        IntStream.range(0, array.length)
                  .parallel()
                  .forEach(i -> { array[i] = generator.applyAsInt(i); });
    }
    public static void setAll(...) {...}
    public static void parallelSetAll(...) {...}
    
    // 转换为流  
    public static IntStream stream(int[] array) {
        return stream(array, 0, array.length);
    }
    public static ... stream(...) {...}
    ...
}

Arrays 主要提供的功能：

sort 排序：使用 DualPivotQuicksort 对数组快速排序
parallelSort 并行排序：数据足够大时，使用 ArraysParallelSortHelpers 来排序，通过 ForkJoinTask 多线程排序
parallelPrefix 并行计算：对数组的每个元素，执行 BinaryOperator 二元计算（计算结果参与下一个元素继续计算）；也是多线程操作
binarySearch 对有序数组进行二分查找
equals 对给定两个数组进行比较，数组元素是否完全相同
fill 使用给定值对数组进行填充
copyOf 拷贝：将原有数组拷贝到指定新长度的数组中；数组动态扩容经常会有数组拷贝
asList 数组转换为列表
hashCode 计算给定数组的 hashCode
setAll/parallelSetAll 根据给定计算公式，更新数组每个元素
stream 数组转换为流

`Collections`

public class Collections {
    
    public static <T extends Comparable<? super T>> void sort(List<T> list){
        list.sort(null);
    }
    
    public static <T> int binarySearch(...) {...}
    public static void reverse(List<?> list) {...}
    public static void shuffle(List<?> list) {...}
    public static void swap(List<?> list, int i, int j) {...}
    public static <T> void fill(List<? super T> list, T obj) {...}
    public static <T> void copy(List<? super T> dest, 
        List<? extends T> src) {...}
    public static void rotate(List<?> list, int distance) {...}
    public static <T> boolean replaceAll(List<T> list, 
        T oldVal, T newVal) {...}
    public static int indexOfSubList(List<?> source, List<?> target){...}
    public static int lastIndexOfSubList(List<?> source, 
        List<?> target) {...}
    
    public static <T extends Object & Comparable<? super T>> T 
        min(Collection<? extends T> coll) {...}
    public static <T extends Object & Comparable<? super T>> T 
        max(Collection<? extends T> coll) {...}
        
    public static <T> Collection<T> unmodifiableCollection(
            Collection<? extends T> c) {
        return new UnmodifiableCollection<>(c);
    }
    public static <T> ...<T> unmodifiable...(...){...}
    
    public static <T> Collection<T> synchronizedCollection(
            Collection<T> c) {
        return new SynchronizedCollection<>(c);
    }
    public static <T> ...<T> synchronized...(...){...}
    
    public static <E> Collection<E> checkedCollection(
            Collection<E> c, Class<E> type) {
        return new CheckedCollection<>(c, type);
    }
    public static <E> ...<E> checked...(...){...}
    
    public static final <T> List<T> emptyList() {
        return (List<T>) EMPTY_LIST;
    }
    public static final <T> ...<T> empty...() {...}
    
    public static <T> List<T> singletonList(T o) {
        return new SingletonList<>(o);
    }
    public static <T> ...<T> singleton...(...) {...}
    
    public static int frequency(Collection<?> c, Object o) {...}
    public static boolean disjoint(Collection<?> c1, 
        Collection<?> c2) {...}
    
    public static <T> Queue<T> asLifoQueue(Deque<T> deque) {
        return new AsLIFOQueue<>(deque);
    }
    ...
}

Collections 主要提供的功能：

sort 列表按照给定比较器排序
binarySearch 已经排好序的列表，二分查找
reverse 反转列表中的元素
shuffle 将列表随机移位；特别是算法中，避免出现最坏时间复杂度，通常需要将输入序列打乱
swap 交换列表中的两个元素
fill 列表中填充指定元素
copy 拷贝列表中的元素到另一个列表
rotate 将列表中的元素循环移位 distance ，默认向左移动
indexOfSubList 如果子列表存在，返回索引值
replaceAll 将列表中所有指定旧元素替换为新元素
min, max 找出集合中的最小值，最大值
unmodifiableCollection 根据给定集合，返回一个不可修改的集合；相当于集合每个元素及状态 final
synchronizedCollection 根据给定集合，返回一个同步操作的集合；该集合上所有的操作都是同步的，线程安全的
checkedCollection 根据给定集合，返回一个类型检查的集合；集合上的添加等操作，会做类型检查
emptyList 返回一个空的列表；返回空集合操作
singletonList 返回单个元素列表；单个元素集合操作
frequency 返回集合中元素出现的次数
disjoint 判断两个集合是否有共同元素；有则返回 true
asLifoQueue 双端队列转换为 LIFO 先进先出队列

集合间异同

集合和数组

数组
大小固定，同一个数组只能存放一种基本类型或者对象。定义时需要声明存储类型。
集合
大小动态改变，只能存储对象。集合是对数组的封装，所以数组比集合存取速度要快。

// 1. 数组
int[] a = new int[5];
String[] s = new String[1];
// 2. 集合
List<String> list = new ArrayList<String>();
Map<String, String> map = new HashMap<String, String>();
// List存放Map数据列表
List<Map<String, Object>> myData = new ArrayList<Map<String, Object>>();

`List` 接口

AbstractList, AbstractSequentialList
AbstractList 既支持随机访问，也支持顺序访问；AbstractSequentialList 只支持顺序访问。
ArrayList
数组列表，支持数组动态扩容；数组特性：访问效率高，插入和删除需要移动数据效率低；非线程安全。
LinkedList
链表列表，双向链表；链表特性：插入和删除效率高，访问效率低；非线程安全。
Vector
数组列表的同步实现，拥有 ArrayList 使用特性，但是是线程安全的。
Stack
继承 Vector，模拟了栈的特性 LIFO ，是线程安全的。

`Map` 接口

Map, SortedMap, NavigableMap
Map 的三个基本接口；SoretedMap 表示存储有序的键值对；NavigableMap 继承了 SoretedMap ，额外提供键值对导航方法，支持大于、小于、小于等于等操作。
HashMap
基于拉链法实现的散列表，使用数组+链表存储键值对；链表长度大于 8 时转换为红黑树；非线程安全。
HashTable
线程安全的散列表，不过通常建议使用并发包中的 ConcurrentHashMap 来代替。
TreeMap
红黑树的 Java 实现，散列表中存储的键值对是无序的，但按大小排序；非线程安全。
LinkedHashMap
实现方式为：链表+散列表；HashMap 存储数据，链表保持元素的有序性；非线程安全。

`Set` 接口

HashSet
HashSet 依赖于 HashMap，它实际上是通过 HashMap 实现的。HashSet 中的元素是无序的；非线程安全。
TreeSet
TreeSet 依赖于 TreeMap，它实际上是通过 TreeMap 实现的。TreeSet 中的元素是无序的，但按大小排序；非线程安全。
LinkedHashSet
HashSet 依赖于 LinkedHashMap，它实际上是通过 LinkedHashMap 实现的。LinkedHashSet 的元素是有序的；非线程安全。

`Queue/Deque` 接口

LinkedList
双端队列的链表实现。
ArrayDeque
双端队列的数组实现。
PriorityQueue
优先队列的 Java 实现，默认为小根堆。

小结

在使用中，集合的选取主要从多线程环境、数据访问的特性（数组、链表）、有序性、使用哪种接口来考虑。

其他

有序无序

有序、无序是指在进行插入操作时，插入位置的顺序性；先加入的元素位置在前，后加入的元素位置在后，这就是有序，反之为无序。
所以通常所说 List 是有序的，指的是加入和删除元素都是按照加入顺序进行；而 Set 通常是通过 Map 来实现的，元素加入顺序为随机的。
而和有序性容易混淆的是排序，排序是指集合内的元素是否按照升序或降序来排序，和插入顺序并没有关系。

动态扩容特性

如果使用数组来存储元素，集合默认都是支持动态扩容的，但是动态扩容涉及到整个数组拷贝，所以在使用集合前，预估集合数据大小，减少扩容次数能提高效率。

线程安全

java.util 包中的集合大部分都不是线程安全的：ArrayList, LinkedList, HashMap, TreeMap, HashSet, TreeSet, ArrayDeque, PriorityQueue 等，只有 Vector, Stack, HashTable 是线程安全的。
在多线程环境下，建议使用并发包中的集合：CopyOnWriterArrayList, ConcurrentHashMap 等。

遍历

通常 Collection 接口实现类都使用 for-each 遍历；Map 接口实现类使用 entrySet 来遍历。

// 1. 遍历 Collection
ArrayList<Integer> lists = new ArrayList<>();
...
for (Integer element : lists){
    System.out.print(element + " ");
}

// 2. 遍历 Map 
Map<String, String> map = new HashMap<String, String>();
...
for(Map.Entry<String, String> entry : map.entrySet()){
    String key = entry.getKey();
    String value = entry.getValue();
    // 也可以通过key，获取value
    // String value = map.get(key);
}

后续

每个集合类源码分析
并发包中的集合
Google Guava 中的集合

基础

概念

for-each

Iterator

Iterable

接口

Collection 接口

List 接口

Queue 接口

Deque 接口

Set 接口

Map 接口

SoretedSet 接口

NavigableSet 接口

SoretedMap 接口

NavigableMap 接口

抽象实现类

AbstractCollection 抽象类

AbstractList 抽象类

AbstractSequentialList 抽象类

AbstractQueue 抽象类

AbstractSet 抽象类

AbstractMap 抽象类

实现类分类

常用集合实现类

存储方式分类

按照接口分类

ArrayList 及集合操作

定义

遍历方式

数组转换

fail-fast 机制

常用集合实现类

LinkedList

Vector

Stack

HashMap

LinkedHashMap

HashTable

TreeMap

HashSet

LinkedHashSet

TreeSet

ArrayDeque

PriorityQueue

工具类

Arrays

Collections

集合间异同

集合和数组

List 接口

Map 接口

Set 接口

Queue/Deque 接口

小结

其他

有序无序

动态扩容特性

线程安全

遍历

后续

参考文档

`Collection` 接口

`List` 接口

`Queue` 接口

`Deque` 接口

`Set` 接口

`Map` 接口

`SoretedSet` 接口

`NavigableSet` 接口

`SoretedMap` 接口

`NavigableMap` 接口

`AbstractCollection` 抽象类

`AbstractList` 抽象类

`AbstractSequentialList` 抽象类

`AbstractQueue` 抽象类

`AbstractSet` 抽象类

`AbstractMap` 抽象类

`ArrayList` 及集合操作

`fail-fast` 机制

`LinkedList`

`Vector`

`Stack`

`HashMap`

`LinkedHashMap`

`HashTable`

`TreeMap`

`HashSet`

`LinkedHashSet`

`TreeSet`

`ArrayDeque`

`PriorityQueue`

`Arrays`

`Collections`

`List` 接口

`Map` 接口

`Set` 接口

`Queue/Deque` 接口