第8章 Java集合
1.Java集合框架
为了保存数量不确定的数据，以及保存具有映射关系的数据（即关联数组），Java提供了集合类。
Set：无序集合，元素不可重复
List：有序集合，元素可以重复
Map实现类用于保存具有映射关系的数据，由key-value对组成，其中key不可重复。
2.Collection和Iterator接口
（1）Collection是Set、List和Queue接口的父接口。其用法（函数功能）有：添加元素，删除元素，返回Collection集合元素个数以及清空整个集合。
（2）Iterable接口是Collection接口的父接口，该接口中唯一的抽象方法是forEach(Consumer action)进行遍历元素，其中Consumer是函数式接口，可以使用Lambda表达式遍历集合元素。
3.Set集合
Set集合不允许有重复元素，
（1）HashSet类
1）HashSet按Hash算法来存储集合中的元素，不能保证元素的排列顺序（可能与添加的顺序不同），集合元素值也可以是null。
2）HashSet判断两个元素是否相等的标准是两个对象通过equals()比较相等，并且两个对象的hashcode()相等。
3）HashSet访问集合元素时也是根据元素的hashCode值进行快速定位。
（2）LinkedHashSet类
LinkedHashSet使用链表记录集合元素的添加顺序（按插入元素的顺序保存），依然不允许元素重复。
(3)TreeSet类
1）TreeSet中的元素是有序的，增加了访问第一个，前一个，后一个，最后一个元素的方法，并提供了从TreeSet中截取子TreeSet的方法。
2）TreeSet采用红黑树的数据结构来存储集合元素，支持两种排序方法：自然排序和定制排序。
a)自然排序：TreeSet调用集合元素的compareTo（Object obj）方法来比较元素之间的大小关系，然后将元素按升序排列。（自然排序必须实现Comparable接口，否则会引发运行时异常）
b)如果希望TreeSet能正常运作，TreeSet只能添加同一种类型的对象。
c)定制排序：通过TreeSet接口里的int compare(T o1,T o2)方法，比较o1和o2的大小。由Comparator对象负责集合元素的排序逻辑，依然不可以向TreeSet中添加类型不同的对象。
（4）EnumSet类
EnumSet是专为枚举类设计的集合类，在内部以位向量的形式存储，不允许加入null元素。
4.List集合
List集合代表一个元素有序、可重复的集合。List集合增加了根据索引来操作集合元素的方法。List判断两个对象相等的标准是通过equals()方法比较返回true即可。
5.Queue集合
Queue是一种先进先出的容器，有一个PriorityQueue实现类，还有一个Deque接口，代表一个双端队列。Java为Deque提供了ArrayDeque和LinkedList两个实现类。
(1)PriorityQueue实现类
(a）PriorityQueue实现类保存队列元素的顺序并不是按加入队列的顺序，而是按队列元素的大小进行重新排序（不遵从先进先出规则）。
(b)PriorityQueue不允许插入null元素，对其有两种排序方式：自然排序和定制排序。自然排序必须实现comparable接口，而且应该是同一个类的多个示例。定制排序在创建PriorityQueue队列时，传入一个Comparator对象（负责对队列中的所有元素进行排序）。
（2）Deque接口和ArrayDeque实现类
ArrayDeque是一个基于数组实现的双端队列，其底层都采用一个动态的、可重新分配的Object[]数组来存储集合元素。（若超出容量，则重写分配）
（3）LinkedList实现类
既可以当作栈使用，也可以当作队列使用。其内部是以链表的形式来保存集合中的元素，因此随机访问集合元素时性能较差，但在插入、删除元素时性能出色。
6.Map集合
Map的key不允许重复，通过指定的key，总能找到唯一的、确定的value。
(1) HashMap和Hashtable实现类
a)Hashtable是一个线程安全的Map实现，但HashMap线程不安全。（故性能更高）
b)Hashtable不允许使用null作为key和value，但HashMap可以使用null作为key或value.
c)HashMap和Hashtable判断两个key相等的标准是通过equals()方法比较返回true，两个key的hashCode值也相等。（应该保证两个方法的判断标准一致）
d)HashMap和Hashtable判断两个value相等的标准只需两个对象通过equals()方法比较返回true即可。
(2) LinkedHashMap实现类
HashMap是LinkedHashMap的父类，使用双向链表来维护key-value对的次序，该链表负责维护Map的迭代顺序，迭代顺序与key-value对的插入顺序保持一致。
(3) Properties类
Properties类是Hashtable类的子类，可以把Map对象和属性文件关联起来，从而把Map对象中的key-value对写入属性文件中。Properties相当于一个key、value都是String类型的Map.
(4) SortedMap接口和TreeMap实现类
（a）TreeMap就是一个红黑树数据结构，每个key-value对即作为红黑树的一个节点，在存储key-value对时，需要根据key对节点进行排序，使得所有的key-value对处于有序状态。其排序方式也有两种：自然排序和定制排序。
(b)TreeMap中的key-value对是有序的，所以其类的方法增加了访问第一个、前一个、后一个、最后一个key-value对的方法，并提供了几个从TreeMap中截取子TreeMap的方法。
(5) WeakHashMap实现类
WeakHashMap中的每个key对象只持有对实际对象的弱引用，当垃圾回收了该key所对应的实际对象之后，WeakHashMap会自动删除该key所对应的Key-value对。
(6) IdentityHashMap实现类
IdentityHashMap是一个特殊的Map实现，要求两个key严格相等时才认为两个key相等。允许使用null作为key和value，但不能保证key-value对之间的顺序。
(7) EnumMap实现类
EnumMap是一个与枚举类一起使用的Map实现，其key必须是单个枚举类的枚举值。其特点有：
- EnumMap在内部以数组形式保存。
- 根据key的自然顺序来维护key-value对的顺序。
- 不允许使用null作为key，但允许使用null作为value。
- 创建EnumMap时必须指定一个枚举类，从而将EnumMap和指定枚举类关联起来。
7.性能分析
（1）Hash表里可以存储元素的位置称为“桶”，hash算法可以根据hashCode值计算桶的存储位置，接着从桶中取出元素。但在发生hash冲突的情况下，单个桶会存储多个元素，这些元素以链表的形式存储，必须按顺序检索。
（2）hash表中还有一个“负载极限”，负载极限是一个0~1的数值，其决定了hash表的最大填满程度。当hash表中的负载因子达到指定的负载极限时，hash表会自动成倍的增加容量，并将原有的对象重新分配，放入新的桶中，称为refreshing.