HashSet 和 TreeSet

Question

Set 接口

Set 不允许包含相同的元素，如果试图把两个相同元素加入同一个集合中，add 方法返回 false。

Set 判断两个对象相同不是使用==运算符，而是根据 equals 方法。也就是说，只要两个对象用 equals 方法比较返回 true，Set 就不 会接受这两个对象,并且最多包含一个 null 元素。

HashSet 与 TreeSet 都是基于 Set 接口的实现类。其中 TreeSet 是 Set 的子接口 SortedSet 的实现类。Set 接口及其子接口、实现类的结构如下所示：

 	     |——SortedSet 接口——TreeSet 实现类
Set 接口——|——HashSet 实现类
         		|——LinkedHashSet 实现类

HashSet

• 不能保证元素的排列顺序，顺序有可能发生变化
• 不是同步的
• 集合元素可以是 null,但只能放入一个 null

当向 HashSet 结合中存入一个元素时，HashSet 会调用该对象的 hashCode() 方法来得到该对象的 hashCode 值，然后根据 hashCode 值来决定该对象在 HashSet 中存储位置。

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

注意，如果要把一个对象放入 HashSet 中，重写该对象对应类的 equals 方法，也应该重写其 hashCode() 方法。其规则是如果两个对 象通过 equals 方法比较返回 true 时，其 hashCode 也应该相同。另外，对象中用作 equals 比较标准的属性，都应该用来计算 hashCode 的值。

import java.util.HashSet;
import java.util.Iterator;
public class HashSetTest {
         public static void main(String[] args){
                 HashSet hs=new HashSet();
                 /**//*hs.add("one");
                 hs.add("two");
                 hs.add("three");
                 hs.add("four");*/
                 hs.add(new Student(1,"zhangsan"));
                 hs.add(new Student(2,"lishi"));
                 hs.add(new Student(3,"wangwu"));
                 hs.add(new Student(1,"zhangsan"));
                
                 Iterator it=hs.iterator();
                 while(it.hasNext()){
                         System.out.println(it.next());
                 }
         }
}
class Student{         //HashSet 要重写 hashCode 和 equals 方法
         int num;
         String name;
         Student(int num,String name){
                 this.num=num;
                 this.name=name;
         }
         public String toString(){
                 return "num :"+num+" name:"+name;
         }
	     public int hashCode(){
                 return num*name.hashCode();
         }
         public boolean equals(Object o){
                 Student s=(Student)o;
                 return num==s.num && name.equals(s.name);
         }
}

TreeSet 类

TreeSet 是 SortedSet 接口的唯一实现类，TreeSet 可以确保集合元素处于排序状态。TreeSet 支持两种排序方式，自然排序 和定制排序，其中自然排序为默认的排序方式。向 TreeSet 中加入的应该是同一个类的对象。

TreeSet 判断两个对象不相等的方式是两个对象通过 equals 方法返回 false，或者通过 CompareTo 方法比较没有返回 0

1. 自然排序

自然排序使用要排序元素的 CompareTo（Object obj）方法来比较元素之间大小关系，然后将元素按照升序排列。

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

obj1.compareTo(obj2) 方法如果返回 0，则说明被比较的两个对象相等，如果返回一个正数，则表明 obj1 大于 obj2，如果是 负数，则表明 obj1 小于 obj2。

如果我们将两个对象的 equals 方法总是返回 true，则这两个对象的 compareTo 方法返回应该返回 0

2. 定制排序

自然排序是根据集合元素的大小，以升序排列，如果要定制排序，应该使用 Comparator 接口，实现 int compare(T o1,T o2) 方法,我们可以构造 TreeSet 对象时,传递实现了 Comparator 接口的比较器对象.

import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

public class TreeSetTest {
	public static void main(String[] args) {

		TreeSet<Students> ts = new TreeSet<Students>(new CompareToStudent());
		ts.add(new Students(2, "zhangshan"));
		ts.add(new Students(3, "lishi"));
		ts.add(new Students(1, "wangwu"));
		ts.add(new Students(4, "maliu"));

		Iterator<Students> it = ts.iterator();
		while (it.hasNext()) {
			System.out.println(it.next());
		}
	}
}

class Students implements Comparable<Students> {
	int num;
	String name;

	Students(int num, String name) {
		this.num = num;
		this.name = name;
	}

	public String toString() {
		return num + ":" + name;
	}

	@Override
	public int compareTo(Students o) {
		int result;
		Students s = (Students) o;
		result = num > s.num ? 1 : (num == s.num ? 0 : -1);
		if (result == 0) {
			result = name.compareTo(s.name);
		}
		return result;
	}
}

class CompareToStudent implements Comparator<Object> {
	public int compare(Object o1, Object o2) {
		Students s1 = (Students) o1;
		Students s2 = (Students) o2;
		int rulst = s1.num > s2.num ? 1 : (s1.num == s2.num ? 0 : -1);
		if (rulst == 0) {
			rulst = s1.name.compareTo(s2.name);
		}
		return rulst;
	}
}

与 HashSet 相比，TreeSet 还提供了几个额外的方法：

1. Comparator comparator（）：返回当前 set 使用的 Comparator，或者返回 null，表示以自然方式排序。
2. Object first（）：返回集合中的第一个元素。
3. Object last（）：返回集合中的最后一个元素。
4. Object lower（Object e）：返回集合中位于指定元素之前的一个元素。
5. Object higher（Object e）：返回集合中位于指定元素之后的一个元素。
6. SortedSet subSet（from Element，to Element）：返回此 set 的子集合，范围从 from Element 到 to Element（闭包）。
7. SortedSet headSet（toElement）：返回此 Set 的子集，由小于 toElement 的元素组成。
8. SortedSet tailSet（fromElement）：返回此 Set 的子集，由大于等于 fromElement 的元素组成。

LinkedHashSet

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

所以 LinkedHashSet 的性能略低于 HashSet，但在迭代访问全部元素时将有很好的性能，因为它以链表来维护内部顺序。