Set概述

Set也是集合中的一个容器，类似于一个罐子，程序可以依次把若干个对象放进Set，但是Set无法保存元素添加的顺序，Set不允许包含相同的元素，如果把两个相同的元素加入同一个Set中，则添加失败，add()方法会返回false，并且新元素不会被添加。Set接口主要有两个实现类HashSet、TreeSet。

HashSet

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

不能保证元素的排列顺序，顺序可能与添加顺序不同，顺序也有可能发生变化。HashSet 不是同步的，如果多个线程同时访问一个 HashSet，假设有两个或者两个以上线程同时修改了HashSet集合时，则必须通过代码来保证其同步。集合元素值可以是 null。当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象的 hashCode()方法来得到该对象的 hashCode 值，然后根据该hashCode 值决定该对象在 HashSet 中的存储位置。如果有两个元素通过equals()方法比较返回 true，但它们的 hashCode()方法返回值不相等，HashSet 将会把它们存储在不同的位置，依然可以添加成功。也就是说，HashSet 集合判断两个元素相等的标准是两个对象通过 equals()方法比较相等，并且两个对象的 hashCode()方法返回值也相等。11.2.1 HashSet常用API

方法

描述

add(Object o)

添加元素

remove(Object o)

移除元素

isEmpty()

判断元素是否为空

size()

获取set中元素个数

下面通过示例：

package cn.bytecollege;import java.util.HashSet;import java.util.Set;public class HashSetDemo {	public static void main(String[] args) {		Set<String> set = new HashSet<>();		//添加元素		set.add("张无忌");		//移除元素		set.remove("张无忌");		//此时set中没有元素		System.out.println(set.isEmpty());	}}

HashSet遍历因为HashSet中的元素没有索引，所以不支持for循环直接遍历，但是可以使用foreach进行遍历

package cn.bytecollege;import java.util.HashSet;import java.util.Set;/** * 本例将演示使用foreach遍历Set * @author MR.W * */public class HashSetForDemo {	public static void main(String[] args) {		Set<String> set = new HashSet<>();				set.add("乔峰");		set.add("虚竹");		set.add("段誉");				for (String name : set) {			System.out.println(name);		}			}}

HashSet继承了Iterable接口，因此HashSet还可以使用迭代器遍历。

package cn.bytecollege;import java.util.HashSet;import java.util.Iterator;import java.util.Set;public class HashSetIteDemo {	public static void main(String[] args) {		Set<String> set = new HashSet<>();				set.add("乔峰");		set.add("虚竹");		set.add("段誉");				Iterator<String> it = set.iterator();		while(it.hasNext()) {			System.out.println(it.next());		}				for (Iterator iterator = set.iterator(); iterator.hasNext();) {			System.out.println(iterator.next());		}			}}

重写hashCode

HashSet 中每个能存储元素的"槽位"（slot）通常称为"桶"（bucket），如果有多个元素的 hashCode值相同，但它们通过equals()方法比较返回 false，就需要在一个"桶"里放多个元素，这样会导致性能下降。

下面给出重写 hashCode() 方法的基本规则。

在程序运行过程中，同一个对象多次调用 hashCode（）方法应该返回相同的值。当两个对象通过 equals()方法比较返回 true 时，这两个对象的 hashCode()方法应返回相等的值对象中用作 equals()方法比较标准的实例变量，都应该用于计算 hashCode 值。

下面给出重写hashCode() 方法的一般步骤。

把对象内每个有意义的实例变量（即每个参与 equals方法比较标准的实例变量）计算出一个 int 类型的 hashCode 值，计算方式如下：

实例变量类型

计算方式

实例变量类型

计算方式

boolean

hashCode=(f?1:0);

float

hashCode=Float.floatToIntBits(f)

整型

hashCode=(int)f;

double

long l = Double.doubleToLongBits(f);

hashCode = (int)(l^l>>>32);

long

hashCode=(int)(f^(f>>>32))

引用类型

hashCode = f.hashCode();

用第1步计算出来的多个hashCode 值组合计算出一个 hashCode 值返回。

return f1.hashCode() + (int)f2;

为了避免直接相加产生偶然相等 （两个对象的 f、f 实例变量并不相等，但它们的 hashCode 的和恰好相等），可以通过各实例变量的 hashCode 值乘以任意一个质数后再相加。例如如下代码;

return f1.hashCode()*19 + (int)f2*31;

HashSet使用场景

根据HashSet的特点可以知道HashSet中存放的元素不能重复，利用这个特性就可以做一些去重的业务，例如在给定字符串HelloWorld中统计出现的字符。

package cn.bytecollege;import java.util.HashSet;import java.util.Set;public class HashSetDemo {	public static void main(String[] args) {				String str = "HelloWorld";		//将字符串转换成字符数组		char[] ch = str.toCharArray();				Set<Character> set = new HashSet<>();		//遍历字符数组将所有元素添加进set去重		for (Character c : ch) {			set.add(c);		}		//遍历set		for (Character c : set) {			System.out.println(c);		}	}}

LinkedHashSet

HashSet有一个子类LinkedHashSet，LinkedHashSet集合同HashSet一样，也是根据元素的hashCode值来确定元素的存储位置，并且通过链表维护元素的顺序，换句话说，遍历LinkedHashSet时，LinkedHashSet将会按照元素的添加顺序来访问集合里的元素。

由于LinkedHash需要维护元素插入的顺序，因此性能略低于HashSet。下面通过示例学习LinkedHashSet

package cn.bytecollege;import java.util.LinkedHashSet;import java.util.Set;/** * 本例将演示LinkedHashSet * @author MR.W * */public class LinkedHashSetDemo {	public static void main(String[] args) {		Set<String> set = new LinkedHashSet<>();		set.add("乔峰");		set.add("虚竹");		set.add("段誉");		for (String name : set) {			System.out.println(name);		}	}}

从示例代码以及HashSet的遍历我们可以看出LinkedHashSet维护了添加顺序，也就是说添加进容器的元素和取出的元素顺序是一致的。

如果在某些场景下要使用set容器保存元素，并且需要维护set中的存放元素的顺序，那么就可以使用LinkedHashSet

TreeSet

TreeSet 是 SortedSet 接口的实现类，TreeSet 可以确保集合元素处于排序状态。

TreeSet常用API

与 HashSet 集合相比，TreeSet 还提供了如下几个额外的方法。

Comparator comparator()∶如果 TreeSet 采用了定制排序，则该方法返回定制排序所使用的Comparator;如果 TreeSet 采用了自然排序，则返回 null。Object first()∶返回集合中的第一个元素。Object last(): 返回集合中的最后一个元素。Object lower(Object e)∶ 返回集合中位于指定元素之前的元素（即小于指定元素的最大元素，参考元素不需要是 TreeSet集合里的元素）。Object higher(Object e)∶返回集合中位于指定元素之后的元素（即大于指定元素的最小元素，参考元素不需要是 TreeSet 集合里的元素）SortedSet subSet(Object fromElement，Object toElement)∶返回此Set 的子集合，范围从fromElement（包含）到 toElement （不包含）。SortedSet headSet(Object toElement)∶ 返回此 Set 的子集，由小于 toElement 的元素组成。SortedSet tailSet(Object fromElement)∶ 返回此 Set 的子集，由大于或等于 fromElement 的元素组成。

下面通过示例学习TreeSet的常用方法：

package cn.bytecollege;import java.util.TreeSet;public class TreeSetDemo {    public static void main(String[] args) {        TreeSet<Integer> treeSet = new TreeSet<Integer>();        treeSet.add(10);        treeSet.add(20);        treeSet.add(30);        treeSet.add(40);        treeSet.add(50);        //如果 TreeSet 采用了定制排序，则该方法返回定制排序所使用的Comparator;如果 TreeSet 采用了自然排序，则返回 null。        System.out.println(treeSet.comparator());        //返回集合中的第一个元素。        System.out.println(treeSet.first());        //返回集合中的最后一个元素。        System.out.println(treeSet.last());        //返回集合中位于指定元素之前的元素（即小于指定元素的最大元素，参考元素不需要是 TreeSet集合里的元素）。        System.out.println(treeSet.lower(25));        //返回集合中位于指定元素之后的元素（即大于指定元素的最小元素，参考元素不需要是 TreeSet 集合里的元素）        System.out.println(treeSet.higher(25));        //返回此Set 的子集合，范围从fromElement（包含）到 toElement （不包含）。        System.out.println(treeSet.subSet(20,50));        //返回此 Set 的子集，由小于 toElement 的元素组成        System.out.println(treeSet.headSet(30));        //返回此 Set 的子集，由大于或等于 fromElement 的元素组成。        System.out.println(treeSet.tailSet(30));    }}

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

与 HashSet 集合采用 hash 算法来决定元素的存储位置不同，TreeSet 采用红黑树的数据结构来存储集合元素。那么 TreeSet 进行排序的规则是怎样的呢? TreeSet 支持两种排序方法∶自然排序和定制排序。在默认情况下，TreeSet 采用自然排序。

11.4.2 自然排序

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

Java 提供了一个 Comparable接口，该接口里定义了一个 compareTo(Object obj)方法，该方法返回一个整数值，实现该接口的类必须实现该方法，实现了该接口的类的对象就可以比较大小。当一个对象调用该方法与另一个对象进行比较时，例如 obj1.compareTo(obj2)，如果该方法返回 0，则表明这两个对象相等;如果该方法返回一个正整数，则表明 obj1 大于 obj2;如果该方法返回一个负整数，则表明 obj1小于obj2。

下面通过示例学习该接口，首先定义Student类，类中包含name和age属性：

package cn.bytecollege;public class Student {	private String name;	private int age;	public Student(String name) {		super();		this.name = name;	}}

package cn.bytecollege;import java.util.Set;import java.util.TreeSet;public class HashSetDemo {	public static void main(String[] args) {		Set<Student> set = new TreeSet<>();		Student s1 = new Student("张三",18);		Student s2 = new Student("李四",18);				set.add(s1);		set.add(s2);	}}

当运行以上程序时，发现程序抛出了异常：

这是因为Student没有继承Comparable接口，如果把一个对象添加到TreeSet时，则该对象的类必须继承Comparable接口，否则程序将会抛出异常。

下面的程序将演示正确的添加方式：

package cn.bytecollege;public class Student implements Comparable<Student>{	private String name;	private int age;	public Student(String name,int age) {		super();		this.name = name;		this.age = age;	}	@Override	public int compareTo(Student o) {		return this.age-o.age;	}}

package cn.bytecollege;import java.util.Set;import java.util.TreeSet;public class HashSetDemo {	public static void main(String[] args) {		Set<Student> set = new TreeSet<>();		Student s1 = new Student("张三",18);		Student s2 = new Student("李四",19);				set.add(s1);		set.add(s2);	}}

Student类继承Comparable接口并重写compareTo()方法后再次向TreeSet中添加，可以顺利添加，并且可以按照age属性的大小进行排序。

当把一个对象加入 TreeSet 集合中时，TreeSet 调用该对象的 compareTo(Object obj)方法与容器中的其他对象比较大小，然后根据红黑树结构找到它的存储位置。如果两个对象通过 compareTo(Object obj)方法比较相等，新对象将无法添加到 TreeSet 集合中。

对于TreeSet集合而言，它判断两个对象是否相等的唯一标准是∶两个对象通过compareTo(Object obj)方法比较是否返回 0——如果通过 compareTo(Object obj)方法比较返回 0，TreeSet 则会认为它们相等;否则就认为它们不相等。

定制排序

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

如果需要实现定制排序，则需要在创建 TreeSet 集合对象时，提供一个 Comparator 对象与该TreeSet集合关联，由该 Comparator 对象负责集合元素的排序逻辑。

下面通过示例学习Comparator的用法，继续使用上例中的Student类：

package cn.bytecollege;public class Student{	private String name;	private int age;	public Student(String name,int age) {		super();		this.name = name;		this.age = age;	}}

package cn.bytecollege;import java.util.Comparator;import java.util.Set;import java.util.TreeSet;public class ComparatorDemo {	public static void main(String[] args) {		Set<Student> set = new TreeSet<Student>(new Comparator<Student>() {			@Override			public int compare(Student o1, Student o2) {				return o1.age-o2.age;			}		});				Student s1 = new Student("张三",18);		Student s2 = new Student("李四",19);		Student s3 = new Student("王五",20);			}}

各个Set性能分析

HashSet 和 TreeSet 是 Set 的两个典型实现，到底如何选择 HashSet 和 TreeSet 呢?HashSet 的性能总是比 TreeSet 好（特别是最常用的添加、查询元素等操作），因为 TreeSet 需要额外的红黑树算法来维护集合元素的次序。只有当需要一个保持排序的 Set 时，才应该使用 TreeSet，否则都应该使用 HashSet。

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