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 引入的特性。其语法如下：

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 接口

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 也是如此。

数组转换

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

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

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

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

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

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

TreeMap

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

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 中的集合

参考文档

• Java tutorial
• Java 8 API
• Java 8 API: Collection
• Java 8 API: Map
• Java 集合框架
• 集合类图
• IBM 系列：Java 集合框架
• Java集合之LinkedHashMap
• Java集合类: Set、List、Map、Queue使用场景梳理
• Java 集合常见问题
• Java 集合系列
• Java8 增强工具类 Arrays 笔记
• 集合系列 Arrays和Collections工具类