集合框架概览

　　Java集合框架由一套设计优良的接口和类组成。高度的封装使我们操作多个数据或对象元素极为方便。所有的Java集合都在java.util包中。
　　在编写程序的过程中，使用到集合类，要根据不同的需求，来决定使用哪种集合类，比如，要经常遍历集合内元素，就要使用List，如果要保证集合中不存在重复的数据，就要用Set;如果要通过某一键来查找某一值，就要使用Map。
Java中集合类主要有两大分支：

1. Collection
2. Map

Collection接口

Colloction接口继承关系

详细的类图结构

1、接口定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public interface Collection<E> extends Iterable<E> {
  int size();

  boolean isEmpty();

  boolean contains(Object var1);

  Iterator<E> iterator();

  Object[] toArray();

  <T> T[] toArray(T[] var1);

  boolean add(E var1);

  boolean remove(Object var1);

  boolean containsAll(Collection<?> var1);

  boolean addAll(Collection<? extends E> var1);

  boolean removeAll(Collection<?> var1);

  default boolean removeIf(Predicate<? super E> var1) {}

  boolean retainAll(Collection<?> var1);

  void clear();

  boolean equals(Object var1);

  int hashCode();

  default Spliterator<E> spliterator() {}

  default Stream<E> stream() {}

  default Stream<E> parallelStream() {}
}

2、Set实现类

Set
　　该类中的元素不按特定方式排序，只是简单的把对象加入集合中，就像往口袋里放东西。
对Set中成员的访问和操作是通过Set中对象的引用进行的，所以集中不能有重复对象。
　　Set也有多种变体，可以实现排序等功能，如TreeSet，它把对象添加到集中的操作将变为按照某种比较规则将其插入到有序的对象序列中。它实现的是SortedSet接口，也就是加入了对象比较的方法。通过对集中的对象迭代，我们可以得到一个升序的对象集合。
HashSet
　　能够快速定位一个元素，要注意的是：存入HashSet中的对象必须实现HashCode()方法；
TreeSet
　　将放入其中的元素按序存放。

3、Queue实现类

Queue
　　用于模拟队列这种数据结构。队列通常是指“先进先出（FIFO）”的容器。队列的头部保存在队列中存放时间最长的元素，尾部保存存放时间最短的元素。新元素插入到队列的尾部，取出元素会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。
PriorityQueue
　　保存队列元素的顺序不是按照元素添加的顺序来保存的，而是在添加元素的时候对元素的大小排序后再保存的。因此在PriorityQueue中使用peek()或pool()取出队列中头部的元素，取出的不是最先添加的元素，而是最小的元素。
Deque
　　该接口是Queue接口的子接口，它代表一个双端队列。
ArrayDeque
　　该类是Deque接口的实现类，ArrayDeque采用了循环数组的方式来完成双端队列的功能。

1. 无限的扩展，自动扩展队列大小的。（当然在不会内存溢出的情况下。）
2. 非线程安全的，不支持并发访问和修改。
3. 支持fast-fail.
4. 作为栈使用的话比比栈要快.
5. 当队列使用比linklist要快。
6. null元素被禁止使用。

4、List实现类

List
　　该接口及其实现类是容量可变的列表，可按索引访问集合中的元素。
列表在数据结构中分别表现为：数组和向量、链表、堆栈、队列。
ArrayList
　　实现一个数组，它的规模可变并且能像链表一样被访问。它提供的功能类似Vector类但不同步，它是以Array方式实现的List，允许快速随机存取。
LinkedList
　　实现一个链表，提供最佳顺序存取，适合插入和移除元素。由这个类定义的链表也可以像栈或队列一样被使用。提供最佳顺序存取，适合插入和移除元素。LinkedList与ArrayList，ArrayDeque的实现机制完全不同，ArrayList和ArrayDeque内部以数组的形式来保存集合中的元素，因此随机访问集合元素时有较好的性能；而LinkedList以链表的形式来保存集合中的元素，因此随机访问集合元素时性能较差，但是插入和删除元素时性能比较出色（只需改变指针所指的地址即可），需要指出的是，虽然Vector也是以数组的形式来存储集合但因为它实现了线程同步（而且实现的机制不好），故各方面的性能都比较差。
Vector
　　Vector同步了每个方法，你几乎从不要那样做，通常有想要同步的是整个操作序列。同步单个的操作也不安全（如果你迭代一个Vector，你还是要加锁，以避免其它线程在同一时刻改变集合）.而且效率更慢。当然同样有锁的开销即使你不需要，这是个很糟糕的方法在默认情况下同步访问。你可以一直使用Collections.sychronizedList来装饰一个集合。

Map接口

Map接口继承关系

详细的类图结构

1、接口定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

public interface Map<K, V> {
  int size();

  boolean isEmpty();

  boolean containsKey(Object var1);

  boolean containsValue(Object var1);

  V get(Object var1);

  V put(K var1, V var2);

  V remove(Object var1);

  void putAll(Map<? extends K, ? extends V> var1);

  void clear();

  Set<K> keySet();

  Collection<V> values();

  Set<Map.Entry<K, V>> entrySet();

  boolean equals(Object var1);

  int hashCode();

  default V getOrDefault(Object var1, V var2) {}

  default void forEach(BiConsumer<? super K, ? super V> var1) {}

  default void replaceAll(BiFunction<? super K, ? super V, ? extends V> var1) {}

  default V putIfAbsent(K var1, V var2) {}

  default boolean remove(Object var1, Object var2) {}

  default boolean replace(K var1, V var2, V var3) {}

  default V replace(K var1, V var2) {}

  default V computeIfAbsent(K var1, Function<? super K, ? extends V> var2) {}

  default V computeIfPresent(K var1, BiFunction<? super K, ? super V, ? extends V> var2) {}

  default V compute(K var1, BiFunction<? super K, ? super V, ? extends V> var2) {}

  default V merge(K var1, V var2, BiFunction<? super V, ? super V, ? extends V> var3) {}

  public interface Entry<K, V> {
    K getKey();

    V getValue();

    V setValue(V var1);

    boolean equals(Object var1);

    int hashCode();

    static default <K extends Comparable<? super K>, V> Comparator<Map.Entry<K, V>> comparingByKey() {}

    static default <K, V extends Comparable<? super V>> Comparator<Map.Entry<K, V>> comparingByValue() {}

    static default <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> var0) {}

    static default <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> var0) {}
  }
}

2、AbstractMap

HashMap
　　基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
　　HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
　　通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。
　　该类不是线程安全的。
WeakHashMap
　　以弱键实现的基于哈希表的 Map。在 WeakHashMap 中，当某个键不再正常使用时，将自动移除其条目。更精确地说，对于一个给定的键，其映射的存在并不阻止垃圾回收器对该键的丢弃，这就使该键成为可终止的，被终止，然后被回收。丢弃某个键时，其条目从映射中有效地移除，因此，该类的行为与其他的 Map 实现有所不同。

3、LinkedHashMap

LinkedHashMap
　　该类是 Map 接口的哈希表和链表实现。该类维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序），亦即它保留插入的顺序，输出的顺序即为输入时的插入顺序。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
　　根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用 get 方法)的链表。
　　默认是按插入顺序排序，如果指定按访问顺序排序，那么调用 get 方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。 可以重写 removeEldestEntry 方法返回 true 值指定插入元素时移除最老的元素。
　　注意，此实现不是同步的。

4、SortedMap

TreeMap
　　基于红黑树（Red-Black tree）的 NavigableMap 实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
　　在添加、删除和定位映射关系上，TreeMap类要比HashMap类的性能差一些，但是其中的映射关系具有一定的顺序，如果不需要一个有序的集合，则建议使用HashMap类；如果需要进行有序的遍历输出，则建议使用TreeMap类，在这种情况下，可以先使用由HashMap类实现的Map集合，在需要顺序输出时，再利用现有的HashMap类的实例，创建一个具有完全相同映射关系的TreeMap类型的实例。

5、ConcurrentMap

　　该类是线程安全的 Map 实现。与 Hashtable 相似，但 Hashtable 的 synchronized 是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap 允许多个修改操作并发进行，其关键在于使用了锁分离技术。它使用了多个锁来控制对 hash 表的不同部分进行的修改。ConcurrentHashMap 内部使用段(Segment)来表示这些不同的部分，每个段其实就是一个小的hash table，它们有自己的锁。只要多个修改操作发生在不同的段上，它们就可以并发进行。
　　Hashtable 对 get,put,remove 都使用了同步操作，它的同步级别是正对 Hashtable 来进行同步的，也就是说如果有线程正在遍历集合，其他的线程就暂时不能使用该集合了，这样无疑就很容易对性能和吞吐量造成影响，从而形成单点。而ConcurrentHashMap 则不同，它只对 put,remove 操作使用了同步操作，get 操作并不影响。
　　该类不允许将 null 用作键或值。

6、Hashtable

　　Hashtable 的实例有两个参数影响其性能：初始容量 和加载因子。容量 是哈希表中桶 的数量，初始容量就是哈希表创建时的容量。注意，哈希表的状态为 open：在发生“哈希冲突”的情况下，单个桶会存储多个条目，这些条目必须按顺序搜索。加载因子 是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。关于何时以及是否调用 rehash 方法的具体细节则依赖于该实现。
　　通常，默认加载因子(.75)在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查找某个条目的时间（在大多数 Hashtable 操作中，包括 get 和 put 操作，都反映了这一点）。
　　初始容量主要控制空间消耗与执行 rehash 操作所需要的时间损耗之间的平衡。如果初始容量大于 Hashtable 所包含的最大条目数除以加载因子，则永远 不会发生 rehash 操作。但是，将初始容量设置太高可能会浪费空间。
　　Hashtable 是同步的，现在一般情况下，都使用 HashMap ，而不使用陈旧的 Hashtbale，即便需要同步的时候，也是采用加同步的HashMap或者ConcurrentHashMap等实现。