1// rt.jar/java/util/Collection.java
 2public interface Collection<E> extends Iterable<E> {
 3    // 返回元素数量
 4    int size();
 5    // 判断集合是否为空
 6    boolean isEmpty();
 7    // 判断集合中是否有该元素
 8    // 如果待判定的元素类型兼容容器中的元素类型，抛出ClassCastException异常
 9    // 如何元素为空，但是结合不允许为空，抛出NullPointerException异常
10    boolean contains(Object o);
11    // 获取元素的迭代器
12    Iterator<E> iterator();
13    // 返回集合中所有元素的对象数组
14    Object[] toArray();
15    // 返回包含指定元素的数组
16    <T> T[] toArray(T[] a);
17    // 添加元素
18    boolean add(E e);
19    // 移除元素
20    boolean remove(Object o);
21    // 集合中是否都包含要查询的所有元素
22    boolean containsAll(Collection<?> c);
23    // 批量添加元素
24    boolean addAll(Collection<? extends E> c);
25    // 批量移除元素
26    boolean removeAll(Collection<?> c);
27    // 按条件移除元素，条件需要实现Predicate接口，重写test方法
28    default boolean removeIf(Predicate<? super E> filter) {...}
29    // 保留指定的元素
30    boolean retainAll(Collection<?> c);
31    // 清空集合
32    void clear();
33    // 判断集合是否相等
34    boolean equals(Object o);
35    int hashCode();
36    // java8新增的接口
37    @Override
38    default Spliterator<E> spliterator() {
39        return Spliterators.spliterator(this, 0);
40    }
41
42    // java8新增的接口，将集合转为流
43    default Stream<E> stream() {
44        return StreamSupport.stream(spliterator(), false);
45    }
46
47    // java8新增的接口，将集合转为并行操作的流
48    default Stream<E> parallelStream() {
49        return StreamSupport.stream(spliterator(), true);
50    }
51}

 1public interface Iterator<E> {
 2    // 判断集合中是否还有更多的元素
 3    boolean hasNext();
 4    // 获取集合中迭代器获取到的元素
 5    E next();
 6    // 移除集合中迭代器当前的元素
 7    default void remove() {
 8        throw new UnsupportedOperationException("remove");
 9    }
10    // java8新增的接口，对元素执行某个动作
11    default void forEachRemaining(Consumer<? super E> action) {
12      ...
13    }
14}

 1public interface Map<K,V> {
 2    // 返回元素个数
 3    int size();
 4    // 是否为空
 5    boolean isEmpty();
 6    // 是否包含某个key
 7    boolean containsKey(Object key);
 8    // 是否包含某个value
 9    boolean containsValue(Object value);
10    // 根据key获取value
11    V get(Object key);
12    // 设置key对应的value
13    V put(K key, V value);
14    // 移除某个key
15    V remove(Object key);
16    // 批量设置
17    void putAll(Map<? extends K, ? extends V> m);
18    // 清空所有数据
19    void clear();
20    // 获取所有的key集合
21    Set<K> keySet();
22    // 获取所有的value列表
23    Collection<V> values();
24    // Entry是Map的内部接口，表示map中的一个实体（key-value对）
25    Set<Map.Entry<K, V>> entrySet();
26    // 内部接口，保存key-value对
27    interface Entry<K,V> {
28        // 获取一个实体的key
29        K getKey();
30        // 获取value
31        V getValue();
32        // 设置value
33        V setValue(V value);
34        boolean equals(Object o);
35        int hashCode();
36        ...
37    }
38
39    boolean equals(Object o);
40    int hashCode();
41    // 获取key对应value，获取不到就返回默认值
42    default V getOrDefault(Object key, V defaultValue) {...}
43    // java8新增的接口， 遍历元素并对每个元素执行需要执行的动作
44    default void forEach(BiConsumer<? super K, ? super V> action) {...}
45    // java8新增的接口，对满足函数要求的元素替代为新值
46    default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {...}
47    // 如果元素存在直接返回，不存在就插入
48    default V putIfAbsent(K key, V value) {...}
49    // 移除指定的key和value键值对
50    default boolean remove(Object key, Object value) {...}
51    // 替换旧值为新值，旧值必须存在，新值必须不为null
52    default boolean replace(K key, V oldValue, V newValue) {...}
53    // 替换值，不管旧值是什么
54    default V replace(K key, V value) {...}
55    // 通过给的的方法，设置新值
56    default V computeIfAbsent(K key,
57            Function<? super K, ? extends V> mappingFunction) {...}
58
59    default V computeIfPresent(K key,
60            BiFunction<? super K, ? super V, ? extends V> remappingFunction) {...}
61
62    default V compute(K key,
63            BiFunction<? super K, ? super V, ? extends V> remappingFunction) {...}
64
65    //
66    default V merge(K key, V value,
67            BiFunction<? super V, ? super V, ? extends V> remappingFunction) {...}
68}

 1public interface Set<E> extends Collection<E> {
 2    int size();
 3    boolean isEmpty();
 4    boolean contains(Object o);
 5    Iterator<E> iterator();
 6    Object[] toArray();
 7    <T> T[] toArray(T[] a);
 8    boolean add(E e);
 9    boolean remove(Object o);
10    boolean containsAll(Collection<?> c);
11    boolean addAll(Collection<? extends E> c);
12    boolean retainAll(Collection<?> c);
13    boolean removeAll(Collection<?> c);
14    void clear();
15    boolean equals(Object o);
16    int hashCode();
17
18    default Spliterator<E> spliterator() {...}
19}

 1public interface List<E> extends Collection<E> {
 2    ...
 3    // java8新增的接口，根据operator指定的计算规则重新设置集合中所有的元素
 4    default void replaceAll(UnaryOperator<E> operator) {...}
 5    // java8新增的接口，根据Comparator参数对list集合的元素排序
 6    default void sort(Comparator<? super E> c) {...}
 7    // 获取list中的特定索引的元素
 8    E get(int index);
 9    // 替换特定位置的元素
10    E set(int index, E element);
11    // 索引位置插入元素
12    void add(int index, E element);
13    // 移除索引位置元素
14    E remove(int index);
15    // 元素在list中首次出现的索引
16    int indexOf(Object o);
17    // 元素在list中最后一次出现的索引
18    int lastIndexOf(Object o);
19    // 返回list迭代器
20    ListIterator<E> listIterator();
21    // 返回从指定的索引开始的迭代器
22    ListIterator<E> listIterator(int index);
23    // 获取指定范围的子元素列表，包括fromIndex，不包括toIndex
24    List<E> subList(int fromIndex, int toIndex);
25
26    default Spliterator<E> spliterator() {...}
27}

 1public interface Queue<E> extends Collection<E> {
 2    // 队列尾部插入元素，空间不足时抛出异常
 3    boolean add(E e);
 4    // 队列尾部插入元素，空间不足不会抛出异常
 5    boolean offer(E e);
 6    // 返回并移除队列头部的元素，如果队列为空将抛出异常
 7    E remove();
 8    // 返回并移除队列头部的元素，如果队列为空将返回null
 9    E poll();
10    // 返回队列头部元素，但是不移除，队列为空抛出异常
11    E element();
12    // 返回头部元素，但是不移除，队列为空返回null
13    E peek();
14}

 1public class HashSet<E>
 2    extends AbstractSet<E>
 3    implements Set<E>, Cloneable, java.io.Serializable
 4{
 5    // HashSet的底层实现是HashMap，内部定义了一个HashMap存储元素
 6    private transient HashMap<E,Object> map;
 7
 8    // 空的object，作为HashSet底层存储的HashMap中所有的value
 9    private static final Object PRESENT = new Object();
10
11    // 构造函数new一个HashMap对象
12    public HashSet() {
13        map = new HashMap<>();
14    }
15    // 这里内部使用LinkedHashMap作为底层存储结构
16    // 私有的方法，仅仅提供给LinkedHashSet使用
17    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
18        map = new LinkedHashMap<>(initialCapacity, loadFactor);
19    }
20}

 1// 只有四个构造函数
 2public class LinkedHashSet<E>
 3    extends HashSet<E>
 4    implements Set<E>, Cloneable, java.io.Serializable {
 5    // 这里调用父类的构造函数，也就是前面介绍过的内部new的LinkedHashMap来存储底层数据
 6    public LinkedHashSet(int initialCapacity, float loadFactor) {
 7        super(initialCapacity, loadFactor, true);
 8    }
 9    public LinkedHashSet(int initialCapacity) {
10        super(initialCapacity, .75f, true);
11    }
12    public LinkedHashSet() {
13        super(16, .75f, true);
14    }
15    public LinkedHashSet(Collection<? extends E> c) {
16        super(Math.max(2*c.size(), 11), .75f, true);
17        addAll(c);
18    }
19    @Override
20    public Spliterator<E> spliterator() {
21        return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
22    }
23}

 1public class TreeSet<E> extends AbstractSet<E>
 2    implements NavigableSet<E>, Cloneable, java.io.Serializable
 3{
 4    // 底层使用NavigableMap存储
 5    private transient NavigableMap<E,Object> m;
 6    // value值
 7    private static final Object PRESENT = new Object();
 8
 9    public TreeSet() {
10        this(new TreeMap<E,Object>());
11    }
12    public Iterator<E> iterator() {
13        return m.navigableKeySet().iterator();
14    }
15    public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
16                                  E toElement,   boolean toInclusive) {
17        return new TreeSet<>(m.subMap(fromElement, fromInclusive,
18                                       toElement,   toInclusive));
19    }
20    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
21        return new TreeSet<>(m.headMap(toElement, inclusive));
22    }
23
24    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
25        return new TreeSet<>(m.tailMap(fromElement, inclusive));
26    }
27    // 返回子元素集合，包括from，不包括to
28    public SortedSet<E> subSet(E fromElement, E toElement) {
29        return subSet(fromElement, true, toElement, false);
30    }
31
32    public SortedSet<E> headSet(E toElement) {
33        return headSet(toElement, false);
34    }
35
36    public SortedSet<E> tailSet(E fromElement) {
37        return tailSet(fromElement, true);
38    }
39    // 返回元素进行比较的比较器，内部返回的是NavigableMap的比较器
40    public Comparator<? super E> comparator() {
41        return m.comparator();
42    }
43    // 返回set中第一个元素
44    public E first() {
45        return m.firstKey();
46    }
47    // 返回set中最后一个元素
48    public E last() {
49        return m.lastKey();
50    }
51    // 返回小于给定元素的最大元素
52    public E lower(E e) {
53        return m.lowerKey(e);
54    }
55    public E floor(E e) {
56        return m.floorKey(e);
57    }
58    public E ceiling(E e) {
59        return m.ceilingKey(e);
60    }
61    // 返回大于给定元素的最小元素
62    public E higher(E e) {
63        return m.higherKey(e);
64    }
65    public E pollFirst() {
66        Map.Entry<E,?> e = m.pollFirstEntry();
67        return (e == null) ? null : e.getKey();
68    }
69    public E pollLast() {
70        Map.Entry<E,?> e = m.pollLastEntry();
71        return (e == null) ? null : e.getKey();
72    }
73}

 1public interface ListIterator<E> extends Iterator<E> {
 2    // 后向迭代
 3    boolean hasNext();
 4    E next();
 5    // 前向迭代
 6    boolean hasPrevious();
 7    E previous();
 8    // 下一个索引
 9    int nextIndex();
10    // 前一个索引
11    int previousIndex();
12    // 移除元素
13    void remove();
14    // 替换元素
15    void set(E e);
16    // 添加元素
17    void add(E e);
18}

 1public class ArrayList<E> extends AbstractList<E>
 2        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
 3{
 4    // 默认容量为10
 5    private static final int DEFAULT_CAPACITY = 10;
 6    private static final Object[] EMPTY_ELEMENTDATA = {};
 7    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 8    // 底层存储结构为Object数组
 9    transient Object[] elementData; // non-private to simplify nested class access
10    // 元素数量
11    private int size;
12    // 指定容量的ArrayList
13    public ArrayList(int initialCapacity) {
14        if (initialCapacity > 0) {
15            this.elementData = new Object[initialCapacity];
16        } else if (initialCapacity == 0) {
17            this.elementData = EMPTY_ELEMENTDATA;
18        } else {
19            throw new IllegalArgumentException("Illegal Capacity: "+
20                                               initialCapacity);
21        }
22    }
23    // 不指定容量的ArrayList，默认元素数量为10
24    public ArrayList() {
25        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
26    }
27    // 扩容函数，确保能够容纳最小容量的元素数
28    public void ensureCapacity(int minCapacity) {
29        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
30            // any size if not default element table
31            ? 0
32            // larger than default for default empty table. It's already
33            // supposed to be at default size.
34            : DEFAULT_CAPACITY;
35
36        if (minCapacity > minExpand) {
37            ensureExplicitCapacity(minCapacity);
38        }
39    }
40}

 1public class LinkedList<E>
 2    extends AbstractSequentialList<E>
 3    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
 4{
 5    // 链表元素数量
 6    transient int size = 0;
 7    // 链表的表头
 8    transient Node<E> first;
 9    // 链表的表尾
10    transient Node<E> last;
11    // 内部类，Node数据结构
12    private static class Node<E> {
13        // 表示集合元素值
14        E item;
15        // 指向下一个元素
16        Node<E> next;
17        // 指向上一个元素
18        Node<E> prev;
19
20        Node(Node<E> prev, E element, Node<E> next) {
21            this.item = element;
22            this.next = next;
23            this.prev = prev;
24        }
25    }
26    // 元素插入列表表头
27    public void addFirst(E e) {
28        linkFirst(e);
29    }
30    // 追加元素到队列末尾
31    public void addLast(E e) {
32        linkLast(e);
33    }
34    // 获取第一个元素
35     public E getFirst() {
36        final Node<E> f = first;
37        if (f == null)
38            throw new NoSuchElementException();
39        return f.item;
40    }
41    // 获取最后一个元素
42    public E getLast() {
43        final Node<E> l = last;
44        if (l == null)
45            throw new NoSuchElementException();
46        return l.item;
47    }
48    // 列表头部插入指定元素
49    public boolean offerFirst(E e) {
50        addFirst(e);
51        return true;
52    }
53    // 列表末尾插入指定元素
54    public boolean offerLast(E e) {
55        addLast(e);
56        return true;
57    }
58    // 获取列表第一个元素（但是不删除），如果列表为空，返回null
59    public E peekFirst() {
60        final Node<E> f = first;
61        return (f == null) ? null : f.item;
62     }
63    // 获取最后一个元素（但是不删除），如果列表为空，返回null
64    public E peekLast() {
65        final Node<E> l = last;
66        return (l == null) ? null : l.item;
67    }
68
69    // 获取列表第一个元素（并删除），如果列表为空，返回null
70    public E pollFirst() {
71        final Node<E> f = first;
72        return (f == null) ? null : unlinkFirst(f);
73    }
74    // 获取最后一个元素（并删除），如果列表为空，返回null
75    public E pollLast() {
76        final Node<E> l = last;
77        return (l == null) ? null : unlinkLast(l);
78    }
79    // 获取指定索引的Node节点
80    Node<E> node(int index) {
81        // 判断index和list中元素个数的 1/2 做比较，如果小于 size/2, 从前往后找。如果 大于 size/2, 从后往前找
82        if (index < (size >> 1)) {
83            Node<E> x = first;
84            for (int i = 0; i < index; i++)
85                x = x.next;
86            return x;
87        } else {
88            Node<E> x = last;
89            for (int i = size - 1; i > index; i--)
90                x = x.prev;
91            return x;
92        }
93    }
94}

 1public class PriorityQueue<E> extends AbstractQueue<E>
 2    private static final int DEFAULT_INITIAL_CAPACITY = 11;
 3
 4    // 底层实现是对象数组，堆表示数据的大小关系
 5    transient Object[] queue; // non-private to simplify nested class access
 6    // 插入元素
 7    public boolean offer(E e) {
 8        if (e == null)
 9            throw new NullPointerException();
10        modCount++;
11        int i = size;
12        if (i >= queue.length)
13            // 空间不足时，grow扩容
14            grow(i + 1);
15        size = i + 1;
16        if (i == 0)
17            queue[0] = e;
18        else
19            // 插入数据
20            siftUp(i, e);
21        return true;
22    }
23}

 1public interface Deque<E> extends Queue<E> {
 2    // 队列头部插入元素
 3    void addFirst(E e);
 4    // 队列尾部插入元素
 5    void addLast(E e);
 6    boolean offerFirst(E e);
 7    boolean offerLast(E e);
 8    E removeFirst();
 9    E removeLast();
10    E pollFirst();
11    E pollLast();
12    E getFirst();
13    E getLast();
14    E peekFirst();
15    E peekLast();
16    boolean removeFirstOccurrence(Object o);
17    boolean removeLastOccurrence(Object o);
18    boolean add(E e);
19    boolean offer(E e);
20    E remove();
21    E poll();
22    E element();
23    E peek();
24    void push(E e);
25    E pop();
26    boolean remove(Object o);
27    boolean contains(Object o);
28    public int size();
29    Iterator<E> iterator();
30    Iterator<E> descendingIterator();
31
32}

 1public class ArrayDeque<E> extends AbstractCollection<E>
 2                           implements Deque<E>, Cloneable, Serializable
 3{
 4    // 底层存储数据的数组对象
 5    transient Object[] elements; // non-private to simplify nested class access
 6    // 头部索引
 7    transient int head;
 8    // 尾部索引
 9    transient int tail;
10    // 默认容量，设置时设置为2的N次方
11    private static final int MIN_INITIAL_CAPACITY = 8;
12    // 插入元素
13    public void addFirst(E e) {
14        if (e == null)
15            throw new NullPointerException();
16        // head -1 取模操作
17        elements[head = (head - 1) & (elements.length - 1)] = e;
18        if (head == tail)
19            // 头尾指针一样，说明空间满了，需要扩容
20            // 申请一个2倍数量的空间，并将原数据拷贝过去
21            doubleCapacity();
22    }
23    // 扩容空间
24    private void doubleCapacity() {
25        assert head == tail;
26        int p = head;
27        int n = elements.length;
28        // header右边元素个数
29        int r = n - p; // number of elements to the right of p
30        // 空间*2，扩充一倍
31        int newCapacity = n << 1;
32        if (newCapacity < 0)
33            throw new IllegalStateException("Sorry, deque too big");
34        Object[] a = new Object[newCapacity];
35        // 复制右半部分数据
36        System.arraycopy(elements, p, a, 0, r);
37        // 复制左半部分数据
38        System.arraycopy(elements, 0, a, r, p);
39        elements = a;
40        head = 0;
41        tail = n;
42    }
43}

 1public class HashMap<K,V> extends AbstractMap<K,V>
 2{
 3    // 默认容量大小16，必须为2的N次方
 4    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 5    // 最大容量大小
 6    static final int MAXIMUM_CAPACITY = 1 << 30;
 7    // 默认的加载因子，容量自动增加时的扩容阈值。当空间超过容量总值*0.75时，将hash表扩容为两倍
 8    static final float DEFAULT_LOAD_FACTOR = 0.75f;
 9    // 空间扩容的阈值
10    static final int TREEIFY_THRESHOLD = 8;
11    static final int UNTREEIFY_THRESHOLD = 6;
12    static final int MIN_TREEIFY_CAPACITY = 64;
13    // HashMap底层使用的数组，数组中的每个元素是Node，Node是内部类，在下面定义
14    transient Node<K,V>[] table;
15    // 底层存储元素的数据结构
16    static class Node<K,V> implements Map.Entry<K,V> {
17        // key值计算出来的hash值
18        final int hash;
19        // key值
20        final K key;
21        // value值
22        V value;
23        // 下一个节点指针
24        Node<K,V> next;
25        ......
26    }
27
28    // 所有的键值对的集合
29    transient Set<Map.Entry<K,V>> entrySet;
30    // 元素数量
31    transient int size;
32    // hashmap结构被修改的次数
33    transient int modCount;
34    // 阈值，= size * factor
35    int threshold;
36    final float loadFactor;
37
38    // 指定容量和加载因子的构造函数
39    public HashMap(int initialCapacity, float loadFactor) {
40      ......
41    }
42    // 包含子Map的构造函数
43    public HashMap(Map<? extends K, ? extends V> m) {
44        this.loadFactor = DEFAULT_LOAD_FACTOR;
45        putMapEntries(m, false);
46    }
47
48    // 指定容量的构造函数
49    public HashMap(int initialCapacity) {
50        this(initialCapacity, DEFAULT_LOAD_FACTOR);
51    }
52
53    // 默认构造函数
54    public HashMap() {
55        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
56    }
57    ......
58}

 1public class LinkedHashMap<K,V>
 2    extends HashMap<K,V>
 3    implements Map<K,V>
 4{
 5    // 双向循环列表的头节点
 6    transient LinkedHashMap.Entry<K,V> head;
 7    // 双向循环列表的尾节点
 8    transient LinkedHashMap.Entry<K,V> tail;
 9    // true表示最近最少使用次序，false表示插入顺序
10    final boolean accessOrder;
11
12    static class Entry<K,V> extends HashMap.Node<K,V> {
13        // before和after用于维护插入的先后顺序
14        Entry<K,V> before, after;
15        // 调用父类的Entry初始化方法
16        Entry(int hash, K key, V value, Node<K,V> next) {
17            super(hash, key, value, next);
18        }
19    }
20}