Java的java.util包主要提供了以下三种类型的集合：
List：一种有序列表的集合，例如，按索引排列的Student的List；Set：一种保证没有重复元素的集合，例如，所有无重复名称的Student的Set；Map：一种通过键值（key-value）查找的映射表集合，例如，根据Student的name查找对应Student的Map。
Java的集合类定义在java.util包中，支持泛型，主要提供了3种集合类，包括List，Set和Map。Java集合使用统一的Iterator遍历，尽量不要使用遗留接口。
List
ArrayList在内部使用了数组来存储所有元素。例如，一个ArrayList拥有5个元素，实际数组大小为6（即有一个空位）：
size=5
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │ │
└───┴───┴───┴───┴───┴───┘
当添加一个元素并指定索引到ArrayList时，ArrayList自动移动需要移动的元素：
size=5
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ │ C │ D │ E │
└───┴───┴───┴───┴───┴───┘
然后，往内部指定索引的数组位置添加一个元素，然后把size加1：
size=6
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ F │ C │ D │ E │
└───┴───┴───┴───┴───┴───┘
继续添加元素，但是数组已满，没有空闲位置的时候，ArrayList先创建一个更大的新数组，然后把旧数组的所有元素复制到新数组，紧接着用新数组取代旧数组：
size=6
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ F │ C │ D │ E │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
现在，新数组就有了空位，可以继续添加一个元素到数组末尾，同时size加1：
size=7
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ F │ C │ D │ E │ G │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
可见，ArrayList把添加和删除的操作封装起来，让我们操作List类似于操作数组，却不用关心内部元素如何移动。
但是，实现List接口并非只能通过数组（即ArrayList的实现方式）来实现，另一种LinkedList通过“链表”也实现了List接口。在LinkedList中，它的内部每个元素都指向下一个元素：
┌───┬───┐ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐
HEAD ──▶│ A │ ●─┼──▶│ B │ ●─┼──▶│ C │ ●─┼──▶│ D │ │└───┴───┘ └───┴───┘ └───┴───┘ └───┴───┘我们考察List<E>接口，可以看到几个主要的接口方法：
- 在末尾添加一个元素：
boolean add(E e) - 在指定索引添加一个元素：
boolean add(int index, E e) - 删除指定索引的元素：
E remove(int index) - 删除某个元素：
boolean remove(Object e) - 获取指定索引的元素：
E get(int index) - 获取链表大小（包含元素的个数）：
int size()
创建List
List<String> list = new ArrayList<>();ArrayList类继承自List接口
()是构造函数调用的语法，用于实例化ArrayList对象。<>中的空白部分是 钻石操作符，编译器会根据变量声明的类型自动推断出泛型类型，简化了代码的书写。
所以我们要始终坚持使用迭代器Iterator来访问List。Iterator本身也是一个对象，但它是由List的实例调用iterator()方法的时候创建的。Iterator对象知道如何遍历一个List，并且不同的List类型，返回的Iterator对象实现也是不同的，但总是具有最高的访问效率。
Iterator对象有两个方法：boolean hasNext()判断是否有下一个元素，E next()返回下一个元素。因此，使用Iterator遍历List代码如下：
import java.util.Iterator;
import java.util.List;public class Main {public static void main(String[] args) {List<String> list = List.of("apple", "pear", "banana");for (Iterator<String> it = list.iterator(); it.hasNext(); ) {String s = it.next();System.out.println(s);}}
}import java.util.List;public class Main {public static void main(String[] args) {List<String> list = List.of("apple", "pear", "banana");for (String s : list) {System.out.println(s);}}
}
上述代码就是我们编写遍历List的常见代码。
实际上，只要实现了Iterable接口的集合类都可以直接用for each循环来遍历，Java编译器本身并不知道如何遍历集合对象，但它会自动把for each循环变成Iterator的调用，原因就在于Iterable接口定义了一个Iterator<E> iterator()方法，强迫集合类必须返回一个Iterator实例。
List是接口 Array是一种数据类型
List和Array转换
把List变为Array有三种方法，第一种是调用toArray()方法直接返回一个Object[]数组：
第二种方式是给toArray(T[])传入一个类型相同的Array，List内部自动把元素复制到传入的Array中：
import java.util.List;public class Main {public static void main(String[] args) {List<Integer> list = List.of(12, 34, 56);Integer[] array = list.toArray(new Integer[3]);for (Integer n : array) {System.out.println(n);}}
}
注意到这个toArray(T[])方法的泛型参数<T>并不是List接口定义的泛型参数<E>，所以，我们实际上可以传入其他类型的数组，例如我们传入Number类型的数组，返回的仍然是Number类型：
如果传入的数组不够大，那么List内部会创建一个新的刚好够大的数组，填充后返回；如果传入的数组比List元素还要多，那么填充完元素后，剩下的数组元素一律填充null。
实际上，最常用的是传入一个“恰好”大小的数组：
Integer[] array = list.toArray(new Integer[list.size()]);
最后一种更简洁的写法是通过List接口定义的T[] toArray(IntFunction<T[]> generator)方法：
Integer[] array = list.toArray(Integer[]::new);
这种函数式写法我们会在后续讲到。
Arrat变成List
通过List.of(T...)方法最简单：
Integer[] array = { 1, 2, 3 };
List<Integer> list = List.of(array);List是按索引顺序访问的长度可变的有序表，优先使用ArrayList而不是LinkedList；
可以直接使用for each遍历List；
List可以和Array相互转换。
在List中查找元素时，List的实现类通过元素的equals()方法比较两个元素是否相等，因此，放入的元素必须正确覆写equals()方法，Java标准库提供的String、Integer等已经覆写了equals()方法；
编写equals()方法可借助Objects.equals()判断。
如果不在List中查找元素，就不必覆写equals()方法。
Map<K, V>是一种键-值映射表，当我们调用put(K key, V value)方法时，就把key和value做了映射并放入Map。当我们调用V get(K key)时，就可以通过key获取到对应的value。如果key不存在，则返回null。和List类似，Map也是一个接口，最常用的实现类是HashMap。
重复放入key-value并不会有任何问题，但是一个key只能关联一个value。在上面的代码中，一开始我们把key对象"apple"映射到Integer对象123，然后再次调用put()方法把"apple"映射到789，这时，原来关联的value对象123就被“冲掉”了。实际上，put()方法的签名是V put(K key, V value)，如果放入的key已经存在，put()方法会返回被删除的旧的value，否则，返回null。
遍历Map
对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<String, Integer> 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<String, Integer> map = new HashMap<>();map.put("apple", 123);map.put("pear", 456);map.put("banana", 789);for (Map.Entry<String, Integer> entry : map.entrySet()) {String key = entry.getKey();Integer value = entry.getValue();System.out.println(key + " = " + value);}}
}如果Map的key是enum类型，推荐使用EnumMap，既保证速度，也不浪费空间。
使用EnumMap的时候，根据面向抽象编程的原则，应持有Map接口。
使用TreeMap时，放入的Key必须实现Comparable接口。String、Integer这些类已经实现了Comparable接口，因此可以直接作为Key使用。作为Value的对象则没有任何要求。
如果作为Key的class没有实现Comparable接口，那么，必须在创建TreeMap时同时指定一个自定义排序算法：
import java.util.*;public class Main {public static void main(String[] args) {Map<Person, Integer> map = new TreeMap<>(new Comparator<Person>() {public int compare(Person p1, Person p2) {return p1.name.compareTo(p2.name);}});map.put(new Person("Tom"), 1);map.put(new Person("Bob"), 2);map.put(new Person("Lily"), 3);for (Person key : map.keySet()) {System.out.println(key);}// {Person: Bob}, {Person: Lily}, {Person: Tom}System.out.println(map.get(new Person("Bob"))); // 2}
}class Person {public String name;Person(String name) {this.name = name;}public String toString() {return "{Person: " + name + "}";}
}使用TreeMap时，对Key的比较需要正确实现相等、大于和小于逻辑！
SortedMap在遍历时严格按照Key的顺序遍历，最常用的实现类是TreeMap；
作为SortedMap的Key必须实现Comparable接口，或者传入Comparator；
要严格按照compare()规范实现比较逻辑，否则，TreeMap将不能正常工作
队列（Queue）是一种经常使用的集合。Queue实际上是实现了一个先进先出（FIFO：First In First Out）的有序表。它和List的区别在于，List可以在任意位置添加和删除元素，而Queue只有两个操作：
- 把元素添加到队列末尾；
- 从队列头部取出元素。
在Java的标准库中，队列接口Queue定义了以下几个方法：
| throw Exception | 返回false或null | |
|---|---|---|
| 添加元素到队尾 | add(E e) | boolean offer(E e) |
| 取队首元素并删除 | E remove() | E poll() |
| 取队首元素但不删除 | E element() | E peek() |
PriorityQueue和Queue的区别在于，它的出队顺序与元素的优先级有关，对PriorityQueue调用remove()或poll()方法，返回的总是优先级最高的元素。
要使用PriorityQueue，我们就必须给每个元素定义“优先级”。我们以实际代码为例，先看看PriorityQueue的行为：
import java.util.PriorityQueue;
import java.util.Queue;public class Main {public static void main(String[] args) {Queue<String> q = new PriorityQueue<>();// 添加3个元素到队列:q.offer("apple");q.offer("pear");q.offer("banana");System.out.println(q.poll()); // appleSystem.out.println(q.poll()); // bananaSystem.out.println(q.poll()); // pearSystem.out.println(q.poll()); // null,因为队列为空}
}
我们放入的顺序是"apple"、"pear"、"banana"，但是取出的顺序却是"apple"、"banana"、"pear"，这是因为从字符串的排序看，"apple"排在最前面，"pear"排在最后面。
因此，放入PriorityQueue的元素，必须实现Comparable接口，PriorityQueue会根据元素的排序顺序决定出队的优先级。
如果我们要放入的元素并没有实现Comparable接口怎么办？PriorityQueue允许我们提供一个Comparator对象来判断两个元素的顺序。我们以银行排队业务为例，实现一个PriorityQueue：
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;public class Main {public static void main(String[] args) {Queue<User> q = new PriorityQueue<>(new UserComparator());// 添加3个元素到队列:q.offer(new User("Bob", "A1"));q.offer(new User("Alice", "A2"));q.offer(new User("Boss", "V1"));System.out.println(q.poll()); // Boss/V1System.out.println(q.poll()); // Bob/A1System.out.println(q.poll()); // Alice/A2System.out.println(q.poll()); // null,因为队列为空}
}class UserComparator implements Comparator<User> {public int compare(User u1, User u2) {if (u1.number.charAt(0) == u2.number.charAt(0)) {// 如果两人的号都是A开头或者都是V开头,比较号的大小:return u1.number.compareTo(u2.number);}if (u1.number.charAt(0) == 'V') {// u1的号码是V开头,优先级高:return -1;} else {return 1;}}
}class User {public final String name;public final String number;public User(String name, String number) {this.name = name;this.number = number;}public String toString() {return name + "/" + number;}
}
实现PriorityQueue的关键在于提供的UserComparator对象，它负责比较两个元素的大小（较小的在前）。UserComparator总是把V开头的号码优先返回，只有在开头相同的时候，才比较号码大
栈（Stack）是一种后进先出（LIFO：Last In First Out）的数据结构。
什么是LIFO呢？我们先回顾一下Queue的特点FIFO：
────────────────────────(\(\ (\(\ (\(\ (\(\ (\(\(='.') ──▶ (='.') (='.') (='.') ──▶ (='.')
O(_")") O(_")") O(_")") O(_")") O(_")")────────────────────────
所谓FIFO，是最先进队列的元素一定最早出队列，而LIFO是最后进Stack的元素一定最早出Stack。如何做到这一点呢？只需要把队列的一端封死：
───────────────────────────────┐(\(\ (\(\ (\(\ (\(\ (\(\ │(='.') ◀──▶ (='.') (='.') (='.') (='.')│
O(_")") O(_")") O(_")") O(_")") O(_")")│───────────────────────────────┘
因此，Stack是这样一种数据结构：只能不断地往Stack中压入（push）元素，最后进去的必须最早弹出（pop）来：
Stack只有入栈和出栈的操作：
- 把元素压栈：
push(E)； - 把栈顶的元素“弹出”：
pop()； - 取栈顶元素但不弹出：
peek()。
在Java中，我们用Deque可以实现Stack的功能：
- 把元素压栈：
push(E)/addFirst(E)； - 把栈顶的元素“弹出”：
pop()/removeFirst()； - 取栈顶元素但不弹出：
peek()/peekFirst()。
为什么Java的集合类没有单独的Stack接口呢？因为有个遗留类名字就叫Stack，出于兼容性考虑，所以没办法创建Stack接口，只能用Deque接口来“模拟”一个Stack了。
当我们把Deque作为Stack使用时，注意只调用push()/pop()/peek()方法，不要调用addFirst()/removeFirst()/peekFirst()方法，这样代码更加清
Stack的作用
Stack在计算机中使用非常广泛，JVM在处理Java方法调用的时候就会通过栈这种数据结构维护方法调用的层次。
-
main方法调用：- JVM 执行到
main方法时，为main方法创建一个栈帧，并将其压入调用栈。 main方法内部调用了sum方法。
- JVM 执行到
-
sum方法调用：- 当
sum方法被调用时，JVM 为sum方法创建一个新的栈帧。 sum方法的参数a和b（分别为 10 和 20）会存储在栈帧的局部变量表中。
- 当
-
方法执行：
sum方法执行a + b的加法操作，计算结果（30）存放在操作数栈中。
-
sum方法返回：sum方法执行完毕后，栈帧被弹出，返回值（30）会传递给main方法，main方法继续执行System.out.println(result)。
-
main方法结束：- 最后，
main方法执行完毕，它的栈帧也会被弹出，程序结束。
- 最后，
Collections是JDK提供的工具类，同样位于java.util包中。它提供了一系列静态方法，能更方便地操作各种集合。
注意
Collections结尾多了一个s，不是Collection！
我们一般看方法名和参数就可以确认Collections提供的该方法的功能。例如，对于以下静态方法：
public static boolean addAll(Collection<? super T> c, T... elements) { ... }
addAll()方法可以给一个Collection类型的集合添加若干元素。因为方法签名是Collection，所以我们可以传入List，Set等各种集合类型。
![[Linux] 信号保存与处理](https://i-blog.csdnimg.cn/direct/743ffdeed37346ffa12c2235e13c9fba.jpeg)
