简介 Collection Java 标准库自带的 java.util 包提供了集合类：Collection，它是除 Map 外所有其他集合类的根接口。Java 的 java.util 包主要提供了以下三种类型的集合：
List：一种有序列表的集合，例如，按索引排列的 Student 的 List；
Set：一种保证没有重复元素的集合，例如，所有无重复名称的 Student 的 Set；
Map：一种通过键值（key-value）查找的映射表集合，例如，根据 Student 的 name 查找对应 Student 的 Map。
Java 集合的设计有几个特点：一是实现了接口和实现类相分离，例如，有序表的接口是 List，具体的实现类有 ArrayList，LinkedList 等，二是支持泛型，我们可以限制在一个集合中只能放入同一种数据类型的元素，例如：1 List<String> list = new ArrayList <>();
由于 Java 的集合设计非常久远，中间经历过大规模改进，我们要注意到有一小部分集合类是遗留类，不应该继续使用：
Hashtable：一种线程安全的 Map 实现；
Vector：一种线程安全的 List 实现；
Stack：基于 Vector 实现的 LIFO 的栈。
还有一小部分接口是遗留接口，也不应该继续使用：
Enumeration：已被 Iterator 取代。
小结
Java 的集合类定义在 java.util 包中，支持泛型，主要提供了 3 种集合类，包括 List，Set 和 Map。Java 集合使用统一的 Iterator 遍历，尽量不要使用遗留接口。
List List 是最基础的一种集合：它是一种有序列表。0 开始。
在实际应用中，需要增删元素的有序列表，我们使用最多的是 ArrayList。实际上，ArrayList 在内部使用了数组来存储所有元素。例如，一个 ArrayList 拥有 5 个元素，实际数组大小为 6（即有一个空位）
List 接口
在末尾添加一个元素：boolean add(E e)
在指定索引添加一个元素：boolean add(int index, E e)
删除指定索引的元素：int remove(int index)
删除某个元素：int remove(Object e)
获取指定索引的元素：E get(int index)
获取链表大小（包含元素的个数）：int size()
但是，实现 List 接口并非只能通过数组（即 ArrayList 的实现方式）来实现，另一种 LinkedList 通过 “链表” 也实现了 List 接口。在 LinkedList 中，它的内部每个元素都指向下一个元素：1 2 3 ┌───┬───┐ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐ HEAD ──>│ A │ ●─┼──>│ B │ ●─┼──>│ C │ ●─┼──>│ D │ │ └───┴───┘ └───┴───┘ └───┴───┘ └───┴───┘
ArrayList
LinkedList
获取指定元素
速度很快
需要从头开始查找元素
添加元素到末尾
速度很快
速度很快
在指定位置添加 / 删除
需要移动元素
不需要移动元素
内存占用
少
较大
通常情况下，我们总是优先使用 ArrayList。
List 的特点 使用 List 时，我们要关注 List 接口的规范。List 接口允许我们添加重复的元素，即 List 内部的元素可以重复：1 2 3 4 5 6 7 8 9 public class Main { public static void main (String[] args) { List<String> list = new ArrayList <String>(); list.add("apple" ); list.add("pear" ); list.add("apple" ); System.out.println(list.size()); } }
1 2 3 4 5 6 7 8 9 10 public class Main { public static void main (String[] args) { List<String> list = new ArrayList <>(); list.add("apple" ); list.add(null ); list.add("pear" ); String second = list.get(1 ); System.out.println(second); } }
创建 List 除了使用 ArrayList 和 LinkedList，我们还可以通过 List 接口提供的 of() 方法，根据给定元素快速创建 List：1 List<Integer> list = List.of(1 , 2 , 5 );
遍历List 和数组类型，我们要遍历一个 List，完全可以用 for 循环根据索引配合 get(int) 方法遍历：1 2 3 4 5 6 7 8 9 public class Main { public static void main (String[] args) { List<String> list = List.of("apple" , "pear" , "banana" ); for (int i=0 ; i<list.size(); i++) { String s = list.get(i); System.out.println(s); } } }
boolean hasNext()判断是否有下一个元素，E next()返回下一个元素。因此，使用Iterator遍历List代码如下：1 2 3 4 5 6 7 8 9 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); } } }
1 2 3 4 5 6 7 8 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); } } }
实际上，只要实现了 Iterable 接口的集合类都可以直接用 for each 循环来遍历，Java 编译器本身并不知道如何遍历集合对象，但它会自动把 for each 循环变成 Iterator 的调用，原因就在于 Iterable 接口定义了一个 Iterator<E> iterator() 方法，强迫集合类必须返回一个 Iterator 实例。
Note: Java的 for - each 遍历不是只读的。
List和Array转换 把List变为Array有三种方法，第一种是调用toArray()方法直接返回一个Object[]数组：1 2 3 4 5 6 7 8 9 public class Main { public static void main (String[] args) { List<String> list = List.of("apple" , "pear" , "banana" ); Object[] array = list.toArray(); for (Object s : array) { System.out.println(s); } } }
第二种方式是给 toArray(T[]) 传入一个类型相同的 Array，List 内部自动把元素复制到传入的 Array 中：1 2 3 4 5 6 7 8 9 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 类型：<T> 并不是 List 接口定义的泛型参数 <E>，所以，我们实际上可以传入其他类型的数组，例如我们传入 Number 类型的数组，返回的仍然是 Number 类型：1 2 3 4 5 6 7 8 9 public class Main { public static void main (String[] args) { List<Integer> list = List.of(12 , 34 , 56 ); Number[] array = list.toArray(new Number [3 ]); for (Number n : array) { System.out.println(n); } } }
String[]类型的数组，由于 List 的元素是 Integer，所以无法放入 String 数组，这个方法会抛出 ArrayStoreException。List 实际的元素个数不一致怎么办？根据 List 接口的文档，我们可以知道：List 内部会创建一个新的刚好够大的数组，填充后返回；如果传入的数组比 List 元素还要多，那么填充完元素后，剩下的数组元素一律填充 null。1 Integer[] array = list.toArray(new Integer [list.size()]);
toArray(IntFunction<T[]> generator) 方法：1 Integer[] array = list.toArray(Integer[]::new );
1 2 Integer[] array = { 1 , 2 , 3 }; List<Integer> list = List.of(array);
Arrays.asList(T...) 方法把数组转换成 List。ArrayList 或者 LinkedList，因为 List 只是一个接口，如果我们调用 List.of()，它返回的是一个只读 List：1 2 3 4 5 6 public class Main { public static void main (String[] args) { List<Integer> list = List.of(12 , 34 , 56 ); list.add(999 ); } }
add()、remove() 方法会抛出 UnsupportedOperationException。
小结
List是按索引顺序访问的长度可变的有序表，优先使用ArrayList而不是LinkedList；
可以直接使用for each遍历List；
List可以和Array相互转换。
编写equal方法 List 还提供了 boolean contains(Object o) 方法来判断 List 是否包含某个指定元素。此外，int indexOf(Object o) 方法可以返回某个元素的索引，如果元素不存在，就返回 -1。1 2 3 4 5 6 7 8 9 public class Main { public static void main (String[] args) { List<String> list = List.of("A" , "B" , "C" ); System.out.println(list.contains("C" )); System.out.println(list.contains("X" )); System.out.println(list.indexOf("C" )); System.out.println(list.indexOf("X" )); } }
"C"和调用contains("C")传入的"C"是不是同一个实例？
如果这两个"C"不是同一个实例，这段代码是否还能得到正确的结果？我们可以改写一下代码测试一下：1 2 3 4 5 6 7 8 import java.util.List;public class Main { public static void main (String[] args) { List<String> list = List.of("A" , "B" , "C" ); System.out.println(list.contains(new String ("C" ))); System.out.println(list.indexOf(new String ("C" ))); } }
new String("C")，所以一定是不同的实例。结果仍然符合预期，这是为什么呢？
因为List内部并不是通过==判断两个元素是否相等，而是使用equals()方法判断两个元素是否相等，例如contains()方法可以实现如下：1 2 3 4 5 6 7 8 9 10 11 public class ArrayList { Object[] elementData; public boolean contains (Object o) { for (int i = 0 ; i < size; i++) { if (o.equals(elementData[i])) { return true ; } } return false ; } }
contains()、indexOf()这些方法，放入的实例必须正确覆写equals()方法，否则，放进去的实例，查找不到。我们之所以能正常放入String、Integer这些对象，是因为Java标准库定义的这些类已经正确实现了equals()方法。
我们以Person对象为例，测试一下：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import java.util.List;public class Main { public static void main (String[] args) { List<Person> list = List.of( new Person ("Xiao Ming" ), new Person ("Xiao Hong" ), new Person ("Bob" ) ); System.out.println(list.contains(new Person ("Bob" ))); } } class Person { String name; public Person (String name) { this .name = name; } }
new Person("Bob")，但是用另一个new Person("Bob")查询不到，原因就是Person类没有覆写equals()方法。
编写equals JAVA当中所有的类都是继承于Object这个超类的，在Object类中定义了一个equals的方法，equals的源码是这样写的：1 2 3 4 5 public boolean equals (Object obj) { return (this == obj); }
如何正确编写equals()方法？equals()方法要求我们必须满足以下条件：
自反性（Reflexive）：对于非 null 的 x 来说，x.equals(x) 必须返回 true；
对称性（Symmetric）：对于非 null 的 x 和 y 来说，如果 x.equals(y) 为 true，则 y.equals(x) 也必须为 true；
传递性（Transitive）：对于非 null 的 x、y 和 z 来说，如果 x.equals(y) 为 true，y.equals(z) 也为 true，那么 x.equals(z) 也必须为 true；
一致性（Consistent）：对于非 null 的 x 和 y 来说，只要 x 和 y 状态不变，则 x.equals(y) 总是一致地返回 true 或者 false；
对 null 的比较：即 x.equals(null) 永远返回 false。
上述规则看上去似乎非常复杂，但其实代码实现equals()方法是很简单的，我们以Person类为例：1 2 3 4 public class Person { public String name; public int age; }
因此，编写equals()方法如下：1 2 3 4 5 6 7 public boolean equals (Object o) { if (o instanceof Person) { Person p = (Person) o; return this .name.equals(p.name) && this .age == p.age; } return false ; }
==。1 2 3 4 5 6 7 8 9 10 11 12 13 14 public boolean equals (Object o) { if (o instanceof Person) { Person p = (Person) o; boolean nameEquals = false ; if (this .name == null && p.name == null ) { nameEquals = true ; } if (this .name != null ) { nameEquals = this .name.equals(p.name); } return nameEquals && this .age == p.age; } return false ; }
equals()方法的正确编写方法：
先确定实例“相等”的逻辑，即哪些字段相等，就认为实例相等；
用instanceof判断传入的待比较的Object是不是当前类型，如果是，继续比较，否则，返回false；
对引用类型用Objects.equals()比较，对基本类型直接用==比较。
使用Objects.equals()比较两个引用类型是否相等的目的是省去了判断null的麻烦。两个引用类型都是null时它们也是相等的。contains()、indexOf()这些方法，那么放入的元素就不需要实现equals()方法。
小结
在List中查找元素时，List的实现类通过元素的equals()方法比较两个元素是否相等，因此，放入的元素必须正确覆写equals()方法，Java标准库提供的String、Integer等已经覆写了equals()方法；
编写equals()方法可借助Objects.equals()判断。
如果不在List中查找元素，就不必覆写equals()方法。
使用Map 我们知道，List是一种顺序列表，如果有一个存储学生Student实例的List，要在List中根据name查找某个指定的Student的分数，应该怎么办？
最简单的方法是遍历List并判断name是否相等，然后返回指定元素：1 2 3 4 5 6 7 8 9 List<Student> list = ... Student target = null ;for (Student s : list) { if ("Xiao Ming" .equals(s.name)) { target = s; break ; } } System.out.println(target.score);
用Map来实现根据name查询某个Student的代码如下：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import java.util.HashMap;import java.util.Map;public class Main { public static void main (String[] args) { Student s = new Student ("Xiao Ming" , 99 ); Map<String, Student> map = new HashMap <>(); map.put("Xiao Ming" , s); Student target = map.get("Xiao Ming" ); System.out.println(target == s); System.out.println(target.score); Student another = map.get("Bob" ); System.out.println(another); } } class Student { public String name; public int score; public Student (String name, int score) { this .name = name; this .score = score; } }
Map<K, V>是一种键-值映射表，当我们调用put(K key, V value)方法时，就把key和value做了映射并放入Map。当我们调用V get(K key)时，就可以通过key获取到对应的value。如果key不存在，则返回null。和List类似，Map也是一个接口，最常用的实现类是HashMap。boolean containsKey(K key)方法。put()方法，分别放入不同的value，会有什么问题呢？例如：1 2 3 4 5 6 7 8 9 10 11 12 13 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 ); System.out.println(map.get("apple" )); map.put("apple" , 789 ); System.out.println(map.get("apple" )); } }
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中不存在重复的key，因为放入相同的key，只会把原有的key-value对应的value给替换掉。
此外，在一个Map中，虽然key不能重复，但value是可以重复的：1 2 3 Map<String, Integer> map = new HashMap <>(); map.put("apple" , 123 ); map.put("pear" , 123 );
遍历Map 对Map来说，要遍历key可以使用for each循环遍历Map实例的keySet()方法返回的Set集合，它包含不重复的key的集合：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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); } } }
for each循环遍历Map对象的entrySet()集合，它包含每一个key-value映射：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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是有序的！
小结
Map是一种映射表，可以通过key快速查找value。
可以通过for each遍历keySet()，也可以通过for each遍历entrySet()，直接获取key-value。
最常用的一种Map实现是HashMap。
编写equals和hashCode Map是一种键-值（key-value）映射表，可以通过key快速查找对应的value。1 2 3 4 5 6 7 Map<String, Person> map = new HashMap <>(); map.put("a" , new Person ("Xiao Ming" )); map.put("b" , new Person ("Xiao Hong" )); map.put("c" , new Person ("Xiao Jun" )); map.get("a" ); map.get("x" );
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ┌───┐ 0 │ │ ├───┤ 1 │ ●─┼───> Person("Xiao Ming") ├───┤ 2 │ │ ├───┤ 3 │ │ ├───┤ 4 │ │ ├───┤ 5 │ ●─┼───> Person("Xiao Hong") ├───┤ 6 │ ●─┼───> Person("Xiao Jun") ├───┤ 7 │ │ └───┘
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import java.util.HashMap;import java.util.Map;public class Main { public static void main (String[] args) { String key1 = "a" ; Map<String, Integer> map = new HashMap <>(); map.put(key1, 123 ); String key2 = new String ("a" ); map.get(key2); System.out.println(key1 == key2); System.out.println(key1.equals(key2)); } }
作为key的对象必须正确覆写equals()方法，相等的两个key实例调用equals()必须返回true；
作为key的对象还必须正确覆写hashCode()方法，且hashCode()方法要严格遵循以下规范：
如果两个对象相等，则两个对象的hashCode()必须相等；
如果两个对象不相等，则两个对象的hashCode()尽量不要相等。
即对应两个实例a和b：
如果a和b相等，那么a.equals(b)一定为true，则a.hashCode()必须等于b.hashCode()；
如果a和b不相等，那么a.equals(b)一定为false，则a.hashCode()和b.hashCode()尽量不要相等。
上述第一条规范是正确性，必须保证实现，否则HashMap不能正常工作。编写equals方法一节中讲过了。
在正确实现equals()的基础上，我们还需要正确实现hashCode()，即上述3个字段分别相同的实例，hashCode()返回的int必须相同：1 2 3 4 5 6 7 8 9 10 11 12 13 14 public class Person { String firstName; String lastName; int age; @Override int hashCode () { int h = 0 ; h = 31 * h + firstName.hashCode(); h = 31 * h + lastName.hashCode(); h = 31 * h + age; return h; } }
1 2 3 int hashCode () { return Objects.hash(firstName, lastName, age); }
延伸阅读 既然HashMap内部使用了数组，通过计算key的hashCode()直接定位value所在的索引，那么第一个问题来了：hashCode()返回的int范围高达±21亿，先不考虑负数，HashMap内部使用的数组得有多大？1 int index = key.hashCode() & 0xf ;
第二个问题：如果添加超过16个key-value到HashMap，数组不够用了怎么办？1 int index = key.hashCode() & 0x1f ;
1 Map<String, Integer> map = new HashMap <>(10000 );
最后一个问题：如果不同的两个key，例如”a”和”b”，它们的hashCode()恰好是相同的（这种情况是完全可能的，因为不相等的两个实例，只要求hashCode()尽量不相等），那么，当我们放入：1 2 map.put("a" , new Person ("Xiao Ming" )); map.put("b" , new Person ("Xiao Hong" ));
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ┌───┐ 0 │ │ ├───┤ 1 │ │ ├───┤ 2 │ │ ├───┤ 3 │ │ ├───┤ 4 │ │ ├───┤ 5 │ ●─┼───> List<Entry<String, Person>> ├───┤ 6 │ │ ├───┤ 7 │ │ └───┘
1 Person p = map.get("a" );
List<Entry<String, Person>>，它还需要遍历这个List，并找到一个Entry，它的key字段是”a”，才能返回对应的Person实例。如果两个对象不相等，则两个对象的hashCode()尽量不要相等。
小结
要正确使用HashMap，作为key的类必须正确覆写equals()和hashCode()方法；
一个类如果覆写了equals()，就必须覆写hashCode()，并且覆写规则是：
如果equals()返回true，则hashCode()返回值必须相等；
如果equals()返回false，则hashCode()返回值尽量不要相等。
实现hashCode()方法可以通过Objects.hashCode()辅助方法实现。
使用EnumMap 因为HashMap是一种通过对key计算hashCode()，通过空间换时间的方式，直接定位到value所在的内部数组的索引，因此，查找效率非常高。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import java.time.DayOfWeek;import java.util.*;public class Main { public static void main (String[] args) { Map<DayOfWeek, String> map = new EnumMap <>(DayOfWeek.class); map.put(DayOfWeek.MONDAY, "星期一" ); map.put(DayOfWeek.TUESDAY, "星期二" ); map.put(DayOfWeek.WEDNESDAY, "星期三" ); map.put(DayOfWeek.THURSDAY, "星期四" ); map.put(DayOfWeek.FRIDAY, "星期五" ); map.put(DayOfWeek.SATURDAY, "星期六" ); map.put(DayOfWeek.SUNDAY, "星期日" ); System.out.println(map); System.out.println(map.get(DayOfWeek.MONDAY)); } }
小结
如果Map的key是enum类型，推荐使用EnumMap，既保证速度，也不浪费空间。
使用EnumMap的时候，根据面向抽象编程的原则，应持有Map接口。
使用TreeMap 我们已经知道，HashMap是一种以空间换时间的映射表，它的实现原理决定了内部的Key是无序的，即遍历HashMap的Key时，其顺序是不可预测的（但每个Key都会遍历一次且仅遍历一次）。1 2 3 4 5 6 7 8 9 10 11 12 13 14 ┌───┐ │Map│ └───┘ ▲ ┌────┴─────┐ │ │ ┌───────┐ ┌─────────┐ │HashMap│ │SortedMap│ └───────┘ └─────────┘ ▲ │ ┌─────────┐ │ TreeMap │ └─────────┘
1 2 3 4 5 6 7 8 9 10 11 12 13 14 import java.util.*;public class Main { public static void main (String[] args) { Map<String, Integer> map = new TreeMap <>(); map.put("orange" , 1 ); map.put("apple" , 2 ); map.put("pear" , 3 ); for (String key : map.keySet()) { System.out.println(key); } } }
Comparable接口。String、Integer这些类已经实现了Comparable接口，因此可以直接作为Key使用。作为Value的对象则没有任何要求。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 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); } System.out.println(map.get(new Person ("Bob" ))); } } class Person { public String name; Person(String name) { this .name = name; } public String toString () { return "{Person: " + name + "}" ; } }
a<b，则返回负数，通常是-1，如果a==b，则返回0，如果a>b，则返回正数，通常是1。TreeMap内部根据比较结果对Key进行排序。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import java.util.*;public class Main { public static void main (String[] args) { Map<Student, Integer> map = new TreeMap <>(new Comparator <Student>() { public int compare (Student p1, Student p2) { return p1.score > p2.score ? -1 : 1 ; } }); map.put(new Student ("Tom" , 77 ), 1 ); map.put(new Student ("Bob" , 66 ), 2 ); map.put(new Student ("Lily" , 99 ), 3 ); for (Student key : map.keySet()) { System.out.println(key); } System.out.println(map.get(new Student ("Bob" , 66 ))); } } class Student { public String name; public int score; Student(String name, int score) { this .name = name; this .score = score; } public String toString () { return String.format("{%s: score=%d}" , name, score); } }
new Student("Bob", 66)进行查找时，结果为null！1 2 3 public int compare (Student p1, Student p2) { return p1.score > p2.score ? -1 : 1 ; }
p1.score和p2.score不相等的时候，它的返回值是正确的，但是，在p1.score和p2.score相等的时候，它并没有返回0！这就是为什么TreeMap工作不正常的原因：TreeMap在比较两个Key是否相等时，依赖Key的compareTo()方法或者Comparator.compare()方法。在两个Key相等时，必须返回0。因此，修改代码如下：1 2 3 4 5 6 public int compare (Student p1, Student p2) { if (p1.score == p2.score) { return 0 ; } return p1.score > p2.score ? -1 : 1 ; }
小结
SortedMap在遍历时严格按照Key的顺序遍历，最常用的实现类是TreeMap；
作为SortedMap的Key必须实现Comparable接口，或者传入Comparator；
要严格按照compare()规范实现比较逻辑，否则，TreeMap将不能正常工作。
使用Properties 在编写应用程序的时候，经常需要读写配置文件。例如，用户的设置：1 2 3 4 # 上次最后打开的文件: last_open_file=/data/hello.txt # 自动保存文件的时间间隔: auto_save_interval=60
Map<String, String>来表示它。
读取配置文件 用Properties读取配置文件非常简单。Java默认配置文件以.properties为扩展名，每行以key=value表示，以#课开头的是注释。以下是一个典型的配置文件：1 2 3 4 last_open_file =/data/hello.txt auto_save_interval =60
.properties文件：1 2 3 4 5 6 String f = "setting.properties" ;Properties props = new Properties ();props.load(new java .io.FileInputStream(f)); String filepath = props.getProperty("last_open_file" );String interval = props.getProperty("auto_save_interval" , "120" );
创建Properties实例；
调用load()读取文件；
调用getProperty()获取配置。
调用getProperty()获取配置时，如果key不存在，将返回null。我们还可以提供一个默认值，这样，当key不存在的时候，就返回默认值。.properties文件，因为load(InputStream)方法接收一个InputStream实例，表示一个字节流，它不一定是文件流，也可以是从jar包中读取的资源流：1 2 Properties props = new Properties ();props.load(getClass().getResourceAsStream("/common/setting.properties" ));
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import java.io.*;import java.util.Properties;public class Main { public static void main (String[] args) throws IOException { String settings = "# test" + "\n" + "course=Java" + "\n" + "last_open_date=2019-08-07T12:35:01" ; ByteArrayInputStream input = new ByteArrayInputStream (settings.getBytes("UTF-8" )); Properties props = new Properties (); props.load(input); System.out.println("course: " + props.getProperty("course" )); System.out.println("last_open_date: " + props.getProperty("last_open_date" )); System.out.println("last_open_file: " + props.getProperty("last_open_file" )); System.out.println("auto_save: " + props.getProperty("auto_save" , "60" )); } }
1 2 3 Properties props = new Properties ();props.load(getClass().getResourceAsStream("/common/setting.properties" )); props.load(new FileInputStream ("C:\\conf\\setting.properties" ));
写入配置文件 如果通过setProperty()修改了Properties实例，可以把配置写入文件，以便下次启动时获得最新配置。写入配置文件使用store()方法：1 2 3 4 Properties props = new Properties ();props.setProperty("url" , "http://www.liaoxuefeng.com" ); props.setProperty("language" , "Java" ); props.store(new FileOutputStream ("C:\\conf\\setting.properties" ), "这是写入的properties注释" );
编码 早期版本的Java规定.properties文件编码是ASCII编码（ISO8859-1），如果涉及到中文就必须用name=\u4e2d\u6587来表示，非常别扭。从JDK9开始，Java的.properties文件可以使用UTF-8编码了。1 2 Properties props = new Properties ();props.load(new FileReader ("settings.properties" , StandardCharsets.UTF_8));
小结
Java集合库提供的Properties用于读写配置文件.properties。.properties文件可以使用UTF-8编码。
可以从文件系统、classpath或其他任何地方读取.properties文件。
读写Properties时，注意仅使用getProperty()和setProperty()方法，不要调用继承而来的get()和put()等方法。
使用Set 我们知道，Map用于存储key-value的映射，对于充当key的对象，是不能重复的，并且，不但需要正确覆写equals()方法，还要正确覆写hashCode()方法。
将元素添加进Set<E>：boolean add(E e)
将元素从Set<E>删除：boolean remove(Object e)
判断是否包含元素：boolean contains(Object e)
我们来看几个简单的例子：1 2 3 4 5 6 7 8 9 10 11 12 13 import java.util.*;public class Main { public static void main (String[] args) { Set<String> set = new HashSet <>(); System.out.println(set.add("abc" )); System.out.println(set.add("xyz" )); System.out.println(set.add("xyz" )); System.out.println(set.contains("xyz" )); System.out.println(set.contains("XYZ" )); System.out.println(set.remove("hello" )); System.out.println(set.size()); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public class HashSet <E> implements Set <E> { private HashMap<E, Object> map = new HashMap <>(); private static final Object PRESENT = new Object (); public boolean add (E e) { return map.put(e, PRESENT) == null ; } public boolean contains (Object o) { return map.containsKey(o); } public boolean remove (Object o) { return map.remove(o) == PRESENT; } }
HashSet是无序的，因为它实现了Set接口，并没有实现SortedSet接口；
TreeSet是有序的，因为它实现了SortedSet接口。
用一张图表示：1 2 3 4 5 6 7 8 9 10 11 12 13 14 ┌───┐ │Set│ └───┘ ▲ ┌────┴─────┐ │ │ ┌───────┐ ┌─────────┐ │HashSet│ │SortedSet│ └───────┘ └─────────┘ ▲ │ ┌─────────┐ │ TreeSet │ └─────────┘
1 2 3 4 5 6 7 8 9 10 11 12 13 import java.util.*;public class Main { public static void main (String[] args) { Set<String> set = new HashSet <>(); set.add("apple" ); set.add("banana" ); set.add("pear" ); set.add("orange" ); for (String s : set) { System.out.println(s); } } }
1 2 3 4 5 6 7 8 9 10 11 12 13 import java.util.*;public class Main { public static void main (String[] args) { Set<String> set = new TreeSet <>(); set.add("apple" ); set.add("banana" ); set.add("pear" ); set.add("orange" ); for (String s : set) { System.out.println(s); } } }
小结
Set用于存储不重复的元素集合：
放入HashSet的元素与作为HashMap的key要求相同；
放入TreeSet的元素与作为TreeMap的Key要求相同；
利用Set可以去除重复元素；
遍历SortedSet按照元素的排序顺序遍历，也可以自定义排序算法。
使用Queue 队列（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()：获取队首元素但并不从队列中删除。
对于具体的实现类，有的Queue有最大队列长度限制，有的Queue没有。注意到添加、删除和获取队列元素总是有两个方法，这是因为在添加或获取元素失败时，这两个方法的行为是不同的。我们用一个表格总结如下：
throw Exception
返回false或null
添加元素到队尾
add(E e)
boolean offer(E e)
取队首元素并删除
E remove()
E poll()
取队首元素但不删除
E element()
E peek()
举个栗子，假设我们有一个队列，对它做一个添加操作，如果调用add()方法，当添加失败时（可能超过了队列的容量），它会抛出异常：
1 2 3 4 5 6 7 Queue<String> q = ... try { q.add("Apple" ); System.out.println("添加成功" ); } catch (IllegalStateException e) { System.out.println("添加失败" ); }
如果我们调用offer()方法来添加元素，当添加失败时，它不会抛异常，而是返回false：
1 2 3 4 5 6 Queue<String> q = ... if (q.offer("Apple" )) { System.out.println("添加成功" ); } else { System.out.println("添加失败" ); }
当我们需要从Queue中取出队首元素时，如果当前Queue是一个空队列，调用remove()方法，它会抛出异常：
1 2 3 4 5 6 7 Queue<String> q = ... try { String s = q.remove(); System.out.println("获取成功" ); } catch (IllegalStateException e) { System.out.println("获取失败" ); }
如果我们调用poll()方法来取出队首元素，当获取失败时，它不会抛异常，而是返回null：
1 2 3 4 5 6 7 Queue<String> q = ... String s = q.poll();if (s != null ) { System.out.println("获取成功" ); } else { System.out.println("获取失败" ); }
因此，两套方法可以根据需要来选择使用。
注意：不要把null添加到队列中，否则poll()方法返回null时，很难确定是取到了null元素还是队列为空。
接下来我们以poll()和peek()为例来说说“获取并删除”与“获取但不删除”的区别。对于Queue来说，每次调用poll()，都会获取队首元素，并且获取到的元素已经从队列中被删除了：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import java.util.LinkedList;import java.util.Queue;public class Main { public static void main (String[] args) { Queue<String> q = new LinkedList <>(); q.offer("apple" ); q.offer("pear" ); q.offer("banana" ); System.out.println(q.poll()); System.out.println(q.poll()); System.out.println(q.poll()); System.out.println(q.poll()); } }
如果用peek()，因为获取队首元素时，并不会从队列中删除这个元素，所以可以反复获取：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import java.util.LinkedList;import java.util.Queue;public class Main { public static void main (String[] args) { Queue<String> q = new LinkedList <>(); q.offer("apple" ); q.offer("pear" ); q.offer("banana" ); System.out.println(q.peek()); System.out.println(q.peek()); System.out.println(q.peek()); } }
从上面的代码中，我们还可以发现，LinkedList即实现了List接口，又实现了Queue接口，但是，在使用的时候，如果我们把它当作List，就获取List的引用，如果我们把它当作Queue，就获取Queue的引用：
1 2 3 4 List<String> list = new LinkedList <>(); Queue<String> queue = new LinkedList <>();
始终按照面向抽象编程的原则编写代码，可以大大提高代码的质量。
小结
队列Queue实现了一个先进先出（FIFO）的数据结构：
通过add()/offer()方法将元素添加到队尾；
通过remove()/poll()从队首获取元素并删除；
通过element()/peek()从队首获取元素但不删除。
要避免把null添加到队列。
使用PriorityQueue 我们知道，Queue是一个先进先出（FIFO）的队列。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import java.util.PriorityQueue;import java.util.Queue;public class Main { public static void main (String[] args) { Queue<String> q = new PriorityQueue <>(); q.offer("apple" ); q.offer("pear" ); q.offer("banana" ); System.out.println(q.poll()); System.out.println(q.poll()); System.out.println(q.poll()); System.out.println(q.poll()); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 public class Main { public static void main (String[] args) { Queue<User> q = new PriorityQueue <>(new UserComparator ()); q.offer(new User ("Bob" , "A1" )); q.offer(new User ("Alice" , "A2" )); q.offer(new User ("Boss" , "V1" )); System.out.println(q.poll()); System.out.println(q.poll()); System.out.println(q.poll()); System.out.println(q.poll()); } } class UserComparator implements Comparator <User> { public int compare (User u1, User u2) { if (u1.number.charAt(0 ) == u2.number.charAt(0 )) { return u1.number.compareTo(u2.number); } if (u1.number.charAt(0 ) == 'V' ) { return -1 ; } else { return 1 ; } } }
小结
PriorityQueue实现了一个优先队列：从队首获取元素时，总是获取优先级最高的元素。
PriorityQueue默认按元素比较的顺序排序（必须实现Comparable接口），也可以通过Comparator自定义排序算法（元素就不必实现Comparable接口）。
使用Deque 我们知道，Queue是队列，只能一头进，另一头出。
既可以添加到队尾，也可以添加到队首；
既可以从队首获取，又可以从队尾获取。
Queue
Deque
添加元素到队尾
add(E e) / offer(E e)
addLast(E e) / offerLast(E e)
取队首元素并删除
E remove() / E poll()
E removeFirst() / E pollFirst()
取队首元素但不删除
E element() / E peek()
E getFirst() / E peekFirst()
添加元素到队首
无
addFirst(E e) / offerFirst(E e)
取队尾元素并删除
无
E removeLast() / E pollLast()
取队尾元素但不删除
无
E getLast() / E peekLast()
对于添加元素到队尾的操作，Queue提供了add()/offer()方法，而Deque提供了addLast()/offerLast()方法。添加元素到对首、取队尾元素的操作在Queue中不存在，在Deque中由addFirst()/removeLast()等方法提供。1 2 3 public interface Deque<E> extends Queue<E> { ... }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import java.util.Deque;import java.util.LinkedList;public class Main { public static void main (String[] args) { Deque<String> deque = new LinkedList <>(); deque.offerLast("A" ); deque.offerLast("B" ); deque.offerFirst("C" ); System.out.println(deque.pollFirst()); System.out.println(deque.pollLast()); System.out.println(deque.pollFirst()); System.out.println(deque.pollFirst()); } }
1 2 3 4 5 6 LinkedList<String> d1 = new LinkedList <>(); d1.offerLast("z" ); Deque<String> d2 = new LinkedList <>(); d2.offerLast("z" );
小结 Deque实现了一个双端队列（Double Ended Queue），它可以：
将元素添加到队尾或队首：addLast()/offerLast()/addFirst()/offerFirst()；
从队首／队尾获取元素并删除：removeFirst()/pollFirst()/removeLast()/pollLast()；
从队首／队尾获取元素但不删除：getFirst()/peekFirst()/getLast()/peekLast()；
总是调用xxxFirst()/xxxLast()以便与Queue的方法区分开；
避免把null添加到队列。
使用Stack 栈（Stack）是一种后进先出（LIFO：Last In First Out）的数据结构。1 2 3 4 5 ──────────────────────── (\(\ (\(\ (\(\ (\(\ (\(\ (='.') ─> (='.') (='.') (='.') ─> (='.') O(_")") O(_")") O(_")") O(_")") O(_")") ────────────────────────
1 2 3 4 5 ───────────────────────────────┐ (\(\ (\(\ (\(\ (\(\ (\(\ │ (='.') <─> (='.') (='.') (='.') (='.')│ O(_")") O(_")") O(_")") O(_")") O(_")")│ ───────────────────────────────┘
把元素压栈：push(E)；
把栈顶的元素“弹出”：pop(E)；
取栈顶元素但不弹出：peek(E)。
在Java中，我们用Deque可以实现Stack的功能：
把元素压栈：push(E)/addFirst(E)；
把栈顶的元素“弹出”：pop(E)/removeFirst()；
取栈顶元素但不弹出：peek(E)/peekFirst()。
为什么Java的集合类没有单独的Stack接口呢？因为有个遗留类名字就叫Stack，出于兼容性考虑，所以没办法创建Stack接口，只能用Deque接口来“模拟”一个Stack了。
Stack的作用 Stack在计算机中使用非常广泛，JVM在处理Java方法调用的时候就会通过栈这种数据结构维护方法调用的层次。例如：1 2 3 4 5 6 7 8 9 10 11 static void main (String[] args) { foo(123 ); } static String foo (x) { return "F-" + bar(x + 1 ); } static int bar (int x) { return x << 2 ; }
1 2 3 4 5 6 7 8 9 public class Main { public static void main (String[] args) { increase(1 ); } static int increase (int x) { return increase(x) + 1 ; } }
计算中缀表达式 小结
栈（Stack）是一种后进先出（LIFO）的数据结构，操作栈的元素的方法有：
把元素压栈：push(E)；
把栈顶的元素“弹出”：pop(E)；
取栈顶元素但不弹出：peek(E)。
在Java中，我们用Deque可以实现Stack的功能，注意只调用push()/pop()/peek()方法，避免调用Deque的其他方法。
最后，不要使用遗留类Stack。
使用Iterator Java的集合类都可以使用for each循环，List、Set和Queue会迭代每个元素，Map会迭代每个key。以List为例：1 2 3 4 List<String> list = List.of("Apple" , "Orange" , "Pear" ); for (String s : list) { System.out.println(s); }
1 2 3 4 for (Iterator<String> it = list.iterator(); it.hasNext(); ) { String s = it.next(); System.out.println(s); }
1 2 3 for (int i=0 ; i<list.size(); i++) { Object value = list.get(i); }
集合类实现Iterable接口，该接口要求返回一个Iterator对象；
用Iterator对象迭代集合内部数据。
这里的关键在于，集合类通过调用iterator()方法，返回一个Iterator对象，这个对象必须自己知道如何遍历该集合。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 import java.util.*;public class Main { public static void main (String[] args) { ReverseList<String> rlist = new ReverseList <>(); rlist.add("Apple" ); rlist.add("Orange" ); rlist.add("Pear" ); for (String s : rlist) { System.out.println(s); } } } class ReverseList <T> implements Iterable <T> { private List<T> list = new ArrayList <>(); public void add (T t) { list.add(t); } @Override public Iterator<T> iterator () { return new ReverseIterator (list.size()); } class ReverseIterator implements Iterator <T> { int index; ReverseIterator(int index) { this .index = index; } @Override public boolean hasNext () { return index > 0 ; } @Override public T next () { index--; return ReverseList.this .list.get(index); } } }
小结
Iterator是一种抽象的数据访问模型。使用Iterator模式进行迭代的好处有：
对任何集合都采用同一种访问模型；
调用者对集合内部结构一无所知；
集合类返回的Iterator对象知道如何迭代。
Java提供了标准的迭代器模型，即集合类实现java.util.Iterable接口，返回java.util.Iterator实例。
使用Collections Collections是JDK提供的工具类，同样位于java.util包中。它提供了一系列静态方法，能更方便地操作各种集合。
注意Collections结尾多了一个s，不是Collection！1 public static boolean addAll (Collection<? super T> c, T... elements) { ... }
创建空集合 Collections提供了一系列方法来创建空集合：
创建空List：List<T> emptyList()
创建空Map：Map<K, V> emptyMap()
创建空Set：Set<T> emptySet()
要注意到返回的空集合是不可变集合，无法向其中添加或删除元素。1 2 List<String> list1 = List.of(); List<String> list2 = Collections.emptyList();
创建单元素集合 Collections提供了一系列方法来创建一个单元素集合：
创建一个元素的List：List<T> singletonList(T o)
创建一个元素的Map：Map<K, V> singletonMap(K key, V value)
创建一个元素的Set：Set<T> singleton(T o)
要注意到返回的单元素集合也是不可变集合，无法向其中添加或删除元素。1 2 List<String> list1 = List.of("apple" ); List<String> list2 = Collections.singletonList("apple" );
List.of(T...)更方便，因为它既可以创建空集合，也可以创建单元素集合，还可以创建任意个元素的集合：1 2 3 4 List<String> list1 = List.of(); List<String> list2 = List.of("apple" ); List<String> list3 = List.of("apple" , "pear" ); List<String> list4 = List.of("apple" , "pear" , "orange" );
排序 Collections可以对List进行排序。因为排序会直接修改List元素的位置，因此必须传入可变List：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 import java.util.*;public class Main { public static void main (String[] args) { List<String> list = new ArrayList <>(); list.add("apple" ); list.add("pear" ); list.add("orange" ); System.out.println(list); Collections.sort(list); System.out.println(list); } }
洗牌 Collections提供了洗牌算法，即传入一个有序的List，可以随机打乱List内部元素的顺序，效果相当于让计算机洗牌：1 2 3 4 5 6 7 8 9 10 11 12 13 14 import java.util.*;public class Main { public static void main (String[] args) { List<Integer> list = new ArrayList <>(); for (int i=0 ; i<10 ; i++) { list.add(i); } System.out.println(list); Collections.shuffle(list); System.out.println(list); } }
不可变集合 Collections还提供了一组方法把可变集合封装成不可变集合：
封装成不可变List：List<T> unmodifiableList(List<? extends T> list)
封装成不可变Set：Set<T> unmodifiableSet(Set<? extends T> set)
封装成不可变Map：Map<K, V> unmodifiableMap(Map<? extends K, ? extends V> m)
这种封装实际上是通过创建一个代理对象，拦截掉所有修改方法实现的。我们来看看效果：1 2 3 4 5 6 7 8 9 10 public class Main { public static void main (String[] args) { List<String> mutable = new ArrayList <>(); mutable.add("apple" ); mutable.add("pear" ); List<String> immutable = Collections.unmodifiableList(mutable); immutable.add("orange" ); } }
1 2 3 4 5 6 7 8 9 10 11 12 import java.util.*;public class Main { public static void main (String[] args) { List<String> mutable = new ArrayList <>(); mutable.add("apple" ); mutable.add("pear" ); List<String> immutable = Collections.unmodifiableList(mutable); mutable.add("orange" ); System.out.println(immutable); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 import java.util.*;public class Main { public static void main (String[] args) { List<String> mutable = new ArrayList <>(); mutable.add("apple" ); mutable.add("pear" ); List<String> immutable = Collections.unmodifiableList(mutable); mutable = null ; System.out.println(immutable); } }
线程安全集合 Collections还提供了一组方法，可以把线程不安全的集合变为线程安全的集合：
变为线程安全的List：List<T> synchronizedList(List<T> list)
变为线程安全的Set：Set<T> synchronizedSet(Set<T> s)
变为线程安全的Map：Map<K,V> synchronizedMap(Map<K,V> m)
多线程的概念我们会在后面讲。因为从Java 5开始，引入了更高效的并发集合类，所以上述这几个同步方法已经没有什么用了。
小结 Collections类提供了一组工具方法来方便使用集合类：
创建空集合；
创建单元素集合；
创建不可变集合；
排序／洗牌等操作。
