Java集合简介
什么是集合(Collection)?集合就是“由若干个确定的元素所构成的整体”。例如,5只小兔构成的集合:
1 2 3 4 5 6 7 ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ │ (\_(\ (\_/) (\_/) (\_/) (\(\ │ ( -.-) (•.•) (>.<) (^.^) (='.') │ C(")_(") (")_(") (")_(") (")_(") O(_")") │ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘
在数学中,我们经常遇到集合的概念。例如:
有限集合:
一个班所有的同学构成的集合;
一个网站所有的商品构成的集合;
…
无限集合:
全体自然数集合:1,2,3,……
有理数集合;
实数集合;
…
为什么要在计算机中引入集合呢?这是为了便于处理一组类似的数据,例如:
计算所有同学的总成绩和平均成绩;
列举所有的商品名称和价格;
……
在Java中,如果一个Java对象可以在内部持有若干其他Java对象,并对外提供访问接口,我们把这种Java对象称为集合。很显然,Java的数组可以看作是一种集合:
1 2 3 String[] ss = new String [10 ]; ss[0 ] = "Hello" ; String first = ss[0 ];
既然Java提供了数组这种数据类型,可以充当集合,那么,我们为什么还需要其他集合类?这是因为数组有如下限制:
数组初始化后大小不可变;
数组只能按索引顺序存取。
因此,我们需要各种不同类型的集合类来处理不同的数据,例如:
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访问集合总是通过统一的方式——迭代器(Iterator)来实现,它最明显的好处在于无需知道集合内部元素是按什么方式存储的。
由于Java的集合设计非常久远,中间经历过大规模改进,我们要注意到有一小部分集合类是遗留类,不应该继续使用:
Hashtable
:一种线程安全的Map
实现;
Vector
:一种线程安全的List
实现;
Stack
:基于Vector
实现的LIFO
的栈。
还有一小部分接口是遗留接口,也不应该继续使用:
Enumeration<E>
:已被Iterator<E>
取代。
小结
Java的集合类定义在java.util
包中,支持泛型,主要提供了3种集合类,包括List
,Set
和Map
。Java集合使用统一的Iterator
遍历,尽量不要使用遗留接口。
在集合类中,List
是最基础的一种集合:它是一种有序列表。
List
的行为和数组几乎完全相同:List
内部按照放入元素的先后顺序存放,每个元素都可以通过索引确定自己的位置,List
的索引和数组一样,从0
开始。
数组和List
类似,也是有序结构,如果我们使用数组,在添加和删除元素的时候,会非常不方便。例如,从一个已有的数组{'A', 'B', 'C', 'D', 'E'}
中删除索引为2
的元素:
1 2 3 4 5 6 7 8 9 10 11 ┌───┬───┬───┬───┬───┬───┐ │ A │ B │ C │ D │ E │ │ └───┴───┴───┴───┴───┴───┘ │ │ ┌───┘ │ │ ┌───┘ │ │ ▼ ▼ ┌───┬───┬───┬───┬───┬───┐ │ A │ B │ D │ E │ │ │ └───┴───┴───┴───┴───┴───┘
这个“删除”操作实际上是把'C'
后面的元素依次往前挪一个位置,而“添加”操作实际上是把指定位置以后的元素都依次向后挪一个位置,腾出来的位置给新加的元素。这两种操作,用数组实现非常麻烦。
因此,在实际应用中,需要增删元素的有序列表,我们使用最多的是ArrayList
。实际上,ArrayList
在内部使用了数组来存储所有元素。例如,一个ArrayList
拥有5个元素,实际数组大小为6
(即有一个空位):
1 2 3 4 size=5 ┌───┬───┬───┬───┬───┬───┐ │ A │ B │ C │ D │ E │ │ └───┴───┴───┴───┴───┴───┘
当添加一个元素并指定索引到ArrayList
时,ArrayList
自动移动需要移动的元素:
1 2 3 4 size=5 ┌───┬───┬───┬───┬───┬───┐ │ A │ B │ │ C │ D │ E │ └───┴───┴───┴───┴───┴───┘
然后,往内部指定索引的数组位置添加一个元素,然后把size
加1
:
1 2 3 4 size=6 ┌───┬───┬───┬───┬───┬───┐ │ A │ B │ F │ C │ D │ E │ └───┴───┴───┴───┴───┴───┘
继续添加元素,但是数组已满,没有空闲位置的时候,ArrayList
先创建一个更大的新数组,然后把旧数组的所有元素复制到新数组,紧接着用新数组取代旧数组:
1 2 3 4 size=6 ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐ │ A │ B │ F │ C │ D │ E │ │ │ │ │ │ │ └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
现在,新数组就有了空位,可以继续添加一个元素到数组末尾,同时size
加1
:
1 2 3 4 size=7 ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐ │ A │ B │ F │ C │ D │ E │ G │ │ │ │ │ │ └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
可见,ArrayList
把添加和删除的操作封装起来,让我们操作List
类似于操作数组,却不用关心内部元素如何移动。
我们考察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
接口并非只能通过数组(即ArrayList
的实现方式)来实现,另一种LinkedList
通过“链表”也实现了List接口。在LinkedList
中,它的内部每个元素都指向下一个元素:
1 2 3 ┌───┬───┐ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐ HEAD ──▶│ A │ ●─┼──▶│ B │ ●─┼──▶│ C │ ●─┼──▶│ D │ │ └───┴───┘ └───┴───┘ └───┴───┘ └───┴───┘
我们来比较一下ArrayList
和LinkedList
:
ArrayList
LinkedList
获取指定元素
速度很快
需要从头开始查找元素
添加元素到末尾
速度很快
速度很快
在指定位置添加/删除
需要移动元素
不需要移动元素
内存占用
少
较大
通常情况下,我们总是优先使用ArrayList
。
List的特点
使用List
时,我们要关注List
接口的规范。List
接口允许我们添加重复的元素,即List
内部的元素可以重复:
1 2 3 4 5 6 7 8 9 10 11 12 import java.util.ArrayList;import java.util.List;public class Main { public static void main (String[] args) { List<String> list = new ArrayList <>(); list.add("apple" ); list.add("pear" ); list.add("apple" ); System.out.println(list.size()); } }
List
还允许添加null
:
1 2 3 4 5 6 7 8 9 10 11 12 13 import java.util.ArrayList;import java.util.List;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.of()
方法不接受null
值,如果传入null
,会抛出NullPointerException
异常。
遍历List
和数组类型类似,我们要遍历一个List
,完全可以用for
循环根据索引配合get(int)
方法遍历:
1 2 3 4 5 6 7 8 9 10 11 import java.util.List;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); } } }
但这种方式并不推荐,一是代码复杂,二是因为get(int)
方法只有ArrayList
的实现是高效的,换成LinkedList
后,索引越大,访问速度越慢。
所以我们要始终坚持使用迭代器Iterator
来访问List
。Iterator
本身也是一个对象,但它是由List
的实例调用iterator()
方法的时候创建的。Iterator
对象知道如何遍历一个List
,并且不同的List
类型,返回的Iterator
对象实现也是不同的,但总是具有最高的访问效率。
Iterator
对象有两个方法:boolean hasNext()
判断是否有下一个元素,E next()
返回下一个元素。因此,使用Iterator
遍历List
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 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); } } }
有童鞋可能觉得使用Iterator
访问List
的代码比使用索引更复杂。但是,要记住,通过Iterator
遍历List
永远是最高效的方式。并且,由于Iterator
遍历是如此常用,所以,Java的for each
循环本身就可以帮我们使用Iterator
遍历。把上面的代码再改写如下:
1 2 3 4 5 6 7 8 9 10 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
有三种方法,第一种是调用toArray()
方法直接返回一个Object[]
数组:
1 2 3 4 5 6 7 8 9 10 11 import java.util.List;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 10 11 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
类型:
1 2 3 4 5 6 7 8 9 10 11 import java.util.List;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()]);
最后一种更简洁的写法是通过List
接口定义的T[] toArray(IntFunction<T[]> generator)
方法:
1 Integer[] array = list.toArray(Integer[]::new );
这种函数式写法我们会在后续讲到。
反过来,把Array
变为List
就简单多了,通过List.of(T...)
方法最简单:
1 2 Integer[] array = { 1 , 2 , 3 }; List<Integer> list = List.of(array);
对于JDK 11之前的版本,可以使用Arrays.asList(T...)
方法把数组转换成List
。
要注意的是,返回的List
不一定就是ArrayList
或者LinkedList
,因为List
只是一个接口,如果我们调用List.of()
,它返回的是一个只读List
:
1 2 3 4 5 6 7 8 import java.util.List;public class Main { public static void main (String[] args) { List<Integer> list = List.of(12 , 34 , 56 ); list.add(999 ); } }
对只读List
调用add()
、remove()
方法会抛出UnsupportedOperationException
。
练习
给定一组连续的整数,例如:10,11,12,……,20,但其中缺失一个数字,试找出缺失的数字:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java.util.*;public class Main { public static void main (String[] args) { final int start = 10 ; final int end = 20 ; List<Integer> list = new ArrayList <>(); for (int i = start; i <= end; i++) { list.add(i); } int removed = list.remove((int ) (Math.random() * list.size())); int found = findMissingNumber(start, end, list); System.out.println(list.toString()); System.out.println("missing number: " + found); System.out.println(removed == found ? "测试成功" : "测试失败" ); } static int findMissingNumber (int start, int end, List<Integer> list) { return 0 ; } }
增强版:和上述题目一样,但整数不再有序,试找出缺失的数字:
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 import java.util.*;public class Main { public static void main (String[] args) { final int start = 10 ; final int end = 20 ; List<Integer> list = new ArrayList <>(); for (int i = start; i <= end; i++) { list.add(i); } Collections.shuffle(list); int removed = list.remove((int ) (Math.random() * list.size())); int found = findMissingNumber(start, end, list); System.out.println(list.toString()); System.out.println("missing number: " + found); System.out.println(removed == found ? "测试成功" : "测试失败" ); } static int findMissingNumber (int start, int end, List<Integer> list) { return 0 ; } }
下载练习
小结
List
是按索引顺序访问的长度可变的有序表,优先使用ArrayList
而不是LinkedList
;
可以直接使用for each
遍历List
;
List
可以和Array
相互转换。
我们知道List
是一种有序链表:List
内部按照放入元素的先后顺序存放,并且每个元素都可以通过索引确定自己的位置。
List
还提供了boolean contains(Object o)
方法来判断List
是否包含某个指定元素。此外,int indexOf(Object o)
方法可以返回某个元素的索引,如果元素不存在,就返回-1
。
我们来看一个例子:
1 2 3 4 5 6 7 8 9 10 11 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("C" )); System.out.println(list.contains("X" )); System.out.println(list.indexOf("C" )); System.out.println(list.indexOf("X" )); } }
这里我们注意一个问题,我们往List
中添加的"C"
和调用contains("C")
传入的"C"
是不是同一个实例?
如果这两个"C"
不是同一个实例,这段代码是否还能得到正确的结果?我们可以改写一下代码测试一下:
1 2 3 4 5 6 7 8 9 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 < elementData.length; i++) { if (o.equals(elementData[i])) { return true ; } } return false ; } }
因此,要正确使用List
的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 19 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
如何正确编写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; }
首先,我们要定义“相等”的逻辑含义。对于Person
类,如果name
相等,并且age
相等,我们就认为两个Person
实例相等。
因此,编写equals()
方法如下:
1 2 3 4 5 6 public boolean equals (Object o) { if (o instanceof Person p) { return this .name.equals(p.name) && this .age == p.age; } return false ; }
对于引用字段比较,我们使用equals()
,对于基本类型字段的比较,我们使用==
。
如果this.name
为null
,那么equals()
方法会报错,因此,需要继续改写如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 public boolean equals (Object o) { if (o instanceof Person p) { 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 ; }
如果Person
有好几个引用类型的字段,上面的写法就太复杂了。要简化引用类型的比较,我们使用Objects.equals()
静态方法:
1 2 3 4 5 6 public boolean equals (Object o) { if (o instanceof Person p) { return Objects.equals(this .name, p.name) && this .age == p.age; } return false ; }
因此,我们总结一下equals()
方法的正确编写方法:
先确定实例“相等”的逻辑,即哪些字段相等,就认为实例相等;
用instanceof
判断传入的待比较的Object
是不是当前类型,如果是,继续比较,否则,返回false
;
对引用类型用Objects.equals()
比较,对基本类型直接用==
比较。
使用Objects.equals()
比较两个引用类型是否相等的目的是省去了判断null
的麻烦。两个引用类型都是null
时它们也是相等的。
如果不调用List
的contains()
、indexOf()
这些方法,那么放入的元素就不需要实现equals()
方法。
练习
给Person类增加equals方法,使得调用indexOf()方法返回正常:
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 import java.util.List;import java.util.Objects;public class Main { public static void main (String[] args) { List<Person> list = List.of( new Person ("Xiao" , "Ming" , 18 ), new Person ("Xiao" , "Hong" , 25 ), new Person ("Bob" , "Smith" , 20 ) ); boolean exist = list.contains(new Person ("Bob" , "Smith" , 20 )); System.out.println(exist ? "测试成功!" : "测试失败!" ); } } class Person { String firstName; String lastName; int age; public Person (String firstName, String lastName, int age) { this .firstName = firstName; this .lastName = lastName; this .age = age; } }
下载练习
小结
在List
中查找元素时,List
的实现类通过元素的equals()
方法比较两个元素是否相等,因此,放入的元素必须正确覆写equals()
方法,Java标准库提供的String
、Integer
等已经覆写了equals()
方法;
编写equals()
方法可借助Objects.equals()
判断。
如果不在List
中查找元素,就不必覆写equals()
方法。
我们知道,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);
这种需求其实非常常见,即通过一个键去查询对应的值。使用List
来实现存在效率非常低的问题,因为平均需要扫描一半的元素才能确定,而Map
这种键值(key-value)映射表的数据结构,作用就是能高效通过key
快速查找value
(元素)。
用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
。
如果只是想查询某个key
是否存在,可以调用boolean containsKey(K key)
方法。
如果我们在存储Map
映射关系的时候,对同一个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); } } }
同时遍历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
和List
不同的是,Map
存储的是key-value
的映射关系,并且,它不保证顺序 。在遍历的时候,遍历的顺序既不一定是put()
时放入的key
的顺序,也不一定是key
的排序顺序。使用Map
时,任何依赖顺序的逻辑都是不可靠的。以HashMap
为例,假设我们放入"A"
,"B"
,"C"
这3个key
,遍历的时候,每个key
会保证被遍历一次且仅遍历一次,但顺序完全没有保证,甚至对于不同的JDK版本,相同的代码遍历的输出顺序都是不同的!
注意
遍历Map时,不可假设输出的key是有序的!
练习
请编写一个根据name
查找score
的程序,并利用Map
充当缓存,以提高查找效率:
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 48 49 50 51 52 53 54 55 56 import java.util.*;public class Main { public static void main (String[] args) { List<Student> list = List.of( new Student ("Bob" , 78 ), new Student ("Alice" , 85 ), new Student ("Brush" , 66 ), new Student ("Newton" , 99 )); var holder = new Students (list); System.out.println(holder.getScore("Bob" ) == 78 ? "测试成功!" : "测试失败!" ); System.out.println(holder.getScore("Alice" ) == 85 ? "测试成功!" : "测试失败!" ); System.out.println(holder.getScore("Tom" ) == -1 ? "测试成功!" : "测试失败!" ); } } class Students { List<Student> list; Map<String, Integer> cache; Students(List<Student> list) { this .list = list; cache = new HashMap <>(); } int getScore (String name) { Integer score = this .cache.get(name); if (score == null ) { } return score == null ? -1 : score.intValue(); } Integer findInList (String name) { for (var ss : this .list) { if (ss.name.equals(name)) { return ss.score; } } return null ; } } class Student { String name; int score; Student(String name, int score) { this .name = name; this .score = score; } }
下载练习
小结
Map
是一种映射表,可以通过key
快速查找value
;
可以通过for each
遍历keySet()
,也可以通过for each
遍历entrySet()
,直接获取key-value
;
最常用的一种Map
实现是HashMap
。
我们知道Map是一种键-值(key-value)映射表,可以通过key快速查找对应的value。
以HashMap
为例,观察下面的代码:
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" );
HashMap
之所以能根据key
直接拿到value
,原因是它内部通过空间换时间的方法,用一个大数组存储所有value
,并根据key直接计算出value
应该存储在哪个索引:
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 │ │ └───┘
如果key
的值为"a"
,计算得到的索引总是1
,因此返回value
为Person("Xiao Ming")
,如果key
的值为"b"
,计算得到的索引总是5
,因此返回value
为Person("Xiao Hong")
,这样,就不必遍历整个数组,即可直接读取key
对应的value
。
当我们使用key
存取value
的时候,就会引出一个问题:
我们放入Map
的key
是字符串"a"
,但是,当我们获取Map
的value
时,传入的变量不一定就是放入的那个key
对象。
换句话讲,两个key
应该是内容相同,但不一定是同一个对象。测试代码如下:
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) { 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)); } }
因为在Map
的内部,对key
做比较是通过equals()
实现的,这一点和List
查找元素需要正确覆写equals()
是一样的,即正确使用Map
必须保证:作为key
的对象必须正确覆写equals()
方法。
我们经常使用String
作为key
,因为String
已经正确覆写了equals()
方法。但如果我们放入的key
是一个自己写的类,就必须保证正确覆写了equals()
方法。
我们再思考一下HashMap
为什么能通过key
直接计算出value
存储的索引。相同的key
对象(使用equals()
判断时返回true
)必须要计算出相同的索引,否则,相同的key
每次取出的value
就不一定对。
通过key
计算索引的方式就是调用key
对象的hashCode()
方法,它返回一个int
整数。HashMap
正是通过这个方法直接定位key
对应的value
的索引,继而直接返回value
。
因此,正确使用Map
必须保证:
作为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
不能正常工作。
而第二条如果尽量满足,则可以保证查询效率,因为不同的对象,如果返回相同的hashCode()
,会造成Map
内部存储冲突,使存取的效率下降。
正确编写equals()
的方法我们已经在编写equals方法 一节中讲过了,以Person
类为例:
1 2 3 4 5 public class Person { String firstName; String lastName; int age; }
把需要比较的字段找出来:
然后,引用类型使用Objects.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; } }
注意到String
类已经正确实现了hashCode()
方法,我们在计算Person
的hashCode()
时,反复使用31*h
,这样做的目的是为了尽量把不同的Person
实例的hashCode()
均匀分布到整个int
范围。
和实现equals()
方法遇到的问题类似,如果firstName
或lastName
为null
,上述代码工作起来就会抛NullPointerException
。为了解决这个问题,我们在计算hashCode()
的时候,经常借助Objects.hash()
来计算:
1 2 3 int hashCode () { return Objects.hash(firstName, lastName, age); }
所以,编写equals()
和hashCode()
遵循的原则是:
equals()
用到的用于比较的每一个字段,都必须在hashCode()
中用于计算;equals()
中没有使用到的字段,绝不可放在hashCode()
中计算。
另外注意,对于放入HashMap
的value
对象,没有任何要求。
延伸阅读
既然HashMap
内部使用了数组,通过计算key
的hashCode()
直接定位value
所在的索引,那么第一个问题来了:hashCode()
返回的int
范围高达±21亿,先不考虑负数,HashMap
内部使用的数组得有多大?
实际上HashMap
初始化时默认的数组大小只有16,任何key
,无论它的hashCode()
有多大,都可以简单地通过:
1 int index = key.hashCode() & 0xf ;
把索引确定在0 ~ 15,即永远不会超出数组范围,上述算法只是一种最简单的实现。
第二个问题:如果添加超过16个key-value
到HashMap
,数组不够用了怎么办?
添加超过一定数量的key-value
时,HashMap
会在内部自动扩容,每次扩容一倍,即长度为16的数组扩展为长度32,相应地,需要重新确定hashCode()
计算的索引位置。例如,对长度为32的数组计算hashCode()
对应的索引,计算方式要改为:
1 int index = key.hashCode() & 0x1f ;
由于扩容会导致重新分布已有的key-value
,所以,频繁扩容对HashMap
的性能影响很大。如果我们确定要使用一个容量为10000
个key-value
的HashMap
,更好的方式是创建HashMap
时就指定容量:
1 Map<String, Integer> map = new HashMap <>(10000 );
虽然指定容量是10000
,但HashMap
内部的数组长度总是2n,因此,实际数组长度被初始化为比10000
大的16384
(214)。
最后一个问题:如果不同的两个key
,例如"a"
和"b"
,它们的hashCode()
恰好是相同的(这种情况是完全可能的,因为不相等的两个实例,只要求hashCode()
尽量不相等),那么,当我们放入:
1 2 map.put("a" , new Person ("Xiao Ming" )); map.put("b" , new Person ("Xiao Hong" ));
时,由于计算出的数组索引相同,后面放入的"Xiao Hong"
会不会把"Xiao Ming"
覆盖了?
当然不会!使用Map
的时候,只要key
不相同,它们映射的value
就互不干扰。但是,在HashMap
内部,确实可能存在不同的key
,映射到相同的hashCode()
,即相同的数组索引上,肿么办?
我们就假设"a"
和"b"
这两个key
最终计算出的索引都是5,那么,在HashMap
的数组中,实际存储的不是一个Person
实例,而是一个List
,它包含两个Entry
,一个是"a"
的映射,一个是"b"
的映射:
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" );
HashMap
内部通过"a"
找到的实际上是List<Entry<String, Person>>
,它还需要遍历这个List
,并找到一个Entry
,它的key
字段是"a"
,才能返回对应的Person
实例。
我们把不同的key
具有相同的hashCode()
的情况称之为哈希冲突。在冲突的时候,一种最简单的解决办法是用List
存储hashCode()
相同的key-value
。显然,如果冲突的概率越大,这个List
就越长,Map
的get()
方法效率就越低,这就是为什么要尽量满足条件二:
提示
如果两个对象不相等,则两个对象的hashCode()尽量不要相等。
hashCode()
方法编写得越好,HashMap
工作的效率就越高。
小结
要正确使用HashMap
,作为key
的类必须正确覆写equals()
和hashCode()
方法;
一个类如果覆写了equals()
,就必须覆写hashCode()
,并且覆写规则是:
如果equals()
返回true
,则hashCode()
返回值必须相等;
如果equals()
返回false
,则hashCode()
返回值尽量不要相等。
实现hashCode()
方法可以通过Objects.hashCode()
辅助方法实现。
使用EnumMap
因为HashMap
是一种通过对key计算hashCode()
,通过空间换时间的方式,直接定位到value所在的内部数组的索引,因此,查找效率非常高。
如果作为key的对象是enum
类型,那么,还可以使用Java集合库提供的一种EnumMap
,它在内部以一个非常紧凑的数组存储value,并且根据enum
类型的key直接定位到内部数组的索引,并不需要计算hashCode()
,不但效率最高,而且没有额外的空间浪费。
我们以DayOfWeek
这个枚举类型为例,为它做一个“翻译”功能:
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)); } }
使用EnumMap
的时候,我们总是用Map
接口来引用它,因此,实际上把HashMap
和EnumMap
互换,在客户端看来没有任何区别。
小结
如果Map
的key是enum
类型,推荐使用EnumMap
,既保证速度,也不浪费空间。
使用EnumMap
的时候,根据面向抽象编程的原则,应持有Map
接口。
我们已经知道,HashMap
是一种以空间换时间的映射表,它的实现原理决定了内部的Key是无序的,即遍历HashMap
的Key时,其顺序是不可预测的(但每个Key都会遍历一次且仅遍历一次)。
还有一种Map
,它在内部会对Key进行排序,这种Map
就是SortedMap
。注意到SortedMap
是接口,它的实现类是TreeMap
。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 ┌───┐ │Map│ └───┘ ▲ ┌────┴─────┐ │ │ ┌───────┐ ┌─────────┐ │HashMap│ │SortedMap│ └───────┘ └─────────┘ ▲ │ ┌─────────┐ │ TreeMap │ └─────────┘
SortedMap
保证遍历时以Key的顺序来进行排序。例如,放入的Key是"apple"
、"pear"
、"orange"
,遍历的顺序一定是"apple"
、"orange"
、"pear"
,因为String
默认按字母排序:
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); } } }
使用TreeMap
时,放入的Key必须实现Comparable
接口。String
、Integer
这些类已经实现了Comparable
接口,因此可以直接作为Key使用。作为Value的对象则没有任何要求。
如果作为Key的class没有实现Comparable
接口,那么,必须在创建TreeMap
时同时指定一个自定义排序算法:
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<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 + "}" ; } }
注意到Comparator
接口要求实现一个比较方法,它负责比较传入的两个元素a
和b
,如果a<b
,则返回负数,通常是-1
,如果a==b
,则返回0
,如果a>b
,则返回正数,通常是1
。TreeMap
内部根据比较结果对Key进行排序。
从上述代码执行结果可知,打印的Key确实是按照Comparator
定义的顺序排序的。如果要根据Key查找Value,我们可以传入一个new Person("Bob")
作为Key,它会返回对应的Integer
值2
。
另外,注意到Person
类并未覆写equals()
和hashCode()
,因为TreeMap
不使用equals()
和hashCode()
。
我们来看一个稍微复杂的例子:这次我们定义了Student
类,并用分数score
进行排序,高分在前:
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 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); } }
在for
循环中,我们确实得到了正确的顺序。但是,且慢!根据相同的Key:new Student("Bob", 66)
进行查找时,结果为null
!
这是怎么肥四?难道TreeMap
有问题?遇到TreeMap
工作不正常时,我们首先回顾Java编程基本规则:出现问题,不要怀疑Java标准库,要从自身代码找原因。
在这个例子中,TreeMap
出现问题,原因其实出在这个Comparator
上:
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 ; }
或者直接借助Integer.compare(int, int)
也可以返回正确的比较结果。
注意
使用TreeMap时,对Key的比较需要正确实现相等、大于和小于逻辑!
小结
SortedMap
在遍历时严格按照Key的顺序遍历,最常用的实现类是TreeMap
;
作为SortedMap
的Key必须实现Comparable
接口,或者传入Comparator
;
要严格按照compare()
规范实现比较逻辑,否则,TreeMap
将不能正常工作。
在编写应用程序的时候,经常需要读写配置文件。例如,用户的设置:
1 2 3 4 last_open_file =/data/hello.txtauto_save_interval =60
配置文件的特点是,它的Key-Value一般都是String
-String
类型的,因此我们完全可以用Map<String, String>
来表示它。
因为配置文件非常常用,所以Java集合库提供了一个Properties
来表示一组“配置”。由于历史遗留原因,Properties
内部本质上是一个Hashtable
,但我们只需要用到Properties
自身关于读写配置的接口。
读取配置文件
用Properties
读取配置文件非常简单。Java默认配置文件以.properties
为扩展名,每行以key=value
表示,以#
课开头的是注释。以下是一个典型的配置文件:
1 2 3 4 # setting.properties 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
读取配置文件,一共有三步:
创建Properties
实例;
调用load()
读取文件;
调用getProperty()
获取配置。
调用getProperty()
获取配置时,如果key不存在,将返回null
。我们还可以提供一个默认值,这样,当key不存在的时候,就返回默认值。
也可以从classpath读取.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 17 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" )); } }
如果有多个.properties
文件,可以反复调用load()
读取,后读取的key-value会覆盖已读取的key-value:
1 2 3 Properties props = new Properties ();props.load(getClass().getResourceAsStream("/common/setting.properties" )); props.load(new FileInputStream ("C:\\conf\\setting.properties" ));
上面的代码演示了Properties
的一个常用用法:可以把默认配置文件放到classpath中,然后,根据机器的环境编写另一个配置文件,覆盖某些默认的配置。
Properties
设计的目的是存储String
类型的key-value,但Properties
实际上是从Hashtable
派生的,它的设计实际上是有问题的,但是为了保持兼容性,现在已经没法修改了。除了getProperty()
和setProperty()
方法外,还有从Hashtable
继承下来的get()
和put()
方法,这些方法的参数签名是Object
,我们在使用Properties
的时候,不要去调用这些从Hashtable
继承下来的方法。
写入配置文件
如果通过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编码了。
不过,需要注意的是,由于load(InputStream)
默认总是以ASCII编码读取字节流,所以会导致读到乱码。我们需要用另一个重载方法load(Reader)
读取:
1 2 Properties props = new Properties ();props.load(new FileReader ("settings.properties" , StandardCharsets.UTF_8));
就可以正常读取中文。InputStream
和Reader
的区别是一个是字节流,一个是字符流。字符流在内存中已经以char
类型表示了,不涉及编码问题。
小结
Java集合库提供的Properties
用于读写配置文件.properties
。.properties
文件可以使用UTF-8编码;
可以从文件系统、classpath或其他任何地方读取.properties
文件;
读写Properties
时,注意仅使用getProperty()
和setProperty()
方法,不要调用继承而来的get()
和put()
等方法。
我们知道,Map
用于存储key-value的映射,对于充当key的对象,是不能重复的,并且,不但需要正确覆写equals()
方法,还要正确覆写hashCode()
方法。
如果我们只需要存储不重复的key,并不需要存储映射的value,那么就可以使用Set
。
Set
用于存储不重复的元素集合,它主要提供以下几个方法:
将元素添加进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 14 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()); } }
Set
实际上相当于只存储key、不存储value的Map
。我们经常用Set
用于去除重复元素。
因为放入Set
的元素和Map
的key类似,都要正确实现equals()
和hashCode()
方法,否则该元素无法正确地放入Set
。
最常用的Set
实现类是HashSet
,实际上,HashSet
仅仅是对HashMap
的一个简单封装,它的核心代码如下:
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; } }
Set
接口并不保证有序,而SortedSet
接口则保证元素是有序的:
HashSet
是无序的,因为它实现了Set
接口,并没有实现SortedSet
接口;
TreeSet
是有序的,因为它实现了SortedSet
接口。
用一张图表示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 ┌───┐ │Set│ └───┘ ▲ ┌────┴─────┐ │ │ ┌───────┐ ┌─────────┐ │HashSet│ │SortedSet│ └───────┘ └─────────┘ ▲ │ ┌─────────┐ │ TreeSet │ └─────────┘
我们来看HashSet
的输出:
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) { 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); } } }
注意输出的顺序既不是添加的顺序,也不是String
排序的顺序,在不同版本的JDK中,这个顺序也可能是不同的。
把HashSet
换成TreeSet
,在遍历TreeSet
时,输出就是有序的,这个顺序是元素的排序顺序:
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) { 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); } } }
使用TreeSet
和使用TreeMap
的要求一样,添加的元素必须正确实现Comparable
接口,如果没有实现Comparable
接口,那么创建TreeSet
时必须传入一个Comparator
对象。
练习
在聊天软件中,发送方发送消息时,遇到网络超时后就会自动重发,因此,接收方可能会收到重复的消息,在显示给用户看的时候,需要首先去重。请练习使用Set
去除重复的消息:
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 import java.util.*;public class Main { public static void main (String[] args) { List<Message> received = List.of( new Message (1 , "Hello!" ), new Message (2 , "发工资了吗?" ), new Message (2 , "发工资了吗?" ), new Message (3 , "去哪吃饭?" ), new Message (3 , "去哪吃饭?" ), new Message (4 , "Bye" ) ); List<Message> displayMessages = process(received); for (Message message : displayMessages) { System.out.println(message.text); } } static List<Message> process (List<Message> received) { return received; } } class Message { public final int sequence; public final String text; public Message (int sequence, String text) { this .sequence = sequence; this .text = text; } }
小结
Set
用于存储不重复的元素集合:
放入HashSet
的元素与作为HashMap
的key要求相同;
放入TreeSet
的元素与作为TreeMap
的Key要求相同。
利用Set
可以去除重复元素;
遍历SortedSet
按照元素的排序顺序遍历,也可以自定义排序算法。
队列(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
添加到队列。
我们知道,Queue
是一个先进先出(FIFO)的队列。
在银行柜台办业务时,我们假设只有一个柜台在办理业务,但是办理业务的人很多,怎么办?
可以每个人先取一个号,例如:A1
、A2
、A3
……然后,按照号码顺序依次办理,实际上这就是一个Queue
。
如果这时来了一个VIP客户,他的号码是V1
,虽然当前排队的是A10
、A11
、A12
……但是柜台下一个呼叫的客户号码却是V1
。
这个时候,我们发现,要实现“VIP插队”的业务,用Queue
就不行了,因为Queue
会严格按FIFO的原则取出队首元素。我们需要的是优先队列:PriorityQueue
。
PriorityQueue
和Queue
的区别在于,它的出队顺序与元素的优先级有关,对PriorityQueue
调用remove()
或poll()
方法,返回的总是优先级最高的元素。
要使用PriorityQueue
,我们就必须给每个元素定义“优先级”。我们以实际代码为例,先看看PriorityQueue
的行为:
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()); } }
我们放入的顺序是"apple"
、"pear"
、"banana"
,但是取出的顺序却是"apple"
、"banana"
、"pear"
,这是因为从字符串的排序看,"apple"
排在最前面,"pear"
排在最后面。
因此,放入PriorityQueue
的元素,必须实现Comparable
接口,PriorityQueue
会根据元素的排序顺序决定出队的优先级。
如果我们要放入的元素并没有实现Comparable
接口怎么办?PriorityQueue
允许我们提供一个Comparator
对象来判断两个元素的顺序。我们以银行排队业务为例,实现一个PriorityQueue
:
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 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 ()); 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 ; } } } 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
开头的号码优先返回,只有在开头相同的时候,才比较号码大小。
上面的UserComparator
的比较逻辑其实还是有问题的,它会把A10
排在A2
的前面,请尝试修复该错误。
小结
PriorityQueue
实现了一个优先队列:从队首获取元素时,总是获取优先级最高的元素;
PriorityQueue
默认按元素比较的顺序排序(必须实现Comparable
接口),也可以通过Comparator
自定义排序算法(元素就不必实现Comparable
接口)。
使用Deque
我们知道,Queue
是队列,只能一头进,另一头出。
如果把条件放松一下,允许两头都进,两头都出,这种队列叫双端队列(Double Ended Queue),学名Deque
。
Java集合提供了接口Deque
来实现一个双端队列,它的功能是:
既可以添加到队尾,也可以添加到队首;
既可以从队首获取,又可以从队尾获取。
我们来比较一下Queue
和Deque
出队和入队的方法:
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()
等方法提供。
注意到Deque
接口实际上扩展自Queue
:
1 2 3 public interface Deque <E> extends Queue <E> { ... }
因此,Queue
提供的add()
/offer()
方法在Deque
中也可以使用,但是,使用Deque
,最好不要调用offer()
,而是调用offerLast()
:
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()); } }
如果直接写deque.offer()
,我们就需要思考,offer()
实际上是offerLast()
,我们明确地写上offerLast()
,不需要思考就能一眼看出这是添加到队尾。
因此,使用Deque
,推荐总是明确调用offerLast()
/offerFirst()
或者pollFirst()
/pollLast()
方法。
Deque
是一个接口,它的实现类有ArrayDeque
和LinkedList
。
我们发现LinkedList
真是一个全能选手,它即是List
,又是Queue
,还是Deque
。但是我们在使用的时候,总是用特定的接口来引用它,这是因为持有接口说明代码的抽象层次更高,而且接口本身定义的方法代表了特定的用途。
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)是一种后进先出(LIFO:Last In First Out)的数据结构。
什么是LIFO呢?我们先回顾一下Queue
的特点FIFO:
1 2 3 4 5 ──────────────────────── (\(\ (\(\ (\(\ (\(\ (\(\ (='.') ──▶ (='.') (='.') (='.') ──▶ (='.') O(_")") O(_")") O(_")") O(_")") O(_")") ────────────────────────
所谓FIFO,是最先进队列的元素一定最早出队列,而LIFO是最后进Stack
的元素一定最早出Stack
。如何做到这一点呢?只需要把队列的一端封死:
1 2 3 4 5 ───────────────────────────────┐ (\(\ (\(\ (\(\ (\(\ (\(\ │ (='.') ◀──▶ (='.') (='.') (='.') (='.')│ 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方法调用的时候就会通过栈这种数据结构维护方法调用的层次。例如:
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 ; }
JVM会创建方法调用栈,每调用一个方法时,先将参数压栈,然后执行对应的方法;当方法返回时,返回值压栈,调用方法通过出栈操作获得方法返回值。
因为方法调用栈有容量限制,嵌套调用过多会造成栈溢出,即引发StackOverflowError
:
1 2 3 4 5 6 7 8 9 10 public class Main { public static void main (String[] args) { increase(1 ); } static int increase (int x) { return increase(x) + 1 ; } }
我们再来看一个Stack
的用途:对整数进行进制的转换就可以利用栈。
例如,我们要把一个int
整数12500
转换为十六进制表示的字符串,如何实现这个功能?
首先我们准备一个空栈:
1 2 3 4 5 6 │ │ │ │ │ │ │ │ │ │ └───┘
然后计算12500÷16=781…4,余数是4
,把余数4
压栈:
1 2 3 4 5 6 │ │ │ │ │ │ │ │ │ 4 │ └───┘
然后计算781÷16=48…13,余数是13
,13
的十六进制用字母D
表示,把余数D
压栈:
1 2 3 4 5 6 │ │ │ │ │ │ │ D │ │ 4 │ └───┘
然后计算48÷16=3…0,余数是0
,把余数0
压栈:
1 2 3 4 5 6 │ │ │ │ │ 0 │ │ D │ │ 4 │ └───┘
最后计算3÷16=0…3,余数是3
,把余数3
压栈:
1 2 3 4 5 6 │ │ │ 3 │ │ 0 │ │ D │ │ 4 │ └───┘
当商是0
的时候,计算结束,我们把栈的所有元素依次弹出,组成字符串30D4
,这就是十进制整数12500
的十六进制表示的字符串。
计算中缀表达式
在编写程序的时候,我们使用的带括号的数学表达式实际上是中缀表达式,即运算符在中间,例如:1 + 2 * (9 - 5)
。
但是计算机执行表达式的时候,它并不能直接计算中缀表达式,而是通过编译器把中缀表达式转换为后缀表达式,例如:1 2 9 5 - * +
。
这个编译过程就会用到栈。我们先跳过编译这一步(涉及运算优先级,代码比较复杂),看看如何通过栈计算后缀表达式。
计算后缀表达式不考虑优先级,直接从左到右依次计算,因此计算起来简单。首先准备一个空的栈:
1 2 3 4 5 6 │ │ │ │ │ │ │ │ │ │ └───┘
然后我们依次扫描后缀表达式1 2 9 5 - * +
,遇到数字1
,就直接扔到栈里:
1 2 3 4 5 6 │ │ │ │ │ │ │ │ │ 1 │ └───┘
紧接着,遇到数字2
,9
,5
,也扔到栈里:
1 2 3 4 5 6 │ │ │ 5 │ │ 9 │ │ 2 │ │ 1 │ └───┘
接下来遇到减号时,弹出栈顶的两个元素,并计算9-5=4
,把结果4
压栈:
1 2 3 4 5 6 │ │ │ │ │ 4 │ │ 2 │ │ 1 │ └───┘
接下来遇到*
号时,弹出栈顶的两个元素,并计算2*4=8
,把结果8
压栈:
1 2 3 4 5 6 │ │ │ │ │ │ │ 8 │ │ 1 │ └───┘
接下来遇到+
号时,弹出栈顶的两个元素,并计算1+8=9
,把结果9
压栈:
1 2 3 4 5 6 │ │ │ │ │ │ │ │ │ 9 │ └───┘
扫描结束后,没有更多的计算了,弹出栈的唯一一个元素,得到计算结果9
。
练习
请利用Stack把一个给定的整数转换为十六进制:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import java.util.*;public class Main { public static void main (String[] args) { String hex = toHex(12500 ); if (hex.equalsIgnoreCase("30D4" )) { System.out.println("测试通过" ); } else { System.out.println("测试失败" ); } } static String toHex (int n) { return "" ; } }
进阶练习:
请利用Stack把字符串中缀表达式编译为后缀表达式,然后再利用栈执行后缀表达式获得计算结果:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java.util.*;public class Main { public static void main (String[] args) { String exp = "1 + 2 * (9 - 5)" ; SuffixExpression se = compile(exp); int result = se.execute(); System.out.println(exp + " = " + result + " " + (result == 1 + 2 * (9 - 5 ) ? "✓" : "✗" )); } static SuffixExpression compile (String exp) { return new SuffixExpression (); } } class SuffixExpression { int execute () { return 0 ; } }
进阶练习2:
请把带变量的中缀表达式编译为后缀表达式,执行后缀表达式时,传入变量的值并获得计算结果:
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.*;public class Main { public static void main (String[] args) { String exp = "x + 2 * (y - 5)" ; SuffixExpression se = compile(exp); Map<String, Integer> env = Map.of("x" , 1 , "y" , 9 ); int result = se.execute(env); System.out.println(exp + " = " + result + " " + (result == 1 + 2 * (9 - 5 ) ? "✓" : "✗" )); } static SuffixExpression compile (String exp) { return new SuffixExpression (); } } class SuffixExpression { int execute (Map<String, Integer> env) { return 0 ; } }
下载练习
小结
栈(Stack)是一种后进先出(LIFO)的数据结构,操作栈的元素的方法有:
把元素压栈:push(E)
;
把栈顶的元素“弹出”:pop(E)
;
取栈顶元素但不弹出:peek(E)
。
在Java中,我们用Deque
可以实现Stack
的功能,注意只调用push()
/pop()
/peek()
方法,避免调用Deque
的其他方法;
不要使用遗留类Stack
。
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); }
实际上,Java编译器并不知道如何遍历List
。上述代码能够编译通过,只是因为编译器把for each
循环通过Iterator
改写为了普通的for
循环:
1 2 3 4 for (Iterator<String> it = list.iterator(); it.hasNext(); ) { String s = it.next(); System.out.println(s); }
我们把这种通过Iterator
对象遍历集合的模式称为迭代器。
使用迭代器的好处在于,调用方总是以统一的方式遍历各种集合类型,而不必关心它们内部的存储结构。
例如,我们虽然知道ArrayList
在内部是以数组形式存储元素,并且,它还提供了get(int)
方法。虽然我们可以用for
循环遍历:
1 2 3 for (int i=0 ; i<list.size(); i++) { Object value = list.get(i); }
但是这样一来,调用方就必须知道集合的内部存储结构。并且,如果把ArrayList
换成LinkedList
,get(int)
方法耗时会随着index的增加而增加。如果把ArrayList
换成Set
,上述代码就无法编译,因为Set
内部没有索引。
用Iterator
遍历就没有上述问题,因为Iterator
对象是集合对象自己在内部创建的,它自己知道如何高效遍历内部的数据集合,调用方则获得了统一的代码,编译器才能把标准的for each
循环自动转换为Iterator
遍历。
如果我们自己编写了一个集合类,想要使用for each
循环,只需满足以下条件:
集合类实现Iterable
接口,该接口要求返回一个Iterator
对象;
用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); } } }
虽然ReverseList
和ReverseIterator
的实现类稍微比较复杂,但是,注意到这是底层集合库,只需编写一次。而调用方则完全按for each
循环编写代码,根本不需要知道集合内部的存储逻辑和遍历逻辑。
在编写Iterator
的时候,我们通常可以用一个内部类来实现Iterator
接口,这个内部类可以直接访问对应的外部类的所有字段和方法。例如,上述代码中,内部类ReverseIterator
可以用ReverseList.this
获得当前外部类的this
引用,然后,通过这个this
引用就可以访问ReverseList
的所有字段和方法。
小结
Iterator
是一种抽象的数据访问模型。使用Iterator
模式进行迭代的好处有:
对任何集合都采用同一种访问模型;
调用者对集合内部结构一无所知;
集合类返回的Iterator
对象知道如何迭代。
Java提供了标准的迭代器模型,即集合类实现java.util.Iterable
接口,返回java.util.Iterator
实例。
Collections
是JDK提供的工具类,同样位于java.util
包中。它提供了一系列静态方法,能更方便地操作各种集合。
注意
Collections结尾多了一个s,不是Collection!
我们一般看方法名和参数就可以确认Collections
提供的该方法的功能。例如,对于以下静态方法:
1 public static boolean addAll(Collection<? super T> c, T... elements) { ... }
addAll()
方法可以给一个Collection
类型的集合添加若干元素。因为方法签名是Collection
,所以我们可以传入List
,Set
等各种集合类型。
创建空集合
对于旧版的JDK,可以使用Collections
提供的一系列方法来创建空集合:
创建空List:List<T> emptyList()
创建空Map:Map<K, V> emptyMap()
创建空Set:Set<T> emptySet()
要注意到返回的空集合是不可变集合,无法向其中添加或删除元素。
新版的JDK≥9可以直接使用List.of()
、Map.of()
、Set.of()
来创建空集合。
创建单元素集合
对于旧版的JDK,Collections
提供了一系列方法来创建一个单元素集合:
创建一个元素的List:List<T> singletonList(T o)
创建一个元素的Map:Map<K, V> singletonMap(K key, V value)
创建一个元素的Set:Set<T> singleton(T o)
要注意到返回的单元素集合也是不可变集合,无法向其中添加或删除元素。
新版的JDK≥9可以直接使用List.of(T...)
、Map.of(T...)
、Set.of(T...)
来创建任意个元素的集合。
排序
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 15 16 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 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); immutable.add("orange" ); } }
然而,继续对原始的可变List
进行增删是可以的,并且,会直接影响到封装后的“不可变”List
:
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.add("orange" ); System.out.println(immutable); } }
因此,如果我们希望把一个可变List
封装成不可变List
,那么,返回不可变List
后,最好立刻扔掉可变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<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
类提供了一组工具方法来方便使用集合类:
创建空集合;
创建单元素集合;
创建不可变集合;
排序/洗牌等操作。
留言與分享