“集合框架”重点概念整理
注：以下仅个人常用集合整理，更多待后续学习整理
所有的集合类位于java.util包下，后来为了解决并发问题，Java 5 还在Java.util.concurrent包下提供了一些线程支持的集合类。
对于Set\List\Deque\Map 最常用的集合类有：
HashSet、TreeSet、ArrayList、ArrayList、ArrayDeque、LinkedList、HashMap、TreeMap
一、常用集合分类
按照实现划分，如图：
image.png
按照数据结构划分，如图：
image.png
下面此图来自博友：
image.png
三 、Set不能存放重复值的原因
Set 集合访问时，是通过访问元素本身来实现的。
Set本质上与Collection没有什么区别，主要在于Set不允许包含重复元素
（Set比较两个对象相等是通过equals方法比较的）
四、Set
（一）HashSet 主要特性
①不排序、不同步、元素可为 null
②HashSet 集合判断添加的元素是否包含重复是通过“equals”和“hashCode” 方法返回值来判断的，如果一个类只重写了其中某一个方法，另一个方法的返回值与之不对应，同样也会出现添加了重复元素。若多个元素的hashCode值相等，将会导致性能下降。
③采用Hash算法 决定元素的存储位置，Hash算法详见：https://www.jianshu.com/p/4cb61f333b51
③结合上述特征：所以HashSet最好用于添加不可变元素
（二）LinkedHashSet主要特征
①它是HashSet的一个“子类”，但它是使用“链表”维护元素的次序，所以这个类是按照插入的顺序存储元素的。
②需要维护元素的插入顺序，因此性能略低于HashSet。
（三）TreeSet主要特征
①SortedSet的实现类，因此可以支持排序
②采用“红黑树”来存储集合元素，支持“自然排序”和“定制排序”
③所添加的元素必须实现Comparable接口，因为TreeSet会调用集合元素的 o1.compareTo（Object o2）方法来判断大小（compareTo返回0相等，返回正数，o1大于o2，反之小于）。
④所添加元素必须是同一类型对象，否则发生ClassCastException异常。
⑤当我们重写对应类的equals方法时，必须保证compareTo方法与之对应。
⑥结合上述特征：所以TreeSet也最好用于添加不可变元素
（四）EnumSet
①专为枚举类设计的集合类，此类中所有元素都必须是指定枚举类型的枚举值
②集合元素也是有序的：以枚举值在枚举类中的定义顺序来决定集合元素的顺序。
③内部以向量的形式存储，非常紧凑、高效，占用内存小，运行效率高。
④不允许添加null元素。
各Set实现类的性能分析
①HashSet的性能总是比TreeSet性能好，特别是常用的添加、查询元素，因为TreeSet需要额外的红黑树算法来维护集合元素的次序，只有需要一个保持排序的Set时候，才使用TreeSet。否则都用HashSet。
②HashSet的子类LinkedHashSet对于普通的插入、删除操作，它比HashSet要略微慢一点，这是由于维护链表的开销造成的，不过也因为链表，遍历会更快一些。
③EnumSet是所有实现类中性能最好的，但只适用于枚举类
最后最重要的是Set的HashSet、TreeSet和EnumSet都是线程不安全的，通常可以通过Collections工具类（只是java.util包下的一个工具类）的synchronizedSortedSet方法来包装Set集合，在创建的时候执行：
SortedSet s = Collections.synchronizedSortedSet( new TreeSet( ....) );
五、List
List集合代表一个有序、可重复的集合，默认按照添加顺序设置元素的索引。
（一）List接口和ListIterator接口
①List是Collection的子接口
②与Set集合相比，List增加了根据索引来插入、替换和删除集合元素的方法。
③List集合判断两个对象相等只要通过equals方法比较返回true即可。
④与Set集合遍历方法Iterator不同的是：List集合额外提供了一个listIterator方法，继承自Iterator接口，提供专门操作List接口的方法，这个方法增加了向前迭代的功能：hasPrevious和previous，还可以add元素，Iterator只能remove删除元素。
（二）ArrayList和Vector实现类
①两者都是List的典型实现
②基于数组，所以内部封装了一个动态的、允许再分配的Object[]数组，使用initialCapacity参数来设置数组的长度，当元素超过数组长度时候，就会自动增加initialCapacity。
下面两种情况可提前指定initialCapacity提高性能：
第一添加大量元素时，第二知道元素个数的时候。
③trimToSize方法用来减少集合对象占用的多于空间，调整数组长度为当前元素个数。
④ArrayList与Vector最显著的区别在于前者是线程不安全的，但是Collections提供的一个方法能结解决这个问题，所以就性能上讲，淘汰Vector是必然的。
固定长度的List（Arrays数组工具类）
提供asList(Object......a)方法把一个数组或指定个数的对象转换成一个List对象，这个对象只是Arrays的内部类ArrayList的实例。它是一个固定长度的List集合，程序只能遍历访问该集合里面的元素，不可以增加、删除，否则应发UnsupportedOperationException异常。
*：LinkedList也是List集合的实现类，在后面Queue集合中简述。
六、Queue
Queue用于模拟队列这种数据结构
（一）PriorityQueue
①一个标准的队列实现类
②之所以称之为标准：是因为它保存队列元素的顺序并不是以加入队列的元素的顺序，而是按队列元素的“大小”进行重新排序，因袭调用peek或者poll方法取出队列中的元素时，是取出队列中最小的元素。
③不允许插入Null值
④有两种排序方式，与TreeSet有异曲同工的特点。
（二）Deque接口与ArrayDeque实现类
①Deque是Queue接口的子接口，代表双端队列
②Deque不仅可以当成双端队列使用，而且可以被当成栈来使用，因为该类包含出栈pop、push 出栈入栈两个方法。
③Deque接口提供了一个典型的实现类：ArrayDeque：基于数组实现的双端队列，创建Deque的同时同样可以指定一个numElements参数指定内部数组的长度。
④ArrayList和ArrayDeque两个集合类的实现机制基本 相似，它们的底层都采用一个动态、可重新分配的Object[]数组来存储集合元素。
⑤程序中需要使用“栈”这种数据结构时，推荐使用ArrayDeque或者LinkedList。
（三）LinkedList
①List接口、Deque接口的实现类，所以可根据索引访问元素，也可被当做双端队列来使用，自然也可以被当做“栈”来使用。
②此类与ArrayDeque、ArrayList实现机制完全不同，前者是以链表的形式保存元素，后者是数组，所以此类随机访问性能较差，但插入删除和迭代的性能非常好，原因就在于数组和链表这两种数据结构的不同。
*：对于所有基于数组实现的集合：使用随机访问的性能比使用Iterator迭代访问的性能要好。
七、Map
如果把Map的key放在一起，就组成了一个Set集合（所有的key没有顺序，不重复），keySet方法返回所有key值组成的Set对象。Set和Map关系密切。当然values方法返回所有value组成的Collection集合。
事实上，Map提供了一个Entry内部类来封装key-value对，而计算Entry存储时则只考虑Entry封装的key，从Java源码来看，Java是先实现了Map ，然后通过包装一个所有value都为null的Map就实现了Set集合。
如果把Map 里所有value放在一起看又类似于一个List，元素与元素之间可以重复，每个元素可以根据索引查找，只是Map中的索引不再使用整数值，而是以另一个对象作为索引，Map有时也被称为字典，或关联数组。
（一）HashMap 和Hashtable 实现类
①Map的典型实现类，所以大部分特性为Map特性，Hashtable从Java 1.0就开始了，目前很少使用
HashMap与Hashtable的区别？
1、Hashtable是线程安全的，所以HashMap的性能高一点
Hashtable底层是利用锁住整个操作来实现线程安全，所以在多线程情况下是串行的，这就导致了运行效率非常低。
2、Hashtable不允许使用Null值作为key，HashMap可以。
尽量少用Hashtable,即使要线程安全，也可以使用前面提到的Collections工具类的方法把HashMap变成线程安全的。
②所有的Map实现类都重写了toString 方法，调用Map对象的toString方法总是返回一个类似于json字符串的数据。
③用作key的对象必须实现hashCode方法和equals方法。
与HashSet类似的是：
④这两个都不能保证其中key-value对的顺序。
⑤判断两个key相等的标准也是：两个key通过equals方法比较返回true，两个key的hashCode返回值也相等。
⑥尽量使用不可变对象作为存储元素，若要存可变元素，也必须保证元素不要被更改，否则可能引发不必要的错误。
⑥判断两个value相等的标准更简单：只要两个对象通过equals方法比较返回true即可。
（二）LinkedHashMap
①使用双向链表来维护key-value对的次序（其实只需要考虑key的次序），该链表负责维护Map的迭代顺序，迭代顺序与key-value的插入顺序保持一致，且性能较好。
②可以避免对HashMap、Hashtable里的key-value对进行排序，同时又可以避免使用TreeMap所增加的成本。
③需要维护元素的插入顺序，因此性能略低于HashMap的性能。
（三）Properties
Properties作为Hashtable类的子类，在处理属性文件时特别方便（windows 操作平台上的ini文件就是一种属性文件，Java中的xml文件），此类可以把Map对象和属性文件关联起来，从而可以把Map对象中的key-value对写入属性文件中，也可以把属性文件中的“属性名=属性值”加载到Map对象中。
（四）SortedMap接口和TreeMap实现类
正如Set接口派生出SortedSet子接口，SortedSet接口有一个TreeSet实现类一样，Map接口也派生出SortedMap，也有一个TreeMap实现类。
①TreeMap就是一个红黑树结构，每个key-value对即为红黑树的一个节点，在存储节点时，需要根据key对节点进行排序，TreeMap是有序的。
同TreeSet类似，也有两个排序方式：
1、自然排序：所有key必须实现Compatable接口，而且所有key必须是同一个对象，否则会抛出ClassCastException异常。
2、定制排序：创建TreeMap时，传入一个Comparator对象，该对象负责对TreeMap中所有key进行排序，采用定制排序时不要求Map的key实现Comparable接口。
②判断两个key相等的标准是：两个key通过compareTo方法返回0，和equals方法返回值为true，TreeMap就认为这两个key是相等的。
③TreeMap是有序的：所以访问前一个、后一个、第一个、最后一个都有相应的API。
（五）WeakHashMap实现类与HashMap的区别
此类的key只保留了对实际对象（字符串是强引用）的弱引用，意味着当此类对象的key所引用的对象没有被其他强引用变量所引用，则这些key将可能被垃圾回收，WeakHashMap也可能自动删除这些key所对应的key-value对。
而HashMap的key保留了对实际对象的强引用，意味着只要该HashMap对象不被销毁，该HashMap的所有key所引用的对象就不会被垃圾回收，HashMap也不会自动删除这些key所对应的key-value对。
那么什么是强引用？什么是弱引用？详情见：https://www.jianshu.com/p/14a778168840
（六）EnumMap实现类
①此类中的所有key都必须是单个枚举类的枚举值，创建此类时必须显示或者隐式的指定它对应的枚举类。
②在内部是以数组形式保存的，所以这种形式非常紧凑高效。
③根据key的自然顺序来维护key-value对的顺序
④不允许使用null值作为key，但允许使用null作为value。
（七）各Map实现类的性能分析
①HashMap通常比Hashtable要快，因为Hashtable需要额外的线程同步控制。
②TreeMap通常比HashMap、Hashtable要慢（尤其是插入、删除），因为TreeMap采用红黑树来管理key-value键值对。但使用TreeMap的好处在于：TreeMap中的key-value对总是有序状态，无须专门进行排序操作，可以调用keySet()，取得key组成的Set，然后使用toArray()方法生成key的数组，接下来使用Arrays的binarySearch(）方法在已 排序的数组中快速地查询对象。
③LinkedHashMap比HashMap要慢，没什么特别出色之处
④EnumMap性能最好，但是它只能使用同一个枚举类的枚举值作为key。
（八）HashSet和HashMap的性能选项
①HashSet和HashMap都是使用hash算法来决定集合中元素的存储位置（HashMap是key），来控制元素的大小（HashMap是key）
②hash表里可以存储元素的位置叫作“桶”，在通常情况下，单个“桶”中存储一个元素，此时有最好的性能。
③hash算法可以根据hashCode值计算出“桶”的存储位置，接着就可以从桶中取出元素。
④但hash表中的状态我open：在发生hash冲突的时候，单个桶会存储多个元素，这些元素就会以链表的形式存储，必须按照顺序搜索。
⑤hash表包含如下属性：
1、容量(capacity)：hash表中桶的数量
2、初始化容量（initial capacity）:创建hash表时桶的数量，HashMap和HashSet都允许在构造器中指定初始化容量。
3、尺寸（size）：当前hash表中记录的数量。
4、负载因子（load factory）：负载因子 = size/capacity，轻负载的hash表具有冲突少、适宜查询与插入的特点（但是Iterator遍历较慢）
⑥负载极限：范围0~1，决定了hash表的最大填满程度，hash表会自动成倍的增加桶的数量，称为“rehashing”，默认为0.75，也就是当该hash表的3/4被填满的时候，就会发生“rehashing”
为什么是0.75？
较高会降低hash表占用的内存空间，但会增加查询数据的时间开销，当然对于时间效率和占用内存可以根据实际情况进行调整。
最后提及一个操作集合的工具类：Collections
该工具类提供了大量的方法对集合元素进行排序、查询和修改等操作，还提供将集合设置为不可变、对集合实现同步控制等方法。具体见API文档。
（以上为纯Java集合框架必知基础，整理来源：《Java疯狂讲义》第八章 Java集合）
