集合--基础知识

集合

集合类是一种工具类，存储数量不等的对象，可以实现栈，队列等数据结构。可以分为：Set：无序，不可重复的集合； List：有序，重复的集合； Queue：队列集合实现； Map：具有映射关系的集合 四种。
集合类主要由：Collection和Map两个接口派生而出.
Map保存的的每项数据都是由key-value对即两个值组成，key用来标识集合里面的每项数据并且不可以重复，根据key值来获取value数据。

Stream

对java集合进行操作，将要处理的集合的元素看成一种流，流在管道中传输，在管道的节点上进行处理，并支持聚合操作。stream的聚合、消费或收集操作只能进行一次，再次操作会报错。

Set集合

Set集合不能记住元素的添加顺序，不允许包含重复元素。
所有Set接口的内部都是Map做支撑，

1. HashSet

按照Hash算法来存储集合中的元素，底层的数据结构是Hash表。
HashSet不是同步的。集合的元素值可以是空。
根据hashCode值决定元素在集合中的存储位置，HashSet判断两个对象相等的标准：两个对象通过equals()方法比较相等，并且两个对象的hashCode()方法返回值也相等。

两个对象的hashCode值不同，但是两个对象的equals()方法返回相同，会把两个对象保存在hash表的不同位置。
两个对象hashCode值相同，但是equals()方法比较不同，会在同一个位置用链式存储结构保存多个对象。
重写hashCode()方法的基本规则
两个对象通过equals()方法比较返回true，这两个对象的hashCode值也应该相同。

LinkedHashSet：是HashSet的子类。也是根据hashCode值来决定元素在集合中的存储位置。使用双重链表维护元素的插入次序。遍历集合中的元素时会按元素的添加顺序来访问集合中的元素。

2. TreeSet

是SortedSet接口的实现类，可以确保集合元素处于排序状态。不是根据元素的插入顺序进行排序，根据实际值的大小进行排序。
TreeSet采用红黑树的数据结构来存储集合元素。分为自然排序和定制排序。
自然排序：TreeSet调用集合元素的comparaTo()方法来比较元素之间的大小，然后按升序排列。敲重点：1. 加入TreeSet的元素都要实现Comparable接口 2.加入的最好都是同一个类型的元素。3. 两个元素相等的依据是两个对象的comparaTo()方法返回为0；4. 注意不要修改可变对象的实例变量。
两个对象通过equals()方法返回true时，两个对象的comparaTo()方法比较应返回0。

定制排序：在创建TreeSet集合时，创建一个Comparator对象，与TreeSet集合关联，Comparator负责排序逻辑，通过Comparator接口的帮助，通过利用该函数式接口的compara()方法来实现。

3. EnumSet

为枚举类设计的集合类，所有元素必须是指定枚举类型的枚举值。是有序的集合，以枚举值在Enum类中的定义顺序来决定集合元素的顺序。不允许加入null元素。EnumSet没有暴露任何构造器来创建该类的实例。
这三个Set的实现类都是线程不安全的。

List集合

代表元素有序可以重复的集合。每个元素都有其对应的顺序索引，通过索引来访问指定位置的元素。List判断两个对象相等的标准：通过equals()方法比较返回true即可。

List的listIterator()方法：返回一个ListIterator对象，ListIterator接口继承自Iterator接口，提供了操作List集合的方法。ListIterator增加了向前迭代的功能，还可以向List集合里面添加元素。
两个实现类：ArrayList和Vector，都是基于数组实现的List类。封装了一个动态的，允许再分配的Object[]数组，可以设置数组的长度，当数组中的元素超过设置的数组长度时，数组长度会增加。
创建时不指定集合的大小时，动态的Object[]数组的长度默认为10。

ArrayList：是线程不安全的，
Vector：是线程安全的，性能低于ArrayList。

ArrayDeque也是List的实现类，同时也实现了Deque接口。实现了Deque接口，因此可以当作栈来使用，它的底层也是基于数组的实现。

Queue集合

用于模拟队列这种数据结构。

1. PriorityQueue

队列的实现类，保存队列元素的顺序不是按加入队列的顺序，是按照队列元素的大小进行重新排序。不允许加入null元素。有两种排序方式：自然排序和定制排序。

2. Deque接口

是Queue接口的子接口，代表一个双端队列。包含一些栈方法。
ArrayDeque：基于数组实现的双端队列。可以当作栈来使用。

3. LinkedList

是List接口的实现类，还实现了Deque接口。内部以链表的形式来保存集合中的元素。
提供了List的功能，还提供了双端队列和栈的功能。

Map集合

保存具有映射关系的数据，集合里面保存着两组值，一组用于保存key，另一组保存value，key和value都可以是任何引用类型的数据。key不允许重复。key集的存储形式和Set集合中元素的存储形式相似。Map提供了一个Entry内部类来封装key-value对，在计算Entry存储时只考虑Entry封装的key。

1. HashMap
   线程不安全的实现。允许使用null值作为key和value。
2. Hashtable
   线程安全的Map实现。不允许使用null值作为key和value。

HashMap和Hashtable中用作key的对象必须实现hashCode()方法和equals()方法，并且这两个map集合也不能保证其中的key-value的顺序。1. 判断key值相等的标准：通过equals()方法返回true，hashCode值也相等。2. 判断两个value相等的标准：只要两个对象通过equals()方法比较返回true

3. LinkedHashMap
   是HashMap的子类。使用双向链表来维护key-value对的次序，与插入顺序保持一致。
4. Properties
   是Hashtable的子类。处理属性文件，将map对象和属性文件关联起来。相对于key,value都是String类型的Map。
5. SortedMap接口和TreeMap实现类
   TreeMap是一个红黑树数据结构。key-value对作为红黑树的一个节点，在存储key-value对时，会根据key对节点进行排序。
   自然排序
定制排序·
6. WeakHashMap
   key的类型是WeakRerfence，key被回收，key对应的指向的对象会被从Map容器中移除。
7. IdentityHashMap
   实现机制与HashMap基本相似，但在处理两个key相等时：要求两个key严格相等时才认为两个key相等。
8. EnumHashMap
   在内部以数组形式存储。不允许使用null作为key。

HashSet与HashMap

HashSet采用hash算法来决定集合中元素的存储位置，通过hash算法控制集合的大小。
HashMap类似HashSet，采用hash算法决定集合中key的存储位置，也通过hash算法来增加key集合的大小。

遍历集合

1. Iterable接口的forEach()方法来遍历集合：传给该方法的参数是一个目标类型为Consumer类型的Lambda表达式。
2. Iterator遍历集合元素：

Iterator对象是迭代器，必须依附于Collection对象。
Iterator遍历集合时，不是将集合元素本身传给了Iterator迭代变量，是将集合元素的值传给了迭代变量。
Iterator迭代访问集合的元素时，集合里的元素不能被改变，否则会引发ConcurrentModificationException异常。只有使用Iterator的remove()方法删除上一次next()方法返回的集合元素才可以。

Iterator采用快速失败机制(fail-fast)，在迭代过程中检测到集合元素已经被修改，立即引发ConcurrentModification异常。

快速失败机制(fail-fast)
对集合修改次数的期望值：
对集合的修改次数:每次调用集合的add()方法或者remove()方法就会将该值加1或者减1。
修改次数的期望值刚刚开始时是等于修改次数的。

检查修改次数和修改次数的期望值是否相等，不等时抛出ConcurrentModificationException异常。

在Iterator的next()方法中，先会检查修改次数和修改次数的期望值是否相等，然后再得到集合里的下一个元素。

在Iterator实现类的remove()方法中，删除一个元素时，是调用集合自己的删除函数，并会将修改次数加一，并将修改次数的值赋值给修改次数的期望值。
没有调用Iterator的remove()方法进行删除操作，使用集合的删除函数来进行删除操作时，修改次数会加1，但是不会将修改次数的值赋值为修改次数的期望值，导致修改次数的值和修改次数期望值的值不一致，在进行下一次next()迭代时，会检测出两者不相等，然后抛出ConcurrentModificationException异常。

单线程环境下：将使用集合进行删除操作修改为使用Iterator对象进行删除就会正确，不会抛出异常。
多线程环境下：就是使用Iterator的删除函数进行删除也还是会抛出异常。
因为在多线程环境下，每个线程是不同的Iterator对象，修改次数的期望值是线程私有的，修改次数是共享的。
当一个线程使用Iterator对象进行remove()删除时，这时候共享的修改次数值和这个线程的修改次数期望值都会自增；但是其他线程的私有的修改次数期望值没有自增，所以其他线程就会抛出ConcurrentModificationException异常了。

3. Lambda表达式遍历：类似第一种。
4. foreach循环遍历

迭代变量是集合元素的值，不是集合本身。
使用循环进行遍历时，也不能改变集合，否则会引发ConcurrentModificationException异常。

Hash算法

散列表
也叫哈希表，基于高速存取角度设计的，是以空间换时间，其中的元素不是紧密排列的，可能存在空隙。
以一种键-值(key-indexed)存储数据的结构，输入key，可查找到对应的值。

通过关键码值(key)直接进行访问存放记录(indexed值)的数组(散列表)。把关键码值通过映射函数(散列函数)映射到散列表中的一个位置来访问散列表中的记录。
表中存储元素的位置称为桶。

哈希表包含的属性
容量(capacity)：表中桶的数量。
初始化容量：创建哈希表时桶的数量。
尺寸：当前哈希表中记录的数量。
负载因子：等于尺寸/容量。
负载极限：是一个0-1的数值。默认的负载极限为0.75。决定了hash表的最大填满程度。当负载因子达到负载极限时，哈希表会自动成倍的增加桶的数量，并会将原有的对象重新分配，放入新的桶中。

hash冲突
两个元素通过映射函数得到的在散列表中的存储位置相同。
发生冲突的两个元素称为同义词。

解决冲突
取决于3点：
a.散列函数，散列函数计算得到的表中的存储位置应平均分布。
b.处理冲突的方法。
c.负载因子的大小。
方法：
a.线性探测法：冲突后，线性向前探测，找到最近的一个空位置。
b.双散列函数法：

CopyOnWriteArrayList
HashSet同步
LinkedHashSet的底层的链表

• ClassCastException：JVM在检测到两个类型间转换不兼容时引发的运行时异常。