文章导读
【Set接口存放的元素是无序的且不包含重复的元素，类似于数学中的集合概念，集合概念不允许有重复元素。Set接口有三个常用的实现类，分别是HashSet、LinkedHashSet、TreeSet。本文将对这三个类进行讲解。】
文章分成三个小节。第一小节讲述Set接口及HashSet类；第二小节讲述LinkedHashSet，LinkedHashSet和HashSet的区别在于存储结构的不同；第三小节讲述树结构TreeSet。
第一小节 认识Set接口及HashSet类
HashSet是Set接口实现类之一，使用较为广泛，它不保存元素的加入顺序，并且不允许存储重复的元素。也就是当容器中已经存储一个相同的元素时，无法再添加一个完全相同的元素。
下面先通过一个应用实例来认识HashSet
package com.milihua.hashsettest;
import java.util.HashSet;
import java.util.Iterator;
public class HashSetTest {
public static void main(String[] args) {
HashSet<String> set = new HashSet<String>();
set.add("a");
set.add("b");
set.add("c");
set.add("d");
set.add("e");
Iterator<String> iter = set.iterator();
while(iter.hasNext()){
String value = (String)iter.next();
System.out.println(value);
}
}
}程序码声明并实例化了一个HashSet对象，HashSet存储的元素是String对象，然后通过HashSet的add方法添加String对象，最后通过Iterator迭代器遍历HashSet集合。
运行上述程序，在控制台上显示效果如下图所示：
图1 HashSetTest输出结果
从图中可以看出，HashSet添加的顺序与迭代显示的结果顺序并不一致，这也验证了HashSet存储元素的无序特征。有的读者可能会问，前面讲过的数组结构和ArrayList都与加入元素的顺序相关，为什么HashSet与加入的元素顺序无关呢？
其实，HashSet类是根据元素的哈希码进行存储的，HashSet根据每个存储对象的哈希码值（调用hashCode方法获得），用固定的算法算出它的存储索引，把存储对象存放在一个叫做散列表的结构中，如果散列表对应的位置没有其它元素，就只需要直接存入；如果该位置已经有元素了，就会将新对象跟该位置的所有对象进行比较（调用equals（）方法），以查看容器中是否已经存在该对象，若不存在，就存放该对象，若已经存在，就直接使用该对象。
图2 HashSet存储结构
HashSet的存储结构是个链表数组，每一个数组元素就是一个链表，类似这种数据结构称为散列表。上图中左边是数组，用于存储元素，该存储元素对应的数组下标是调用hashCode方法返回的存储元素的哈希码。当后加入元素的哈希码与已经加入的元素哈希码相同时，HashSet就会创建一个链表，将相同哈希码的元素存入一个链表，并将该链表的头指针存储到哈希码对应的数组元素中。
前面的示例只是添加了String对象，如果要添加一个自定义的对象，又该如何呢？
用HashSet存储自定义对象的示例应用。
package hasesetexample;
import java.util.HashSet;
public class RemoveDuplicateObj {
static class Test {
private String name;
private Integer age;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
// 重写equal
@Override
public boolean equals(Object var1) {
if (!(var1 instanceof Test)) {
return false;
}
Test testVal1 = (Test) var1;
if (testVal1.name == null) {
return false;
}
return this.name == testVal1.getName();
}
// 重写hashCode
@Override
public int hashCode() {
return this.name.hashCode();
}
// 重写toString，为打印方便
@Override
public String toString() {
return "{" + this.name + "," + this.getAge() + "}";
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
// 测试数据
Test test1 = new Test();
test1.setName("小明");
test1.setAge(10);
Test test2 = new Test();
test2.setName("小红");
test2.setAge(20);
Test test3 = new Test();
test3.setName("小明");
test3.setAge(30);
// 测试代码
HashSet<Test> testSet = new HashSet<Test>();
testSet.add(test1);
testSet.add(test2);
testSet.add(test3);
System.out.println(testSet.size());
System.out.println(testSet.toString());
}
}因为Set集合中不能加入重复的元素，所以对于自定义类，需要提供判断怎样才算重复元素的方法。在例子代码中，hashCode()和equals()方法即是用来判断对象是否为重复对象的标准方法。
equals()方法用来比较两个对象是否为相等的对象。在自己实现的equals()方法中，用相关的条件来进行比较。例如对于RemoveDuplicateObj类，这里用name属性进行比较，name属性相同的为相等对象。
hashCode()方法是用来在散列存储结构中确定对象的存储地址的，两个对象的hashCode相同，并不一定表示两个对象就相同，只能够说明这两个对象在散列存储结构中，存储在在同一个链表中。Java初学者可以这样理解，hashCode（）方法实际上返回的就是对象存储的物理地址（实际可能并不是，而是一个与对象相关的值）。 当集合要添加新的元素时，先调用这个元素的hashCode方法，就一下子能定位到它应该放置的物理位置上。
第二小节 认识LinkedHashSet类
相对HashSet来说，LinkedHashSet存储结构是一个双向链表，因此它存储的元素是有序的。
LinkedHashSet继承自HashSet，源码更少、更简单，唯一的区别是LinkedHashSet内部使用的是LinkHashMap。这样做的意义或者好处就是LinkedHashSet中的元素顺序是可以保证的，也就是说遍历序和插入序是一致的。
LinkedHashSet类支持四个构造函数。第一种构造函数初始化一个空的LinkedHashSet：
LinkedHashSet( )；
第二种构造函数使用Collection元素集初始化LinkedHashSet：
LinkedHashSet(Collection c)
第三种构造函数用给定的容量初始化LinkedHashSet：
LinkedHashSet(int capacity)
第四种构造函数通过传入的容量和填充比初始化LinkedHashSet：
LinkedHashSet(int capacity, float fillRatio)
下面先通过一个应用实例来认识LinkedHashSet类
package linkhashset;
import java.util.LinkedHashSet;
public class LinkedHashSetTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
/**
* @param args
* LinkedHashSet 底层是链表实现的,是set集合中唯一一个能保证怎么存就怎么取的集合对象
* 因为是HashSet的子类,所以也是保证元素唯一的,与HashSet的原理一样
*/
LinkedHashSet<String> lhs = new LinkedHashSet<>();
lhs.add("a");
lhs.add("a");
lhs.add("a");
lhs.add("a");
lhs.add("b");
lhs.add("c");
lhs.add("d");
System.out.println(lhs);
}
}LinkedHashSet 底层采用双向链表实现，可以保证元素的插入顺序，又因为是HashSet的子类，所以插入的元素不能重复。
运行上面的程序，输出结果如下图所示：
图3 LinkedHashSetTest输出结果
从图中可以看出，LinkedHashSet添加了多个内容为“a”的String对象，但只有一个String对象添加成功。另外，元素的输出顺序也和添加元素的顺序一致。
LinkedHashSet需要维护元素的插入顺序，因此性能略低于HashSet的性能，但在迭代访问Set里的全部元素时将有很好的性能，因为它以链表来维护内部顺序。
第三小节 认识TreeSet类
TreeSet 也是一个有序的集合，TreeSet使用二叉树的原理对加入的元素按照升序或降序排序，该类对新添加的元素都会进行排序，将元素插入到二叉树指定的位置。
下面先通过一个应用实例来认识TreeSet类
package treeset;
import java.util.TreeSet;
public class TreeSetTest {
public static void main(String[] args) {
TreeSet<Integer> set = new TreeSet();
set.add(9);
set.add(-2);
set.add(3);
set.add(10);
System.out.println(set);//[-2, 5, 9, 10]
//输出集合中第一个元素
System.out.println("set.first() = "+set.first());//set.first() = -2
//输出集合中最后一个元素
System.out.println("set.last() = "+set.last());//set.last() = 10
//返回小于4的子集，不包含4
System.out.println("set.headSet() = "+set.headSet(4));//set.headSet() = [-2, 3]
//返回大于5的子集，包含5
System.out.println("set.tailSet() = "+set.tailSet(5));//set.tailSet() = [9, 10]
//返回大于等于-3，小于4的子集
System.out.println("set.subSet() = "+set.subSet(-3, 4));//set.subSet() = [-2, 3]
}
}与HashSet集合采用通过hash算法来决定元素的存储位置不同，TreeSet采用二叉树的数据结构来存储集合元素。
图4 TreeSetTest示例输出结果
从输出结果可以看出，TreeSet对加入元素默认按照升序进行排序。
TreeSet的排序原理
TreeSet调用元素的compareTo方法来比较元素之间的大小关系，然后将元素按升序或降序排列，因此待加入的元素必须实现compareTo方法，并通过compareTo方法比较两个元素的大小。
这里有个问题，待加入的元素如何实现compareTo方法呢？Java提供了一个Comparable接口，该接口定义了一个compareTo(Object o)方法，用于比较两个元素的大小，并返回一个整数值。需要加入TreeSet集合的元素必须要实现该接口，该接口的实现代码用于比较当前元素与传入元素的大小进行比较，并返回结果。实现该接口类的对象就可以比较大小。当一个对象调用该方法与另一个对象进行比较时，该方法返回比较结果。例如：tempObj1.compareTo(obj2)，如果该方法返回0，则代表这两个对象相等；如果该方法返回1，则表明tempObj1大于obj2；如果该方法返回-1，则表明tempObj1小于obj2。
需要加入TreeSet集合的元素必须实现Comparable接口，如果试图把没有实现Comparable接口的类对象加入TreeSet时，程序就会抛出异常。
没有实现Comparable接口类的程序代码如下：
package treesetnum;
import java.util.TreeSet;
public class MainTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeSet<MyNumber> set = new TreeSet();
set.add(new MyNumber(12));
set.add(new MyNumber(8));
set.add(new MyNumber(19));
}
}
// MyNumber类
package treesetnum;
public class MyNumber {
public int num;
public MyNumber(int innum)
{
num = innum;
}
public void OutNum()
{
System.out.println("序号：" + num);
}
}MyNumber为自定义的序号类，该类没有实现Comparable接口。程序在MainTest类的main方法中声明了TreeSet集合，并添加MyNumber对象。运行上述代码后，程序抛出错误，如下图所示：
图5 MainTest程序输出结果
从输出结果可以看出，程序抛出“Exception in thread "main" java.lang.ClassCastException: treesetnum.MyNumber cannot be cast to java.lang.Comparable”异常，意思是MyNumber类没有实现Comparable接口，导致进行元素比较时发生错误。
在上面的例子代码中，TreeSet集合添加了三个MyNumber对象，添加第一个对象时，TreeSet里没有任何元素，所以不会出现任何问题，当添加第二个MyNumber对象时，TreeSet就会调用该对象的compareTo(Object obj)方法与集合中的其他元素进行比较，如果其对应的类没有实现Comparable 接口，则会引发ClassCastException异常。
修改上面的代码如下：
package treesetnum;
import java.util.Iterator;
import java.util.TreeSet;
public class MainTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeSet<MyNumber> set = new TreeSet();
set.add(new MyNumber(12));
set.add(new MyNumber(8));
set.add(new MyNumber(19));
//输出集合元素
Iterator<MyNumber> i = set.iterator();
while(i.hasNext()) {
MyNumber temp = (MyNumber)i.next();
temp.OutNum();
}
}
}
// MyNumber类
package treesetnum;
public class MyNumber implements Comparable{
public int num;
public MyNumber(int innum)
{
num = innum;
}
public void OutNum()
{
System.out.println("序号：" + num);
}
@Override
public int compareTo(Object o) {
// TODO Auto-generated method stub
MyNumber inMyNumner = (MyNumber)o;
// 大于返回1
if( this.num > inMyNumner.getNum() )
return 1;
//小于返回-1
if( this.num < inMyNumner.getNum() )
return -1;
//相等返回0
return 0;
}
public int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
}修改后的代码在MyNumber类中实现了Comparable接口，实现方法名为compareTo，该方法实现两个类属性num的大小比较。如果当前num大于传入的num，该方法返回1；如果当前num小于传入的num，该方法返回-1；若相等则返回0。
修改后的代码输出结果如下图所示：
图6 修改后代码输出结果
从图中可以看出，修改后的代码可以正常地加入元素，并能对加入的元素进行正确排序。
文章小结
1、HashSet类存储对象时，根据对象的哈希吗值计算出该对象在散列表的存储位置，查询时通过对象的哈希吗可以直接定位到散列表的存储位置，因此其存储和查询操作都有很高的效率。
2、LinkedHashSet和HashSet的主要区别是存储结构的不同，LinkedHashSet的存储结构是一个双向链表，双向链表可以确保插入元素的顺序，也就是说元素的遍历序和插入顺序是一致的。
3、放入TreeSet集合中的元素必须是可排序的，对加入的元素（自定义类），若要实现compareTo方法，必须实现Comparable接口。在Java SDK中，已经有一些实现了Comparable接口的类，其中包括String字符串类，还包括Float、Interger、Long、Short、Double等数值类。
思考与练习
1、定义一个学生类，学生类包含姓名、性别、班级属性。在控制台输入多个学生，用HashSet存储输入的学生对象，最后遍历输出学生对象。
2、在控制台输入多个整数, 直到输入quit时结束输入. 把所有输入的整数倒序排列打印，用TreeSet实现。