集合类型是Java标准库中被使用最多的类型，如果一个Java对象可以在内部持有若干其他Java对象，并对外提供访问接口，则把这种Java对象称为集合
Java标准库自带的java.util包提供了集合类：Collection，它是除Map外所有其他集合类的根接口。Java的java.util包主要提供了以下三种类型的集合：
graph LR
集合-->Collection
Collection-->List-->ArrayList
Collection-->Set-->HashSet
集合-->Map-->HashMap
List-->linkedList
List-->......
Set-->TreeSet
Set-->.....
Map-->...
List
Interface List，有序集合，可重复，有索引
List几个主要的接口方法：
实现List接口能通过数组（ArrayList）来实现，也可通过linkedList“链表”实现。通常情况下优先使用ArrayList
可以通过List接口提供的of()方法，根据给定元素快速创建List，但不接受null值
迭代器或者for循环索引的方式遍历，优先使用Iterator。Iterator本身也是一个对象，但它是由List的实例调用iterator()方法的时候创建的。Iterator对象知道如何遍历一个List，并且不同的List类型，返回的Iterator对象实现也是不同的，但总是具有最高的访问效率。
public class Main {
public static void main(String[] args) {
List list = List.of("apple", "pear", "banana");
for (Iterator it = list.iterator(); it.hasNext(); ) {
String s = it.next();
System.out.println(s);
}
}
}
何时使用for循环？当可能存在并发修改异常时，例如一边遍历数组，一边实现添加/减少的功能
public class Main {
public static void main(String[] args) {
List list = List.of("apple", "pear", "banana");
//报错：ConcurrentModificationException
for (Iterator it = list.iterator(); it.hasNext(); ) {
String s = it.next();
if(s.equals("pear")){
list.add("watermelon");
}
}
//正常运行：
for (int i=0; i
ListIterator
ListIterator是List特有的迭代器，其add方法不会产生ConcurrentModificationException
List和Array的转换
List转Array三种方法：
- 调用toArray()方法直接返回一个Object[]数组，这种方法会丢失类型信息，所以实际应用很少。
- 给toArray(T[])传入一个类型相同的Array，List内部自动把元素复制到传入的Array中
Integer[] array = list.toArray(new Integer[list.size()]);
- 通过List接口定义的T[] toArray(IntFunction
generator)方法：
Integer[] array = list.toArray(Integer[]::new);
通过List.of(T…)方法把Array变为List
Integer[] array = { 1, 2, 3 };
List list = List.of(array);
Set
元素不能重复且不保证顺序的存储方式，不能使用索引，主要方法：
- 将元素添加进Set：boolean add(E e)
- 将元素从Set删除：boolean remove(Object e)
- 判断是否包含元素：boolean contains(Object e)
Set实际上相当于只存储key、不存储value的Map。经常用Set用于去除重复元素
因为放入Set的元素和Map的key类似，都要正确实现equals()和hashCode()方法，否则该元素无法正确地放入Set。
最常用的Set实现类是HashSet。Set接口并不保证有序，而SortedSet接口则保证元素是有序的：
HashSet是无序的，因为它实现了Set接口，并没有实现SortedSet接口；
TreeSet是有序的，因为它实现了SortedSet接口。
HashSet
对集合迭代顺序不作任何保证。
哈希值：JDK根据对象地址或者字符串或数字算出来的int型数值，Object类里有hashCode()返回哈希值，可以被Override
HashSet集合特点：底层数据结构是哈希表，不保证迭代顺序，没有带索引方法，不包含重复元素
linkedHashSet
哈希表和链表，具有可预测的迭代次序，唯一且存储和读取有序
TreeSet
使用TreeSet和使用TreeMap的要求一样，添加的元素必须正确实现Comparable接口，如果没有实现Comparable接口，那么创建TreeSet时必须传入一个Comparator对象
哈希表
数组+链表实现，JDK8后优化
Map
Map是一种键值（key-value）映射表的数据结构，能高效通过key快速查找value
Map是一种键-值映射表，当调用put(K key, V value)方法时，就把key和value做了映射并放入Map。当调用V get(K key)时，就可以通过key获取到对应的value。如果key不存在，则返回null。
和List类似，Map也是一个接口，最常用的实现类是HashMap。如果只是想查询某个key是否存在，可以调用boolean containsKey(K key)方法。
Map中不存在重复的key，因为放入相同的key，只会把原有的key-value对应的value给替换掉
遍历Map
要遍历key可以使用for each循环遍历Map实例的keySet()方法返回的Set集合，它包含不重复的key的集合
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
Map map = new HashMap<>();
map.put("apple", 123);
map.put("pear", 456);
map.put("banana", 789);
for (String key : map.keySet()) {
Integer value = map.get(key);
System.out.println(key + " = " + value);
}
}
}
同时遍历key和value可以使用for each循环遍历Map对象的entrySet()集合，它包含每一个key-value映射
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
Map map = new HashMap<>();
map.put("apple", 123);
map.put("pear", 456);
map.put("banana", 789);
for (Map.Entry entry : map.entrySet()) {
String key = entry.getKey();
Integer value = entry.getValue();
System.out.println(key + " = " + value);
}
}
}
遍历Map时，不可假设输出的key是有序的
HashMap
类似于HashSet，一个无序、key不重复的Map，但Value可以重复
要正确使用HashMap，作为key的类必须正确覆写equals()和hashCode()方法，一个类如果覆写了equals()，就必须覆写hashCode()，并且覆写规则是：
- 如果equals()返回true，则hashCode()返回值必须相等；
- 如果equals()返回false，则hashCode()返回值尽量不要相等。
实现hashCode()方法可以通过Objects.hashCode()辅助方法实现。
因为HashMap是一种通过对key计算hashCode()，通过空间换时间的方式，直接定位到value所在的内部数组的索引，因此，查找效率非常高。如果作为key的对象是enum类型，还可以使用Java集合库提供的一种EnumMap，它在内部以一个非常紧凑的数组存储value，并且根据enum类型的key直接定位到内部数组的索引，并不需要计算hashCode()，不但效率最高，而且没有额外的空间浪费
TreeMap
SortedMap是接口，内部会对Key进行排序，SortedMap保证遍历时以Key的顺序来进行排序。它的实现类是TreeMap，使用TreeMap时，放入的Key必须实现Comparable接口。如果作为Key的class没有实现Comparable接口，那么，必须在创建TreeMap时同时指定一个自定义排序算法（Comparator对象）。
TreeMap不使用equals()和hashCode()
集合类数据结构
包括队列Queue，栈Stack
队列Queue
Queue实际上是实现了一个先进先出（FIFO：First In First Out）的有序表。它和List的区别在于，List可以在任意位置添加和删除元素，而Queue只有两个操作：把元素添加到队列末尾；从队列头部取出元素。
在Java的标准库中，队列接口Queue定义了以下几个方法：
- int size()：获取队列长度；
- boolean add(E)/boolean offer(E)：添加元素到队尾；
- E remove()/E poll()：获取队首元素并从队列中删除；
- E element()/E peek()：获取队首元素但并不从队列中删除。
不要在队列中添加null
PriorityQueue
PriorityQueue和Queue的区别在于，它的出队顺序与元素的优先级有关，对PriorityQueue调用remove()或poll()方法，返回的总是优先级最高的元素。要使用PriorityQueue，我们就必须给每个元素定义“优先级”，因此，放入PriorityQueue的元素，必须实现Comparable接口，PriorityQueue会根据元素的排序顺序决定出队的优先级，也可以通过Comparator自定义排序算法（元素就不必实现Comparable接口）
Deque
双端队列（Double Ended Queue），允许两头都进，两头都出，学名Deque。
Java集合提供了接口Deque来实现一个双端队列，它的功能是：
- 既可以添加到队尾，也可以添加到队首；
- 既可以从队首获取，又可以从队尾获取。
对于添加元素到队尾的操作，Queue提供了add()/offer()方法，而Deque提供了addLast()/offerLast()方法。添加元素到对首、取队尾元素的操作在Queue中不存在，在Deque中由addFirst()/removeLast()等方法提供。
使用Deque，推荐总是明确调用offerLast()/offerFirst()或者pollFirst()/pollLast()方法
Deque是一个接口，它的实现类有ArrayDeque和linkedList，由于Deque继承自Queue，也不要添加null
Stack
栈（Stack）是一种后进先出（LIFO：Last In First Out）的数据结构，只能不断地往Stack中压入（push）元素，最后进去的必须最早弹出（pop）来
Stack只有入栈和出栈的操作：
- 把元素压栈：push(E)；
- 把栈顶的元素“弹出”：pop()；
- 取栈顶元素但不弹出：peek()。
Java中用Deque可以实现Stack的功能，注意只调用push()/pop()/peek()方法，避免调用Deque的其他方法
Collections
Collections是JDK提供的工具类，位于java.util包中。它提供了一系列静态方法，能更方便地操作各种集合
创建空集合
Collections提供了一系列方法来创建不可变空集合：
- 创建空List：List emptyList()
- 创建空Map：Map
emptyMap() - 创建空Set：Set emptySet()
也可以用各个集合接口提供的of(T…)方法创建空集合
创建单元素集合
Collections提供了一系列方法来创建一个不可变单元素集合：
- 创建一个元素的List：List singletonList(T o)
- 创建一个元素的Map：Map
singletonMap(K key, V value) - 创建一个元素的Set：Set singleton(T o)
也可以用各个集合接口提供的of(T…)方法创建单元素集合
排序
Collections可以对List进行排序（Collections.sort()）。因为排序会直接修改List元素的位置，因此必须传入可变List
洗牌
Collections提供了洗牌算法（Collections.shuffle(list)），即传入一个有序的List，可以随机打乱List内部元素的顺序，效果相当于让计算机洗牌
