Java:Collection.Set接口实现

1．Set接口

Set 接口继承 Collection 接口，而且它不允许集合中存在重复项，每个具体的 Set 实现类依赖添加的对象的 equals()方法来检查独一性。Set接口没有引入新方法，所以Set就是一个Collection，只不过其行为不同。
下面介绍Set接口3种主要的实现类。
HashSet 为快速查找而设计的Set。存入HashSet的元素必须定义hashCode()。
TreeSet 保存次序的Set，底层为树结构。使用它可以从Set中提取有序的序列。元素必须实现Comparable接口。
LinkedHashSet 具有HashSet的查询速度，且内部使用链表维护元素的顺序（插入顺序）。在使用迭代器遍历Set时，结果会按插入的次序显示。元素必须定义hashCode()方法。

2．HashSet
1）是实现Set接口的hash table(哈希表)，依靠HashMap来实现的。

2）我们应该为要存放到散列表的各个对象定义hashCode()和equals()。
import java.util.HashSet;
import java.util.Iterator;

class HashSetTest {
    public static void main(String[] args) {
       HashSet<Student> hs = new HashSet<Student>();
       hs.add(new Student(1, "zhangsan"));
       hs.add(new Student(2, "lisi"));
       hs.add(new Student(3, "wangwu"));
       hs.add(new Student(1, "zhangsan"));// 重写hashCode()方法、equals()方法后，hashset不再接受重复的元素
       Iterator it = hs.iterator();
       while (it.hasNext()) {
           System.out.println(it.next());
       }
    }
}

class Student {
    int num;
    String name;

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

    public int hashCode() {// 重写hashCode()方法
       return num * name.hashCode();
    }

    public boolean equals(Object o) {// 重写equals()方法
       Student s = (Student) o;
       return num == s.num && name.equals(s.name);
    }

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

结果：
1:zhangsan
3:wangwu
2:lisi
3．TreeSet
1）TreeSet是依靠TreeMap来实现的。

2）TreeSet是一个有序集合，TreeSet中元素将按照升序排列，缺省是按照自然顺序进行排列，意味着TreeSet中元素要实现Comparable接口。

3）我们可以在构造TreeSet对象时，传递实现了Comparator接口的比较器对象。
示例一，是按照缺省的自然顺序（对于String，则是字母顺序）排列。
import java.util.Iterator;
import java.util.TreeSet;

class TreeSetTest {
    public static void main(String[] args) {
       TreeSet<String> ts = new TreeSet<String>();
       ts.add("a");
       ts.add("b");
       ts.add("c");
       Iterator it = ts.iterator();
       while (it.hasNext()) {
           System.out.println(it.next());
       }
    }
}

结果：
a
b
c

示例二Student类通过实现Comparable接口来自定义排列顺序。这里排序的依据是Student类的成员变量(int num)。从运行结果可以发现，当出现num重复的情况，只保存首次加入的元素。
import java.util.Iterator;
import java.util.TreeSet;

class TreeSetTest {
    public static void main(String[] args) {
       TreeSet<Student> ts = new TreeSet<Student>();
       ts.add(new Student(2, "Tom"));
       ts.add(new Student(1, "Jeff"));
       ts.add(new Student(3, "Ada"));
       ts.add(new Student(3, "Mary"));
ts.add(new Student(1, "Peter"));//compareTo()返回0，则不加入

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

class Student implements Comparable {
    int num;
    String name;

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

    public int compareTo(Object o) {
       Student s = (Student) o;
       return num > s.num ? 1 : (num == s.num ? 0 : -1);
    }

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

结果：
1:Jeff
2:Tom
3:Ada

示例三通过Student的内部类StudentComparator，来实现第二关键字的排序，即当第一关键字num相等时，使用第二关键字name排序。
import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

class TreeSetTest {
    public static void main(String[] args) {
       TreeSet<Student> ts = new TreeSet<Student>();
       ts.add(new Student(2, "Tom"));
       ts.add(new Student(1, "Jeff"));
       ts.add(new Student(3, "Ada"));
       ts.add(new Student(3, "Mary"));
       ts.add(new Student(1, "Peter"));

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

class Student implements Comparable {
    int num;
    String name;

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

    private class StudentComparator implements Comparator {
       public int compare(Object o1, Object o2) {
           Student s1 = (Student) o1;
           Student s2 = (Student) o2;
           int result = s1.num > s2.num ? 1 : (s1.num == s2.num ? 0 : -1);
           if (result == 0) {
              result = s1.name.compareTo(s2.name);
           }
           return result;
       }
    }

    public int compareTo(Object o) {
       /*Student s = (Student) o;
       return num > s.num ? 1 : (num == s.num ? 0 : -1);*/
       StudentComparator sc=new StudentComparator();
       return sc.compare(this, o);
    }

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

结果：
1:Jeff
1:Peter
2:Tom
3:Ada
3:Mary
4．LinkedHashSet
1）应该为要存放到散列表的各个对象定义hashCode()和equals()。

2）按插入顺序输出元素。（比较下面示例结果与HashSet示例的结果）
import java.util.Iterator;
import java.util.LinkedHashSet;

public class LinkedHashSetTest2 {
    public static void main(String[] args) {
       LinkedHashSet<Student> hs = new LinkedHashSet<Student>();
       hs.add(new Student(1, "zhangsan"));
       hs.add(new Student(2, "lisi"));
       hs.add(new Student(3, "wangwu"));
       hs.add(new Student(1, "zhangsan"));// 重写hashCode()方法、equals()方法后，hashset不再接受重复的元素
       Iterator it = hs.iterator();
       while (it.hasNext()) {
           System.out.println(it.next());
       }
    }
}

class Student {
    int num;
    String name;

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

    public int hashCode() {// 重写hashCode()方法
       return num * name.hashCode();
    }

    public boolean equals(Object o) {// 重写equals()方法
       Student s = (Student) o;
       return num == s.num && name.equals(s.name);
    }

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

结果：
1:zhangsan
2:lisi
3:wangwu
5．SortedSet接口
“集合框架”提供了个特殊的Set接口：SortedSet，它保持元素的有序顺序。添加到SortedSet实现类的元素必须实现Comparable接口，否则您必须给它的构造函数提供一个Comparator接口的实现。TreeSet类是它的唯一一份实现。
因为集必须包含唯一的项，如果添加元素时比较两个元素导致了0返回值（通过Comparable的compareTo()方法或Comparator的compare()方法），那么新元素就没有添加进去。
注意，SortedSet意思是“根据对象的比较顺序”，而不是“插入顺序”进行排序。
SortedSet中的元素一定是有序的。这使得SortedSet接口多了一些方法：
①     Comparator comparator()：返回Set锁使用的Comparator对象，或者用null表示它使用Object自有的排序方法。
②     Object first()：返回最小的元素。
③     Object last()：返回最大的元素。
④     SortedSet subSet(fromElement, toElement)：返回Set的子集，其中的元素从fromElement开始到toElement为止（包括fromElement，不包括 toElement）。
⑤     SortedSet headSet(toElement)：返回Set的子集，其中的元素都应小于toElement。
⑥     SortedSet headSet(toElement)：返回Set的子集，其中的元素都应大于fromElement。
import java.util.Collections;
import java.util.Iterator;
import java.util.SortedSet;
import java.util.TreeSet;

public class SortedSetDemo {
    static void print(Object obj){
       System.out.println(obj);
    }
  
    public static void main(String[] args) {
       SortedSet<String> sortedSet = new TreeSet<String>();
       Collections.addAll(sortedSet, "one two three four five six seven eight"
              .split(" "));
       print(sortedSet);
       String low=sortedSet.first();
       String high=sortedSet.last();
       print(low);
       print(high);
       Iterator<String> it=sortedSet.iterator();
        for(int i=0;i<=6;i++){
           if(i==3)
              low=it.next();
           if(i==6)
              high=it.next();
           else it.next();
       }
       print(low);
       print(high);
       print(sortedSet.subSet(low, high));
       print(sortedSet.headSet(high));
       print(sortedSet.tailSet(low));
    }