作者：jjp
Set和數(shù)學(xué)中的集合是同一個(gè)概念，就是沒有重復(fù)元素的集合。
這篇文章主要論述了Set是如何實(shí)現(xiàn)"沒有重復(fù)元素"（no duplicate elements）的，以及闡述了什么是“重復(fù)”（duplicate），是相同的地址空間？是equals的返回值為true？是compareTo的返回值為0 ？還是有相同的hashCode？本文還給出了在什么情況下使用什么樣的Set的建議。
注：本文不涉及范型。
1、樹形結(jié)構(gòu)：
?public interface Set<E> extends Collection<E>{}
?public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E>{}
?public class CopyOnWriteArraySet<E>extends AbstractSet<E>implements Serializable{}
?public abstract class EnumSet<E extends Enum<E>>extends AbstractSet<E>implements Cloneable, Serializable{}
?public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, Serializable{}
?public final class JobStateReasonsextends HashSet<JobStateReason>implements PrintJobAttribute{}
?public class LinkedHashSet<E>extends HashSet<E>implements Set<E>, Cloneable, Serializable{}
?public class TreeSet<E>extends AbstractSet<E>implements SortedSet<E>, Cloneable, Serializable{}
?? 可以看出，可以實(shí)例化的類為：CopyOnWriteArraySet，HashSet，LinkedHashSet，TreeSet。
2、Set是如何實(shí)現(xiàn)元素唯一性的
?? javadoc中對(duì)Set的描述第一段如下：“A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1
?? and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.”
?? 這段話是對(duì)是錯(cuò)，請(qǐng)看下面分析。
?? 要進(jìn)行下面的論述，我們先了解一下Map。Map中的元素是“鍵－值”對(duì)，其中“鍵”必須是唯一的。TreeSet和HashSet就是利用這個(gè)特性實(shí)現(xiàn)“no duplicate??? elements”。它把set中的元素作為Map中的“鍵”，從而保持元素的唯一性。這些鍵在Map中又是如何區(qū)分的呢？不同的Map有不同的做法，而且區(qū)別很大。
?? 下面我們分別就TreeSet、HashSet和CopyOnWriteArraySet進(jìn)行論述：
2.1、TreeSet部分：
?? 以下以TreeSet為例進(jìn)行分析。
?? 請(qǐng)看TreeSet的部分實(shí)體：
?public class TreeSet<E> extends AbstractSet<E>
????? implements SortedSet<E>, Cloneable, java.io.Serializable
?{
? // The backing Map
????? private transient SortedMap<E,Object> m;
????? // The keySet view of the backing Map
????? private transient Set<E> keySet;
????? // Dummy value to associate with an Object in the backing Map
????? //這是每個(gè)鍵所指的對(duì)像
????? private static final Object PRESENT = new Object();
????? //constructor
????? private TreeSet(SortedMap<E,Object> m) {
????????? this.m = m;
?????????? keySet = m.keySet();
????? }
????? public TreeSet() {
?? this(new TreeMap<E,Object>());
????? }
????? //以下省略..........
?}
??? 可以看到TreeSet使用了SortedMap作為其Map保存“鍵－值”對(duì)，而這個(gè)SortedMap的真正實(shí)體是TreeMap。
???
??? 請(qǐng)看示例程序1：
?import java.util.*;
?public class SetTest1 {
? public static void main(String[] args){
?? Set set = new TreeSet();
?? set.add(new SetElement1("aa"));
?? set.add(new SetElement1("bb"));
? }
? static class SetElement1{
?? String s;
?? public SetElement1(String s){
??? this.s =? s;
?? }
?? public String toString(){
??? return s;
?? }
?? public boolean equals(Object obj) {
??? return s.equals(((SetElement1)obj).s);
?? }
? }
?}
??? 該程序能夠正常編譯，但是運(yùn)行時(shí)會(huì)拋出異常java.lang.ClassCastException。為什么？
???
??? 請(qǐng)看示例程序2：
?import java.util.*;
?public class SetTest2 {
? public static void main(String[] args){
?? Set set = new TreeSet();
?? set.add(new SetElement2("aa"));
?? set.add(new SetElement2("aa"));
?? set.add(new SetElement2("bb"));
?? System.out.println(set);
? }
? static class SetElement2 implements Comparable{
?? String s;
?? public SetElement2(String s){
??? this.s =? s;
?? }
?? public String toString(){
??? return s;
?? }
?? public int compareTo(Object o){
??? return s.compareTo(((SetElement2)o).s);
?? }
?? public boolean equals(Object obj) {
??? return s.equals(((SetElement2)obj).s);
?? }
? }
?}
?? 運(yùn)行結(jié)果：
?? [aa, bb]
?? 這正是我們所期望的結(jié)果。那“示例程序1”和“示例程序2”有什么區(qū)別？
?? 是因?yàn)镾etElement2實(shí)現(xiàn)了Comparable接口，而SetElement1沒有。SetElement2實(shí)現(xiàn)Comparable接口有什么用呢？因?yàn)樵赥reeSet的add方法中需要比較兩個(gè)??? 元素的“值”。請(qǐng)看TreeMap中的compare方法：
?? private int compare(K k1, K k2) {
??????? return (comparator==null ? ((Comparable</*-*/K>)k1).compareTo(k2)
???????????????????????????????? : comparator.compare((K)k1, (K)k2));
?? }
?? 可見這個(gè)方法先把要比較的元素down cast成Comparable類型。這里就可以解釋“示例程序1”中為什么會(huì)拋出異常java.lang.ClassCastException，因SetElement1沒有實(shí)現(xiàn)Comparable接口，當(dāng)然就不能down cast成Comparable。可見，要用TreeSet來做為你的Set，那么Set中所裝的元素都必須實(shí)現(xiàn)了Comparable接口。
?? 說到這里，你是不是想到了TreeSet中是采用Comparable接口中的compareTo方法來判斷元素是否相同（duplicate），而不是采用其他類似equals之類的東東來判斷。
??
?? 請(qǐng)看示例程序3：
??? import java.util.Set;
?import java.util.*;
?public class SetTest3 {
? public static void main(String[] args){
?? Set set = new HashSet();
?? set.add(new SetElement3("aa"));
?? set.add(new SetElement3("aa"));
?? set.add(new SetElement3("bb"));
?? System.out.println(set);
? }
? static class SetElement3 implements Comparable{
?? String s;
?? public SetElement3(String s){
??? this.s =? s;
?? }
?? public String toString(){
??? return s;
?? }
?? public int compareTo(Object o){
??? //return s.compareTo(((SetElement3)o).s);
??? return -1;
?? }
?? public boolean equals(Object obj) {
??? return s.equals(((SetElement3)obj).s);
?? }
? }
?}
?? 運(yùn)行結(jié)果：
?? [bb, aa, aa]
?? 看到?jīng)]有，有兩個(gè)“aa”！！這是因?yàn)閏ompareTo返回值始終是"-1"，也就是說“把任何元素都看成不同”。
??
?? 綜上所述，你是否對(duì)javadoc中對(duì)Set功能的描述有了懷疑？！
2.2、HashSet部分：
?? 以下以HashSet為例進(jìn)行分析。
?? 從Hashset類的主體部分：
?public class HashSet<E> extends AbstractSet<E>
???? implements Set<E>, Cloneable, java.io.Serializable
?{
? static final long serialVersionUID = -5024744406713321676L;
? private transient HashMap<E,Object> map;
? // Dummy value to associate with an Object in the backing Map
? //這是每個(gè)鍵所指的對(duì)像
? private static final Object PRESENT = new Object();
???? public HashSet() {
?? map = new HashMap<E,Object>();
????? }
???? public boolean add(E o) {
?? return map.put(o, PRESENT)==null;
????? }
??? //以下省略..........
??? }
?
??????? public HashSet() {
?
? map = new HashMap<E,Object>();
???
?}
?? 可以看到HashSet使用了HashMap作為其Map保存“鍵－值”對(duì)。
??
?? 請(qǐng)看示例程序4：
?import java.util.*;
?public class SetTest4 {
?public static void main(String[] args){
? Set set = new HashSet();
? set.add(new SetElement4("aa"));
? set.add(new SetElement4("aa"));
? set.add(new SetElement4("bb"));
? System.out.println(set);
?}
?static class SetElement4{
? String s;
? public SetElement4(String s){
?? this.s =? s;
? }
? public String toString(){
?? return s;
? }
? public boolean equals(Object obj) {
?? return s.equals(((SetElement4)obj).s);
? }
?}
}
?? 運(yùn)行結(jié)果：
?? [bb, aa, aa]
?? 沒有“示例程序1”中的java.lang.ClassCastException，但是運(yùn)行結(jié)果似乎不對(duì)，因?yàn)橛袃蓚€(gè)“aa”。
??
?? 請(qǐng)看示例程序5：
?import java.util.*;
?public class SetTest5 {
? public static void main(String[] args){
?? Set set = new HashSet();
?? set.add(new SetElement5("aa"));
?? set.add(new SetElement5("aa"));
?? set.add(new SetElement5("bb"));
?? System.out.println(set);
? }
? static class SetElement5{
?? String s;
?? public SetElement5(String s){
??? this.s =? s;
?? }
?? public String toString(){
??? return s;
?? }
?? public boolean equals(Object obj) {
??? return s.equals(((SetElement5)obj).s);
?? }
?? public int hashCode() {
??? //return super.hashCode();
??? return s.hashCode();
?? }
? }
?}
??? 運(yùn)行結(jié)果：
??? [bb, aa]
??? 這就對(duì)了。“示例程序4”和“示例程序5”有什么區(qū)別？是SetElement5重寫了hashCode方法。
???
??? 可見HashSet中是采用了比較元素hashCode的方法來判斷元素是否相同（duplicate），而不是采用其他類似equals之類的東東來判斷。
???
??? 說了這么多，那java類庫(kù)中到底有沒有根據(jù)equals來判斷元素是否相同（duplicate）的Set呢？請(qǐng)看下文。
2.2、CopyOnWriteArraySet部分：
?? 類CopyOnWriteArraySet是java.util.concurrent包中的一個(gè)類，所以它是線程安全的。
?? CopyOnWriteArraySet是使用CopyOnWriteArrayList作為其盛放元素的容器。當(dāng)往CopyOnWriteArrayList添加新元素，它都要遍歷整個(gè)List，并且用equals來??? 比較兩個(gè)元素是否相同。
?? 請(qǐng)看示例程序6：
?import java.util.*;
?import java.util.concurrent.*;
?public class SetTest6 {
? public static void main(String[] args){
?? Set set = new CopyOnWriteArraySet();
?? set.add(new SetElement6("aa"));
?? set.add(new SetElement6("aa"));
?? set.add(new SetElement6("bb"));
?? System.out.println(set);
? }
? static class SetElement6{
?? String s;
?? public SetElement6(String s){
??? this.s =? s;
?? }
?? public String toString(){
??? return s;
?? }
?? public boolean equals(Object obj) {
??? return s.equals(((SetElement6)obj).s);
?? }
? }
?}
?? 運(yùn)行結(jié)果：
?? [aa, bb]
?? 好了，一切搞定！！
3、總結(jié)：
?? Javadoc中的一些描述可能是不準(zhǔn)確的，大家要當(dāng)心了！
??
?? Set中實(shí)現(xiàn)元素互異的各種方法差異很大，大致可以分為三種：使用equals，使用hashCode，使用compareTo。但是我還沒有發(fā)現(xiàn)采用“判斷地址空間是否相同”來判斷元素是否相同的類，當(dāng)然我們可以用現(xiàn)有的三種方法來實(shí)現(xiàn)“判斷地址空間是否相同”。
??
?? 綜上所述，我們可以總結(jié)出使用Set的三種不同的情形：（以下假設(shè)元素類為Element）
?? A、如果想使用Element的equals方法來判斷元素是否相同，那么可以使用CopyOnWriteArraySet來構(gòu)造類的實(shí)體。
?? B、如果Element實(shí)現(xiàn)了Comparable接口，而且想使用compareTo方法來判斷元素是否相同，那么可以使用TreeSet來構(gòu)造類的實(shí)體。
?? C、如果想使用判斷hashCode是否相同的方法來判斷元素是否相同，那么可以使用HashSet來構(gòu)造類的實(shí)體。