Java集合框架

Java集合类是一种特别有用的工具类,可用于存储数量不等的对象,并实现常用的数据结构,如栈、队列等。除此之外,还可用于保存具有映射关系的关联数组。Java集合大致可分为SetListQueueMap 四种体系,其中Set代表无序、不可重复的集合List代表有序、重复的集合Map代表具有映射关系的集合,Java5增加的Queue 代表一种队列集合实现

Java集合就像一种容器,可以把多个对象(实际上是对象的引用,习惯上都称对象)“丢进”容器中。Java5之前,Java集合会丢失容器中所有对象的数据类型,把所有对象都当成Object类型处理;Java5增加了泛型 后,Java集合可以记住容器中对象的数据类型。

Java集合概述

在编程中,常常需要集中存放多个数据,我们可以使用数组保存多个对象,但是数组长度不可变化,一旦在初始化数组时指定了长度,这个数组长度是不可改变的,如果需要保存数量变化的数据,数组就有点无能为力了;而且数组无法保存具有映射关系的数据,如成绩表:语文-79,数学-80,这种数据看上去像两个数组,但是这两个数组之间有一定的关联关系。

为了保存数量不确定的数据,以及保存具有映射关系的数据(也称为关联数组),Java提供了集合类。集合类主要负责保存、盛装其他数据,因此也被称为容器类。所有集合类都为java.util 包下,后来为了处理多线程环境下的并发安全问题,Java5 还在java.util.concurrent (J.U.C)包下提供了一些多线程支持的集合类。

集合类和数组不一样,数组元素既可以是基本类型的值,也可以是对象(实际上保存的是对象的引用变量);而集合里只能保存对象。

Java集合类主要由两个接口派生而出:CollectionMap ,它们是Java集合框架的根接口,又包含了一些子接口或实现类。

Collection集合体系的继承树

上图是Collection接口、子接口及其实现类的继承树。红框标出的SetList 接口是Collection接口派生的两个子接口,分别代表无序集合和有序集合;Queue 是Java提供的队列实现,有点类似List。

Map体系的继承树

上图是Map体系的继承树,所有Map实现类用于保存具有映射关系的数据。图上显示的众多实现类在功能、用法上存在一定的差异,但都有一个功能特征:Map保存的每项数据都是key-value对,即由key和value两个值组成Key是不可重复的,它是用于标识集合里的每项数据,如果需要查阅Map中的数据时,总是根据Map的key来获取。

访问List集合中的元素,可以直接根据元素的索引来访问;访问Map集合中的元素,可以根据每项元素的key来访问其value;访问Set集合中的元素,则只能根据元素本身来访问(这也是Set集合元素不允许重复的原因)。

对于Set、List、Queue和Map四种集合,最常用的实现类在图中以黄色背景色覆盖,分别是HashSetTreeSetArrayListArrayDequeLinkedListHashMapTreeMap 等实现类。

★Collection 接口

Collection 接口是List、Set和Queue接口的父接口。它定义了如下操作集合元素的方法。

CollectionMethod

集合类就像容器,现实中容器的功能无非就是添加对象、删除对象、清空容器、判断容器是否为空等,集合类就是为这些功能提供了对应的方法。

代码示例:

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
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
public class CollectionTest {
public static void main(String[] args) {
Collection c=new ArrayList();
//添加元素
c.add("孙悟空");
//虽然集合里不能放基本类型的值,但Java支持自动装箱
c.add(66);
System.out.println("c集合的元素个数:"+c.size());
//删除指定元素
c.remove(66);
System.out.println("c集合的元素个数:"+c.size());
//判断是否包含指定元素
System.out.println("判断是否包含\'孙悟空\'字符串:"+c.contains("孙悟空"));
c.add("猪八戒");
c.add("西游记");
System.out.println("c集合的元素:"+c);
Collection books=new HashSet();
books.add("西游记");
books.add("水浒传");
//判断是否包含参数集合的所有元素
System.out.println("c集合是否完全包含books集合?"+c.containsAll(books));
//删除参数集合包含的所有元素。用c集合减去books集合里的元素
c.removeAll(books);
System.out.println("c集合的元素:"+c);
c.clear();
System.out.println("c集合的元素:"+c);
//删除在参数集合不包含的元素。控制books集合里只剩下在c集合里也包含的元素,也就是只剩下两个集合的交集部分
books.retainAll(c);
System.out.println("books集合的元素:"+books);
}
}

运行结果:

CollectionTestResult

上面示例在使用System.out.println 方法输出集合对象时,输出结果是以格式良好的[ele1,ele2,……]形式输出,而不是调用Object的toString()方法输出。因为所有的Collection实现类都重写了toString()方法,可以一次性输出集合中的所有元素。

如果想依次访问集合里的每一个元素,则需要使用某种方式来遍历集合元素。

Java8 之前我们可以采用普通for循环遍历、迭代器iterator遍历或者采用增强for循环(foreach)遍历集合元素(ps:三种集合遍历方式示例);现Java8可采用新特性Lambda 表达式 遍历Iterator,本文暂不介绍。现在先具体说明一下Iterable 接口和Iterator接口。

Iterator接口

Iterator英文翻译“迭代者“。Iterator接口也是Java集合框架的成员,但它与Collection系列、Map系列的集合不一样,Collection系列集合、Map系列集合主要用于盛装其他对象,而Iterator则主要用于遍历(即迭代方向)Collection集合中的元素,Iterator对象也被称为迭代器。

Iterator接口隐藏了各种Collection实现类的底层细节(即无需关心集合对象的内部实现方式),向应用程序提供了遍历Collection集合元素的统一编程接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package java.util;
import java.util.function.Consumer;
/* @since 1.2 */
public interface Iterator<E> {
boolean hasNext();//判断是否还有下一个对象,如果有,则返回true,否则false
E next();//返回集合的下一个元素,此方法只能在hasNext方法返回true时调用
default void remove() {//删除集合里上一次next方法返回的元素
throw new UnsupportedOperationException("remove");
}
/*
* 可适用Lambda表达式来遍历集合元素
* @since 1.8
*/
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}

通过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
public class IteratorTest {
public static void main(String[] args) {
//创建集合
Collection books=new ArrayList();
//添加元素
books.add("西游记");
books.add("红楼梦");
books.add("水浒传");
books.add("三国演义");
//获取books集合对应的迭代器
Iterator it = books.iterator();
while (it.hasNext()){
//it.next()返回的是Object类型,此处需要强转类型
String book = (String) it.next();
System.out.println(book);
if(book.equals("西游记")){
//删除上一次next()方法返回的集合元素
it.remove();
//使用Iterator迭代过程中,不可修改集合元素,下面代码会引发ConcurrentModificationException异常
//books.remove(book);//②
}
//对book变量赋值不会改变集合元素本身
book="测试字符串";//①
}
System.out.println(books);
}
}

可以看出,Iterator仅用于遍历集合,它本身并不提供盛装对象的能力。如果需要创建Iterator对象,则必须有一个被迭代的集合。

上面①标注的代码对迭代变量book进行赋值,但当再次输出books集合时,其元素并没有任何改变。可以得出结论:当使用Iterator对集合元素进行迭代时,Iterator并不是把集合元素本身传给了迭代变量,而是把集合元素的值传给了迭代变量,所以修改迭代变量的值对集合元素本身没有任何影响。

上面标注②的代码位于Iterator迭代块内,在Iterator迭代Collection集合过程中修改了Collection集合,所以程序将在运行时引发异常。注意:当使用Iterator迭代访问Collection集合元素时,Collection集合里的元素不能被改变,只能通过Iterator的remove()方法删除上一次next()方法返回的集合元素才可以;否则将会引发 java.util.ConcurrentModificationException 异常。

Iterator迭代器采用的是快速失败(fail-fast)机制,一旦在迭代过程中检测到该集合已经被修改(通常是程序中的其他线程修改),程序立即引发 ConcurrentModificationException 异常,而不是显示修改后的结果,这样可以避免共享资源而引发的潜在问题。

Iterable 接口

Iterable 英文翻译“可迭代的”。 Java5 以后添加了Iterable接口用于支持foreach循环。Iterable接口是Collection的父接口。Iterable接口在Java8之前只有一个iterator() 方法,返回集合的Iterator 对象。所有实现Iterable接口的集合都可以使用foreach循环进行遍历。

Iterable的主要作用为:实现Iterable接口来实现适用于foreach遍历的自定义类

🐬 扩展:

对foreach循环进行反编译,可以知道它的底层就是通过迭代器模式来实现的。

可以参见→→Java中的增强for循环(for each)的实现原理与坑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package java.lang;
import java.util.Iterator;
import java.util.Objects;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.function.Consumer;
/* @since 1.5*/
public interface Iterable<T> {
Iterator<T> iterator();
/* @since 1.8 */
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
/* @since 1.8*/
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}

🐬 Iterator 和Iterable 的区别:

Iterator接口是提供了一种统一的遍历集合元素的方式。使用Iterator对象可以不用关心具体集合对象的具体类型和内部实现,统一使用Iterator对象的接口方法就可以遍历集合。

Iterable接口,是为了foreach循环设计的。Iterable接口表示,集合可以返回Iterator对象。最终还是使用Iterator进行遍历。

🐬 问题:为什么不让集合类直接实现iterator接口呢?

因为Iterator接口的核心方法next()或者hasNext() 是依赖于迭代器的当前迭代位置的。 如果Collection直接实现Iterator接口,势必导致集合对象中包含当前迭代位置的数据(指针)。 当集合在不同方法间被传递时,由于当前迭代位置不可预知,那么next()方法的结果会变成不可预知。 除非再为Iterator接口添加一个reset()方法,用来重置当前迭代位置。但即使这样,Collection也只能同时存在一个当前迭代位置,而Iterable则不然,每次调用都会返回一个从头开始计数的迭代器,多个迭代器是互不干扰的。 也可以简单理解,如果在两个不同的方法里面调用Iterator的next会得到不同的值。而返回迭代器就不一样了,你只能每次都从头开始取。

Set 集合

Set集合类似于一个罐子,程序可以依次把多个对象“丢进”Set集合,而Set集合通常不能记住元素的添加顺序。Set集合与Collection集合基本相同,没有提供任何额外的方法。实际上Set就是Collection,只是行为略有不同(Set不允许包含重复元素)。

Set集合不允许包含相同的元素,如果试图把两个相同的元素加入同一个Set集合,则添加操作失败,add()方法返回false,且新元素不会被加入。

上面介绍的是Set集合的通用知识,因此完全适合后面介绍的HashSetTreeSetEnumSet 三个实现类,只是三个实现类还各有特色。

HashSet 类

HashSet 是Set接口的典型实现,大多数时候使用Set集合时就是使用这个实现类。HashSetSet 按Hash 算法来存储集合中的元素,因此具有很好的存取和查找性能

🐳 HashSet 具有以下特点:

  • 不能保证元素的排列顺序,顺序可能与添加顺序不同,顺序也有可能发生变化。
  • HashSet 不是同步的,如果多个线程同时访问一个HashSet ,假设有两个或两个以上线程同时修改了HashSet集合时,则必须通过代码来保证其同步。
  • 集合元素值可以是null

当向HashSet集合中存入一个元素时,HashSet会调用该对象的hashCode() 方法来得到该对象的hashCode值,然后根据该hashCode值决定该对象在HashSet中的存储位置。如果有两个元素通过equals() 方法比较返回true,但它们的hashCode() 方法返回值不相等,HashSet将会把它们存储在不同的位置,依然可以添加成功。

也就是说,🐰 HashSet 集合判断两个元素相等的标准是两个对象通过equals() 方法比较相等,并且两个对象的hashCode() 方法返回值也相等🐰

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
/**
* 测试HashSet判断集合元素相等的标准
*/
public class HashSetTest {
public static void main(String[] args) {
HashSet books =new HashSet();
books.add(new A());
books.add(new A());
books.add(new B());
books.add(new B());
books.add(new C());
books.add(new C());
System.out.println(books);
}
}
class A{
public boolean equals(Object obj){
return true;
}
}
class B{
public int hashCode(){
return 1;
}
}
class C{
public int hashCode(){
return 2;
}
public boolean equals(Object obj){
return true;
}
}

输出结果:

1
[com.study.demo.B@1, com.study.demo.B@1, com.study.demo.C@2, com.study.demo.A@7d4991ad, com.study.demo.A@28d93b30]

分析:

虽然两个A对象通过equals方法比较返回true,但是HashSet依然把它们当成两个对象;即使两个B对象的hashCode()返回相同值(都是1),但是HashSet依然把它们当成两个对象。所以注意:当把一个对象放入HashSet中时,如果需要重写该对象对应类的equals方法,则也应该重写其hashCode()方法。规则是:如果两个对象通过equals方法比较返回true,这两个对象的hashCode值也应该相同。

🐳 🐳 hashCode 方法在HashSet中的必要性:

hash(也翻译为哈希、散列)算法的功能是,它能保证快速查找被检索的对象,hash算法的价值在于速度。当需要查询集合中某个元素时,hash算法可以直接根据该元素的hashCode值计算出该元素的存储位置,从而快速定位该元素。

类比数组(数组是所欲能存储一组元素里最快的数据结构)。数组可以包含多个元素,每个元素都有索引,如果需要访问某个数组元素,只需提供该元素的索引,接下来即可根据该索引计算元素在内存里的存储位置。

表面上看,HashSet集合里的元素都没有索引,实际上当程序向HashSet集合里添加元素时,HashSet会根据该元素的hashCode值来计算它的存储位置,这样也可快速定位该元素。

🐳 为什么不直接使用数组,还需要使用HashSet呢?

因为数组元素的索引是连续的,而数组的长度是固定的,无法自由增加数组的长度。而HashSet用每个元素的hashCode值来计算器存储位置,从而可以自由增加Hashset的长度,并可以根据元素的hashCode值来访问元素。因此,当从HashSet中访问元素时,HashSet先计算该元素的hashCode值(即调用该对象的hashCode方法的返回值),然后直接到该hashCode值对应的位置去取出该元素——这就是HashSet速度很快的原因。

LinkedHashSet 类

HashSet还有一个子类LinkedHashSet ,LinkedHashSet集合也是根据元素的hashCode值来决定元素的存储位置,但它同时使用链表维护元素的次序,这样使元素看起来是以插入的顺序保存的。也就是说,当遍历LinkedHashSet集合里的元素时,LinkedHashSet 将会按元素的添加顺序来访问集合里的元素。

LinkedHashSet 需要维护元素的插入顺序,因此性能略低于HashSet的性能。但在迭代访问Set里的全部元素时将有很好的性能,因此它以链表来维护内部顺序。

⚠️ 注意:

虽然LinkedHashSet使用了链表记录集合元素的添加顺序,但是LinkedHashSet依然是HashSet,因此它依然不允许集合元素重复。

TreeSet 类

TreeSetSortedSet接口的实现类,正如SortedSet名字所表达的,TreeSet可以确保集合元素处于排序状态。与HashSet集合相比,TreeSet还提供了如下额外的方法:

TreeSetMethod

表面方法很多,其实很简单:因为TreeSet中的元素是有序的,所以增加了访问第一个、前一个、后一个、最后一个元素的方法,并提供了三个从TreeSet中截取子TreeSet的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class TreeSetTest {
public static void main(String[] args) {
TreeSet nums=new TreeSet();
//向TreeSet集合添加四个Integer对象
nums.add(5);
nums.add(2);
nums.add(10);
nums.add(-9);
//输出集合元素,发现集合元素已处于排序状态
System.out.println(nums);//[-9, 2, 5, 10]
//输出集合里的第一个元素
System.out.println(nums.first());//-9
//输出最后一个元素
System.out.println(nums.last());//10
//返回小于4的子集,不包含4
System.out.println(nums.headSet(4));//[-9, 2]
//返回大于5的子集,如果Set包含5,子集中还包含5
System.out.println(nums.tailSet(5));//[5, 10]
//返回大于等于-3,小于4的子集
System.out.println(nums.subSet(-3,4));//[2]
}
}

根据上面运行结果来看,TreeSet 并不是根据元素的插入顺序进行排序的,而是根据元素的实际值的大小来进行排序的

与HashSet 集合采用hash算法来决定元素的存储位置不同,TreeSet采用红黑树的数据结构来存储集合元素。TreeSet支持两种排序方法:自然排序定制排序 。默认情况下,采用自然排序。

自然排序 Comparable

TreeSet 会调用集合中元素的compareTo(Object obj)方法来比较元素之间的大小关系,然后将集合元素按升序排列,这种方式就是自然排序。

Java数据结构之数组 数组元素比较已经介绍了Java提供的两种比较机制。这里再说明一下:

Java提供了一个Comparable接口,该接口定义了一个compareTo(Object obj)方法,该方法返回一个整数值,实现该接口的类必须实现该方法,实现了该接口的类的对象就可以比较大小。

Java 一些常用类已经实现了Comparable 接口,并提供了比较大小的标准。

  • BigDecimalBigInteger 以及所有的数值型对应的包装类:按它们对应的数组大小进行比较。
  • Character :按字符的UNICODE值进行比较。
  • Boolean :true对应的包装类实例大于false对应的包装类实例。
  • String :按字符串中字符的UNICODE值进行比较。
  • DateTime :后面(较晚)的时间、日期比前面(较早)的时间、日期大。

如果试图把一个对象添加到TreeSet时,则该对象的类必须实现Comparable接口,否则程序将会抛出异常。

ClassCastException

上面程序试图向TreeSet集合添加两个Err对象,添加第一个对象时,TreeSet没有任何元素,所以不会出现问题;当添加第二个对象时,TreeSet就会调用该Err对象的compareTo方法与集合中的其他元素(要求都是同一个类的实例,否则也会引发ClassCastException 异常,这里比较的元素正好是添加的第一个Err对象)进行比较——如果其对应的类没有实现Comparable接口,则会引发ClassCastException 异常。因此,上面程序将在①处引发该异常。

如果向TreeSet中添加的对象是自定义类的对象,则可以向TreeSet中添加多种类型的对象,前提是用户自定义类实现了Comparable接口,且实现compareTo(Object obj)方法没有进行强制类型转换。但当试图取出TreeSet里的集合元素时,不同类型的元素依然会发生ClassCastException异常。

⚠️ 如果希望TreeSet能正常运作,TreeSet只能添加同一种类型的对象。

当把一个对象加入TreeSet集合中时,TreeSet调用该对象的compareTo方法与容器中的其他对象比较大小,然后根据红黑树结构找到它的存储位置。如果两个对象通过compareTo 方法比较相等,新对象将无法添加到TreeSet集合中。所以,TreeSet集合判断两个对象是否相等的唯一标准是:两个对象通过compareTo(Object obj)方法比较是否返回0——如果返回0,TreeSet则认为它们相等;否则不相等。

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
class ZZ implements Comparable{
int age;
public ZZ(int age) {
this.age = age;
}
//重写Object的equals方法,总是返回true
@Override
public boolean equals(Object o) {
return true;
}
//重写Comparable的compareTo方法,总是返回1
@Override
public int compareTo(Object o) {
return 1;
}
}
public class TreeSetTest2 {
public static void main(String[] args) {
TreeSet ts=new TreeSet();
ZZ z1=new ZZ(6);
ts.add(z1);
//第二次添加同一个对象,输出true,表明添加成功
System.out.println(ts.add(z1));//①
System.out.println(ts);//[com.xx.ZZ@7d4991ad, com.xx.ZZ@7d4991ad]
//修改ts集合的第一个元素的age变量
((ZZ)ts.first()).age=9;
//输出ts集合的最后一个元素的age变量,发现值变成了9
System.out.println(((ZZ)ts.last()).age);
}
}

代码标注①处是把同一个对象再次添加到TreeSet集合中,因为z1对象的compareTo方法总是返回1,虽然它的equals 方法总是返回true,但TreeSet认为z1对象和它自己也不相等,因此TreeSet可以添加两个z1对象。下图是TreeSet及ZZ对象在内存中的存储示意图。

TreeSetTest2

上图可以看出TreeSet对象保存的两个元素(集合里的元素总是引用,但是习惯上把被引用的对象称为集合元素),实际上是同一个元素。所以当修改TreeSet集合里的第一个元素的age变量后,该TreeSet集合里最后一个元素的age变量也随之改变了。

由此需要注意:当需要把一个对象放入TreeSet中,重写该对象对应类的equals()方法时,应保证该方法与compareTo(Object obj)方法有一致的结果。其规则是:两个对象通过equals()方法比较返回true时,这两个对象通过compareTo(Object obj)方法比较应返回0.

ps:如果向TreeSet中添加一个可变对象后,并且后面程序修改了该可变对象的实例变量,这将导致它与其他对象的大小顺序发生改变,但是TreeSet不会再次调整它们的顺序,甚至可能导致TreeSet中保存的这两个对象通过compareTo方法比较返回0。为了让程序更加健壮,推荐不要修改放入HashSet和TreeSet集合中元素的关键实例变量。

定制排序 Comparator

TreeSet 的自然排序是根据集合元素的大小,TreeSet将它们以升序排列。如果需要实现定制排序,例如以降序排列,则可以通过Comparator 接口的帮助。该接口包含一个int compare(T o1, T o2) 方法,该方法用于比较o1和o2的大小。如果该方法返回正整数则表明o1大于o2;返回0表明o1等于o2;返回负整数,则表明o1小于o2。

🍭 具体两者的区别可以参考文章:

Java排序之Comparable接口和Comparator接口的比较和应用示例

EnumSet 类

EnumSet 是一个专为枚举类设计的集合类,EnumSet 中的所有元素都必须是指定枚举类型的枚举值,该枚举类型在创建EnumSet 时显示或隐式地指定。EnumSet 的集合元素也是有序的,以枚举值在Enum 类内的定义顺序来决定集合元素的顺序

EnumSet 在内部以位向量的形式存储,这种存储形式非常紧凑、高效,因此EnumSet 对象占用内存很小,而且运行效率很好。尤其是进行批量操作(如调用containsAll()retainAll() 方法)时,如果参数也是EnumSet 集合,则该批量操作的执行速度也非常快。

EnumSet 集合不允许加入null元素,如果试图插入null元素,EnumSet 将抛出NullPointerException 异常。如果只想判断EnumSet 是否包含null元素或试图删除null元素都不会抛出异常,只是删除操作将返回false,因为没有任何null元素被删除。

EnumSetMethod

示例:

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
enum Season{
SPRING,SUMMER,FALL,WINTER
}
public class EnumSetTest {
public static void main(String[] args) {
//创建一个EnumSet集合,集合元素就是Season枚举类的全部枚举值
EnumSet es1=EnumSet.allOf(Season.class);
System.out.println(es1);//[SPRING, SUMMER, FALL, WINTER]
//创建一个EnumSet空集合,指定集合元素是Season类的枚举值
EnumSet es2 = EnumSet.noneOf(Season.class);
System.out.println(es2);//[]
//手动添加2个元素
es2.add(Season.WINTER);
es2.add(Season.SPRING);
System.out.println(es2);//[SPRING, WINTER]
//以指定枚举值创建集合
EnumSet es3 = EnumSet.of(Season.SUMMER, Season.WINTER);
System.out.println(es3);//[SUMMER, WINTER]
EnumSet es4 = EnumSet.range(Season.SUMMER, Season.WINTER);
System.out.println(es4);//[SUMMER, FALL, WINTER]
//es5集合元素+es4集合元素=Season枚举类的全部枚举值
EnumSet es5 = EnumSet.complementOf(es4);
System.out.println(es5);//[SPRING]
//复制另一个EnumSet集合中的所有元素来创建新的EnumSet集合
EnumSet es6 = EnumSet.copyOf(es5);
System.out.println(es6);//[SPRING]
Collection c=new HashSet();
c.clear();
c.add(Season.FALL);
c.add(Season.SPRING);
//复制Collection集合中的所有元素来创建EnumSet集合
EnumSet es7=EnumSet.copyOf(c);//①
System.out.println(es7);//[SPRING, FALL]
c.add("凭空冒出个孙猴子");
c.add("孙猴子往哪跑");
//下面代码出现异常ClassCastException:因为c集合里的元素不是全部都为Season枚举类的枚举值
// es7=EnumSet.copyOf(c);//②
}
}

注意:当试图复制一个Collection集合里的元素来创建EnumSet集合时,必须保证Collection集合里的所有元素都是同一个枚举类的枚举值。

各Set实现类性能分析

HashSetTreeSet 是Set的两个典型实现,如何选择呢?

HashSet的性能总是比TreeSet好(特别是最常用的添加、查询元素等操作),因为TreeSet需要额外的红黑树算法来维护集合元素的次序。只有当需要一个保持排序的Set时,才应该使用TreeSet,否则都应该使用HashSet。

HashSet还有一个子类:LinkedHashSet ,对于普通的插入、删除等操作,LinkedHashSet比HashSet要略微慢一点,这是由于维护链表所带来的额外开销造成的,但是由于有了链表,遍历LinkedHashSet会更快。

EnumSet 是所有Set实现类中性能最好的,但它只能保存同一个枚举类的枚举值作为集合元素。

必须指出,Set的三个实现类HashSet、TreeSet和EnumSet都是线程不安全的。如果有多个线程同时访问一个Set集合,并且有超过一个线程修改了该Set集合,则必须手动保证该集合的同步性。通常可以通过Collections 工具类的synchronizedSortedSet 方法来“包装”该Set集合。此操作最好在创建时进行,以防止对Set集合的意外非同步访问。

1
SortedSet sortedSet = Collections.synchronizedSortedSet(new TreeSet(...));

List 集合

List 集合代表一个元素有序、可重复的集合,集合中每个元素都有其对应的顺序索引。List集合允许使用重复元素,可以通过索引来访问指定位置的集合元素。List集合默认按元素的添加顺序设置元素的索引,比如第一次添加的元素索引为0,第二次为1……

List作为Collection接口的子接口,当然可以使用Collection接口里的全部方法。而且由于List是有序集合,因此List集合里增加了一些根据索引来操作集合元素的方法。

ListMethod

所有List实现类都可以调用这些方法来操作集合元素。与Set集合相比,List集合增加了根据索引来插入、替换和删除集合元素的方法。除此之外,Java 8 还为List接口添加了如下两个默认方法:

1
2
3
4
//根据 operator 指定的计算规则重新设置List集合的所有元素
default void replaceAll(UnaryOperator<E> operator)
//根据Comparator参数对List集合的元素排序
default void sort(Comparator<? super E> c)

List集合的常规用法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class ListTest {
public static void main(String[] args) {
List books=new ArrayList();
books.add(new String("西游记"));
books.add(new String("红楼梦"));
books.add(new String("三国演义"));
System.out.println(books);//[西游记, 红楼梦, 三国演义]
//将新字符串对象插入在第二个位置
books.add(1,new String("水浒传"));
for (int i=0;i<books.size();i++){
System.out.println(books.get(i));
}
//删除第三个元素
books.remove(2);
System.out.println(books);//[西游记, 水浒传, 三国演义]
//判断指定元素在List集合中的位置:输出1表示位于第二位
System.out.println(books.indexOf(new String("水浒传")));//①
//将第二个元素替换成新字符串对象
books.set(1,new String("红楼梦"));
System.out.println(books);//[西游记, 红楼梦, 三国演义]
//将集合的第二个元素(包含)到第三个元素(不包含)截取成子集合
System.out.println(books.subList(1,2));//[红楼梦]
}
}

注意标注①代码处,试图返回新字符串对象在List集合中的位置,实际上List集合中并未包含该字符串对象。因为List集合添加字符串对象时,添加的是通过new关键字创建的新字符串对象。①处也是通过new关键字创建的新字符串对象,两个字符串显然不是同一个对象,但是List的indexOf 方法依然可以返回1。可见 List判断两个对象相等只要通过equals()方法返回true即可

与Set只提供了一个iterator() 方法不同,List还额外提供了一个listIterator() 方法,该方法返回一个ListIterator 对象,ListIterator接口继承了Iterate接口,提供了专门操作List的方法。在原来Iterator接口的基础上增加了如下方法:

1
2
3
4
5
6
//返回该迭代器关联的集合是否还有上一个元素
boolean hasPrevious();
//返回该迭代器的上一个元素
E previous();
//在指定位置插入一个元素
void add(E e);

与普通的Iterator相比,ListIterator 增加了向前迭代的功能(Iterator只能删除元素)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class ListIteratorTest {
public static void main(String[] args) {
String[] books={"西游记","红楼梦","水浒传"};
List bookList = new ArrayList();
for (int i = 0; i < books.length; i++) {
bookList.add(books[i]);
}
ListIterator lit = bookList.listIterator();
while (lit.hasNext()) {//正向迭代
System.out.println(lit.next());//使用next方法进行迭代
lit.add("~~~~~~分隔符~~~~~~~");//在迭代过程中使用add方法向上一次迭代元素的后面添加一个新元素
}
System.out.println("=======下面开始反向迭代========");
while (lit.hasPrevious()) {
System.out.println(lit.previous());
}
}
}

运行结果:

ListIteratorTestResult

ArrayList 和Vector 实现类

ArrayListVector 作为List类的两个典型实现,完全支持前面介绍的List接口的全部功能。

ArrayList 和Vector 类都是基于数组实现的List类,所以ArrayList 和Vector类封装了一个动态的、允许再分配的Object[] 数组。ArrayList 或Vector对象使用initialCapacity 参数来设置该数组的长度,当向ArrayList 或Vector中添加元素超出了该数组的长度时,它们的initialCapacity 会自动增加。

可以在创建ArrayList 或Vector集合时就指定initialCapacity 大小。如果不指定,则Object[] 数组的长度默认为10

对于通常的编程场景,程序员无需关心ArrayList 或Vector的initialCapacity 。但如果向ArrayList 或Vector集合中添加大量元素时,可使用ensureCapacity(int minCapacity) 方法一次性地增加initialCapacity 。这可以减少重分配的次数,从而提高性能。

ArrayList 和Vector提供了如下两个方法来重新分配Object[]数组:

1
2
3
4
//将ArrayList 或Vector集合的Object[]数组长度增加大于或等于minCapacity值
void ensureCapacity(int minCapacity)
//调整ArrayList 或Vector集合的Object[]数组长度为当前元素的个数。调用该方法可减少ArrayList 或Vector集合对象占用的存储空间
void trimToSize()

ArrayList 和Vector在用法上几乎完全相同,但是由于Vector是一个古老的集合(从JDK1.0就有了),那时候Java还没提供系统的集合框架,所以Vector里提供了一些方法名很长的方法,例如addElement(E obj) ,实际上这个方法与add(E e) 没有任何区别。从JDK1.2 以后,Java提供了系统的集合框架,就将Vector改为实现List接口,作为List的实现之一,从而导致Vector里有一些功能重复的方法。Vector系列方法中方法名更短的方法属于后来新增的方法,方法名更长的方法则是Vector原有的方法。Java改写了Vector原有的方法,将其方法名缩短是为了简化编程。而ArrayList开始就作为List的主要实现类,因此没有那些方法名很长的方法。实际上,Vector具有很多缺点,通常尽量少用Vector实现类。

除此之外,ArrayList和Vector的显著区别:ArrayList是线程不安全的,当多个线程访问同一个ArrayList集合时,如果超过一个线程修改了ArrayList集合,则程序必须手动保证该集合的同步性;但Vector集合则是线程安全的( 其 capacity() / size() / isEmpty() / indexOf() / lastIndexOf() / removeElement() / addElement() 等方法均是 sychronized 的,所以,对Vector的操作均是线程安全的),无需程序保证该集合的同步性。因为Vector是线程安全的,所以它的性能要比ArrayList性能低。实际上,即使需要保证List集合线程安全,也同样不推荐使用Vector实现类。Collections 工具类可以将一个ArrayList变成线程安全的。

Stack 类

Vector还提供了一个Stack 子类,它用于模拟“”这种数据结构,“栈”通常是指“后进先出”(LIFO)的容器。最后“push”进栈的元素,将最后先被“pop”出栈。与Java中的其他集合一样,进栈出栈的都是Object,因此从栈中取出元素后必须进行类型转换,除非你只是使用Object具有的操作。

StackMethod

需要指出的是,由于Stack继承了Vector,因此它也是一个非常古老的Java集合类,它同样是线程安全的、性能较差的,因此应该尽量少用Stack类。如果程序需要使用“栈”这种数据结构,则可以考虑ArrayDeque

ArrayDeque 也是List的实现类,ArrayDeque 既实现了List接口,也实现了Deque接口,由于实现了Deque接口,因此可以作为栈来使用;而且ArrayDeque 底层也是基于数组的实现,因此性能也很好。

固定长度的List

前面数组时介绍了一个操作数组的工具类Arrays ,该工具类里提供了asList(Object… a) 方法,该方法可以把一个数组或指定个数的对象转换成一个List集合,这个List集合既不是ArrayList实现类的实例,也不是Vector实现类的实例,而是Arrays的内部类ArrayList的实例

Arrays.ArrayList 是一个固定长度的List集合,只能遍历访问该集合里的元素,不可增加、删除该集合里的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class FixedSizeTest {
public static void main(String[] args) {
List fixedList= Arrays.asList("111","222");
//获取fixedList的实现类,将输出Arrays$ArrayList
System.out.println(fixedList.getClass());
//遍历集合元素
for (Object s:fixedList) {
System.out.println(s.toString());
}
//试图增加、删除元素都会引发UnsupportedOperationException异常
fixedList.add("333");//①
fixedList.remove("222");//②
}
}

上面标注的代码在编译时完全正常,但会在运行①处引发UnsupportedOperationException 异常。

Queue 集合

Queue 是JDK1.5开始出现的,用于模拟队列 这种数据结构,队列通常是指“先进先出”(FIFO)的容器。队列的头部保存在队列中存放时间最长的元素,队列的尾部保存在队列中存放时间最短的元素。新元素插入offer 到队列的尾部,访问元素poll 操作会返回队列头部的元素。通常,队列不允许随机访问队列中的元素。

QueueMethod

Queue接口有一个PriorityQueue 实现类。除此之外,还有一个Deque 接口(Jdk1.6),Deque代表一个“ 双端队列 ”,双端队列可以同时从两端来添加、删除元素,因此Deque的实现类既可以当成队列使用,也可当成栈使用。Java为Deque提供了ArrayDequeLinkedList 两个实现类。

PriorityQueue 实现类

PriorityQueue 是一个比较标准的队列实现类,而不是绝对标准的队列实现,是因为PriorityQueue保存队列元素的顺序并不是按加入队列的顺序,而是按队列元素的大小重新排序。因此当调用peek() 方法或poll() 方法取出队列中的元素时,并不是取出最先进入队列的元素,而是取出队列中最小的元素。从这个意义上来看,PriorityQueue已经违反了队列最基本规则:先进先出FIFO。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class PriorityQueueTest {
public static void main(String[] args) {
PriorityQueue pq=new PriorityQueue();
//依次向pq加入4个元素
pq.offer(6);
pq.offer(-3);
pq.offer(20);
pq.offer(18);
//输出pq队列,并不是按元素的加入顺序排列
System.out.println(pq);//[-3, 6, 20, 18]
//访问队列的第一个元素其实就是队列中最小元素
System.out.println(pq.poll());//-3
}
}

运行上面程序输出PriorityQueue集合时,可能看到该队列里的元素并没有很好地按照大小进行排序,但这只是受到PriorityQueue的toString方法的返回值影响。实际上,程序多次调用PriorityQueue集合对象的poll()方法,即可看到元素按从小到大的顺序“移出队列”。

PriorityQueue 不允许插入null元素,它还需对队列元素进行排序。PriorityQueue的元素有两种排序方式:

  • 自然排序:集合中的元素必须实现Comparable接口,而且应该是同一个类的多个实例,否则可能导致ClassCastException异常;
  • 定制排序:创建PriorityQueue队列时,传入Comparator对象,该对象负责对队列中的所有元素进行排序。采用定制排序时不要求队列元素实现Comparable接口。

PriorityQueue队列对元素的要求与TreeSet对元素的要求基本一致。

Deque 接口

Deque 接口是Queue接口的子接口,它代表一个双端队列,Deque接口里定义了一些双端队列的方法,这些方法允许从两端来操作队列的元素。

DequeMethod

从上面方法中可以看出,Deque 不仅可以当成双端队列使用,而且可以被当成栈来使用,因为该类里还包含了pop(出栈)、push(入栈)两个方法。

Deque 的方法与Queue方法对照表:

Queue的方法(队列) Deque的方法
add(e)/offer(e) addLast(e)/offerLast(e)
remove()/poll() removeFirst()/pollFirst()
element()/peek() getFirst()/peekFirst()

Deque 的方法与Stack方法对照表:

Stack的方法(栈) Deque的方法
push(e) addFirst(e)/offerFirst(e)
pop() removeFirst()/pollFirst()
peek() getFirst()/peekFirst()

ArrayDeque 实现类

Deque接口提供了一个典型的实现类:ArrayDeque 。从名称可以看出,它是一个基于数组实现的双端队列,创建Deque时同样可以指定numElements 参数,该参数用于指定Object[]数组的长度,如果不指定numElements参数,Deque底层数组的长度为16

ArrayList 和ArrayDeque两个集合类的实现机制基本相似,它们的底层都采用一个动态的、可重分配的Object[]数组来存储集合元素,当集合元素超出了该数组的容量时,系统会在底层重新分配一个Object[]数组来存储集合元素。

下面代码示范了把ArrayDeque当成 来使用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class ArrayDequeStack {
public static void main(String[] args) {
ArrayDeque stack = new ArrayDeque();
//依次将三个元素push入“栈”,注意不是add
stack.push("111");
stack.push("222");
stack.push("333");
System.out.println(stack);//[333, 222, 111]
//访问第一个元素,但并不将其pop出“栈”
System.out.println(stack.peek());//333
System.out.println(stack);//[333, 222, 111]
//pop出第一个元素
System.out.println(stack.pop());//333
System.out.println(stack);//[222, 111]
}
}

当程序中需要使用 这种数据结构时,推荐使用ArrayDeque,尽量避免使用Stack——因为Stack是古老的集合,性能较差。

下面代码示例ArrayDeque当成队列 使用。按照“先进先出”的方式操作集合元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class ArrayDequeQueue {
public static void main(String[] args) {
ArrayDeque queue=new ArrayDeque();
//依次将三个元素加入队列
queue.offer("111");
queue.offer("222");
queue.offer("333");
System.out.println(queue);//[111, 222, 333]
//访问队列头部的元素,但并不将其poll出队列
System.out.println(queue.peek());//111
System.out.println(queue);//[111, 222, 333]
//poll出第一个元素
System.out.println(queue.poll());//111
System.out.println(queue);//[222, 333]
}
}

LinkedList 实现类

LinkedList 类是List接口的实现类——这意味着它是个List集合,可以根据索引来随机访问集合中的元素。除此之外,LinkedList 还实现了Deque接口,可以被当成双端队列来使用,因此既可以被当成 来使用,也可以当成队列使用。

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
public class LinkedListTest {
public static void main(String[] args) {
LinkedList l=new LinkedList();
//将字符串对象加入队列的尾部
l.offer("666");
//将一个字符串元素加入栈的顶部
l.push("111");
//将字符串元素添加到队列的头部(相当于栈的顶部)
l.offerFirst("222");
//以List方式(按索引访问的方式)来遍历集合元素
for (int i = 0; i < l.size(); i++) {
System.out.println("遍历中:"+l.get(i));
}
//访问并不删除队列的第一个元素
System.out.println(l.peekFirst());//222
//访问并不删除队列的最后一个元素
System.out.println(l.peekLast());//666
//将栈顶元素弹出“栈”
System.out.println(l.pop());//222
System.out.println(l);//输出发现队列中的第一个元素被删除[111, 666]
//访问并删除队列的最后一个元素
System.out.println(l.pollLast());//666
System.out.println(l);//[111]
}
}

上面示范了LinkedList 作为List集合双端队列的用法。由此可见,LinkedList是一个功能非常强大的集合类。

LinkedList 与ArrayList、ArrayDeque的实现机制完全不同,ArrayList、ArrayDeque内部以数组的形式保存集合中的元素,因此随机访问集合元素时有较好的性能;而LinkedList内部以链表的形式保存集合中的元素,因此随机访问集合元素性能较差,但在插入、删除元素时性能比较出色(只需要改变指针所指的地址即可)。需要指出,虽然Vector也是以数组的形式来存储集合元素的,但因为它实现了线程功能(而且实现机制也不好),所以各方面性能都比较差。

🐟 ps:

对于所有的内部基于数组的集合实现,例如ArrayList、ArrayDeque等,使用随机访问的性能比使用Iterator迭代访问的性能要好,因为随机访问会被映射成对数组元素的访问。

各线性表的性能分析

Java提供的List就是一个线性表接口,而ArrayListLinkedList 又是线性表的两种典型实现:基于数组的线性表和基于链表的线性表。Queue 代表了队列Deque 代表了双端队列(既可作为队列使用,也可作为栈使用)。接下来对各种实现类的性能进行分析:

一般来说,由于数组以一块连续内存区来保存所有数组元素,所以数组在随机访问时性能最好,所有的内部以数组作为底层实现的集合在随机访问性能都比较好;而内部以链表作为底层实现的集合在执行插入、删除操作时有较好性能。但总体来说,ArrayList的性能比LinkedList的性能要好,因此大部分时候都应该考虑使用ArrayList。

🐳 关于使用List集合的建议:

  • 如果需要遍历List集合元素,对于ArrayList、Vector集合,应该使用**随机访问方法(get)来遍历集合元素,这样性能更好;对于LinkedList集合,则应采用迭代器(Iterator)**来遍历集合元素。
  • 如果需要经常执行插入、删除操作来改变包含大量数据的List集合的大小,可以考虑使用LinkedList 集合。使用ArrayList、Vector集合可能经常重新分配内部数组的大小,效果较差。
  • 如果有多个线程需要同时访问List集合中的元素,可以考虑使用Collections 工具类将集合包装成线程安全的集合。

★Map 接口

Map用于保存具有映射关系的数据,因此Map集合里保存着两组值,一组值用于保存Map里的key,另一组值用于保存Map里的value,key和value都可以是任何引用类型的数据。Map的key不允许重复,即同一个Map对象的任何两个key通过equals方法比较总是返回false。

key和value之间存在单向一对一关系,即通过指定的key,总能找到唯一的、确定的value。如果把Map里所有key放在一起看,它们就组成了一个Set集合(所有key没有顺序,不能重复),实际上Map确实包含了一个keySet() 方法,用于返回Map里所有key组成的Set集合。Map里Key集和Set集合里元素的存储形式很像。

不仅如此,Map子类和Set子类在名字上也很相似,比如Set接口下有HashSet、LinkedHashSet、SortedSet(接口)、TreeSet、EnumSet等子接口和实现类,而Map接口下有HashMapLinkedHashMapSortedMap(接口)、TreeMapEnumMap等子接口和实现类。正如它们的名字所暗示,Map的这些实现类和子接口中key集的存储形式和对应Set集合中元素的存储形式完全相同。(ps:从Java源码看,Java是先实现了Map(HashMap、TreeMap等集合),然后通过包装一个所有value都为null的Map就实现了Set集合)

如果把Map里的所有value放在一起看,它们有非常类似于一个List:元素之间可以重复,每个元素可以根据索引来查找,只是Map中的索引不再使用整数值,而是以另一个对象作为索引。如果需要从List集合中取出元素,则需要提供该元素的数组索引;如果需要从Map中取出元素,则需要提供该元素的key索引。因此,Map有时也被称为 字典 或 关联数组 。

MapMethod

Map中包含一个内部类Entry,该类封装了一个key-value对。Entry包含如下三个方法:

1
2
3
4
5
6
//返回该Entry里包含的key值
K getKey();
//返回该Entry里包含的value值
V getValue();
//设置该Entry里包含的value值,并返回新设置的value值。
V setValue(V value);

Map集合最典型的用法就是成对地添加、删除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
public class MapTest {
public static void main(String[] args) {
Map map =new HashMap();
//成对放入多个key-value对
map.put("语文",90);
map.put("数学",100);
map.put("英语",88);
//多次放入的key-value对中value可以重复
map.put("化学",90);
//放入重复的key时,新的value会覆盖原有的value,如果覆盖了,则返回原有的value
System.out.println(map.put("英语",95));//88
System.out.println(map);//{语文=90, 英语=95, 数学=100, 化学=90}
//判断是否包含指定key
System.out.println("是否包含 英语 key:"+map.containsKey("英语"));//true
System.out.println("是否包含 90 value:"+map.containsValue(90));//true
//获取Map集合的所有key组成的集合,通过遍历key来实现遍历所有的key-value对
for (Object key:map.keySet()) {
//map.get(key)获取指定key对应的value
System.out.println(key+"-->"+map.get(key));
}
//根据key来删除key-value对
map.remove("化学");
System.out.println(map);//{语文=90, 英语=95, 数学=100}
}
}

添加key-value对时,Map允许多个value重复,但如果添加key-value对时已有重复的key,那么新添加的value会覆盖该key原来对应的value,返回被覆盖的value。

上面用foreach循环遍历Map集合:程序先调用Map集合的keySet()获取所有的key,然后使用foreach循环来遍历Map所有的key,根据key即可遍历所有的value。

HashMap重写了toString方法,实际上所有的Map实现类都重写了toString方法,调用Map对象的toString方法总是返回如下格式的字符串:{key1=value1,key2=value2……}

HashMap和Hashtable 实现类

HashMapHashtable 都是Map接口的典型实现类,它们之间的关系完全类似于ArrayList和Vector的关系:Hashtable是一个古老的Map实现类(JDK1.0),当时还没有Map接口,它实现了抽象类Dictionary的两个方法elements() (类似于Map接口定义的values方法)和keys() (类似于Map接口定义的keySet方法),现在很少使用这两个方法。

除此之外,HashMap和Hashtable存在两点典型区别:

  • Hashtable 是一个线程安全的Map实现(提供的操作Hashtable集合的方法都是synchronized的,不会出现两个线程同时对数据进行操作的情况,因此保证了线程安全性,但是也大大的降低了执行效率),HashMap是线程不安全的实现。所以HashMap比Hashtable的性能高一点;如果有多个线程访问同一个Map对象时,使用Hashtable实现类会更好。
  • Hashtable 不允许使用null作为key和value。如果试图把null值放进Hashtable中,将会引发NullPointException异常;但HashMap可以使用null作为key或value

由于HashMap里的key不能重复,所以最多只有一个key-value对的key为null,但可以有无数多个key-value对的value为null。

🐟 ps:

从Hashtable的类名上就可以看出它是一个古老的类,它的命名甚至没有遵守Java的命名规范:每个单词的首字母都应该大写。由于后来大量Java程序中使用了Hashtable类,所以这个类名也不能随便改了,否则将导致大量程序需要改写。与Vector类似的是,尽量少用Hashtable实现类,即使需要创建线程安全的Map实现类,也无需使用Hashtable实现类,可以通过后面的Collections工具类把HashMap变成线程安全的。

为了成功地在HashMap、Hashtable中存储、获取对象,用作key的对象必须实现hashCode() 方法和equals() 方法

与HashSet集合不能保证元素的顺序一样,HashMap、Hashtable也不能保证其中key-value对的顺序。类似于HashSet,HashMap、Hashtable判断两个key相等的标准也是:两个key通过equals()方法比较返回true,两个key的hashCode值也相等

除此之外,HashMap、Hashtable中还包含一个containsValue()方法,用于判断是否包含指定的value。它们判断两个value相等的标准是:只要两个对象通过equals()方法比较返回true即可

与HashSet类似的是,如果使用可变对象作为HashMap、Hashtable的key,并且程序修改了作为key的可变对象,则也可能出现与HashSet类似的情形:程序再无法准确访问到Map中被修改过的key.

LinkedHashMap 实现类

HashSet有一个LinkedHashSet子类,HashMap也有一个LinkedHashMap子类:LinkedHashMap也使用双向链表来维护key-value对的次序(其实只需要考虑key的次序),该链表负责维护Map的迭代顺序,迭代顺序与key-value对的插入顺序保持一致

LinkedHashMap 可以避免对HashMap、Hashtable里的key-value对进行排序(只要插入key-value对时保持顺序即可),同时又可避免使用TreeMap所增加的成本。

LinkedHashMap 需要维护元素的插入顺序,因此性能略低于HashMap的性能;但因为它以链表来维护内部顺序,所以在迭代访问Map里的全部元素时将有较好的性能。

使用Properties 读写属性文件

Properties 是Hashtable类的子类,该对象在处理属性文件时特别方便。Properties类可以把Map对象和属性文件关联起来,从而可以把Map对象中的key-value对写入属性文件中,也可以把属性文件中的“属性名=属性值”加载到Map对象中。由于属性文件里的属性名、属性值只能是字符串类型,所以Properties里的key、value都是字符串类型。Properties相当于key、value都是String类型的Map

PropertiesMethod

上面loadstore 两个读写属性文件的方法,使用了InputStream类和OutputStream类,它们是Java IO体系中的两个基类。下面示范了properties的用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class PropertiesTest {
public static void main(String[] args) throws IOException {
Properties props=new Properties();
//向properties中添加属性
props.setProperty("username","xiaopenyou");
props.setProperty("password","123456");
//将properties中的key-value对保存到a.ini属性文件中(如果文件不存在,则直接在当前项目下创建)
props.store(new FileOutputStream("a.ini"),"comment line");
//新建一个properties对象
Properties props2 = new Properties();
//向properties中添加属性
props2.setProperty("gender","male");
//从a.ini文件中读取key-value对,并添加到props2对象中
props2.load(new FileInputStream("a.ini"));
System.out.println(props2);
}
}

编译、运行上面程序,输出:

1
{password=123456, gender=male, username=xiaopenyou}

上面程序还在当前项目下生成一个a.ini文件,文件内容如下:

1
2
3
4
#comment line
#Wed Aug 30 11:21:53 CST 2017
password=123456
username=xiaopenyou

Properties可以把key-value对以XML文件的形式保存起来,也可以从XML文件中加载key-value对,用法与上面类似。

SortedMap 接口和TreeMap 实现类

与Set接口类似,Map接口也派生一个SortedMap子接口,SortedMap接口也有一个TreeMap实现类。

TreeMap 就是一个红黑树数据结构,每个key-value对即作为红黑树的一个节点。TreeMap存储key-value对(节点)时,需要根据key的大小对节点进行排序。TreeMap可以保证所有key-value对处于有序状态。TreeMap也有两种排序方式:

  • 自然排序:TreeMap的所有key必须实现Comparable接口,而且所有的key应该是同一个类的对象,否则将会抛出ClassCastException异常。
  • 定制排序:创建TreeMap时,传入一个Comparator对象,该对象负责对TreeMap中的所有key进行排序。

类似TreeSet,TreeMap中判断两个key相等的标准是:两个key通过compareTo()方法返回0,即认为两个key相等。如果使用自定义类作为Map的key,且让TreeMap良好地工作,则重写该类的equals()方法和compareTo()方法时应该保持一致的返回结果。

与TreeSet类似的是,TreeMap中也提供了一系列根据key顺序访问key-value对的方法:

TreeMapMethod

表面看这些方法很复杂,其实很简单。因为TreeMap中的key-value对是有序的,所以增加了访问第一个、前一个、后一个、最后一个key-value对的方法,并提供了几个从TreeMap中截取子TreeMap的方法。

WeakHashMap 实现类

WeakHashMap 与HashMap的用法基本相似。与HashMap区别在于:HashMap的key保留了对实际对象的强引用 ,这意味着只要该HashMap对象不被销毁,该HashMap的所有key所引用的对象就不会被垃圾回收,HashMap也不会自动删除这些key所对应的key-value对;但WeakHashMap的key只保留了对实际对象的弱引用 ,这意味着如果WeakHashMap对象的key所引用的对象没有被其他强引用变量所引用,则这些key所引用的对象可能被垃圾回收,WeakHashMap也可能自动删除这些key所对应的key-value对。

WeakHashMap 中的每个key对象只持有对实际对象的弱引用(它的键key就是弱引用对象,无需我们再手动包装原始对象)。因此,当垃圾回收了该key所对应的实际对象之后,WeakHashMap 会自动删除该key对应的key-value对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class WeakHashMapTest {
public static void main(String[] args) {
WeakHashMap whm=new WeakHashMap();
//向WeakHashMap中添加三个key-value对
//三个key都是匿名字符串对象(没有其他引用)
whm.put(new String("语文"),new String("良好"));
whm.put(new String("数学"),new String("中等"));
whm.put(new String("英语"),new String("及格"));
//向WeakHashMap中添加一个key-value对,该key是一个系统缓存的字符串对象
whm.put("java",new String("good"));//①
System.out.println(whm);//输出:{java=good, 数学=中等, 英语=及格, 语文=良好}
//通知系统立即进行垃圾回收
//告诉垃圾收集器打算进行垃圾收集,而垃圾收集器进不进行收集是不确定的
System.gc();
//强制调用已经失去引用的对象的finalize方法
System.runFinalization();
System.out.println(whm);//输出:{java=good}
}
}

从输出结果看,当系统进行垃圾回收时,删除了WeakHashMap对象的前三个key-value对。这是因为添加前三个key-value对时,这三个key都是匿名的字符串对象,WeakHashMap只保留了对它们的弱引用,这样垃圾回收时自动删除这三个key-value对。代码①标注的key是一个字符串直接量,(系统会自动保留对该字符串对象的强引用),所以垃圾回收时不会回收它。

⚠️ 注意:

如果需要使用WeakHashMap的key来保留对象的弱引用,则不要让该key所引用的对象具有任何强引用,否则将失去使用WeakHashMap的意义。

IdentityHashMap 实现类

这个Map实现类的实现机制与HashMap基本相似,但它在处理两个key相等时比较独特:在IdentityHashMap中,当且仅当两个key严格相等(key1==key2)时,IdentityHashMap才认为两个key相等;对于普通的HashMap而言,只要key1和key2通过equals()方法比较返回true,且它们的hashCode值相等即可。

IdentityHashMap提供了与HashMap基本相似的方法,也允许使用null作为key和value。IdentityHashMap也不保证key-value对之间的顺序,更不保证它们的顺序随时间的推移保持不变。

1
2
3
4
5
6
7
8
9
10
11
12
public class IdentityHashMapTest {
public static void main(String[] args) {
IdentityHashMap ihm=new IdentityHashMap();
//下面两行代码向IdentityHashMap对象添加两个key-value对
ihm.put(new String("语文"),89);
ihm.put(new String("语文"),99);
//下面两行 只会向IdentityHashMap添加一个key-value对
ihm.put("java",90);
ihm.put("java",96);
System.out.println(ihm);//输出:{java=96, 语文=89, 语文=99}
}
}

上面程序前面两个key-value对中的key是新创建的字符串对象,它们通过==比较不相等,所以IdentityHashMap会把它们当成2个key来处理;后面两个的key都是字符串直接量,而且它们的字符序列完全相同,Java使用常量池来管理字符串直接量,所以它们通过==比较返回true,IdentityHashMap会认为它们是同一个key,因此只有一次可以添加成功。

EnumMap 实现类

EnumMap 是一个与枚举类一起使用的Map实现,EnumMap 中的所有key都必须是单个枚举类的枚举值。创建EnumMap 时必须显示或隐式指定它对应的枚举类。

EnumMap 具有以下特征:

  • 在内部以数组形式保存,所以这种实现形式非常紧凑、高效;
  • EnumMap 根据key的 自然顺序(即枚举值在枚举类中的定义顺序) 来维护key-value对的顺序。
  • EnumMap 不允许使用null作为key ,但允许使用null作为value。如果试图插入key为null,将抛出NullPointerException 异常。如果只是查询是否包含为null的key,或只是删除值为null的key,都不会抛出异常。

与创建普通的Map有所区别,创建EnumMap 时必须指定一个枚举类,从而将该EnumMap 和指定枚举类关联起来。

1
2
3
4
5
6
7
8
9
10
11
12
enum Season{
SPRING,SUMMER,FALL,WINTER
}
public class EnumMapTest {
public static void main(String[] args) {
//创建EnumMap对象,该EnumMap的所有key都是Season1枚举类的枚举值
EnumMap enumMap = new EnumMap(Season.class);
enumMap.put(Season.SUMMER,"夏日炎炎");//key只能是Season枚举类的枚举值
enumMap.put(Season.SPRING,"春暖花开");
System.out.println(enumMap);//以自然顺序排序输出:{SPRING=春暖花开, SUMMER=夏日炎炎}
}
}

各Map实现类的性能分析

对于Map的常用实现类而言,虽然HashMapHashtable 的实现机制几乎一样,但由于Hashtable 是一个古老的、线程安全的集合,因此HashMap通常比Hashtable要快。

TreeMap 通常比HashMap、Hashtable要慢(尤其在插入、删除key-value对时更慢),因为TreeMap底层采用红黑树来管理key-value对(红黑树的每个节点就是一个key-value对)。

使用TreeMap有一个好处:TreeMap中的key-value对总是处于有序状态,无须专门进行排序操作。当TreeMap被填充之后,就可以调用keySet(),取得由key组成的Set,然后使用toArray()方法生成key的数组,接下来使用Arrays的binarySearch()方法在已排序的数组中快速地查询对象。

对于一般的应用场景,程序应该多考虑使用HashMap,因为HashMap正是为快速查询设计的(HashMap底层其实也是采用数组来存储key-value对)。但如果程序需要一个总是排好序的Map时,则可以考虑使用TreeMap。

LinkedHashMap 比HashMap慢一点,因为它需要维护链表来保持Map中key-value时添加顺序。IdentityHashMap 性能没有特别出色之处,因为它采用与HashMap基本相似的实现,只是它使用==而不是equals()方法来判断元素相等。EnumMap 的性能最好,但它只能使用同一个枚举类的枚举值作为key。

HashSet和HashMap的性能选项

对于HashSet及其子类而言,它们采用hash算法 来决定集合中元素的存储位置,并通过hash算法来控制集合大小;对于HashMap、Hashtable及其子类而言,它们采用hash算法来决定Map中key的存储,并通过hash算法来增加key集合的大小。

hash表里可以存储元素的位置被称为“桶(bucket)”,在通常情况下,单个桶里存储一个元素,此时有最好的性能:hash算法可以根据hashCode值就算出桶的存储位置,接着从桶中取出元素。但hash表的状态是open的:在发生“hash冲突”的情况下,单个桶会存储多个元素,这些元素以链表形式存储,必须按顺序搜索。下图是hash表保存各元素,且发生“hash冲突”的示意图。

HashConflict

因为HashSet和HashMap、hashtable都使用hash算法来决定其元素(HashMap则只考虑key)的存储,因此HashSet、HashMap的hash表包含如下属性:

  • 容量(capacity):hash表中桶的数量。
  • 初始化容量(initial capacity):创建hash表时桶的数量。HashMap和HashSet都允许在构造器中指定初始化容量。
  • 尺寸(size):当前hash表中记录的数量。
  • 负载因子(load factor):负载因子等于“size/capacity”。负载因子为0,表示空的hash表,0.5表示半满的hash表,依此类推。轻负载的hash表具有冲突少、适宜插入与查询的特点(但是使用Iterator迭代元素时比较慢)。

除此之外,hash表里还有一个“负载极限 ”,“负载极限”是一个0~1的数值,“负载极限”决定了hash表的最大填满承兑。当hash表中的负载因子达到指定的“负载极限”时,hash表会自动成倍地增加容量(桶的数量),并将原有的对象重新分配,放入新的桶内,这称为rehashing

HashSet和HashMap、Hashtable的构造器允许指定一个负载极限,它们默认的“负载极限”为0.75,这表明当该hash表的3/4已经被填满时,hash表会发生rehashing。

“负载极限”的默认值0.75是时间和空间成本上的一种折中:较高的“负载极限”可以降低hash表所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的操作(HashMap的get()和put()方法都要用到查询);较低的“负载极限”会提高查询数据的性能,但会增加hash表所占用的内存开销。可以根据实际情况调整负载极限值。

如果开始就知道HashSet和HashMap、Hashtable会保存很多记录,则可以在创建时就使用较大的初始化容量,如果初始化容量始终大于HashSet和HashMap、Hashtable所包含的最大记录数除以“负载极限”,就不会发生rehashing。但使用足够大的初始化容量创建HashSet和HashMap、Hashtable时,可以更高效地增加记录,但将初始化容量设置太高可能会浪费空间,因此通常不要将初始化容量设置的过高。

操作集合的工具类Collections

Java提供了一个操作Set、List和Map等集合的工具类:Collections ,该工具类里提供了大量方法对集合元素进行排序、查询和修改等操作,还提供了将集合对象设置为不可变、对集合对象实现同步控制等方法。

排序操作

CollectionsSortMethod

下面简单示范利用Collections工具类来操作List集合:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class SortTest {
public static void main(String[] args) {
ArrayList nums=new ArrayList();
nums.add(2);
nums.add(-3);
nums.add(80);
nums.add(45);
System.out.println(nums);//[2, -3, 80, 45]
Collections.reverse(nums);//将List集合元素的次序反转
System.out.println(nums);//[45, 80, -3, 2]
Collections.sort(nums);//将List集合元素按自然顺序排序
System.out.println(nums);//[-3, 2, 45, 80]
Collections.shuffle(nums);//将List集合元素按随机顺序排序
System.out.println(nums);//每次输出次序不固定
}
}

查找、替换操作

CollectionsSearchMethod

同步控制

Collections类中提供了多个synchronizedXxx()方法,该方法可以将指定集合包装成线程同步的集合,从而解决多线程并发访问集合时的线程安全问题。

Java中常用的集合框架中的实现类HashSetTreeSetArrayListArrayDequeLinkedListHashMapTreeMap都是线程不安全的。如果多个线程访问它们,而且有超过一个的线程试图修改它们,则存在线程安全的问题。Collections提供了多个类方法可以把它们包装成线程同步的集合。

CollectionsSynchronizedMethod

1
2
3
4
5
6
7
8
9
public class SynchronizedTest {
public static void main(String[] args) {
//下面创建了4个线程安全的集合对象
Collection c= Collections.synchronizedCollection(new ArrayList());
List list = Collections.synchronizedList(new ArrayList());
Set s=Collections.synchronizedSet(new HashSet());
Map m=Collections.synchronizedMap(new HashMap());
}
}

设置不可变集合

Collections提供了如下三类方法来返回一个不可变的集合。

CollectionsUnmodifiableMethod

上面三类方法的参数是原有的集合对象,返回值是该集合的“只读”版本。通过Collections提供的三类方法,可以生成“只读”的Collection或Map。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class UnmodifiableTest {
public static void main(String[] args) {
//创建一个空的、不可改变的List对象
List unmodifiableList = Collections.emptyList();
//创建一个只有一个元素、且不可改变的Set对象
Set unmodifiableSet = Collections.singleton("11111");
//创建一个普通的Map对象
Map map=new HashMap();
map.put("语文",80);
map.put("数学",82);
//返回普通的Map对象对应的不可变版本
Map unmodifiableMap = Collections.unmodifiableMap(map);
//下面任意一行代码都会引发UnsupportedOperationException异常
unmodifiableList.add("Java");//①
unmodifiableSet.add("Java");//②
unmodifiableMap.put("Java",99);//③
}
}

不可变的集合对象只能访问集合元素,不可修改集合元素。所以上面①②③处代码都将引发UnsupportedOperationException异常。

古老的 Enumeration 接口

Enumeration 接口是Iterator迭代器的“古老版本”,从JDK1.0开始,Enumeration 接口就已经存在了(Iterator从JDK1.2出来后在集合框架中代替Enumeration )。Enumeration 接口只有两个名字很长的方法:

1
2
boolean hasMoreElements();//如果此迭代器还有剩下的元素,则返回true
E nextElement();//返回该迭代器的下一个元素,如果还在的话(否则抛出异常)。

如果现在编写Java程序,应尽量采用Iterator迭代器。

Java之所以保留Enumeration 接口,主要是为了照顾以前那些“古老”的程序,那些程序里大量使用了Enumeration 接口。

实际上,前面介绍的Vector(包括其子类Stack)、Hashtable两个集合类,以及另一个极少使用的BitSet,都是从JDK1.0遗留下来的集合类,而Enumeration 接口可用于遍历这些“古老”的集合类。对于ArrayListHashMap等集合类,不再支持使用Enumeration 迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class EnumerationTest {
public static void main(String[] args) {
Vector v =new Vector();
v.add("111");
v.add("222");
Enumeration em = v.elements();
while (em.hasMoreElements()) {
System.out.println(em.nextElement());
}
Hashtable ht=new Hashtable();
ht.put("语文",88);
ht.put("数学",89);
Enumeration keys = ht.keys();
while (keys.hasMoreElements()){
Object key = keys.nextElement();
System.out.println(key+"--->"+ht.get(key));
}
}
}

上面程序使用Enumeration迭代器来遍历Vector和Hashtable集合里的元素,其工作方式与Iterator迭代器的工作方式基本相似。但使用Enumeration迭代器时方法名更冗长,而且Enumeration迭代器只能遍历Vector、Hashtable这种古老的集合,因此通常不要使用它。除非在某些极端情况下,不得不使用Enumeration,否则都应该选择Iterator迭代器。

文章目录
  1. 1. Java集合概述
  2. 2. ★Collection 接口
    1. 2.1. Iterator接口
    2. 2.2. Iterable 接口
  3. 3. Set 集合
    1. 3.1. HashSet 类
    2. 3.2. LinkedHashSet 类
    3. 3.3. TreeSet 类
      1. 3.3.1. 自然排序 Comparable
      2. 3.3.2. 定制排序 Comparator
    4. 3.4. EnumSet 类
    5. 3.5. 各Set实现类性能分析
  4. 4. List 集合
    1. 4.1. ArrayList 和Vector 实现类
    2. 4.2. Stack 类
    3. 4.3. 固定长度的List
  5. 5. Queue 集合
    1. 5.1. PriorityQueue 实现类
    2. 5.2. Deque 接口
      1. 5.2.1. ArrayDeque 实现类
      2. 5.2.2. LinkedList 实现类
  6. 6. 各线性表的性能分析
  7. 7. ★Map 接口
    1. 7.1. HashMap和Hashtable 实现类
    2. 7.2. LinkedHashMap 实现类
    3. 7.3. 使用Properties 读写属性文件
    4. 7.4. SortedMap 接口和TreeMap 实现类
    5. 7.5. WeakHashMap 实现类
    6. 7.6. IdentityHashMap 实现类
    7. 7.7. EnumMap 实现类
    8. 7.8. 各Map实现类的性能分析
  8. 8. HashSet和HashMap的性能选项
  9. 9. 操作集合的工具类Collections
    1. 9.1. 排序操作
    2. 9.2. 查找、替换操作
    3. 9.3. 同步控制
    4. 9.4. 设置不可变集合
  10. 10. 古老的 Enumeration 接口
|